@daniel-lemire
Publisher
42
Posts
A few years ago, a friend of mine was stuck. He needed to quickly process over a hundred high-quality images according to a complicated sequence. He was using Photoshop, but it was going to take him days. Initially, he asked for my help, could I do the manual labor? I spent 15 minutes writing a …...
I have been on X for a long time. Like most people who post regularly, I have a gut feeling for what might interest people. I post in the morning. Longer posts seem to do better. But gut feelings are not measurements. And until recently, digging into your own posting data meant either clicking ar...
When I was a kid, most people did not know how to type. We took typing class. The final exam was a speed test: words per minute. Today, you will not impress anyone by saying you can type. In fact, cursive writing is fading. Kids increasingly cannot read or write it. We type constantly. We … Conti...
Suppose that you have a configuration file in JSON. Something like this: { "width": 1920, "height": 1080, "fullscreen": true, "title": "My Game", "volume": 0.8 } Normally you ship this file alongside your program, open it at startup, read it, and parse it. That is a lot of work for data that neve...
The keyword in politics these days is ‘sovereign’. What few will admit is that it is effectively the adoption of the American strategy: Make America Great Again. In other words, reindustrialization of key sectors of the economy. The UK used to be a computing champion. Our chip designs (ARM) origi...
Our 64-bit Intel and AMD processors have evolved over decades. When you compile a Go program for a 64-bit Intel or AMD processor, the compiler targets, by default, a nearly 20-year-old instruction set. The binary that comes out runs on essentially any x64 chip, but it also leaves on the table eve...
Where is your intelligence located? In your brain? It is a simplistic answer. A better model is that your intelligence is embodied. Consider a cook working at an expensive restaurant. He has all his favorite knives and cooking instructions, placed exactly where he wants them. His kitchen is part...
Every machine connected to the Internet has an address called an IP address. Originally, these addresses were 32-bit integers (IPv4), giving a theoretical maximum of about four billion distinct addresses. We are all familiar with these addresses (e.g., 192.168.0.0). There was a big fuss about how...
In software programming, the product between two integers is often computed to a fixed number of bits with overflow. Consider 8-bit integers. If you multiply 127 by 127, you get back the number 1 as an 8-bit unsigned integer, with an overflow. The actual full product is 16129. To represent 16129,...
Converting a 64-bit integer to its decimal string representation is a mundane task that shows up everywhere: logging, JSON serialization, CSV output, debug prints, etc. In C++, you might use std::to_chars, sprintf, or some library routine. How do these functions work? At a high level, they repeat...
Suppose that x is a variable of an unsigned type. In C/C++, it could be of type size_t for example. You have an expression like 6 * x and you want to know whether 6 * x overflows. That is, you want to know if 6 * x exceeds the range of values that can … Continue reading Checking multiplication ov...
A common pattern in modern software is to map a string key to a small array of floating-point numbers. Word embeddings, feature vectors, lookup tables for physical constants: all variations on the same theme. In Go, the obvious way to write this is a map[string][]float32. But how fast is it, real...
No, rising house prices are not the driver of sharp fertility declines. The evidence shows only modest, mixed effects that cannot explain the large drops observed in places like Canada. What the Research Actually Shows: A well-known study by Dettling and Kearney (2014) found that rising house pri...
We sometimes have to look for a value in a sorted array. The simplest algorithm consists in just going through the values one by one, until we encounter the value, or exhaust the array. We sometimes call this algorithm a linear search. In C++, you can get the desired effect with the std::find fun...
Consider the following problem. Given a string, you must match all of the ASCII white-space characters (\t, \n, \r, and the space) and some characters important in JSON (:, ,, [, ], {, }). JSON is a text-based data format used for web services. A toy JSON document looks as follows. { "name": "Ali...
Initially, we had languages like Fortran (1957), Pascal (1970), and C (1972). Fortran was designed for number crunching and scientific computing. Pascal was restrictive with respect to low-level access (it was deliberately "safe", as meant for teaching structured programming). So C won out as a l...
Suppose you have several strings and you want to count the number of instances of the character ! in your strings. In C++, you might solve the problem as follows if you are an old-school programmer. size_t c = 0; for (const auto &str : strings) { c += std::count(str.begin(), str.end(), '!'); } Yo...
Consider the following problem. You have a large set of strings, maybe millions. You need to map these strings to 8-byte integers (uint64). These integers are given to you. If you are working in Go, the standard solution is to create a map. The construction is trivial, something like the followin...
The next C++ standard (C++26) is getting exciting new features. One of these features is compile-time reflection. It is ideally suited to serialize and deserialize data at high speed. To test it out, we extended our fast JSON library (simdjson) and we gave a talk at CppCon 2025. The video is out...
Modern processors have the ability to execute many instructions per cycle, on a single core. To be able to execute many instructions per cycle in practice, processors predict branches. I have made the point over the years that modern CPUs have an incredible ability to predict branches. It makes b...
Suppose that you have a record of your sales per day. You might want to get a running record where, for each day, you are told how many sales you have made since the start of the year. day sales per day running sales 1 10$ 10 $ 2 15$ 25 $ 3 5$ 30 … Continue reading Prefix sums at tens of gigabyte...
The Internet relies on text formats. Thus, we spend a lot of time producing and consuming data encoded in text. Your web pages are HTML. The code running in them is JavaScript, sent as text (JavaScript source), not as already-parsed code. Your emails, including their attachments, are sent as text...
We locate web content using special addresses called URLs. We are all familiar with addresses like https://google.com. Sometimes, URLs can get long and they can become difficult to read. Thus, we might be tempted to format them like so in HTML using newline and tab characters, like so: <a href="h...
JavaScript represents strings using Unicode, like most programming languages today. Each character in a JavaScript string is stored using one or two 16-bit words. The following JavaScript code might surprise some programmers because a single character becomes two 16-bit words. > t="🧰" '🧰' > t.l...
When programming, we need to allocate memory, and then deallocate it. If you program in C, you get used to malloc/free functions. Sadly, this leaves you vulnerable to memory leaks: unrecovered memory. Most popular programming languages today use automated memory management: Java, JavaScript, Pyth...
Much of the West has been economically stagnant. Countries like Canada have failed to improve their productivity and standard of living as of late. In Canada, there has been no progress in Canadian living standards as measured by per-person GDP over the past five years. It is hard to overstate ho...
When programming, we chain functions together. Function A calls function B. And so forth. You do not have to program this way, you could write an entire program using a single function. It would be a fun exercise to write a non-trivial program using a single function... as long as you delegate th...
Given any string of bytes, you can convert it to an hexadecimal string by mapping the least significant and the most significant 4 bits of byte to characters in 01...9A...F. There are more efficient techniques like base64, that map 3 bytes to 4 characters. However, hexadecimal outputs are easier...
When serializing data to JSON, CSV or when logging, we convert numbers to strings. Floating-point numbers are stored in binary, but we need them as decimal strings. The first formally published algorithm is Steele and White's Dragon schemes (specifically Dragin2) in 1990. Since then, faster metho...
One of the first steps we take when we want to optimize software is to look at profiling data. Software profilers are tools that try to identify where your software spends its time. Though the exact approach can vary, a typical profiler samples your software (steps it at regular intervals) and co...
Irrespective of your programming language of choice, calling C functions is often a necessity. For the longest time, the only standard way to call C was the Java Native Interface (JNI). But it was so painful that few dared to do it. I have heard it said that it was deliberately painful so that pe...
Sometimes, people tell me that there is no more progress in CPU performance. Consider these three processors which had comparable prices at release time. The AMD Ryzen 7 9800X3D (Zen 5, with up to 5.3 GHz boost) was released in 2024. The AMD Ryzen 7 7800X3D (Zen 4, with up to 5.1 GHz boost) was …...
When I was younger, in my 20s, I assumed that everyone was working "hard," meaning a solid 35 hours of work a week. Especially, say, university professors and professional engineers. I'd feel terribly guilty when I would be messing around, playing video games on a workday. Today I realize that mo...
Galileo Galilei was the OpenAI of his time. He helped establish modern science by emphasizing experimentation as the primary means to uncover natural truths. To this end, he built his own telescopes. He revealed to the world the moons of Jupiter, thereby changing forever how we viewed the cosmos....
We are experiencing one of the most significant technological breakthroughs of the last few decades. Call it what you will: AI, generative AI, large language models... But where does it come from? Academics will tell you that it stems from decades of mathematical efforts on campus. But think abou...
Culture wars are real. They occur when a dominant culture faces a serious challenge. But unless you pay close attention, you might miss them entirely. As a kid, I was a “nerd.” I read a lot and spent hours on my computer. I devoured science and technology magazines. I taught myself programming. “...
How much virtual memory does the following C++ expression allocate on the heap? new char[4096] The answer is at least 4 kibibytes but surely more. Firstly, each heap memory allocation requires some memory to keep track of what has been allocated. You are likely using 8 bytes or so of overhead tha...
Many people say that they crave more freedom. But what do we mean by “freedom”? Being free from constraints? Is that what we mean? Would you feel “freer” if you could walk outside in your underwear? It is almost surely not what you mean by “freedom.” I submit to you that it is almost always … Con...
I used to always want to rewrite my code. Maybe even use another programming language. « If only I could rewrite my code, it would be so much better now. » If you maintain software projects, you see it all the time. Someone new comes along and they want to start rewriting everything. They always...
Most programmers are familiar with IP addresses. They take the form of four numbers between 0 and 255 separated by dots: 192.168.0.1. In some sense, it is a convoluted way to represent a 32-bit integer. The modern version of an IP address is IPv6 which is usually surrounded by square brackets. It...
Strings in programming are often represented as arrays of 8-bit words. The string is ASCII if and only if all 8-bit words have their most significant bit unset. In other words, the byte values must be no larger than 127 (or 0x7F in hexadecimal). A decent C function to check that the string is ASC...
Much of the data on the Internet is shared using a simple format called JSON. JSON is made of two composite types (arrays and key-value maps) and a small number of primitive types (64-bit floating-point numbers, strings, null, Booleans). That JSON became ubiquitous despite its simplicity is telli...
