Daniel LemireModify

2026-09-17 04:26:36

C++23 added a new type to the standard library: std::flat_map. There is also a std::flat_set and other variants, but let me focus on std::flat_map.

A flat map is a sorted vector of keys next to a vector of values. A query is a binary search over the sorted keys.

You need a recent standard library: GCC 15’s libstdc++ has std::flat_map, as does LLVM’s libc++ since LLVM 20 (Apple’s clang 17 has it too).

Because the container is just two arrays, we can save it by copying the two arrays. Take a map from 64-bit keys to a fixed-size value:

struct point {
  double x;
  double y;
};
std::flat_map<uint64_t, point> m;
m[42] = {1.0, 2.0};
m[7] = {3.0, 4.0};
m[1000] = {5.0, 6.0};
std::vector<uint64_t> keys(m.keys().begin(), m.keys().end());
std::vector<point> values(m.values().begin(), m.values().end());
// keys   = {7, 42, 1000}
// values = {{3, 4}, {1, 2}, {5, 6}}

The keys array is 8 * keys.size() bytes and the values array is 16 * values.size() bytes: you can write them to disk with two memcpy or write calls, as they are.

If you loaded both arrays from a network or the disk, you can then move them straight into your std::flat_map like so.

std::flat_map<uint64_t, point> back(std::sorted_unique,
                                    std::move(keys), std::move(values));
// back == m

With the std::sorted_unique tag, you promise that the keys are sorted and distinct. In practice, if the data comes from the network or some untrusted source, you should do some sanity testing.

Like the good old std::map, a flat map keeps its keys in sorted order, so you can iterate over it in key order. But the std::map is a red-black tree so you have significant storage overhead and possibly poor memory locality.

The downside of a std::flat_map is that it might be slower if you need to mutate it.

Let us examine the speed.

I use random 64-bit keys mapped to 64-bit values, GCC 16.1 with -O3
-march=native, on an Intel Xeon Gold 6548N (Emerald Rapids), pinned to one core. I report nanoseconds per operation

Let us start with inserting elements one at a time, in random order, into an initially empty container.

Up to maybe a thousand elements or so, the std::flat_map is fine and maybe faster than the std::map. But as the size grows, the time goes up quadratically. Thus, do not use an std::flat_map if you need to insert millions of keys in random order. It is bad.

If the keys arrive in increasing order, then it is entirely different. The std::flat_map is much faster.

You can also do bulk inserts. Given a batch of new pairs, in any order, the map sorts the batch and merges it with its arrays in one pass, instead of shifting the arrays once per element:

std::vector<std::pair<uint64_t, point>> more = {{500, {7.0, 8.0}},
                                                {3, {9.0, 10.0}}};
m.insert_range(more);
// keys = {3, 7, 42, 500, 1000}

Constructing a map from a range of random key-value pairs works the same way, and it is much faster with a std::flat_map:

Random lookups are also much faster for large maps in part because the std::flat_map uses less memory.

In many practical cases, the new std::flat_map is a better alternative to the std::map. It is somewhat amusing considering that you are replacing a fancy textbook data structure (red-black tree) with a trivial one.

My source code is available.

2026-09-15 20:54:32

We represent floating-point numbers using the IEEE standard. For very small numbers, the standard uses special subnormal numbers. Unfortunately, they have a reputation of making operations slow. Thus video game programmers and machine learning specialists sometimes avoid computing with subnormal numbers for performance.

How slow are they? Let me measure. I wrote a small C++ benchmark with a few kernels over arrays of 16384 values (small enough to fit in cache):

• multiply each value by 0.75,
• add two arrays,
• divide each value by 3,
• multiply normal values by a tiny constant (2^-1030) so that the inputs are normal but the outputs are subnormal,
• a dependent chain x *= 0.9999 repeated 16384 times.

For each kernel, I feed either normal values (in [0.5, 1)), subnormal values, or normal values where one value in a hundred is subnormal. The compiler is allowed to autovectorize the array computations. I use GCC 15 with -O3 -march=native on Linux and Apple clang 17 with the same flags on macOS. I also checked with clang 21 on Linux to make sure.

I ran the benchmark on five processors:

• Intel Xeon 6975P-C (Granite Rapids), on an AWS c8i.xlarge instance,
• Intel Xeon Gold 6548N (Emerald Rapids), a server in my lab,
• AMD EPYC 9R45 (Zen 5), on an AWS c8a.xlarge instance,
• AWS Graviton 5 (Arm Neoverse V3), on a c9g.xlarge instance,
• Apple M4 Max.

Here are the results for double values, in nanoseconds per element (or per step).

Intel Granite Rapids

Intel Emerald Rapids

AMD Zen 5

AWS Graviton 5

