Faster bitset decoding using Intel AVX-512

I refer to “bitset decoding” as the action of finding the positions of the 1s in a stream of bits. For example, given the integer value 0b11011 (or 27 in decimal),  I want to find 0,1,3,4. In my previous post, Fast bitset decoding using Intel AVX-512, I explained how you can use Intel’s new instructions, from the AVX-512 family, to decode bitsets faster. The AVX-512 instructions, as the name implies, often can process 512-bit (or 64-byte) registers. At least two readers (Kim Walisch and Jatin Bhateja) pointed out that you could do better if you used the very latest AVX-512 instructions available on Intel processors with the Ice Lake or Tiger Lake microarchitectures. These processors support VBMI2 instructions including the vpcompressb instruction and its corresponding intrinsics (such as _mm512_maskz_compress_epi8). What this instruction does is take a 64-bit word and a 64-byte register, and it outputs (in packed manner) only the bytes corresponding to set bits in the 64-bit word. Thus if you use as the 64-bit word the value 0b11011 and you provide a 64-byte register with the values 0,1,2,3,4……

https://lemire.me/blog/2022/05/10/faster-bitset-decoding-using-intel-avx-512/

Avoid exception throwing in performance-sensitive code

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 handling exceptions is better than dealing with error codes. I will happily use one or the other. What I will object to, however, is the use of exceptions for control flow. It is fine to throw an exception when a file cannot be opened, unexpectedly. But you should not use exceptions to branch on the type of a value. Let me illustrate. Suppose that my code expects integers to be always positive. I might then have a function that checks such a condition: int get_positive_value(int x) { if(x < 0) { throw std::runtime_error("it is not positive!"); } return x; } So far, so good. I am assuming that the exception is normally never thrown. It gets thrown if I have some kind of error. If I want…

https://lemire.me/blog/2022/05/13/avoid-exception-throwing-in-performance-sensitive-code/

Parsing JSON faster with Intel AVX-512

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 the speed of a memory copy. Most modern processors have SIMD instructions. The AVX-512 instructions are wider (more bits per register), but that is not necessarily their main appeal. If you merely take existing SIMD algorithms and apply them to AVX-512, you will probably not benefit as much as you would like. It is true that wider registers are beneficial, but in superscalar processors (processors that can issue several instructions per cycle), the number of instructions you can issue per cycle matters as much if not more. Typically, 512-bit AVX-512 instructions are more expensive and the processor can issue fewer of them per cycle. To fully benefit from AVX-512, you need to carefully design your code. It is made more challenging by the fact that Intel is releasing these instructions progressively: the…

https://lemire.me/blog/2022/05/25/parsing-json-faster-with-intel-avx-512/

Data structure size and cache-line accesses

On many systems, memory is accessed in fixed blocks called “cache lines”. On Intel systems, the cache line spans 64 bytes. That is, if you access memory at byte address 64, 65… up to 127… it is all on the same cache line. The next cache line starts at address 128, and so forth. In turn, data in software is often organized in data structures having a fixed size (in bytes). We often organize these data structures in arrays. In general, a data structure may reside on more than one cache line. For example, if I put a 5-byte data structure at byte address 127, then it will occupy the last byte of one cache line, and four bytes in the next cache line. When loading a data structure from memory, a naive model of the cost is the number of cache lines that are accessed. If your data structure spans 32 bytes or 64 bytes, and you have aligned the first element of an array, then you only ever need to access one cache line every time you load a…

https://lemire.me/blog/2022/06/06/data-structure-size-and-cache-line-accesses/

Memory-level parallelism : Intel Ice Lake versus Amazon Graviton 3

One of the most expensive operation in a processor and memory system is a random memory access. If you try to read a value in memory, it can take tens of nanosecond on average or more. If you are waiting on the memory content for further action, your processor is effectively stalled. While our processors are generally faster, the memory latency has not improved quickly and the latency can even be higher on some of the most expensive processors. For this reason, a modern processor core can issue multiple memory requests at a given time. That is, the processor tries to load one memory element, keeps going, and can issue another load (even though the previous load is not completed), and so forth. Not long ago, Intel processor cores could support about 10 independent memory requests at a time. I benchmarked some small ARM cores that could barely issue 4 memory requests. Today, the story is much nicer. The powerful processor cores can all sustain many memory requests. They support better memory-level parallelism. To measure the performance of the processor,…

https://lemire.me/blog/2022/06/07/memory-level-parallelism-intel-ice-lake-versus-amazon-graviton-3/

Filtering numbers quickly with SVE on Amazon Graviton 3 processors

