NYSRG

Git is a version control system used by the most of the world’s software developers. What’s under the hood? Let’s get a glimpse into the workings of the “.git” folder, featuring content-addressed storage and hash trees.

Compilers in machine learning are the silent toolchains that make compute possible at massive scale, on CPUs and on hardware accelerators like GPUs. How do they work? And what really goes into doing matrix multiplication fast?

Cooperative and preemptive multitasking, schedulers, concurrency vs parallelism models, and how they influence language features. Case studies in Go and Rust internals, and mentions of Python, JavaScript, C#, Dart, and Lua.

Storage is at the heart of databases, lying below execution and query planning, but above the file system, OS, and hardware. Let’s learn about them and get started with our own.

Security is hard, and browsers are incredibly complex artifacts with tens of millions of lines of code. What could go wrong? From distributed systems security to process sandboxing, and from type confusion to Spectre.

Build processes are complex and computationally intensive. How can we make builds fast, reproducible, and flexible, all while retaining simplicity? Maybe studying their underpinnings and reimplementing them can teach us a bit about computing.

Complex systems tend to produce more copies of themselves, and computers are no exception to this self-referential behavior. Let’s see how virtualization and emulation work on the OS and machine levels.

Schema-based binary formats, and their associated languages, for specifying and serializing structured data. Design tradeoffs for RPCs, data archiving, OLAP, and embedded.

Kubernetes is, undeniably, tech’s favorite system for deploying code. It’s also crazy complex. Let’s look at it (a healthy serving of YAML!), then at Slurm (a scheduler for supercomputers from the 2000s), so we can discuss what the essential complexity is.

Time-series databases index massive amounts of data. They’re the tools that let engineers understand and do more with systems. How do they work, and what are the key data structures and ideas in balancing their speed, storage, and cost?

You may have no idea what a plasmid is, me neither! It’s a circular DNA sequence. But treat this as a complex data visualization and UI exercise. We’ll each try to write an interactive SVG viewer, learning about libraries and reactive programming models.

We’ll read the specification for the Java Virtual Machine, with a focus on Chapter 3 (compilation). Java is the most successful cross-platform compiled bytecode in the world.

Compilers compile code. But compilers are also code themselves. It’s 2024, and as we reflect on our past and present, let’s also reflect on some of the classic and modern takes on self-referentiality of compilers and staging.

Exploring state-of-the-art lossless data compression. How do you pack big things in a small package, fast? (Note: This is a hard algorithm and we probably won’t make it all the way through in one sitting.)

Still talking about compression like last week, but lossy codecs come with spicy cosine transforms, color spaces, and legal trickery. Video encoding is also absurdly complicated; who knew an algorithm could be broken up into 5000+ patents!

We’ll continue where we left off in Week 14 by understanding finite-state entropy in depth. Then, buckle down to read the actual zstd spec, followed by Brotli.

What goes into executables and dynamic linking? How do they work, and how much of their functionality is engineered versus operating system magic? We’ll start reading a series by Amos Wenger.

A blog post by Mitchell Hashimoto, dissecting the Zig compiler. Zig is a self-hosted, low-level compiled systems programming language.

The working operations of a secure VPN tunnel. Public-key cryptography and forward secrecy, parallelism techniques, and kernel networking.

What ties together FASTA, ripgrep, bzip2, Prometheus, and Sublime Text? Algorithms and data structures for practical string indexing and search, with a healthy dose of practical automata theory.

Training big ML models is the elephant in the room. So everyone starts by talking about compute, but it ends up being mostly about networking. Hello, data movement!

We’ll read through a recent guide on Linux kernel module programming in C. (Before the meeting, get an x86-64 cloud VM with a fresh install of Ubuntu 22.04.)

Reading about an up-and-coming Linux subsystem for high-performance async I/O. Thinking about memory access models, buffer ownership, and fault-tolerant parallelism.

A discussion of general-purpose memory allocators. We’ll focus on the successful jemalloc, and the newer but promising mimalloc. Let’s peruse some source code if time permits.

Selected readings from The Architecture of Open Source Applications, Volume 1. How the software we know and love was designed, redesigned, and built.

Selected readings from The Architecture of Open Source Applications, Volume 2.

A trio of classic papers on building a distributed file system from the ground up for exabyte-scale storage. How the biggest organizations in the world keep track of data. Let’s start with the first two papers: CRUSH and RADOS.

