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
People still tell me that CPUs are boring. That nothing much happens anymore. Let us look at AMD Ryzen 7 processors from 2022 to 2024: the 5800X3D (Zen 3), the 7800X3D (Zen 4) and the 9800X3D (Zen 5). They are comparable 8-core chips with 3D V-Cache. I have written about them before, in How stagnant … Continue reading…
When a program is mostly just accessing memory randomly, a standard cost model is to count the number of distinct random accesses. The general idea is that memory access is much slower than most other computational tasks. Furthermore, the cost model can be extended to count "nearby" memory accesses as free. That is…
One of the most common "data type" in programming is the text string. When programmers think of a string, they imagine that they are dealing with a list or an array of characters. It is often a "good enough" approximation, but reality is more complex. The characters must be encoded into bits in some way. Most ……
In my previous blog post, I compared the performance of my new ARM-based MacBook Pro with my 2017 Intel-based MacBook Pro. I used a number parsing benchmark. In some cases, the ARM-based MacBook Pro was nearly twice as fast as the older Intel-based MacBook Pro. I think that the Apple M1 processor is a breakthrough ……
In software, it is common to represent time as a time-stamp string. It is usually specified by a time format string. Some standards use the format %Y%m%d%H%M%S meaning that we print the year, the month, the day, the hours, the minutes and the seconds. The current time as I write this blog post would be … Continue…
Computers store data as streams of bits. Binary files like image, audio or video files are allowed to contain just about any sequence of bits. However, we also often use text formats; for example, web pages and emails are required to be text. So how do we send images by email? How do we embed … Continue reading…
Sometimes programmers want to prune out characters from a string of characters. For example, maybe you want to remove all line-ending characters from a piece of text. Let me consider the problem where I want to remove all spaces (' ') and linefeed characters ('\n' and '\r'). How would you do it efficiently? size_t…
Not all instructions on modern processors cost the same. Additions and subtractions are cheaper than multiplications which are themselves cheaper than divisions. For this reason, compilers frequently replace division instructions by multiplications. Roughly speaking, it works in this manner. Suppose that you want to…
Almost all our computers are made of several processing cores. Thus it can be efficient to "parallelize" expensive processing in a multicore manner. That is, instead of using a single core to do all of the work, you divide the work among multiple cores. A standard way to approach this problem is to create threads. ……
When benchmarking software, we often start by measuring the time elapsed. If you are benchmarking data bandwidth or latency, it is the right measure. However, if you are benchmarking computational tasks where you avoid disk and network accesses and where you only access a few pages of memory, then the time elapsed is…
Developers often believe that software performance follows a Pareto distribution: 80% of the running time is spent in 20% of the code. Using this model, you can write most of your code without any care for performance and focus on the narrow pieces of code that are performance sensitive. Engineers like Casey Muratori…
Note: This blog post from 2018 predates the Intel Ice Lake (Sunny Core) and AMD Zen 4 processors. These newer processors are not affected by the issues described in this blog post. Our processors typically do computations using small data stores called registers. On 64-bit processors, 64-bit registers are frequently…
Many recent Intel processors benefit from a new family of instructions called AVX-512. These instructions operate over wide registers (up to 512 bits) and follow the Single instruction, multiple data (SIMD) paradigm. These new AVX-512 instructions allow you to break some speed records, such as decoding base64 data at…
There are various ways in software to handle error conditions. In C or Go, one returns error code. Other programming languages like C++ or Java prefer to throw exceptions. One benefit of using exceptions is that it keeps your code mostly clean since the error-handling code is often separate. It is debatable whether…
Though most relational databases (like MySQL) are "row oriented", in that they keep rows stored together... experience has taught us that pivoting the data arrow so that columns, and not rows, are stored together can be beneficial. This is an old observation that most experienced programmers know about as the…
If I give a programmer a string such as "9223372036854775808" and I ask them to convert it to an integer, they might do the following in C++: std::string s = .... uint64_t val; auto [ptr, ec] = std::from_chars(s.data(), s.data() + s.size(), val); if (ec != std::errc()) {} // I have an error ! // val … Continue reading…
Whenever you enter a URL into a system, it must be parsed and validated. It is a surprisingly challenging task: it may require hundreds of nanoseconds and possibly over a thousand cycles to parse a typical URL. We can use URL parsing as a reasonable benchmark of a system performance. Of course, no single measure ……
Modern processors have powerful vector instructions which allow you to load several values at once, and operate (in one instruction) on all these values. Similarly, they allow you to have vector constants. Thus if you wanted to add some integer (say 10001) to all integers in a large array, you might first load a…
When receiving bytes from the network, we often assume that they are unicode strings, encoded using something called UTF-8. Sadly, not all streams of bytes are valid UTF-8. So we need to check the strings. It is probably a good idea to optimize this problem as much as possible. In earlier work, we showed that ……
In software, it is a common problem to want to remove specific characters from a string. To make the problem precise, let us consider the removal of all ASCII control characters and spaces. In practice, it means the removal of all byte values smaller or equal than 32. I covered a related problem before, the … Continue…
I wanted to know how a modern C compiler like clang would process the following C code: #include <stdint.h> int count(uint64_t x) { int v = 0; while(x != 0) { x &= x - 1; v++; } return v; } Can you guess? popcntq %rdi, %rax That is right. A fairly sophisticated C function, … Continue reading The surprising cleverness…
Twitter user opdroid1234 remarked that they are getting more performance out of the ARM nodes than out of the Intel nodes on Amazon's cloud (AWS). I found previously that the Graviton 3 processors had less bandwidth than comparable Intel systems. However, I have not done much in terms of raw compute power. The Intel…
The division instruction is one of the most expensive instruction in your CPU. Thus optimizing compilers often compile divisions by known constants down to a multiplication followed by a shift. However, in some lucky cases, the compiler does not even need a shift. I call the corresponding divisors ideal. For the math…
Modern processors execute instructions in parallel in many different ways: multi-core parallelism is just one of them. In particular, processor cores can have several outstanding memory access requests "in flight". This is often described as "memory-level parallelism". You can measure the level of memory-level…
Most strings found on the Internet are encoded using a particular unicode format called UTF-8. However, not all strings of bytes are valid UTF-8. The rules as to what constitute a valid UTF-8 string are somewhat arcane. Yet it seems important to quickly validate these strings before you consume them. In a previous…
In many information systems, we work with arrays of integers. For example, maybe you need to keep track of which records in a database contain a given value. This sort of mapping can be expressed as an array of integers. These arrays can end up taking up a large fraction of your memory or disk … Continue reading…
Though most strings online today follow the Unicode standard (e.g., using UTF-8), the Latin 1 standard is still in widespread inside some systems (such as browsers) as JavaScript strings are often stored as either Latin 1, UTF-8 or UTF-16 internally. Latin 1 captures the first 256 characters from the Unicode standard…
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…
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…
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…