I have had access to Amazon’s latest ARM processors (graviton 3) for a few weeks. To my knowledge, these are the first widely available processors supporting Scalable Vector Extension (SVE). SVE is part of the Single Instruction/Multiple Data paradigm: a single instruction can operate on many values at once. Thus, for example, you may add N integers with N other integers using a single instruction. What is unique about SVE is that you work with vectors of values, but without knowing specifically how long the vectors are. This is in contrast with conventional SIMD instructions (ARM NEON, x64 SSE, AVX) where the size of the vector is hardcoded. Not only do you write your code without knowing the size of the vector, but even the compiler may not know. This means that the same binary executable could work over different blocks (vectors) of data, depending on the processor. The benefit of this approach is that your code might get magically much more efficient on new processors. It is a daring proposal. It is possible to write code that would work…

https://lemire.me/blog/2022/06/23/filtering-numbers-quickly-with-sve-on-amazon-graviton-3-processors/

Looking at assembly code with gdb

Most of us write code using higher level languages (Go, C++), but if you want to understand the code that matters to your processor, you need to look at the ‘assembly’ version of your code. Assembly is a just a series of instructions. At first, assembly code looks daunting, and I discourage you from writing sizeable programs in assembly. However, with little training, you can learn to count instructions and spot branches. It can help you gain a deeper insight into how your program works. To assess the performance of a code routine, my first line of attack is always to count instructions. Keeping everything the same, if you can rewrite your code so that it generates fewer instructions, it should be faster. I also like to spot conditional jumps because that is often where your code can suffer, if the branch is hard to predict. Under Linux, the standard ‘debugger’ (gdb) is a great tool to look at the assembly code produced by the compile. Let us consider my previous blog post, Filtering numbers quickly with SVE on Amazon Graviton…

https://lemire.me/blog/2022/06/28/looking-at-assembly-code-with-gdb/

Go generics are not bad

When programming, we often need to write ‘generic’ functions where the exact data type is not important. For example, you might want to write a simple function that sums up numbers. Go lacked this notion until recently, but it was recently added (as of version 1.18). So I took it out for a spin. In Java, generics work well enough as long as you need “generic” containers (arrays, maps), and as long as stick with functional idioms. But Java will not let me code the way I would prefer. Here is how I would write a function that sums up numbers: int sum(int[] v) { int summer = 0; for(int k = 0; k < v.length; k++) { summer += v[k]; } return summer; } What if I need to support various number types? Then I would like to write the following generic function, but Java won’t let me. // this Java code won't compile static T sum(T[] v) { T summer = 0; for(int k = 0; k < v.length; k++) { summer += v[k]; }…

https://lemire.me/blog/2022/07/08/go-generics-are-not-bad/

Filtering numbers faster with SVE on Graviton 3 processors

Processors come, roughly, in two large families x64 processors from Intel and AMD, and ARM processors from Apple, Samsung, and many other vendors. For a long time, ARM processors occupied mostly the market of embedded processors (the computer running your fridge at home) with the ‘big processors’ being almost exclusively the domain of x64 processors. Reportedly, the Apple CEO (Steve Jobs) went to see Intel back when Apple was designing the iPhone to ask for a processor deal. Intel turned Apple down. So Apple went with ARM. Today, we use ARM processors for everything: game consoles (Nintendo Switch), powerful servers (Amazon and Google), mobile phones, embedded devices, and so forth. Amazon makes available its new ARM-based processors (Graviton 3). These processors have sophisticated SIMD instructions (SIMD stands for Single Instruction Multiple Data) called SVE (Scalable Vector Extensions). With these instructions, we can greatly accelerate software. It is a form of single-core parallelism, as opposed to the parallelism that one gets by using multiple cores for one task. The SIMD parallelism, when it is applicable, is often far more efficient than…

https://lemire.me/blog/2022/07/14/filtering-numbers-faster-with-sve-on-amazon-graviton-3-processors/

How quickly can you convert floats to doubles (and back)?

Many programming languages have two binary floating-point types: float (32-bit) and double (64-bit). It reflects the fact that most general-purpose processors supports both data types natively. Often we need to convert between the two types. Both ARM and x64 processors can do in one inexpensive instructions. For example, ARM systems may use the fcvt instruction. The details may differ, but most current processors can convert one number (from float to double, or from double to float) per CPU cycle. The latency is small (e.g., 3 or 4 cycles). Thus if you have many numbers to convert, then the cost is small. A typical processor might run at 3 GHz, thus we have 3 billion cycles per second. Thus we can convert 3 billion numbers per second. A 64-bit number uses 8 bytes, so it is a throughput of 24 bytes per second. It is therefore unlikely that the type conversion can be a performance bottleneck, in general. If you would like to measure the speed on your own system: I have written a small C++ benchmark.

https://lemire.me/blog/2022/07/20/how-quickly-can-you-convert-floats-to-doubles-and-back/

How quickly can you convert floats to doubles (and back)?

