Daniel Lemire's blog

We are told that AI entities much like ChatGPT might soon kill us all. The statement is vague and unfalsifiable. It might be true, it might be false. People with credentials (e.g., Turing Award recipient Yoshua Bengio) believe it.

Many still remember the Year-2000 bug. Our computers used two-digit coding for dates, and some software could get confused. At the time, experts worried that a bug in dates might trigger nuclear Armageddon or an infrastructure collapse. At the very least, planes could fall.

The Club of Rome predicted mass starvation. As an answer, we sterilized by force millions of Indians, and introduced the devastating one-child policy in China. The authors were never held accountable. The projections were purely mathematical, unescapable. They said. But also totally wrong and silly. Yet, we listened to them and caused great harm.

End-of-the-world scenarios are nothing new. Pretty much all civilizations have lived with various such predictions.

Some people are offended by my comparisons. I truly do not mean to offend. But the fact that disagreeing can lead to deep offense is, by itself, a sign that we face a moral issue. There is a sense in which you must agree that these intense fears are warranted.

Many will remember that when OpenAI first developed GPT-2, they told the world that it was too dangerous to release. Year after year, we were warned that the next iteration of it would doom us all.

A large language model takes tokens (words) in and outputs tokens (words). The big models can take many, many tokens in. And they do much compute. And they are based on clever ideas like vector embeddings. But, ultimately, no large language model can do anything but output tokens. You can build a better model, but the model itself does not ‘learn’. It is a fixed set of weights. If you take a model that has been used for months, and always feed the same tokens, you will get the same results (up to some randomness).

I fear that some people exploit the fact that people cannot grasp how conceptually simple a language model is. In any case, most people don’t understand how things work.

Things become interesting because these models can be hooked up to tools. So you can tell your language model that whenever it outputs ‘boom’, then a nuclear weapon will be launched. And if you hook up a nuclear weapon, then, certainly, you may start a nuclear war. So don’t do that.

One unproven thesis is that the models (that take in tokens and output tokens) will ‘decide’ to acquire access to these nuclear weapons, maybe through a subterfuge. What does that mean? It is always conveniently vague. In the movie WarGames (1983), a teenager uses his computer to access a computer in charge of nuclear weapons. He almost wipes out humanity. Could this happen by accident with a kid using a language model hooked up to the Internet? But if it happens, we should blame whoever hooked up a deadly computer to the Internet.

Of course, any technology is inherently dangerous. Invent the bow to go hunting, and someone might soon turn the bow against you. Invent the engine, and one might soon build tanks and destroy nations. Develop nuclear technology, and one might soon raze your cities.
 
Yet that is not what is at stake in these discussions. The concrete threats are not ascertained and addressed. No doubt, there are some people doing this work, hopefully in the US military. What if an adversary can take control of the economy or military installations? What if an AI agent goes rogue? It is worth investing time in designing defenses.

What we have instead is something of the sort:

1. A vague but global threat. It could be a fatal virus engineered in a lab, a climate catastrophe, a fatal bug affecting all our software, an alien invasion, a rogue AI, Jews taking over our institutions.
2. A few people come forward and they offer to save us. Importantly we must give them resources and influence. Ultimately, they seek a totalitarian solution: everyone must be made to agree so that we can be saved.
3. As the process unfolds, people with an opposing viewpoint are described as a danger. They must be silenced and discredited. Eventually, it can become moral to exaggerate the threat or to rewrite counterpoints. People must be made to understand one way or another.

In this instance, I refer to people who advocate that AI will doom us as AI Doomers. These people tend to carry a totalitarian ideology. Their ideas will only work if everyone is made to agree. And it would severely restrict the freedom of billions of people, although they usually present it differently.

Doomers do not have bad intentions. On the contrary, they are often really out there to save the world. But good intentions do not, in any way, justify the means nor guarantee a good outcome.

Human beings reason based on cultural knowledge. For centuries or more, totalitarian ideas have led to ruin. We ignore the warnings at our peril.

But shouldn’t we just be prudent and adopt their views, just in case? It is a fallacious argument. Members of the intellectual elite have a tendency to fall for the kind of hubris where they think that, if only they were given more power, the world would be better off. It is rarely true. Thomas Sowell has an excellent book on the topic, Intellectuals and Society. He makes the case that intellectuals often promote harmful ideas, at no cost to themselves. Rationally, we should therefore be cautious.

You are not safer without technology. In fact, the risk of human extinction is assuredly higher if we are poorer and have less technology.

Is this unprecedented? The printing press was unprecedented. Arabic numbers were unprecedented. Maybe we should go back to Roman numerals, to be safe. Fear of what is without precedent soon becomes indistinguishable from an anti-innovation stance.