We’ll continue where we left off from last week, reading the Ceph distributed file system paper from OSDI ’06. Ceph is a near-POSIX file system built on CRUSH and RADOS.

JAX is a differentiable programming language embedded in Python, which implements forward and reverse-mode automatic differentiation via functors and a tracing JIT. Come for a unique mix of vector calculus + category theory + compilers, as we make our own JAX.

What does it take to write a fast interpreter in 2024? We’ll read the source code of a recent and relatively small (~50,000 LoC) runtime for WebAssembly, with interesting tradeoffs between startup speed and performance.

Disaggregation is a technique to separate compute, storage, and memory needs in warehouse-scale computing. We’ll read about how people balance these features with the limitations of networked systems.

FoundationDB is a distributed, transactional key-value store that underpins several new database systems. It claims to be strict serializable and lock-free, while having very strong failure tolerance. We’ll read the FoundationDB paper and some docs.

A series of three posts on how memory consistency is preserved by multicore processors: in hardware, in programming languages, and in specifically the Go programming language.

Sorting is one of the most common problems in computing. It’s also heavily optimized. Let’s look at research into two hand-tuned sorting implementations that are tailored for performance, which were recently merged into the Rust standard library.

We’ll read the source code of Redis 1.3.6, the oldest tagged release (March 18, 2010). Redis is a cornerstone of modern systems, and its data structures power much of the Internet. But in 2010, Redis was mostly a single 9000-line C file written by one developer.

The foundations of dynamic instrumentation in kernels. Case studies on DTrace (Solaris) and eBPF (Linux, Windows). Note that eBPF has a very large scope, we’ll discuss the groundwork rather than applications in this meeting.

Trusted computing: how can you possibly run sensitive code on a computer that’s been completely compromised? Obviously homomorphic encryption isn’t practical in 2024, so let’s try to learn a bit about how SGX promises this.

A study on reactive programming. Solid is a popular frontend framework for user interfaces. It’s known for fine-grained reactivity and minimal runtime overhead, being faster than React and Svelte. We’ll read the source code to see how it works (~6000 lines).

We’ll read the literature about garbage collection algorithms for Java. While the JVM’s heap allocation interfaces have been largely the same for decades, its garbage collection algorithms have evolved to reflect changing needs.

We’ll explore DreamWorks’ 3D renderer, used in films like How to Train Your Dragon. MoonRay (~650,000 LoC) is a state-of-the-art system with GPU-accelerated ray tracing, real-time distributed computation, denoising, and a huge number of materials and simulations.

We will read about writing embedded firmware and drivers in Rust. I bought one STM32F3DISCOVERY kit (STM32F303VC MCU) for us to share, but feel free to bring your own hardware.

We’ll read some reflections from scientists on AWS S3, the oldest service of the world’s largest cloud provider. As of 2024, S3 stores over 350,000,000,000,000 objects (~100,000,000,000,000,000,000 bytes) with 99.999999999% durability.

We’ll read Parts I–II of Types and Programming Languages by Benjamin Pierce, a classic book on type theory. If you’re like me and never formally studied this, let’s speedrun through it together. Feel free to start before the meeting if you want!

We’ll read Parts III–IV (Recursive Types, Polymorphism) of Types and Programming Languages. Try to catch up to Chapter 14 before coming!

We’ll read Parts V–VI (Polymorphism, Higher-Order Systems) of Types and Programming Languages, completing the book. Try to catch up to Chapter 28 before coming!

SQL was introduced in 1974, so this year it turns 50. (Woah! It’s so old!) Let’s celebrate databases by reading an old paper from each decade, so we can reflect on how SQL has found and kept its place uncannily well as the world changes.

We’ll discuss spatial and temporal sharing of GPUs. How can you run multiple applications on the same accelerator hardware?

Chalk is an experimental system that implements the Rust trait system, based on logic programming. It currently powers rust-analyzer. We’ll read it as a case study on type system implementation.

Some people like to push things to their limit. We’ll read the (relatively short!) source code of simdjson, one of the fastest popular JSON parsers. We’ll learn a thing or two about SIMD, parsing, and performance optimization along the way.

We’ll check out recent advancements in hybrid OT/CRDT algorithms for collaborative editing and offline synchronization. We’ll also read new research on problems such as interleaving, rich text, and tree CRDTs, which are summarized in blog posts by Loro.