Daniel LemireModify

2026-10-27 02:23:08

A lot of software spends its time mapping strings to values. A web server must identify the HTTP method (GET, POST, …). It must recognize header names. A URL parser must recognize the protocol (http, https, ftp, …). A compiler must recognize keywords.

In C++, the default approach is to put the strings in a std::unordered_map.

std::unordered_map<std::string_view, Method> methods = {
    {"GET", Method::GET}, {"POST", Method::POST}, {"PUT", Method::PUT},
    {"DELETE", Method::DELETE}, {"PATCH", Method::PATCH}};

It works. But notice something: the keys are known when you write the code. They never change. And yet we pay at runtime as if they could change at any time: we hash the whole string, we pick a bucket, we follow a pointer, we compare, maybe we walk a list.

Perfect hashing

A hash function maps keys to slots. When two keys land in the same slot, we have a collision, and we must deal with it. Collisions are what make hash tables complicated and slow.

If you know all of your keys ahead of time, you can construct a hash function designed for your keys, a function that never produces a collision. It is called a perfect hash function. The idea is old: the GNU gperf tool has been doing it since 1989. You give it a list of keywords, and it generates C code.

We follow the same design as gperf. The slot for a key is computed as follows.

slot = (length + asso[key[i]] + asso[key[j]] + ...) % table_size

We add the length of the key to a few small values taken from an association table (asso) indexed by the characters at a few selected positions. Usually, one or two positions are enough. The table size is a power of two, so the modulo is a single bitwise AND.

Consider the four HTTP methods GET, PUT, POST and DELETE. We use only the first character. Set asso['G'] = 0, asso['P'] = 1 and asso['D'] = 0. Then GET goes in slot 3 + 0 = 3, PUT goes in slot 3 + 1 = 4, POST goes in slot 4 + 1 = 5 and DELETE goes in slot 6 + 0 = 6. No collision.

To look up PUT, we compute the slot (4), and we compare PUT with the one key stored in slot 4. One hash, one comparison. If you look up PATCH, which is not in the set, you land in slot 5 + 1 = 6, you compare with DELETE, and you are done: not found. There is no probing, no chain to walk.

How do we find the association values? We sort the characters by how many keys they touch. We then take them one at a time and try 0, 1, 2, … until we find a value that does not cause a collision. We never revise a value once it is set. It is a greedy algorithm with bounded work. The bound matters because we do all of this at compile time, and C++ compilers limit how much work a constexpr function may do.

Doing it in C++

With our library, you write ordinary C++23. There is no external tool to run.

#include <ConstexprCore/perfect_hash.h>
using namespace ConstexprCore;
enum class Method { GET, POST, PUT, DELETE, PATCH };
constexpr auto methods = make_perfect_map<
    kv<"GET",    Method::GET>,
    kv<"POST",   Method::POST>,
    kv<"PUT",    Method::PUT>,
    kv<"DELETE", Method::DELETE>,
    kv<"PATCH",  Method::PATCH>
>();

The map is a compile-time constant. The compiler searches for the perfect hash function when it compiles your code. At runtime, computing the hash can take as few as four instructions: load one byte of the key, load one byte from the association table, add the length, apply a mask.

Comparing strings quickly

Computing the hash is cheap. But we still need to check that the string we are looking up matches the key stored in the slot. And comparing strings can be expensive: the textbook approach is a loop over the bytes with a branch for each byte. You can easily end up with dozens of instructions and several branches, and the branches are hard to predict when the strings vary.

Instead, we treat the key as a vector. Our processors, whether ARM or x64, have 16-byte registers. So we load 16 bytes unconditionally, even if the key is only three bytes long. We then use a shuffle instruction (tbl on ARM NEON) to zero the bytes past the end of the key. The stored keys are zero-padded at compile time. A single vector comparison handles the whole key. We go from about forty instructions and eight branches to five instructions and no branch.

But wait: is it safe to read 16 bytes when you only have three? Reading past the end of a buffer is fine as long as you do not cross into another memory page, and pages are at least 4 kilobytes. So we check whether the address is within 16 bytes of the end of its page. If it is, we take a slower path. Otherwise, we do the wide load. We traded several unpredictable branches for a single branch that is almost always taken the same way.

How fast is it?

I ran the benchmarks on an Apple M3 Max with AppleClang 15. We look up the keys in random order and we report the time per lookup. Let us first consider the 20 standard HTTP header names.

We need about 1.3 ns per lookup, or about 5 cycles. The classic gperf needs 7.7 ns. Abseil’s flat_hash_map, an excellent hash table, needs 10.9 ns. And std::unordered_map needs 16.6 ns. We are thirteen times faster than the standard library.