What if you do not like the people who lead the big AI companies like OpenAI and Anthropic. Maybe you think that these billionaires are a danger. And you might be right. But consider the history of humanity. Wealthy people have primarily caused harm through the promotion of bad ideas. The mass murders are almost invariably derived from politics. Stalin, Hitler, Mao.

Throughout much of the world, we are facing demographic collapse and an inverted age pyramid. Soon there may be just one worker per retiree. Choosing to have fewer kids has consequences and we are about to face them. AI might be a way out of significant problems. If you are otherwise wealthy, that might not be a significant concern to you. But for the least fortunate, it might turn out to be quite a problem. Who will take care of you when you are sick?

Further, we need to consider how powerful people might use the fear of AI for their own purposes. It is entirely credible that the owners of large companies could promote fear so that they get to write the regulations that will keep out their competitors, or merely as a form of cheap marketing.

How do I know that it is moral? Because there cannot be reasoned debate about a moral question. The facts are obvious or you are a bad person. Whenever there is a complex question, one that involves predicting the future, that cannot be discussed, unless it is in agreement with the side of fear, then you are very likely in a moral question. « Don’t you see, AI will soon kill all of us, it is obvious. » No explanation can be demanded.

You might accuse me of, in turn, promoting fear. But it should be obvious that I am doing no such thing. What I am encouraging rather is the use of reason. I am forced to give examples where inciting fear has led to disastrous effects, but my hope is that it will lead my reader to sit and reflect.

To my friends who fear AI, I urge you. Use reason. Do the work. Do not rely on hasty thought experiments. Work out the details. Think. Think about the countermeasures.

And for the rest of us. Let us build. Let us bring prosperity. Let us hasten the cure for cancer. Let us dream of exploring our solar system.

Further reading.

• • Nirit Weiss-Blatt, “The Weak Foundations of AI Doomsday” — AI Panic, May 15, 2026.
  • Cal Newport, “Dear A.I. Companies, the Doom Trolling Needs to Stop” — New York Times, June 17, 2026
  • Andrew Orlowski, “Anthropic’s doom predictions are merely hype intended to make AI look important” — The Telegraph, June 5, 2026.

If you write in C, by default, you use a single thread. Extra cores do not help until you create more threads. However, if you include the header <threads.h>, you can pass a function to thrd_create, and wait for it with thrd_join.

#include <threads.h>
#include <stdio.h>
int worker(void *arg) {
    printf("hello from thread %d\n", *(int *)arg);
    return 0;
}
int main(void) {
    thrd_t t;
    int id = 1;
    thrd_create(&t, worker, &id);
    thrd_join(t, NULL);
}

Be warned that C11 threads are an optional feature. If the macro __STDC_NO_THREADS__ is defined, you do not have them. Apple’s C library has never shipped <threads.h>, so the program above does not compile on macOS, and glibc only added it in version 2.28 (2018). On such systems you fall back on POSIX threads (pthread_create, pthread_join).

Once you have more than one thread, they may share memory. If two threads access the same non-atomic variable with no ordering between them, and at least one of them writes, the C language calls that a data race. In other words, it is unsafe.

If you have a variable and it is effectively constant, then it is fine to share it. But as soon as anyone changes it, then it might get corrupted. If it is not guarded somewhat, you are in trouble.

To be clear, that is what the C programming language says. I don’t mean that it will happen on your machine.

To get a better behavior, we can use atomic variables. In C, you have the <stdatomic.h> header.

An atomic integer is never garbage. You always read a value that was once written.

In practice, on most computers you might use today, aligned 8-, 16-, 32- and 64-bit loads and stores are atomic. The C language does not care about that, so if you don’t specifically require atomicity, you might get in trouble with your C compiler.

The next funny problem is that instructions can be reordered. When you write:

x = 2
y = 3

This may not happen in this sequence. The variable y might be set before the variable x. You may wonder why this is allowed at all. The fundamental reason is that our processors are quite complex. They have layers of buffers and they can execute multiple instructions at once. They can issue several memory loads or stores at once.

By default, in C, atomic accesses are all ordered. It is as if there is an oracle that watches all threads and comes up with a consistent story where everything is in order. This can be expensive, so we prefer not to do it that way.

At the other extreme is the relaxed model: your reads and stores are not garbage, and a given atomic still has one modification order (you will not see 1 and then 0 if the counter only went from 0 to 1), but there is no ordering with respect to other memory.