Many programming languages have two binary floating-point types: float (32-bit) and double (64-bit). It reflects the fact that most general-purpose processors supports both data types natively. Often we need to convert between the two types. Both ARM and x64 processors can do in one inexpensive instructions. For example, ARM systems may use the fcvt instruction. The details may differ, but most current processors can convert one number (from float to double, or from double to float) per CPU cycle. The latency is small (e.g., 3 or 4 cycles). A typical processor might run at 3 GHz, thus we have 3 billion cycles per second. Thus we can convert 3 billion numbers per second. A 64-bit number uses 8 bytes, so it is a throughput of 24 bytes per second. It is therefore unlikely that the type conversion can be a performance bottleneck, in general. If you would like to measure the speed on your own system: I have written a small C++ benchmark.

https://lemire.me/blog/2022/07/20/how-quickly-can-you-convert-floats-to-doubles-and-back/

Negative incentives in academic research

In the first half of the XXth century, there were relatively few scientists, and these scientists were generally not lavishly funded. Yet it has been convincingly argued that these scientists were massively more productive. We have entered a ‘dark age’ where we are mostly stagnant. It is not that there is no progress per se, but progress is slow, uncommon and expensive. Why might that be? I believe that it has to do with important ‘negative incentives’ that we have introduced. In effect, we have made scientists less productive. We probably did so through several means, but two effects are probably important: the widespread introduction of research competitions and the addition of extrinsic motivations.  Prior to 1960, there was hardly any formal research funding competitions. Today, by some estimates, it takes about 40 working days to prepare a single grant application, and the success rates is often low which means that for a single successful research grant, hundreds of days might have been spent, purely on the acquisition of funding. This effect is known in economics as rent dissipation. Suppose…

https://lemire.me/blog/2022/07/21/negative-incentives-in-academic-research/

Science and Technology links (July 23rd 2022)

Compared to 1800, we eat less saturated fat and much more processed food and vegetable oils and it does not seem to be good for us: Saturated fats from animal sources declined while polyunsaturated fats from vegetable oils rose. Non-communicable diseases (NCDs) rose over the twentieth century in parallel with increased consumption of processed foods, including sugar, refined flour and rice, and vegetable oils. Saturated fats from animal sources were inversely correlated with the prevalence of non-communicable diseases. Kang et al. found that saturated fats reduce your risk of having a stroke: a higher consumption of dietary saturated fat is associated with a lower risk of stroke, and every 10 g/day increase in saturated fat intake is associated with a 6% relative risk reduction in the rate of stroke. Saturated fats come from meat and dairy products (e.g., butter). A low-fat diet can significantly increase the risk of coronary heart disease events. Leroy and Cofnas argues against a reduction of red meat consumption: The IARC’s (2015) claim that red meat is “probably carcinogenic” has never been substantiated. In fact, a…

https://lemire.me/blog/2022/07/21/science-and-techno/

Round a direction vector to an 8-way compass