Apple M4 Max

On Intel processors, a multiplication involving a subnormal number is about 45 to 50 times slower than a multiplication over normal numbers. A division is 18 times slower. The dependent chain, where each multiplication waits for the previous one, goes from about 1 ns to over 30 ns per step. A normal multiplication in the dependent chain has a latency of 4 cycles. With a subnormal, it has a latency of 128 cycles. It does not matter whether the subnormal is an input or an output: multiplying normal numbers into a subnormal result is just as slow as multiplying subnormal numbers. The exception is additions and subtractions: they run at full speed. Even if subnormals are rare (1%), the cost on Intel can be significant because when the compiler vectorizes the computation, a single subnormal can slow down a whole block of computations.

AMD does much better. On Zen 5, multiplications and additions run at full speed regardless of the inputs. The dependent multiplication chain is a third slower (0.66 ns to 0.88 ns per step): the multiplier needs an extra cycle or so to handle a subnormal. Divisions are about twice as slow. Interestingly, with divisions, having one subnormal in a hundred is almost as slow as having all subnormals. The two Arm processors, the Graviton 5 and the Apple M4 Max, do not care at all. Subnormal numbers are handled at full speed.

Thus it appears that on the latest AMD and ARM processors subnormals might not be a concern. But they remain very much a performance issue under Intel processors.

My source code is available.

2026-09-12 03:53:31

Mathematicians are unhappy about OpenAI. Several influential mathematicians wrote an open letter. The gist of their argument is that they form a community that trains young people.

When AI started producing breakthroughs on hard mathematical problems, I asked what a very smart 17-year-old would feel. Do you still choose a math major and train yourself to prove difficult results by hand?

This crisis has been coming for a long time. When I was a kid, the four-colour theorem was proved by a computer, in 1976. An intense debate followed. Does it count as a proof?

I wrote my PhD thesis using symbolic algebra software. To my knowledge, nobody then would publish their scripts. I tried to include mine. I was told it would make me look bad.

The letter says:

“In recent months, the success of AI in solving major mathematical problems has made headlines even outside mathematical circles. But solving problems is only a tool and proxy for achieving the primary goal of conceptual understanding and insight. Forgetting this in the world of AI may turn the tool against the primary goal. Often these solutions are announced in a rush, leaving no time for a proper writeup, the isolation of new methods and ideas, and citing relevant previous work of others. As in all creative professions, this raises severe attribution and plagiarism questions. We are witnessing a general threat to intellectual work, with misalignment between the outcome of the use of AI and its initial purpose. In many fields and activities, years of training have traditionally served not only to produce a final answer or product, but also to develop understanding and the ability to formulate new questions and ideas.”

They worry that kids will not choose to become old-school mathematicians. That is a reasonable fear. Yet they do not seem to consider that some kids might still do mathematics, just in a very different way.

The famous mathematician Doron Zeilberger announced the problem in 2009:

“Teaching computers how to discover and prove mathematical results is certainly the way to go, and I believe that mathematicians who continue to do pure human, pencil-and-paper, computer-less, research, are wasting their time.”

The letter implies that people, because of AI, will stop having ideas, or will stop taking the time to understand the issues. If that were true, mathematics would continue only on computers, with no humans interested, or it would stop. Both scenarios assume that people care about mathematics only when they can claim credit.

I am not sure why I cannot study a proof generated by AI if I want to. I can give talks about it. What becomes less likely is the reward of having been the one who proved the result.

The rest of the letter makes a big deal of credit. What if the AI builds on what it read and does not give proper credit? Where is the evidence that AI is worse than human beings at citing sources?

The letter notes that mathematics contributes to society. It never considers that faster progress might increase those contributions.

My stance is simple.

Mathematicians, software developers, engineers, lawyers, physicians will all learn to work with AI. You cannot put the genie back in the bottle. Only a totalitarian world government could try, and some of us would rather avoid that outcome.

Difficult proofs will now be built with AI, just as most code will be written with AI. People who insist on pen and paper should view themselves as artists.

Other mathematicians will work with AI. They will have no trouble finding interested kids. They will contribute to society.

2026-09-11 02:23:42

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.

Americans had a moral panic over alcohol that lasted more than a century. It began with pledges of moderation. From 1920 the Volstead Act banned nearly all legal drink. It collapsed in 1933, at great expense.

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 or pain. We ignore the warnings at our peril. It is one after the other: alcohol, the need to restrict the number of children, and so on.

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? AI and robotics might prove useful to reduce suffering, don’t we think?

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, please, do not include abstract thinking machines. A language model is a box that takes in token and produces tokens. Nothing more.

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.

2026-09-10 04:41:53

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' 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.

2026-09-05 22:02:12