debasishg

Cache Oblivious and Cache Aware Data Structure and Algorithms

1. Cache-Oblivious Algorithms and Data Structures - Erik Demaine (One of the earliest papers in cache oblivious data structures and algorithms that introduces the cache oblivious model in detail and examines static and dynamic cache oblivious data structures built between 2000-2003)

2. Cache Oblivious B-Trees - Bender, Demaine, Farch-Colton (This paper presents two dynamic search trees attaining near-optimal performance on any hierarchical memory. One of the fundamental papers in the field where both search trees discussed match the optimal search bound of Θ(1+log (B+1)N) memory transfers)

3. Cache Oblivious Search Trees via Binary Trees of Small Height - Brodal, Fagerberg, Jacob (The data structure discussed in this paper works on the version of [2] but avoids the use o

debasishg

Basics

1. The Log-Structured Merge-Tree (LSM-Tree)
2. B-Tree vs Log-Structured Merge-Tree
3. Modern B-tree techniques
4. LSM-based Storage Techniques: A Survey

B-trees and CPU Caches

1. B-tree Indexes and CPU Caches by Goetz Graefe and Per-Åke Larson

kconner

macOS Internals

Understand your Mac and iPhone more deeply by tracing the evolution of Mac OS X from prelease to Swift. John Siracusa delivers the details.

Starting Points

How to use this gist

You've got two main options:

rain-1

Purpose

Bootstrap knowledge of LLMs ASAP. With a bias/focus to GPT.

Avoid being a link dump. Try to provide only valuable well tuned information.

Prelude

Neural network links before starting with transformers.

melvic-ybanez

Previous List: What I Didn't Know about Functional Programming until 2020

What I Didn't Know about Functional Programming until 2021

1. A hom-functor is usually implemented in Scala as the reader functor. The type itself is essentially a hom-set, but if we fix the domain to a particular type, we get a functor:

   // A hom-set Hom(A, X)
   type Reader[A, X] = A => X
   

// A hom-functor X => Hom(String, X) or Hom(String, -)

Phate6660

Cryptography

https://github.com/spieglt/cloaker - password-based file encryptor (NOTE: uses Qt)
https://github.com/str4d/rage - file encryption tool and librarary that uses the age format

Media

https://github.com/mohanson/gameboy - gameboy emulator
https://github.com/bartwillems/lyriek - fetch the lyrics of a song playing in an mpris-compatible player
https://github.com/JakeStanger/mpd-discord-rpc - discordrpc for mpd

melvic-ybanez

What I Didn't Know about Functional Programming until 2020

1. Programming using a series of transformations and aggregations, something I've been doing for years, is known as programming in the map/reduce style.
2. The more abstract the type is, the greater its cardinality, and the smaller the set of operations it supports. So make use of universal quantifiers, particularly by implementing fully parametric functions. They guide you on how to implement their term-level definitions by narrowing down the number of possible implementations. In other words, the type system of Scala (or Haskell, for that matter) is not only great for capturing compile-time errors, but is also capable of leading you to the correct solution.
3. You can encode union types by combining different Scala features such as type constructors, subtyping and implicits, and by taking advantage of the Curry-Howard Isomorphism and De Morgan's Laws for neg

tykurtz

GROKKING NOTES

I liked the way Grokking the coding interview organized problems into learnable patterns. However, the course is expensive and the majority of the time the problems are copy-pasted from leetcode. As the explanations on leetcode are usually just as good, the course really boils down to being a glorified curated list of leetcode problems.

So below I made a list of leetcode problems that are as close to grokking problems as possible.

Pattern: Sliding Window

• https://leetcode.com/problems/maximum-subarray/ # Close enough
• https://leetcode.com/problems/minimum-size-subarray-sum/

MineRobber9000

###########################################################
# How to NEVER use lambdas. An inneficient and yet educa- #
# tonal [sic] guide to the proper misuse of the lambda    #
# construct in Python 3.x.  [DO NOT USE ANY OF THIS EVER] #
#          original by (and apologies to): e000 (13/6/11) #
#           now in Python 3 courtesy of: khuxkm (17/9/20) #
###########################################################

## Part 1. Basic LAMBDA Introduction ##
# If you're reading this, you've probably already read e000's

seece

Data-Oriented Design Book Review

Pekka Väänänen, Sep 14 2020

Data-Oriented Design (2018) by Richard Fabian

Computers keep getting faster but the future ain't what it used to be. Instead of higher clock rates we get deeper pipelines, higher latencies, more cores. Programming these systems requires paying attention to how we structure and access our data. In Data-Oriented Design Richard Fabian—who has worked at Frontier Developments, Rockstar Games, and Team17—presents us an approach to reason about these issues from a C++ game developer's perspective.

Data-oriented design is about caches and decoupling meaning from data. The former implies laying out your data so that they're compact and predictably accessed. The latter means exposing the raw transforms from one sequence of bits to another. For example, finding the pla