Modern game controllers can point in a wide range of directions. Game designers sometimes want to convert the joystick direction to get 8-directional movement. A typical solution offered is to compute the angle, round it up and then compute back the direction vector. double angle = atan2(y, x); angle = (int(round(4 * angle / PI + 8)) % 8) * PI / 4; xout = cos(angle); yout = sin(angle); If you assume that the direction vector is in the first quadrant (both x and y are positive), then there is a direct way to compute the solution. Using 1/sqrt(2) or 0.7071 as the default solution, compare both x and y with cos(3*pi/8) and cos(pi/8), and only switch them to 1 or 0 if they are larger than cos(3*pi/8) or smaller than cos(pi/8). The full code looks as follows: xout = 0.7071067811865475; yout = 0.7071067811865475; if (x >= 0.923879532511286) {// cos(3*pi/8) xout = 1; } if (y >= 0.923879532511286) {// cos(3*pi/8) yout = 1; } if (x < 0.3826834323650898) {// cos(pi/8) xout = 0; } if (y < 0.3826834323650898) {// cos(pi/8) yout…

https://lemire.me/blog/2022/07/24/round-a-direction-vector-to-the-nearest-8-way-compass/

Comparing strtod with from_chars (GCC 12)

A reader (Richard Ebeling) invited me to revisit an older blog post: Parsing floats in C++: benchmarking strtod vs. from_chars. Back then I reported that switching from strtod to from_chars in C++ to parse numbers could lead to a speed increase (by 20%). The code is much the same, we go from… char * string = "3.1416"; char * string_end = string; double x = strtod(string, &string_end); if(string_end == string) { //you have an error! } … to something more modern in C++17… std::string st = "3.1416"; double x; auto [p, ec] = std::from_chars(st.data(), st.data() + st.size(), x); if (p == st.data()) { //you have an errors! } Back when I first reported on this result, only Visual Studio had support for from_chars. The C++ library in GCC 12 now has full support for from_chars. Let us run the benchmark again: strtod 270 MB/s from_chars 1 GB/s So it is almost four times faster! The benchmark reads random values in the [0,1] interval. Internally, GCC 12 adopted the fast_float library. Further reading: Number Parsing at a Gigabyte per Second, Software:…

https://lemire.me/blog/2022/07/27/comparing-strtod-with-from_chars-gcc-12/

Science and Technology links (August 7 2022)

Increase in computing performance explain up to 94% of the performance improvements in field such as weather prediction, protein folding, and oil exploration: information technology is a a driver of long-term performance improvement across society. If we stop improving our computing, the consequences could be dire. The coral cover of the Great Barrier Reef has reached its highest level since the Australian Institute of Marine Science (AIMS) began monitoring 36 years ago. Leading Alzheimer’s theory, the amyloid hypothesis, which motivated years of research, was built on fraud. The author of the fraud is professor Sylvain Lesné. His team appeared to have composed figures by piecing together parts of photos from different experiments. Effectively, they “photoshopped” their scientific papers. Not just one or two images, but at least 70. Note that all clinical trials of drugs developed (at high cost) on the amyloid hypothesis have failed. Meanwhile, competing theories and therapies have been sidelined by the compelling amyloid hypothesis. It will be interesting to watch what kind of penalty, if any, Lesné receives for his actions. You may read the testimonies…

https://lemire.me/blog/2022/08/07/science-and-technology-links-august-7-2022/

“Hello world” is slower in C++ than in C (Linux)

A simple C program might print ‘hello world’ on screen: #include #include int main() { printf("hello worldn"); return EXIT_SUCCESS; } You can write the equivalent in C++: #include #include int main() { std::cout

“Hello world” is slower in C++ than in C (Linux)

A simple C program might print ‘hello world’ on screen: #include #include int main() { printf("hello worldn"); return EXIT_SUCCESS; } You can write the equivalent in C++: #include #include int main() { std::cout

Catching sanitizer errors programmatically

The C and C++ languages offer little protection against programmer errors. Errors do not always show up where you expect. You can silently corrupt the content of your memory. It can make bugs difficult to track. To solve this problem, I am a big fan of programming in C and C++ using sanitizers. They slow your program, but the check that memory accesses are safe, for example. Thus if you iterate over an array and access elements that are out of bounds, a memory sanitizer will immediately catch the error: int array[8]; for(int k = 0;; k++) { array[k] = 0; } The sanitizer reports the error, but what if you would like to catch the error and store it in some log? Thankfully, GCC and LLVM sanitizers call a function (__asan_on_error()) when when an error is encounter, allowing us to log it. Of course, you need to record the state of your program. The following is an example where the state is recorded in a string. #include #include #include std::string message; extern "C" { void __asan_on_error() {…

https://lemire.me/blog/2022/08/20/catching-sanitizer-errors-programmatically/

A standard dataset in artificial-intelligence research has ten percent of its images mislabeled. Yet state-of-the-art algorithms achieve better-than-90% classification on the same dataset. (Credit: Leo Boytsov) Despite the reeducation camps and the massive trauma, families that did well before the Chinese socialist revolution are still doing well. In other words, it is difficult and maybe impossible to do away with the competitiveness of some families. Exercise appears to enhance the hippocampus (in mice) so that exercise might enhance spatial learning. Lead is a toxic substance that might accounted for a significant fraction of violent crimes. The more careful use of lead explains in part the reduction in violent crimes over time. Watching a video at 2x the speed can double your learning speed. A man who received a heart transplant from a pig died two months later. Mental speed does not decrease with age as we expected: no mental speed decline is observed before the age of 60. Marmots appear not to age while they are hibernating. It is often stated that twins raised apart have a striking similarity in…

https://lemire.me/blog/2022/09/12/19908/

Science and Technology links (September 12 2022)

A standard dataset in artificial-intelligence research has ten percent of its images mislabeled. Yet state-of-the-art algorithms achieve better-than-90% classification on the same dataset. (Credit: Leo Boytsov) Despite the reeducation camps and the massive trauma, families that did well before the Chinese socialist revolution are still doing well. In other words, it is difficult and maybe impossible to do away with the competitiveness of some families. Exercise appears to enhance the hippocampus (in mice) so that exercise might enhance spatial learning. Lead is a toxic substance that might accounted for a significant fraction of violent crimes. The more careful use of lead explains in part the reduction in violent crimes over time. Watching a video at 2x the speed can double your learning speed. A man who received a heart transplant from a pig died two months later. Mental speed does not decrease with age as we expected: no mental speed decline is observed before the age of 60. Marmots appear not to age while they are hibernating. It is often stated that twins raised apart have a striking similarity in…

https://lemire.me/blog/2022/09/12/science-techno-links/