So we use something intermediate, the release and acquire semantics. They are ordering barriers. A strict barrier would be ‘everything before me really happens before me, and everything after me really happens after me’. (Where ‘really happens’ refers to visible effects, the hardware and compiler are allowed to cheat as long as you don’t catch them.) It is a bit too strong. So we split it in two parts: release and acquire. Intuitively, release means ‘if you see me, you see all the stuff before me’. Acquire means ‘I take that package, and everything I do after this load really happens after it’.

Consider the case where you have a resource (such as a block of allocated memory). You share this resource, but count how many people have access to it. When the counter goes to zero, you free the resource.

One thread could do…

access resource
decrement counter // I won't need it anymore

You see these operations happening one after the other, but they may not execute this way. It is possible that they overlap, or even that the decrement occurs before the access. It is entirely safe in a single threaded context.

Anyhow, so the following could happen

decrement counter // I won't need it anymore
access resource

But what if you have a second thread that does:

access resource
decrement counter // I won't need it anymore
if (counter is zero)
  free(resource)

You could have this interplay:

[thread2] access resource
[thread2] decrement counter
[thread1] decrement counter
[thread2] free(resource)
[thread1] access resource

That would be a bug.

So what you first do is make the decrement a ‘release access’ which means that operations that come before it cannot be reordered after it. So if you do it this way…

access resource
decrement counter using release

Then it is not possible that we ‘see’ the operations as if they happened in the reverse order.

But then we have a second problem. Release is enough for this thread: we cannot still be using the resource after we drop it. It does not tell the last owner that everyone else is finished. The last decrement is itself a release, so it does not observe the other threads’ releases. Without an acquire, that last thread can call free while another thread’s earlier access is not yet done.

[thread2] access resource
[thread2] decrement counter using release
[thread1] decrement counter using release
[thread1] free(resource)

Thread 2 did its access before its release decrement, but thread 1 never acquired, so it is not required to see that access as finished before free.

So we need the counterpart to a release, an acquire. The last owner acquires before it frees, and that pairs with everyone else’s release:

access resource
decrement counter with release
if (counter is zero)
  acquire barrier // see that everyone else is done
  free(resource)

Alternatively, you could do this.

access resource
decrement counter with release and acquire
if (counter is zero)
  free(resource)

The two are equivalent, but they are not necessarily equally cheap.

So let us consider a nice example. Let us build a small array that several threads can share. If you are the only owner, you overwrite an element in place. If not, you copy, then you update the copy. That is called copy-on-write. It is a really nice idea that you will find in many important systems.

We start with the type.

#include <assert.h>
#include <stdatomic.h>
#include <stdlib.h>
#define STR_SIZE 16
typedef struct {
    atomic_int refs;
    int values[STR_SIZE];
} shared_array;

The payload is a plain int array. Only refs is atomic. That is deliberate. We never write values while another thread might be reading them.

We create an instance like so.

shared_array *str_new(void) {
    shared_array *o = malloc(sizeof *o);
    if (o == NULL) {
        return NULL;
    }
    atomic_init(&o->refs, 1);
    for (int i = 0; i < STR_SIZE; i++) {
        o->values[i] = 0;
    }
    return o;
}

The atomic_init is not an atomic access in the memory-model sense. Nobody else has the pointer yet, so there is no other thread to race with. The caller owns one reference. It is just how we initialize an atomic_int.

Here is how we might naively release an instance.

// not real code
void obj_release(shared_array *o) {
    auto ref = o->refs;
    o->refs -= 1;
    if (ref != 1)
        return;
    // we are the last copy
    free(o);
}

What is the problem with this code?

The load and the decrement are two operations. Two threads can both read 2, both subtract, the counter hits zero, and nobody frees: the resource leaks. Write the check the other way around, decrementing first and then testing whether the counter is zero, as in the pseudocode above, and you get the mirror-image bug instead: with refs at 2, one thread decrements to 1, the other decrements to 0, both then read 0, and both call free. You need one atomic subtract that hands you the previous value: only the thread that saw 1 was last.

So you could try

void obj_release(shared_array *o) {
    if (atomic_fetch_sub_explicit(&o->refs, 1, memory_order_relaxed) != 1)
        return;
    free(o);
}

But suppose you have two owners, so that refs is 2. And you have two threads doing

(void)o->values[4];
obj_release(o);

One of them will call free, but the order could be

...
[thread1] o->values[4];
[thread2] atomic_fetch_sub_explicit(&o->refs, 1, memory_order_relaxed)
[thread1] atomic_fetch_sub_explicit(&o->refs, 1, memory_order_relaxed)
[thread1] free(o);
[thread2] o->values[4];

It is a bit confusing because things are not happening in order within thread 2:

[thread2] atomic_fetch_sub_explicit(&o->refs, 1, memory_order_relaxed)
[thread2] o->values[4];

But this is allowed.

