Performance

Discussion: Reddit (r/java) · Hacker News This is Part 3 of a series on building a high-performance hash table for the JVM. Part 1 — Building a Fast, Memory-Efficient Hash Table in Java (by borrowing the best ideas): designing a SwissTable-style map from scratch — control bytes, SWAR probing, and why open addressing beats chaining for cache locality. Part 2 — Further Optimizing my Java SwissTable: Profile Pollution and SWAR Probing: hunting down a surprising Objects.equals() hotspot, and why SWAR beat the Vector API on both ARM and x86. Part 3 (this post): handing the profiler to an AI agent — and what it found. Part 3: letting the agent drive At the end of the last post, I had a SwissMap that felt genuinely fast: the Objects.equals() profile pollution was gone, SWAR had beaten the Vector API on both ARM and x86, and I finally had benchmarks I was willing to trust. ...

CSR (Compressed Sparse Row) comes up constantly in graph computation and storage optimization. It first appeared in a 1977 Yale University report, the Yale Sparse Matrix Package, which is why it’s sometimes called the Yale format. Researchers designed it to store and process sparse matrices efficiently. What a Sparse Matrix Is A sparse matrix is one where most of the entries are zero. You run into them across nearly every corner of modern computing: scientific computing, graph theory, machine learning. Real-world data, once you cast it as a matrix, almost always ends up looking like this. Take a social network: even with a million users, any given person typically has around 500 friends. Representing that directly as a matrix would require something on the order of 10^12 entries, roughly 7.3 petabytes. Storage cost balloons far beyond the actual information the matrix carries. ...

Discussions Hacker News Reddit The next milestone is to build a fully thread-safe hash map. Up to this point, the focus has been entirely on single-threaded performance: minimizing memory overhead, improving cache locality, and squeezing out every last bit of throughput from the underlying data layout. However, real-world applications rarely stay single-threaded. To be practically useful, a hash map must behave correctly—and efficiently—under concurrent access. Before jumping straight into implementation, it’s worth stepping back and studying how existing thread-safe hash map implementations approach this problem. Different designs make different trade-offs between simplicity, scalability, memory usage, and read/write performance. By examining these approaches side by side, we can better understand which ideas scale cleanly—and where the pitfalls are—when multiple threads hit the same structure at once. ...

Discussions Reddit Part 2: optimizing the hot path (and finding a weird villain) “Why Objects.equals() showed up in the profile, and why SWAR beat the Vector API on ARM (and x86).” In the last post, I finally got a SwissTable-ish map running on the JVM and fast enough to make me smile. Naturally, that meant I immediately started staring at the profiler again, thinking: okay… but how do I make it faster? ...

Discussions Hacker News Reddit One day, I ran into SwissTable, the kind of design that makes you squint, grin, and immediately regret every naive linear-probing table you’ve ever shipped. This post is the story of how I tried to bring that same “why is this so fast?” feeling into Java. It’s part deep dive, part engineering diary, and part cautionary tale about performance work. 1) The SwissTable project, explained the way it feels when you first understand it SwissTable is an open-addressing hash table design that came out of Google’s work and was famously presented as a new C++ hash table approach (and later shipped in Abseil). ...

This post is my own summary of Netflix’s tech blog post Seeing through hardware counters: a journey to threefold performance increase, written the way I understood it, with some background I added along the way. The original post is the authoritative source, so check it directly for exact figures and details. The Problem A Netflix service was running short on CPU, so the team scaled its nodes up 3x. Given the CPU-intensive workload, they expected throughput to scale roughly in step. Instead, they got about a 25% improvement, and tail latency got worse. ...

Swiss Tables: A Modern, High-Performance Hash Table Swiss Table is a high-performance hash table design introduced by Google engineers in 2017. It has since inspired many standard-library implementations across languages, including: Go 1.24 ships its map with this design (up to 60% faster) Rust’s standard HashMap has also moved from Robin Hood hashing to a Swiss Table-inspired layout. Datadog reported as much as 70% memory savings after migrating to Swiss Table Open Addressing, Briefly An open addressing hash table is one of the implementation methods for hash tables. Unlike separate chaining, which uses external data structures such as linked lists or trees, open addressing implements the entire hash table as a single contiguous array. ...

This post is my own write-up of Rust hash iteration+reinsertion and the related Rust issue/PR, written the way I understood them. The original is the authoritative source, so check it directly for the exact details. Rust’s HashMap had an interesting bug. The code looks completely ordinary, yet under the right conditions, an operation that should be O(n) blows up to O(n²). Reproducing the Bug Look at the code below. It inserts values 1 through 5,000,000 into a first hash map (one, that’s T1), then iterates over one and reinserts every value into a second hash map (two, that’s T2). Nothing fancy. ...

Limitations of Traditional Scalar State Machine Parsers The JSON parsing algorithms we commonly use are based on scalar state machine parsers. Scalar parsers read the input string byte by byte, parsing it through state transitions within the state machine. For example: When encountering a quotation mark ("), it indicates the start of a string. When encountering a colon (:), it indicates that a value is expected next. Below is a simplified pseudo-code representation of how a scalar parser works: ...