HashMaps are incredibly convenient, but treating them like a magical black box can make it easy to overlook where their performance comes from.

In this article, I explain how HashMaps work using a simple implementation in Rust. I go through hash collisions and linear probing, why primary clustering hurts performance, load factors, resizing, and more.

The implementation is intentionally simplified, but it gives a good picture of what's actually happening underneath a HashMap.

Let me know your thoughts or any feedback you have!

All writing, illustrations, and code are my own. AI was used to clean up wording and catch grammatical mistakes.

Wrote a quick blog post about pushing branch prediction to its limits in a simple experiment. Take a read to learn with me about measuring performance on linux machines and a very basic understanding of branch prediction 😄

Indexing strings by character (Unicode scalar) instead of UTF offsets can be more comfortable for parsers or short manipulations.

The minimum cost for reading a >= U+FE character is:

1. Lookup rope table by byte key (holding a high bit position), in goal of the scalar value in a sequence of higher fixed scalars
2. Check for collision subtable (is not null => repeat the step 1), specializing the target high bit further

For optimal use, contiguous sequences of characters after Latin-* that turn into reserves into the mask sequence still allow for a few trailing Latin-* (e.g. Katakana can still be mixed with Latin-* whitespace), so those trails turn into reseves as well.

Update (I miswrote a detail in the implementation).

https://gitlab.com/mryun/langopt/-/blob/master/encoding/string.md

Getting tokio and .NET’s async runtime talking to each other, over the C ABI

Okay, but I have multiple replicas.

And it gets slightly worse: the number of physical connections is not equal to the number of replicas, and it is not equal to the number of business-level connectors either.

Several business connectors may share one external identity. One external identity may require several physical connections. And those connections need to be spread across whatever replicas are currently alive and have capacity.

So who actually owns the connection?

Then the questions start piling up.

What if one replica dies?
What if it doesn’t die, but loses access to the database?
What if two replicas race for the same connection?
What if the event that was supposed to wake the right worker never arrives?
What if most workers are already full?

A few questions and 2 hours of midnight walk in headphones and ChatGPT later, I had leases, runtime slots, reconciliation, failover, capacity limits, and a distributed ownership problem on my hands.

This is the architecture I ended up with, and I have mixed feelings about this design.

On one hand, I’m proud that I managed to account for so many different edge cases. On the other, the whole thing feels worryingly complex.

So I’d really value input from people who have built similar systems.

What did I miss or do you see anything that can break?
And most importantly: what can be simplified without losing the guarantees?

The full architecture description is a bit lengthy: AEON NEON - Connector Runtime - by Jarek J.

Many thanks if you decide to read it and share your thoughts. I’d really like this one not to become another failed experiment.

Yes, the game development industry wasn’t nearly as complex as it is today. You could probably say that making and releasing a good game was easier back then.

But these people created a legend precisely because they were professionals.

Of course, DOOM wasn’t their first game. There was a time when the team was making a game every month.

What I like most about this video is the sense of creativity — and the feeling that these people simply loved making games.