NP-Incompleteness
Why Do I Care About Names?
20 Sep 2026
In The Pleasure of Finding Things, Richard Feynman recounts a childhood event in which a boy comes to him and asks “See that bird, what kind of bird is that?” and Feynman concedes he has no idea, and the boy proudly answers himself “It’s a brown-throated thrush” and that “Your (Feynman) father doesn’t tell you anything”.
Feynman pointed out that the boy knew about the name of the bird but did not know anything else about it and used it to illustrate shallow knowledge. Later in life he even joked that this attitude caused him trouble because he often didn’t know the conventional names for effects in physics, but understood them once someone described what the effect actually was.
In this post I’d like to reflect on why I think names can be beneficial.
Linux Memory Reclamation
11 Sep 2026
For most operating systems, when memory usage grows beyond what the hardware can support, the kernel starts swapping, i.e. moving data from memory to disk. In this post, we’ll study how the Linux kernel does this, as part of the more general memory reclamation process. We’ll also cover the memory allocation flow, because memory reclamation is just one part of it, one of the unhappy paths.
First, we’ll go over the different components involved, and then how they fit together in the memory allocation flow and then memory reclamation via swap and zswap.
LZ77
05 Sep 2026
Jacob Ziv and Abraham Lempel were both faculty at the Technion in Haifa, Israel, when in 1977 they published a paper called A Universal Algorithm for Sequential Data Compression in which they described a compression algorithm which, unlike Huffman coding, doesn’t rely on knowing the frequency of symbols upfront.
Ziv was an information theorist from the Electrical Engineering department while Lempel was part of the Computer Science department. They met due to their interest in lossless compression and Ziv said [1] that their skills complemented each other well:
I knew all about information theory and statistics, and Abraham was well-equipped in Boolean algebra and computer science.
This algorithm is now known as LZ77 (their last name initials + the year the paper was published). A popular algorithm called DEFLATE combines LZ77 with Huffman and is used by tons of software including gzip, git, png, etc.
In this post we’ll cover the LZ77 algorithm.
CacheLib
28 Aug 2026
CacheLib is an open-source C++ library from Meta for constructing in-process caches. At a high level, we can think of it as a hash table in memory with the option to spill to flash storage.
In this post we’ll study this library, mainly the in-memory portion based on the paper The CacheLib Caching Engine: Design and Experiences at Scale [1] and the code.
Asymmetric Numeral Systems
20 Aug 2026
Jarosław Duda is a Polish professor at the Jagiellonian University in Kraków. He developed a family of entropy coding methods called asymmetric numeral systems (ANS), mainly used in data compression. He wanted these to remain patent-free but has had mixed success.
Google worked with Duda around 2014 in a paper Mixed boolean-token ANS coefficient coding and tried to patent a coder for video, but Duda pushed back and Google abandoned the attempt. In 2019 Microsoft was able to patent a variant and since then other patents have been granted internationally.
A variant of ANS, known as FSE, is used by Meta’s compression library called zstd. I wanted to learn more about it and decided to study this algorithm first.
Visit archive to see all posts...