So what we can do is put a release on the atomic_fetch_sub_explicit and then an acquire right before the free.

void obj_release(shared_array *o) {
    if (atomic_fetch_sub_explicit(&o->refs, 1, memory_order_release) != 1)
        return;
    atomic_thread_fence(memory_order_acquire);
    free(o);
}

The release on every decrement means “I am done with the payload.” The acquire fence, only on the last owner, means “I have seen that everyone else is done.” Then free is safe.

That release does double duty, as we are about to see. It is also what lets the last remaining owner write to the payload in place.

If a thread wants another reference to the same instance, it only needs a relaxed access.

shared_array *str_retain(shared_array *o) {
    atomic_fetch_add_explicit(&o->refs, 1, memory_order_relaxed);
    return o;
}

Why relaxed? Because the caller already holds a reference, so the object cannot be freed under us: the last owner would need our reference to be gone first.

We can now write update. It consumes the caller’s reference and returns a reference to the array that contains the new value, which may or may not be the same object. After you call it, you must not touch the pointer you passed in. There is one exception: if a copy was needed and the allocation failed, it returns NULL and leaves the caller’s reference to o untouched, so you still own it and must still release it.

shared_array *update(size_t idx, int value, shared_array *o) {
    assert(idx < STR_SIZE);
    if (atomic_load_explicit(&o->refs, memory_order_acquire) == 1) {
        o->values[idx] = value;
        return o;
    }
    shared_array *new_o = str_new();
    if (new_o == NULL) {
        return NULL;
    }
    for (int i = 0; i < STR_SIZE; i++) {
        new_o->values[i] = o->values[i];
    }
    new_o->values[idx] = value;
    obj_release(o);
    return new_o;
}

If the load reads 1, we are the only owner. No other thread holds a reference, so we can write values[idx] in place.

The load is an acquire. When the load reads 1, it may read the value written by the release decrement of the last other owner to drop out. Everything that thread did with values happens before our write. Nothing in our code appearing after such as o->values[idx] = value may move before it. No other thread still holds a reference, so the write does not race with a concurrent reader. Later, after a retain, other threads can see it.

On x64, acquire and release are effectively free at the CPU: ordinary loads already behave like acquire, ordinary stores like release. You still have to write them in C, or the compiler may reorder the payload accesses. ARM has a weaker memory model so the acquire/release require different instructions (ldapr, ldaddl) which may incur a small perforamnce hit.

The code is available.

In Python, the dict data structure is the conventional key-value structure. E.g., you might store a list of names as keys and have their phone numbers as values. Valentin Ignatev wrote this amusing post on X:

It is indeed widely believed that, in the strict sense, the dict data structure and its companion, the set data structure, are O(1), meaning that as you increase the size of the data structure, the time to insert or query a key remains constant.

Let us examine the claim.

A hash function is a function from objects (like strings, integers, etc.) to integer values. We typically expect hash functions to be random-like, although they should always map the same object to the same integer within the current program execution. From hash functions, we construct hash tables:

1. Create an array of buckets.
2. Given an object, apply the hash function to map it to a bucket.
3. Store the object in the bucket. When the bucket is already occupied, use some other trick (such as using a nearby bucket).

If everything goes well, access and insertion in a hash table take nearly constant time, meaning that the time they take is independent of the size of the hash table.

This can be almost true in many instances. However, it is not formally true. There are many reasons why it is false. For example, if your data structure grows, it might be necessary to reallocate, which will typically take time proportional to the size of the data structure. But we also have the issue of collisions. A collision is what happens when two objects have the same hash value. When we use hash tables, we assume that collisions are uncommon. But it is not difficult to create many of them by picking our objects carefully.

In Python, set and dict are hash tables. I can ‘easily’ make my version of Python crumble:

M = (1 << 61) - 1
values = [i * M for i in range(1, n + 1)]
s = set(values)                       # insertions
count = sum(v in s for v in values)   # checks

If the insertions and the checks are constant-time operations, then the whole construction and the entire check should take linear time. I ran this on an Apple M4 Max with Python 3.14, reporting the median of three runs.

The time roughly quadruples each time n doubles. That is quadratic time, not linear time. The membership checks behave the same way: 1066 ms at n = 16000. At a hundred thousand elements, building the set takes 45 seconds.

But could we create a hash table that would be truly constant-time? No. As the size of your data structure grows, it requires progressively slower memory. If you have a small hash table, it can reside in the CPU cache and be fast. Once it reaches megabytes in size, the data structure tends to live in RAM, which is much slower. And then, eventually, you have to store it on disk, which is even slower. And so forth.

To put it differently, saying that a hash table is O(1) or constant time is a model. It can be true, maybe even often, but it is not reality. Models are great teaching tools: they present a simplified model that you can quickly learn. But models can also introduce biases in how we think.