It is not one lucky key set. Here are the results over several sets of keys, from 6 URL protocols to the 100 tickers of the S&P 100.

We stay between 1.2 ns and 2 ns per lookup. We are 3 to 6 times faster than gperf, and 7 to 13 times faster than std::unordered_map. Notice how gperf struggles with the JavaScript reserved words: there we are 17 times faster.

Why is std::unordered_map so much slower? The C++ standard essentially requires a chained hash table. A lookup hashes the whole string by calling a function, follows a pointer to a heap-allocated node and walks a list. Our lookup does a few loads and has no function call. The processor can retire over 8.6 instructions per cycle with our code, which is about as good as it gets on this chip, and it almost never mispredicts a branch.

On an Apple M4, with the URL protocols, we exceed one billion lookups per second.

Conclusion

If your keys are known at compile time, you should not pay for collision handling at runtime. A perfect hash function gets you down to one comparison. With some care, a lookup costs about five cycles. The library is a single header you can drop in your project: github.com/ConstexprCore/perfect_hash.

This is joint work with Francisco Geiman Thiesen (Microsoft). We presented it at P99 CONF 2026. You can watch the talk on YouTube.

The benchmark numbers and the plotting script are available.

2026-10-17 12:40:34

We sometimes need to convert binary data to text. For example, your emails must be stored as text files. Naïvely, you could just use a string of 0 and 1, but it would mean using one character per bit. We can do better by using 64 ASCII characters: all letters, all numbers, plus a few extra characters. Base64 represents three bytes with four ASCII characters.

Base64 is how email carries attachments, how certificates are stored, how images get embedded in web pages (data URLs), and how binary data is encoded inside JSON.

Python comes with a base64 module. It is written in C, but it processes the data one character at a time. There is a popular alternative, pybase64.

We have been working on base64 for years. With Wojciech Muła, we showed how to encode and decode base64 with SIMD instructions. More recently, I worked on forgiving base64 decoding: the variant used by web browsers, which skips spaces and line breaks. Our simdutf library implements these ideas. Mainstream browsers rely on it.

But simdutf had no Python binding. So we wrote one: fastpybase64.

pip install fastpybase64

import fastpybase64 as base64
base64.b64encode(b"hello")      # b'aGVsbG8='
base64.b64decode("aGVsbG8=")    # b'hello'

It is meant as a drop-in replacement for the standard base64 module.

How fast is it? I use an Intel Xeon Gold 6548N (Emerald Rapids) pinned to one core, with Python 3.14.6. I installed fastpybase64 0.1.0 and pybase64 1.5.1 from PyPI. I decode the base64 encoding of random bytes, and I report the speed in gigabytes of decoded data per second. A lot of real base64 has line breaks. MIME, the format of email attachments, breaks the base64 text into lines of 76 characters. So that’s what I use as an example. We use a single thread.

The fastpybase64 module is four times faster than pybase64 and 27 times faster than the standard library.

The fastpybase64 module is available on PyPI for Linux, macOS and Windows, for Python 3.10 to 3.14, including free-threaded Python 3.14. My benchmark is available.

Further reading

• Daniel Lemire, Fast Forgiving Base64 Decoding with SIMD Instructions, ACM Transactions on Architecture and Code Optimization, 2026.
• Wojciech Muła, Daniel Lemire, Base64 encoding and decoding at almost the speed of a memory copy, Software: Practice and Experience 50 (2), 2020.
• Wojciech Muła, Daniel Lemire, Faster Base64 Encoding and Decoding using AVX2 Instructions, ACM Transactions on the Web 12 (3), 2018.

2026-10-16 06:46:54

Redis is an in-memory database. Salvatore Sanfilippo started it in 2009, and it is now one of the most widely deployed pieces of server software. It is often used as a cache in front of a slower database.

You talk to it over the network with short text commands such as SET user:42 "Alice" and GET user:42. Each key maps to a value, and the value can be more than a string: Redis has lists, hashes, sets, sorted sets, streams and more, each with its own commands. 

We often represent sets of integers as bitmaps (or bitsets). The simplest bimtap is a single machine word of, say, 8 bits. It can be used to represent all sets of integers smaller than 8. By adding more words, you can represent sets of integers smaller than 16, or any value you like. You can then do fast operations over bitmaps such as intersections and unions. They translate into a few bit-wise operations such as AND, OR, XOR. 

Redis has supported bitmaps for a long time. You call SETBIT key offset 1, and Redis stores a plain bitmap inside an ordinary Redis string: bit i of the bitmap is bit i of the string. It is simple and fast. But the string takes one byte per eight bit positions, up to the largest offset you ever set, however many bits are actually set. Setting a single bit at offset four billion allocates 512 MB, and every BITCOUNT or BITOP has to scan all of it.

