Floats have 15-digit accuracy in their normal range
In programming languages like JavaScript or Python, numbers are typically represented using 64-bit IEEE number types (binary64). For these numbers, we have 15 digits of accuracy. It means that you can pick a 15-digit number, such as 1.23456789012345e100 and it can be represented exactly: there exists a floating-point number that has exactly these 15-most significant digits. In this particular case, it is the number 6355009312518497 * 2280. Having 15-digit of accuracy is excellent: few engineering processes can ever exceed this accuracy. This 15-digit accuracy fails for numbers that outside the valid range. For example, the number 1e500 is too large and cannot be directly represented using standard 64-bit floating-point numbers. Similarly, 1e-500 is too small and it can only be represented as zero. The range of 64-bit floating-point number might be defined as going from 4.94e-324 to 1.8e308 and -1.8e308 to -4.94e-324, together with exactly 0. However, this range includes subnormal numbers where the relative accuracy can be small. For example, the number 5.00000000000000e-324 is best represented as 4.94065645841247e-324, meaning that we have zero-digit accuracy. For the 15-digit accuracy rule…
https://lemire.me/blog/2022/04/13/floats-have-15-digit-accuracy-in-their-normal-range/
In programming languages like JavaScript or Python, numbers are typically represented using 64-bit IEEE number types (binary64). For these numbers, we have 15 digits of accuracy. It means that you can pick a 15-digit number, such as 1.23456789012345e100 and it can be represented exactly: there exists a floating-point number that has exactly these 15-most significant digits. In this particular case, it is the number 6355009312518497 * 2280. Having 15-digit of accuracy is excellent: few engineering processes can ever exceed this accuracy. This 15-digit accuracy fails for numbers that outside the valid range. For example, the number 1e500 is too large and cannot be directly represented using standard 64-bit floating-point numbers. Similarly, 1e-500 is too small and it can only be represented as zero. The range of 64-bit floating-point number might be defined as going from 4.94e-324 to 1.8e308 and -1.8e308 to -4.94e-324, together with exactly 0. However, this range includes subnormal numbers where the relative accuracy can be small. For example, the number 5.00000000000000e-324 is best represented as 4.94065645841247e-324, meaning that we have zero-digit accuracy. For the 15-digit accuracy rule…
https://lemire.me/blog/2022/04/13/floats-have-15-digit-accuracy-in-their-normal-range/
Daniel Lemire's blog
Floats have 15-digit accuracy in their normal range
In programming languages like JavaScript or Python, numbers are typically represented using 64-bit IEEE number types (binary64). For these numbers, we have 15 digits of accuracy. It means that you can pick a 15-digit number, such as 1.23456789012345e100 and…
An overview of version control in programming
In practice, computer code is constantly being transformed. At the beginning of a project, the computer code often takes the form of sketches that are gradually refined. Later, the code can be optimized or corrected, sometimes for many years. Soon enough, programmers realized that they needed to not only to store files, but also to keep track of the different versions of a given file. It is no accident that we are all familiar with the fact that software is often associated with versions. It is necessary to distinguish the different versions of the computer code in order to keep track of updates. We might think that after developing a new version of a software, the previous versions could be discarded. However, it is practical to keep a copy of each version of the computer code for several reasons: A change in the code that we thought was appropriate may cause problems: we need to be able to go back quickly. Sometimes different versions of the computer code are used at the same time and it is not possible for all…
https://lemire.me/blog/2022/04/21/an-overview-of-version-control-in-programming/
In practice, computer code is constantly being transformed. At the beginning of a project, the computer code often takes the form of sketches that are gradually refined. Later, the code can be optimized or corrected, sometimes for many years. Soon enough, programmers realized that they needed to not only to store files, but also to keep track of the different versions of a given file. It is no accident that we are all familiar with the fact that software is often associated with versions. It is necessary to distinguish the different versions of the computer code in order to keep track of updates. We might think that after developing a new version of a software, the previous versions could be discarded. However, it is practical to keep a copy of each version of the computer code for several reasons: A change in the code that we thought was appropriate may cause problems: we need to be able to go back quickly. Sometimes different versions of the computer code are used at the same time and it is not possible for all…
https://lemire.me/blog/2022/04/21/an-overview-of-version-control-in-programming/
Removing characters from strings faster with AVX-512
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 removal of all spaces from strings. At the time, I concluded that the fastest approach might be to use SIMD instructions coupled with a large lookup table. A SIMD instruction is such that it can operate on many words at any given time: most commodity processors have instructions able to operate on 16 bytes at a time. Thus, using a single instruction, you can compare 16 consecutive bytes and identify the location of all spaces, for example. Once it is done, you must somehow move the unwanted characters. Most instruction sets do not have instructions for that purpose, however x64 processors have an instruction that can move bytes around as long as you have a precomputed shuffle mask (pshufb). ARM NEON has similar instructions as…
https://lemire.me/blog/2022/04/28/removing-characters-from-strings-faster-with-avx-512/
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 removal of all spaces from strings. At the time, I concluded that the fastest approach might be to use SIMD instructions coupled with a large lookup table. A SIMD instruction is such that it can operate on many words at any given time: most commodity processors have instructions able to operate on 16 bytes at a time. Thus, using a single instruction, you can compare 16 consecutive bytes and identify the location of all spaces, for example. Once it is done, you must somehow move the unwanted characters. Most instruction sets do not have instructions for that purpose, however x64 processors have an instruction that can move bytes around as long as you have a precomputed shuffle mask (pshufb). ARM NEON has similar instructions as…
https://lemire.me/blog/2022/04/28/removing-characters-from-strings-faster-with-avx-512/
Fast bitset decoding using Intel AVX-512
In software, we often use ‘bitsets’: you work with arrays of bits to represent sets of small integers. It is a concise and fast data structure. Sometimes you want to go from the bitset (e.g., 0b110011) to the integers (e.g., 0, 1, 4, 5 in this instance). We consider with ‘average’ density (e.g., more than a handful of bits set per 64-bit word). You could check the value of each bit, but a better option is to use the fact that processors have fast instructions to compute the number of “trailing zeros”. Given 0b10001100100, this instruction would give you 2. This gives you the first index. Then you need to unset this least significant bit using code such as word & (word - 1). while (word != 0) { result[i] = trailingzeroes(word); word = word & (word - 1); i++; } The problem with this code is that the number of iterations might be hard to predict, thus you might often cause your processor to mispredict the number of branches. A misprediction is expensive on modern processor. You can do better…
https://lemire.me/blog/2022/05/06/fast-bitset-decoding-using-intel-avx-512/
In software, we often use ‘bitsets’: you work with arrays of bits to represent sets of small integers. It is a concise and fast data structure. Sometimes you want to go from the bitset (e.g., 0b110011) to the integers (e.g., 0, 1, 4, 5 in this instance). We consider with ‘average’ density (e.g., more than a handful of bits set per 64-bit word). You could check the value of each bit, but a better option is to use the fact that processors have fast instructions to compute the number of “trailing zeros”. Given 0b10001100100, this instruction would give you 2. This gives you the first index. Then you need to unset this least significant bit using code such as word & (word - 1). while (word != 0) { result[i] = trailingzeroes(word); word = word & (word - 1); i++; } The problem with this code is that the number of iterations might be hard to predict, thus you might often cause your processor to mispredict the number of branches. A misprediction is expensive on modern processor. You can do better…
https://lemire.me/blog/2022/05/06/fast-bitset-decoding-using-intel-avx-512/
Daniel Lemire's blog
Fast bitset decoding using Intel AVX-512
In software, we often use 'bitsets': you work with arrays of bits to represent sets of small integers. It is a concise and fast data structure. Sometimes you want to go from the bitset (e.g., 0b110011) to the integers (e.g., 0, 1, 5, 6 in this instance).…
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/
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/
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/
Daniel Lemire's blog
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…
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/
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/
Daniel Lemire's blog
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…
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/
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/
Daniel Lemire's blog
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…
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/
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/
Daniel Lemire's blog
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…
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/
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/
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/
Daniel Lemire's blog
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…
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/
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/
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/
Daniel Lemire's blog
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…
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/
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/
Daniel Lemire's blog
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…
Often we need to convert between the two types. Both ARM and…
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/
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/
Daniel Lemire's blog
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…
Often we need to convert between the two types. Both ARM and…
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/
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/
Daniel Lemire's blog
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 face a major replication crisis…
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/
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/
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/
Daniel Lemire's blog
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…
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/
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/
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/
Daniel Lemire's blog
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…