For example, even though you have read my paragraph that says that the dict data structure gets slower, you may not believe it. You may also believe that it is typically going to be the fastest approach you can use.

Let us consider another practical case. Suppose that you have a large map from strings to integers, that you build once and then only query. That is a common situation: a dictionary of words to identifiers, a lookup table of country codes, a table of feature names.

The fastconstmap library builds an immutable map from a dict[str, int]. It is suitable when your keys are known in advance.

I build a map from a million random sixteen-character strings to integers, and then look up every key in a shuffled order. With a dict, I write the obvious loop:

total = 0
for k in probes:
    total += d[k]

With fastconstmap, I ask for all the keys at once, writing the values into a buffer that I own, so that no Python object is allocated per key:

out = array("Q", bytes(8 * n))
cm.get_many_into(probes, out)

I am being generous to the dict. I reuse the same string objects for the lookups, and a Python string caches its hash value the first time it is computed. So the dict does not pay for hashing at all, while fastconstmap hashes every key every time. Here are the results, in nanoseconds per key.

The dict is not constant time. It goes from 22 ns to 202 ns per key as the map grows, a factor of nine, and it is not because the algorithm changed or because of collisions. It is because a million keys, their string objects, and their integer objects occupy about 116 bytes per key, so the lookups miss in the cache. The fastconstmap version needs 9 bytes per key: it stays in the cache much longer. Pay attention to how the numbers scale: the dict becomes 10 times slower as the size grows.

The lesson is always the same. Some models are useful but none of them is reality. Be mindful of cognitive biases.

The code is available.

JSON is a standard format for data interchange. It is effectively a tiny subset of JavaScript made of objects and arrays. It looks as follows {"key":1, "text":[1.0,2.0]}.

Many programming languages include a JSON library in their standard libraries: C#, Go, Java (soon), Python, JavaScript, etc. The Go implementation is convenient, but not especially fast.

Go 1.27 makes a new JSON package (encoding/json/v2) available by default in its standard library. The two APIs look almost the same:

import (
    json    "encoding/json"
    jsonv2  "encoding/json/v2"
)
b, err := json.Marshal(v)
b, err  = jsonv2.Marshal(v)
err = json.Unmarshal(b, &v)
err = jsonv2.Unmarshal(b, &v)

The two are not directly comparable as they differ with respect to Unicode validation, case sensitivity, etc. So it is not a drop-in replacement.

However, the legacy API (encoding/json) has also been reimplemented on top of the new engine. You can use the legacy API with either the new engine or the old one (GOEXPERIMENT=nojsonv2) through a flag. So we have three possibilities.

1. json (legacy) — encoding/json built with GOEXPERIMENT=nojsonv2, the original implementation
2. json (Go 1.27) — encoding/json as of 1.27, v1 API on the v2 backend
3. json/v2 — encoding/json/v2

I used the usual simdjson documents: twitter.json (632 kB, nested objects with short string keys), canada.json (2.25 MB, one large array of coordinates), and citm_catalog.json (1.73 MB, nested objects with numeric keys). I parse them into any (interface{}), which is the general-purpose path.

I ran this on an Apple M4 Max and on an Intel Xeon Gold 6548N (Emerald Rapids) using Go 1.27.0, on a single core (GOMAXPROCS=1), reporting the median of eight runs.

When unmarshalling, the legacy API on the new backend is faster than the original on twitter.json (172 MB/s to 203 MB/s) and on citm_catalog.json (186 MB/s to 241 MB/s), but slower on canada.json (128 MB/s down to 106 MB/s). When marshalling, it is up to twice as fast: 198 MB/s to 374 MB/s on twitter.json. So merely upgrading to Go 1.27, without changing a line of code, should make marshalling faster.

Switching to the new API helps more. Compared to the original implementation, encoding/json/v2 unmarshals 1.5x to 2.3x faster and marshals 1.2x to 3x faster. Compared to the Go 1.27 legacy API, unmarshalling gains another 1.8x to 2x, while marshalling gains much less (1.0x to 1.7x): part of the remaining difference is that json/v2 does less work during marshalling.

Thus far, I was unmarshalling into any, meaning that I assumed that I did not know the structure of the document. I also round-trip a slice of 10,000 small structs:

type Record struct {
    ID     int      `json:"id"`
    Name   string   `json:"name"`
    Email  string   `json:"email"`
    Active bool     `json:"active"`
    Score  float64  `json:"score"`
    Tags   []string `json:"tags"`
}

The schema is specified: the JSON must be [{"id":..., "name":...}, {"id":..., "name":...}...]. I still get faster unmarshalling with the new API, but the legacy API with the legacy engine is faster when marshalling.

