Daniel Lemire is a software performance expert. He ranks among the top 2% of scientists globally (Stanford/Elsevier 2025) and is one of GitHub's top 1000 most followed developers.
Visit lemire.me → RSS feedOn Hacker News May 2014 – Sep 2026
Software Engineering 47Systems & Performance 40Math & Algorithms 14Hardware & Electronics 14Society, Policy & Culture 12Tech Industry & Business 8
The ubiquitous IEEE floating-point standard defines two numbers to represent zero, the positive and the negative zeros. You also have the positive and negative infinity. If you compute the inverse of the positive zero, you get the positive infinity. If you compute the inverse of the negative zero, you get the negative…
When programming, we often have to 'escape' strings. A standard way to do it is to insert the backslash character (\) before some characters such as the double quote. For example, the string my title is "La vie" becomes my title is \"La vie\" A simple routine in C++ to escape a string might look … Continue reading…
Most C++ programmers rely on "STL" for their data structures. The most popular data structure is probably vector, which is just a dynamic array. The set and the map are other useful ones. The STL data structures are a minimalist design. You have relatively few methods. All of them allow you to compute the size ……
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 benchmarking difficult…
We learned recently of the suicide of Stefan Grimm, a successful professor at the prestigious Imperial College in London. Professors Grimm regularly published highly cited articles in the best journals. He was highly productive. Unfortunately, some of his colleagues felt that he did not secure sufficiently large…
There is a widely reported threat to our economy: robots are going to replace human workers. It is nothing new... In 1930, Keynes, the famous economist introduced the term "technological unemployment"... We are being afflicted with a new disease of which some readers may not yet have heard the name, but of which they…
In my previous post, I reviewed a new fast random number generator called wyhash. I commented that I expected it to do well on x64 processors (Intel and AMD), but not so well on ARM processors. Let us review again wyhash: uint64_t wyhash64_x; uint64_t wyhash64() { wyhash64_x += 0x60bee2bee120fc15; __uint128_t tmp; tmp…
Modern processors are superscalar, meaning that they can execute many instructions at once. For example, some processors can retire four or six instructions per cycle. Furthermore, many of these processors can initiate instructions out-of-order: they can start working on instructions that appear much later in the…
Suppose you want to pick an integer at random in a set of N elements. Your computer has functions to generate random 32-bit integers, how do you transform such numbers into indexes no larger than N? Suppose you have a hash table with a capacity N. Again, you need to transform your hash values (typically 32-bit ……
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 ……
In most systems, integers are stored using a fixed binary representation. It is common to store integers using 32-bit or 64-bit words. You sometimes need to convert it to a string. For example, the integer 12345 might need to be converted to the five characters '12345'. In an earlier blog post, I presented the simpler…
Many of us rely on a Qwerty keyboard, at least when we are typing at a laptop. It is often said that the Qwerty keyboard is inferior to clearly better alternatives like the Dvorak keyboard. However, this appears to be largely a myth backed by dubious science. There is the similarly often repeated story of … Continue…
At a fundamental level, a programmer needs to manipulate bits. Modern processors operate over data by loading in 'registers' and not individual bits. Thus a programmer must know how to manipulate the bits within a register. Generally, we can do so while programming with 8-bit, 16-bit, 32-bit and 64-bit integers. For…
Most systems today rely on Unicode strings. However, we have two popular Unicode formats: UTF-8 and UTF-16. We often need to convert from one format to the other. For example, you might have a database formatted with UTF-16, but you need to produce JSON documents using UTF-8. This conversion is often called…
In software, we generate random numbers by calling a function called a "random number generator". Such functions have hidden states, so that repeated calls to the function generate new numbers that appear random. If you know this state, you can predict all future outcomes of the random number generators. O'Neill, a…
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…
In C, the length of a string in marked by a 0 byte at the end of the string. Thus to determine the length of the string, one must scan it, looking for the 0 byte. Recent ARM processors have a powerful instruction set (SVE) that is well suited for such problems. It allows you … Continue reading Implementing ‘strlen’…
You sometimes feel the need to make all of your integers positive, without losing any information. That is, you want to map all of your integers from 'signed' integers (e.g., -1, 1, 3, -3) to 'unsigned integers' (e.g., 3,2,6,7). This could be useful if you have a fast function to compress integers that fails to ……
The performance of a processor is determined by several factors. For example, processors with a higher frequency tend to do more work per unit of time. Physics makes it difficult to produce processors that have higher frequency. Modern processors can execute many instructions per cycle. Thus a 3.4GHz processor has 3.4…
The C++ library has long been organized around stream classes, at least when it comes to reading and parsing strings. But streams can be surprisingly slow. For example, if you want to parse numbers, then this C++ routine is close to being the worst possible choice for performance: std::stringstream in(mystring)…
Our most important goal in writing software is that it be correct. The software must do what the programmer wants it to do. It must meet the needs of the user. In the business world, double-entry bookkeeping is the idea that transactions are recorded in at least two accounts (debit and credit). One of the … Continue…
Computers often need random numbers. Most times, random numbers are not actually random... in the sense that they are the output of a mathematical function that is purely deterministic. And it is not even entirely clear what "really random" would mean. It is not clear that we live in a randomized universe... it seems…
We often have to write code using permissive programming languages like C and C++. They tend to generate hard-to-debug problems that can crash your applications. Thankfully, many compilers offer "sanitizers". I discussed them in my post No more leaks with sanitize flags in gcc and clang. I strongly encourage the use…
Integers in programming languages have a valid range but arithmetic operations can result in values that exceed such ranges. For example, adding two large integers can result in an integer that cannot be represented in the integer type. We often refer to such error conditions as overflows. In a programming languages…
I my previous blog post, I documented how one might proceed to compute the number of digits of an integer quickly. E.g., given the integer 999, you want 3 but given the integer 1000, you want 4. It is effectively the integer logarithm in base 10. On computers, you can quickly compute the integer logarithm … Continue…
Up to yesterday, my laptop was a large 15-inch MacBook Pro. It contains an Intel Kaby Lake processor (3.8 GHz). I just got a brand-new 13-inch 2020 MacBook Pro with Apple's M1 ARM chip (3.2 GHz). How do they compare? I like precise data points. Recently, I have been busy benchmarking number parsing routines where you…
Suppose that I give you a relatively long string and you want to remove all spaces from it. In ASCII, we can define spaces as the space character (' '), and the line ending characters ('\r' and '\n'). I am mostly interested in algorithmic and performance issues, so we can simplify the problem by removing all ……