A compressed bitmap avoids this cost: it stores a set of integers in a form that takes little room when the set is sparse, and it computes counts, intersections and unions without decompressing. Roaring is probably the most widely used compressed bitmap format. Rather than compressing a long string of bits, Roaring adapts its storage to the data: sparse regions are stored as short lists of integers, dense regions as plain bitsets, and long stretches of consecutive values as runs. It is often both smaller and faster than an uncompressed bitset. Roaring is used by many systems you already know: Elasticsearch, Apache Spark, ClickHouse …

Antonio Viggiano has brought Roaring into Redis itself. It should ship in Redis 8.12. There is a new type: TYPE key returns bitmap and OBJECT ENCODING key returns bitmap-roaring. It is opt-in: CONFIG SET bitmap-default-roaring yes.

I built Redis at the merge commit and ran the server on one core of an Intel Xeon Gold 6548N. For each workload, I create two bitmaps, a and b, once as strings and once as Roaring bitmaps, with the same content, and I time the commands. My workloads:

• 0.1% random: 100,000 random ids out of 100 million (think: the users who used a given feature today);
• 50% random: 50 million random ids out of 100 million;
• runs: ten runs of one million consecutive ids in a range of 100 million (think: cohorts of users who signed up in the same week);
• hashed 32-bit ids: 100,000 random 32-bit values, so the string is 512 MB.

You can see that Roaring can be much faster than a standard uncompressed bitmap in some cases. The hashed ids are even more compelling. The string must span all four billion bit positions, and each BITOP scans 512 MB. 

Compressed bitmaps like Roaring are not always better. There are many tradeoffs. But turning them on will soon take one configuration setting. Check out the Roaring bitmap website for more information.

2026-10-12 21:06:39

Python used to have limited parallelism, due to its global interpreter lock (GIL). Only one thread could run Python code at a time. Python 3.14 comes in a free-threaded version (python3.14t), without the global interpreter lock. Several threads can now run Python code at the same time.

Let us pick a realistic problem. GitHub publishes everything that happens on its public repositories: pushes, issues, pull requests, stars, and so forth. The GH Archive project collects these events as JSON, one event per line (NDJSON), one file per hour. I took eight hours of March 13, 2024: 7.6 GB of JSON once decompressed, 2.2 million events. I want to know which programming languages get the most new pull requests. So I count the events by type, and for each pull request that was opened, I look up the language of the repository. Each event is a large JSON object, about 3.4 kB on average: I need only a few of its fields.

The answer, for these eight hours: 65,269 pull requests were opened, mostly toward TypeScript (11,565), JavaScript (7,778), Python (7,057) and Java (4,668) repositories. About 5,857 targeted repositories without a language.

With fastsimdjson, our Python binding for simdjson, the code looks as follows. The function map_many calls my function on each event, using as many threads as I ask for.

import collections, threading
import fastsimdjson
local = threading.local()
parts = []
def one_event(e):
    acc = getattr(local, "acc", None)
    if acc is None:  # first event seen by this thread
        acc = local.acc = (collections.Counter(), collections.Counter())
        parts.append(acc)
    t = e["type"]
    acc[0][t] += 1
    if t == "PullRequestEvent":
        p = e["payload"]
        if p["action"] == "opened":
            acc[1][p["pull_request"]["base"]["repo"]["language"]] += 1
data = open("events.json", "rb").read()
fastsimdjson.map_many(one_event, data, format="lines", threads=64, lazy=True)
types, languages = collections.Counter(), collections.Counter()
for t, lang in parts:
    types.update(t)
    languages.update(lang)

Each thread keeps its own counters. The first event a thread sees creates the pair and appends it to parts. Later events on that thread update the same pair. Nothing in the counters is shared, so the threads do not wait for each other. map_many returns only once every event has been counted. The main thread then walks parts, one pair per thread, and Counter.update adds the counts. A few dozen event types and about a hundred languages: the merge is tiny next to the parsing.

With lazy=True, my function receives a lazy view of the event instead of a dictionary: the event is parsed, but Python objects are created only for the values I access. The lazy approach was first developed by Tyler Kennedy in another simdjson binding, pysimdjson.

How does it compare? I tried the usual suspects: the standard library (json), orjson and msgspec. msgspec deserves special mention: it can decode JSON into typed structures that declare only the fields you need, skipping the rest. It is a lot like our lazy views, except that you must declare a schema beforehand. I gave msgspec this advantage. In each case, I verify that we get exactly the same counts.

I use a server with two Intel Xeon Gold 6548N processors (64 cores), Python 3.14.6, and the current versions of the libraries (fastsimdjson 0.6.0, orjson 3.13.0, msgspec 0.22.0). The data is decompressed in memory before the timer starts. I report the best of seven runs, and one run for the slow methods: the single-thread parsers, and the standard library on 64 threads. Let us first use a single core.