The original implementation is faster. The Go 1.27 release notes said that marshal performance is broadly at parity with the previous implementation. For my test, it is not the case.

So unmarshalling gets faster across the board with encoding/json/v2, and marshalling gets faster for any, but it is about 1.5x slower for typed structs in my tests.

The code is available.

In Java, you find the location of a substring using indexOf.

String haystack = "The quick brown fox jumps over the lazy dog";
String needle = "fox";
int index = haystack.indexOf(needle);

Naively, you might implement indexOf by a loop inside a loop, like so.

int naiveIndexOf(String haystack, String needle) {
    for (int i = 0; i <= haystack.length() - needle.length(); i++) {
        int j = 0;
        for (; j < needle.length() 
          && haystack.charAt(i + j) == needle.charAt(j); j++) {}
        if (j == needle.length()) { return i; }
    }
    return -1;
}

The Java implementation is much more sophisticated, and it is highly accelerated.

However, there are pathological cases where the Java implementation can be slow. What do I mean? Well, you do expect that the search will be more and more expensive as the size of the string grows. Right? So if you search through a 1 kilobyte string and then search through a 10 kilobyte search, you would not be surprised if the latter takes ten times slower.

But what of the substring? If you search for short substrings (fox in my example), the everything is fine. But what if you search longer and longer substrings (fox jumps or fox jumps over)? If it gets more expensive when both the string and the substring get longer, then you have what we call a quadratic complexity. In other words, it is slow.

In Java, if n is the length of your string and m is the length of the substring, then the complexity of indexOf is O(n·m). And if you look at my naive implementation (naiveIndexOf) then you see that in the worst case, it might do up to close to haystack.length() * needle.length() comparisons, that is, it is O(n·m).

The exact implementation of the indexOf function depends on your CPU and Java version. I am using OpenJDK 25 on Apple Silicon (ARM). For my purposes, I will use as a haystack of n copies of a and for the needle, the same thing, but ending with a different letter.

// n > m
String haystack = "a".repeat(n);
String needle = "a".repeat(m - 1) + "b";

I measured OpenJDK 25 on an Apple M4 Max. The haystack is one megabyte. Numbers are nanoseconds per haystack character.

At m = 4096, a single indexOf over one megabyte takes 1.1 seconds.

Can you do better against such adversarial inputs? The textbook solution is the Two-Way algorithm of Crochemore and Perrin (1991). The implementation is simple and your favourite AI can code it for you in any programming language.

Two-Way stays at about 0.3 ns/character no matter how long the needle is. At m = 4096 it is about 3500 times faster than indexOf on the first-character adversary.

So, should you switch to Two-Way for everything? No. On random text, the indexOf function is much faster than Two-Way.

And Two-Way has to do non-trivial work before the search begins. So it has additional fixed overhead. It would lose most of the time in the real world, sometimes by a wide margin.

Should you worry about this? No. The indexOf function in Java is fine.

If an adversary can control the needle (substring), then make sure to reject long needles. Most of the time, we search for short sequences (say, less than 80 characters). If you are worried about your system crashing, you will put bounds on inputs in any case.

The Java source is available.

Further reading: Crochemore, M., & Perrin, D. (1991). Two-way string-matching. Journal of the ACM, 38(3), 650–674.

We are all familiar with IP addresses such as 192.168.0.1. They are typically written as four numbers in the range 0 to 255 inclusive, separated by dots. In C#, you can parse them with the standard library using IPAddress.TryParse.

Pedantic people are quick to point out that IP addresses can take different forms: they can be IPv6 or IPv4 and there are many weird ways to write an IPv4 address. But for the purpose of performance optimization, we care about the common case. The common case is strings such as 192.168.0.1 or 12.121.244.111.

Our processors are capable of data parallelism, meaning that they have instructions (called SIMD) that can process several bytes at once, at least 16 bytes, sometimes more. A few years ago, I showed that you can parse IPv4 addresses with SIMD. I have been revisiting this idea with AVX-512, the instruction set that recent x64 (AMD/Intel) processors support. I expect that all Intel and AMD processors made in the near future will have great support for AVX-512, and it is already the case for server processors and recent AMD processors.

So I wondered, could we do it in C#? People are sometimes surprised that I care about C#. Isn’t that more Microsoft slop? No. Not at all. C# and .NET are very reasonable, portable systems.

Plus you can write fast code in C#. I have two optimized libraries that I hope the Microsoft .NET team will one day adopt in the standard .NET library: an optimized Utf8Utility.GetPointerToFirstInvalidByte function used internally to validate Unicode strings (in the SimdUnicode library) and a fast base64 decoding library. I love working with .NET C#.

As of .NET 10, we have AVX-512 support, including masked loads. What are masked loads and why do they matter? Suppose that I give you a string that is no longer than 16 bytes, but could be shorter. If you load data in a SIMD register, you normally have to load the full register width (so 8, 16, 32, 64 bytes). So what do you do when it is not possible? You can pad the input string or pull other tricks, but it gets dirty. A nice approach is to have masked loads where you, say, load the full register (say 16 bytes), but you indicate which bytes you want to be loaded from memory with a mask. So if you use 0b10011 as a mask, then only the first, second, and fifth bytes are loaded from memory. This makes it possible to initialize a 16-byte register with a string that has between 0 and 16 bytes, while never reading beyond the string. I have an article entitled Modern vector programming with masked loads and stores if you want to know more.

To make things trickier, C#, like Java and JavaScript, defaults to UTF-16, meaning that each character, even if it is an ASCII character like A or 1, uses two bytes. The ASCII codepoint value occupies the least significant bits of a 16-bit word.

So what we need to do is to selectively load from a 32-byte input, and then drop the unnecessary zero bytes. The gist of it looks as follows in C#.

unsafe bool TryParseAvx512(ReadOnlySpan<char> s, out uint ip) {
        int len = s.Length;
        fixed (char* cp = s)
        {
            // next two lines are a trick to load just the first len characters
            Vector256<ushort> charMask = Vector256.LessThan(CharLaneIndex, Vector256.Create((ushort)len));
            Vector256<ushort> chars = Avx512BW.VL.MaskLoad((ushort*)cp, charMask, Vector256.Create((ushort)'0'));
            // check that everything is ASCII otherwise, it is not an IP!
            if (Avx512BW.VL.CompareGreaterThan(chars, Vector256.Create((ushort)0x7F)).ExtractMostSignificantBits() != 0)
            {
                return false;
            }
            // There we go, we have the address as ASCII
            // in a 16-byte register.
            Vector128<byte> str = Avx512BW.VL.ConvertToVector128Byte(chars);
            // ...
        }
}

This looks a bit difficult to read, but that’s fine. Most people never need to worry about such code.

Then we use a somewhat fancy trick where we locate the dots, and use the fact that there are only 81 ways to position the dots. We then move the bytes, do a dot product and validate. It is the same routine as the C++ code. It is not trivial, but I am working on a formal paper to document the tricks used.

The pedantic people will say: wait, there are other ways to write IP addresses !!! Ok fine. We handle them with a fallback, like so.

if (TryParseAvx512(s, out uint ip))
{
    address = new IPAddress(ip);
    return true;
}
return IPAddress.TryParse(s, out address);

What about the cases where your processor does not support AVX-512? C# makes this dead easy. You can just guard it with one if:

if (Avx512BW.VL.IsSupported) { ... }

To benchmark this, I generated 10,000 random 32-bit addresses and parsed the resulting strings 20 million times, constructing an IPAddress each time. On a relatively recent Intel processor (Intel Xeon Gold 6548N, Emerald Rapids) running .NET 10, I get the following.

So the AVX-512 approach is about three times faster than the standard library. My routine itself does not take fourteen nanoseconds; there is other overhead.

As usual, the C# source is available.

Like most programming languages, Go has both stack allocations, whose lifetime is limited to the current function, and dynamic (or heap) allocations.

The name stack comes from the fact that the memory management is somewhat trivial. There is typically one stack per thread (or goroutine in Go). When a function needs memory, it simply appends data to the stack. When the function returns, the memory is dropped from the end of the stack. So the memory last allocated is deallocated first.

Heap memory is potentially considerably more complex. For one thing, it is meant to be accessible by several threads (or goroutines). An object can be allocated by one function and later reclaimed after an entirely different function, possibly running on a different thread (or goroutine), has dropped the last reference to it. Unlike the stack, there is no prescribed order for allocating and reclaiming heap memory. In Go, the garbage collector does the reclaiming.

Typically, stack allocations have a size known at compile time. Many systems give each thread a fixed-size stack, although Go grows goroutine stacks as needed.

There are many ways in Go to do a heap allocation. A common one is when you allocate a slice, as in this instance where you allocate memory for 100 integers:

x := make([]int, 100)

If the slice x is not entirely local to a function, Go will typically just allocate it on the heap. It will do so similarly when a function returns a pointer. For example, in the following instance, I assign the value 1 to a local integer variable, but I return a pointer to it.

func f() *int {
  x := 1
  return &x
}

In C/C++, this would be quite bad. You should get a warning such as address of local variable 'x' returned. In Go, the variable x will typically get allocated on the heap.