The standard library needs 42 seconds to go through the eight hours. With fastsimdjson and lazy views, it takes 3.6 seconds. Notice how the methods that materialize everything (json, orjson and fastsimdjson without lazy views) are slow: most of the time goes into creating Python objects that we discard right away.

Now let us use all 64 cores, still in one process. On free-threaded Python, I use a thread pool for json and msgspec, and map_many(..., threads=64) for fastsimdjson. The threads share the input.

We go through 7.6 GB of JSON in about 0.12 seconds, at 66 GB/s, in one Python process. That is 31 times faster than with one core. It is faster than msgspec using 64 threads (25 GB/s).

So, can you parse JSON at tens of gigabytes per second in Python? Yes.

fastsimdjson 0.6.0 is available on PyPI. My benchmark is available.

2026-10-10 16:56:11

WebSocket is a standard protocol to hook up a client and a server in a persistent manner. It is commonly used for live chat, notifications, multiplayer games, collaborative editing, and streaming dashboards. Many servers are written in JavaScript and use Node.js, Bun or Deno as an engine.

A few years ago, I wrote a simple WebSocket benchmark in JavaScript. Two clients exchange messages through a server: client 1 sends a message to the server, the server forwards it to client 2, client 2 answers, and the server forwards the answer back to client 1. I found that Bun could be twice as fast as Node.js. That result was wrong. The Bun server sent each message back to the sender, so a round trip was two messages instead of four. Since then, Anthropic bought Bun. Also, Cloudflare bought Deno.

My benchmark had an issue: my clients were written in JavaScript, and they were slow. So I wrote a client in C. Doing so by hand in 2023 was expensive, but in 2026, my AI friends can write anything in C.

I run a single ping-pong test: a single pair of clients chats through the server.

I compare three servers against a small C relay:

• Node.js 26 with uWebSockets.js, a native addon written in C++;
• Bun 1.4.2 with its built-in server (Bun.serve);
• Deno 2.9.7 with its built-in server (Deno.serve).

My test machine is a Linux server with an Intel Xeon Gold 6548N (Emerald Rapids). Everything runs locally over the loopback interface. The server is restricted to a single core, and the client runs on another core. I repeated the whole benchmark three times: the results are stable, within a few percent.

I report the number of round trips per second and the time per round trip (median and 99th percentile).

A JavaScript WebSocket server can get close to a simple C server in this test. Node.js 26 with uWebSockets.js is quite a bit faster than Bun and Deno: 49,000 round trips per second, against 40,000 for Deno and 37,000 for Bun. The 99th percentile is 24.8 µs, against 32.0 µs and 46.4 µs.

I repeated the same ping-pong test with the Javascript ws package, version 8.22.0, on all three runtimes. 

Node.js is ahead, then Bun, then Deno. On Node.js, ws is close to uWebSockets.js (45,000 against 49,000). On Bun, ws beats Bun.serve (41,000 against 37,000). On Deno, ws is behind Deno.serve (34,000 against 40,000).

My source code is available.

2026-10-09 11:15:06

When a Python program starts, it needs to load all its dependencies (import). With the upcoming version of Python, it is possible to use lazy imports instead.

lazy import json
lazy from decimal import Decimal

In this instance, the name json is no longer the module, but a mere placeholder object. The actual import only happens when you use json. If you never use json, the module is never loaded.

How much does it help? Let us measure.

I wrote a toy command-line tool. It imports sixteen modules: json, csv, decimal, sqlite3, asyncio, email.parser, http.client, urllib.request, xml.etree.ElementTree, zipfile, tarfile, statistics and some popular third-party packages (numpy, pandas, requests, rich). The tool has three paths:

• --version prints a string and needs nothing;
• mean reads a small CSV file with the csv module and calls statistics.fmean;
• stats loads the same file with pandas and prints a summary.

The lazy version of the tool is identical, except that I prefix the imports with lazy. It is a one-word change per line.

I use Python 3.15 (3.15.0b4) on an Intel Xeon Gold 6548N (Emerald Rapids), with numpy 2.5, pandas 3.0 and requests 2.34.

Printing the version number goes from 295 ms to 20 ms. If you subtract the interpreter startup (11.7 ms), the cost of the imports goes from 283 ms to about 8 ms: a 35-fold reduction. The mean command, which needs a few standard modules, is twelve times faster.

There is a downside: errors move. With an eager import, a missing module fails at startup. With a lazy import, it fails at the first use, perhaps deep inside a function, perhaps hours later in a long-running server.

My source code is available.