In many Go programs, we end up doing a lot of heap allocations of small objects. It can become a bottleneck in some cases. Think about when you are maintaining a tree or a linked list where each value (node) is an object that must live on the heap. If the data structure is highly dynamic, you will be constantly allocating these small objects.

Memory allocation on the heap is usually not done at arbitrary sizes. You often cannot get exactly, say, 13 bytes. In Go, small allocations are rounded up to a size class: 8 bytes, 16 bytes, 24 bytes, 32 bytes, and so forth. There is also some overhead to each heap allocation, from rounding and from allocator metadata.

The compiler knows the size of the object, but prior to Go 1.27, Go would call a generic function when doing a heap allocation. This generic function would then look up the size class and take the corresponding path. Starting with 1.27, for small objects (under 80 bytes), Go relies on dedicated functions.

It is easy to benchmark in Go. A basic benchmark might look as follows.

type Node struct {
    value int64
    next  *Node
}
var sink any
func BenchmarkAllocNode16(b *testing.B) {
    for b.Loop() {
        sink = &Node{}
    }
}

On my MacBook, the results are quite telling. Go 1.27 is nearly twice as fast!

This will not help all software, just the components that do many small allocations.

The code is available.

AI-assisted programming is fast evolving and there is a tension between ‘we no longer need to understand the code’ and ‘what is my purpose as a programmer’. I recorded a short video on this topic with how I think the tension can result in conflicts.

When a compiler optimizes your program, it has to guess. Which functions are worth inlining? Which side of a branch is the common one? Which method does this interface call actually reach? At compile time it cannot know, so it uses heuristics. Profile-guided optimization (PGO) replaces the guessing with measurement: you run your program, record where it spends its time, and hand that recording back to the compiler for a second build.

PGO is a common feature of compiler systems. Google applied PGO to Chrome under Windows in 2016, reporting gains of up to 15%. I expect all mainstream Web browsers to be built with PGO.

There are now fancier techniques than mere heuristics with PGO. You can use AI to recognize patterns and so forth. But they are not always widely available.

Go has supported PGO since version 1.20. You collect a profile, and pass it to the compiler.

A CPU profile is a statistical record of where a program spends its time. While the program runs, the Go runtime interrupts it about a hundred times a second and writes down the call stack at that instant. After a few seconds you have thousands of such samples, and counting them tells you which functions were executing and who called them. In Go you produce one by wrapping the work you care about:

f, _ := os.Create("cpu.pprof")
pprof.StartCPUProfile(f)   // from runtime/pprof
defer pprof.StopCPUProfile()

The compiler reads the call-stack counts and uses them for two things above all: inlining call sites that turn out to be hot, and devirtualizing interface calls whose target is nearly always the same concrete type.

I took three JSON documents that I wanted to parse:

• twitter.json (632 kB), a nest of small objects with short string keys
• canada.json (2.25 MB), essentially one enormous array of floating-point coordinates
• citm_catalog.json (1.73 MB), deeply nested objects with numeric keys

I parse each of them with the standard library’s encoding/json into an interface{}. The baseline, with no profile, parses at 112 MB/s for twitter.json, 74 MB/s for canada.json and 116 MB/s for citm_catalog.json.

The procedure is three commands:

go build -o bench .                        # ordinary build
./bench -profile cpu.pprof -train twitter.json   # collect a CPU profile
go build -pgo=cpu.pprof -o bench_pgo .     # build again, with the profile

I did it three times, profiling each document on its own, and then measured all three documents against each of the three builds.

Each panel of the figure is one document being parsed, and the three bars inside it are the three PGO builds: the binary trained on twitter.json, the one trained on canada.json, and the one trained on citm_catalog.json. Bar height is the speed gain over the ordinary, profile-free build of that same document, in percent, so zero means PGO changed nothing and a bar below the axis means the PGO build was slower. The green bar in each panel is the matched case, where the profile was collected on the very document being measured.

The gains are modest. The best result is canada.json at +4.7%, and most differences are in the 2–3% range. Profiling one document usually helps the others, but not reliably. Profiling twitter.json gave a decent improvement everywhere: +3.1%, +2.0%, +2.8%. But profiling canada.json bought 4.7% on canada.json and essentially nothing anywhere else. Interestingly, profiling citm_catalog.json produced a mere +0.8% on its own document while helping twitter.json more.

A 3% speedup is not exciting in isolation, but it may come nearly for free. Observe how you may get slightly negative results for cases you did not train for. That’s expected generally, but the effect is modest in the case of Go because its optimizations are themselves modest in the first pace. That is, you are not getting a much an effect, but the process is less likely to backfire for other workloads.

The code is available.