Making all your integers positive with zigzag encoding

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 work well for negative integers. Many programming languages (Go, C, etc.) allow you just ‘cast’ the integer. For example, the following Go code will print out -1, 18446744073709551615, -1 under most systems: var x = -1 var y = uint(x) var z = int(y) fmt.Println(x, y, z) That is, you can take a small negative value, interpret it as a large integer, and then ‘recover’ back your small value. What if you want to have that small values remain small ? Then  a standard approach is to use zigzag encoding. The recipe is as follows: Compute twice the absolute value of your integer. Add 1 to the result when the original integer was negative. Effectively, what you are doing is that all positive integers become…

https://lemire.me/blog/2022/11/25/making-all-your-integers-positive-with-zigzag-encoding/

Science and Technology links (November 26 2022)

Molière’s famous play, Tartuffe, the main characters is outwardly pious but fundamentally deceitful. Are people who insist on broadcasting their high virtue better people, who are they more like Tartuffe. Dong et al. (2022) conclude that people who say that they have good values are not necessarily better people in practice, but they are more likely to be hypocrites according. That is, Tartuffe is a realistic character. It is worth pointing out that Molière’s play was censored by the king. The thymus is a small organ which plays a critical role in your immune system by producing T cells. As you get older, your thymus becomes nearly disappears. The net result is that by the time you are 60 years old, you have few available T cells left and your immune system cannot adapt to new diseases as well. Calum Chace reports on a small clinical trial that showed that we can rejuvenate the thymus inexpensively. Unfortunately, though the clinical trial has been completed years ago, nobody seems to care about what is possibly a medical breakthrough in the fight…

https://lemire.me/blog/2022/11/26/science-and-technology-links-november-26-2022/

Generic number compression (zstd)

I have done a lot of work that involves compressing and uncompressing data. Most often, I work on data that has specific characteristics, e.g., sorted integers. In such cases, one can do much better than generic compression routines (e.g., zstd, gzip) both in compression ratios and performance. But how well do these generic techniques do for random integers and floats? We generate 32-bit floats in the interval [0,1] and store then as double-precision (64-bit) floats. Roughly speaking, it should be possible to compress this data by a factor of two. We generate 64-bit integers in the range [-127,127]. We should be able to compress this data by a factor of eight (from one byte to eight byte). What are the results? I use zstd v1.5.2 (with default flags) and a couple of small programs. source compression ratio 32-bit floats as 64-bit floats 2x 64-bit integers in the range [-127,127] 5x The compression ratio is pretty good for the floating-point test, nearly optimal. For the 64-bit integers, the results are less exciting but you are within a factor of two of…

https://lemire.me/blog/2022/11/28/generic-number-compression-zstd/

How big are your SVE registers ? (AWS Graviton)

Amazon has some neat ARM-based systems based on Amazon’s own chips (Graviton). You can access them through Amazon’s web services (AWS). These processors have advanced vector instructions able to process many values at once. These instructions are part of an instruction sets called SVE for Scalable Vector Extension. SVE has a trick: it hides its internal register size from you. Thus, to the question “how many values can it process at once?”, the answer is ‘”it depends”. Thankfully, you can still write a program to find out. The svlen_s8 intrinsic tells you how many 8-bit integers fits in a full register. Thus the following C++ line should tell you the vector register size in bytes: std::cout

Optimizing compilers reload vector constants needlessly

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 constant with 8 times the value 10001, then you would load elements from your array, 8 elements by 8 elements, add the vector constant (thus do 8 additions at once), and then store the result. Everything else being equal, this might be 8 times faster. An optimizing compiler might even do this optimization for you (a process called ‘auto-vectorization). However, for more complex code, you might need to do it manually using “intrinsic” functions (e.g., _mm256_loadu_si256, _mm256_add_epi32, etc.). Let us consider the simple case I describe, but where we process two arrays at once… using the same constant: #include #include void process_avx2(const uint32_t *in1, const uint32_t *in2, size_t len) { // define the constant, 8 x 10001 __m256i c = _mm256_set1_epi32(10001); const uint32_t *finalin1…

https://lemire.me/blog/2022/12/06/optimizing-compilers-reload-vector-constants-needlessly/

Fast midpoint between two integers without overflow

Let us say that I ask you to find the number I am thinking about between -1000 and 1000, by repeatedly guessing a number. With each guess, I tell you whether your guess is correct, smaller or larger than my number. A binary search algorithm tries to find a value in an interval by repeating finding the midpoint, using smaller and smaller intervals. You might start with 0, then use either -500 or 500 and so forth. Thus we sometimes need a fast algorithm to find the midpoint in an interval of integers.The following simple routine to find the midpoint is incorrect: int f(int x, int y) { return (x + y)/2; } If the integers use a 64-bit two’s complement representation, we could pick 1 for x and 9223372036854775807 for y, and then the result of the function could be a large negative value. To construct a better solution, we can use the following identity : x == 2*(x>>1) + (x&1). Thus we have that (x>>1) + (y>>1) is close to the midpoint: within ((x+y)/2-2,(x+y)/2]. If we add ((x&1)…

https://lemire.me/blog/2022/12/06/fast-midpoint-between-two-integers-without-overflow/

Science and Technology links (December 11 2022)

As we focus on some types of unfortunate discrimination (race, gender), we may become blind to other types of discrimination. For example, tend to discrimate against ugly people, short men, old people, and so on. Life may have emerged on Earth thanks to ‘aqueous microdroplets’. Naked mole rats are long-lived mammals. We believe that they experience negligible senescence, meaning that they do not lose fitness with age. One theory to explain they particular biology has to do with the fact that they live in a subterranean setting. Dammann et al. suggest that the fact that they are social creatures might also play a role. Low-carb diets may help obese individuals who face food addiction symptoms. Climate change may change how people name their children according to the journal Science. Offshore wind turbines endanger whales according to a Bloomberg report. Grip strength (who strongly you can hold on to something with your hands) is a good indication of your biological age. An mRNA technology might reprogram and rejuvenate your skin (according to a commercial press release). Many climate models predict that…

https://lemire.me/blog/2022/12/11/science-and-technology-links-december-11-2022/

What is the memory usage of a small array in C++?

In an earlier blog post, I reported that the memory usage of a small byte array in Java (e.g., an array containing 4 bytes) was about 24 bytes. In other words: allocating small blocks of memory has substantial overhead. What happens in C++? To find out, I can try to allocate one million 4-byte arrays and look at the total memory usage of the process. Of course, the memory usage of the process will include some overhead unrelated to the 4-byte arrays, but we expect that such overhead will be relatively small. From my benchmark, I get the following results… system memory usage (in bytes) GCC 8, Linux x86 32 bytes LLVM 14, Apple aarch64 16 bytes The results will vary depending on the configuration of your system. The lesson is that allocating four bytes (new char[4] or malloc(4)) does not use four bytes of memory… it will generally use much more.

https://lemire.me/blog/2022/12/12/what-is-the-memory-usage-of-a-small-array-in-c/

Checking for the absence of a string, naive AVX-512 edition

Suppose you would like to check that a string is not present in a large document. In C, you might do the following using the standard function strstr: bool is_present = strstr(mydocument, needle); It is simple and likely very fast. Can you do better? Recent Intel and AMD processors have instructions that operate on 512-bit registers. So we can compare 64 bytes using a single instruction. The simplest algorithm to search for a string might look as follows… Load 64 bytes from our input document, compare them against 64 copies of the first character of the target string. If we find a match, load the second character of the target string, copy it 64 times within a register. Load 64 bytes from our input document, with an offset of one byte. Repeat as needed for the second, third, and so forth characters… Then advance in the input by 64 bytes and repeat. Using Intel intrinsic functions, the algorithm looks as follows: for (size_t i = 0; ...; i += 64) { __m512i comparator = _mm512_set1_epi8(needle[0]); __m512i input = _mm512_loadu_si512(in + i);…

https://lemire.me/blog/2022/12/15/checking-for-the-absence-of-a-string-naive-avx-512-edition/

Checking for the absence of a string, naive AVX-512 edition

Suppose you would like to check that a string is not present in a large document. In C, you might do the following using the standard function strstr: bool is_present = strstr(mydocument, needle); It is simple and likely very fast. Can you do better? Recent Intel and AMD processors have instructions that operate on 512-bit registers. So we can compare 64 bytes using a single instruction. The simplest algorithm to search for a string might look as follows… Load 64 bytes from our input document, compare them against 64 copies of the first character of the target string. If we find a match, load the second character of the target string, copy it 64 times within a register. Load 64 bytes from our input document, with an offset of one byte. Repeat as needed for the second, third, and so forth characters… Then advance in the input by 64 bytes and repeat. Using Intel intrinsic functions, the algorithm looks as follows: for (size_t i = 0; ...; i += 64) { __m512i comparator = _mm512_set1_epi8(needle[0]); __m512i input = _mm512_loadu_si512(in + i);…

https://lemire.me/blog/2022/12/15/checking-for-the-absence-of-a-string-naive-avx-512-edition/

Checking for the absence of a string, naive AVX-512 edition

Suppose you would like to check that a string is not present in a large document. In C, you might do the following using the standard function strstr: bool is_present = strstr(mydocument, needle); It is simple and likely very fast. Can you do better? Recent Intel and AMD processors have instructions that operate on 512-bit registers. So we can compare 64 bytes using a single instruction. The simplest algorithm to search for a string might look as follows… Load 64 bytes from our input document, compare them against 64 copies of the first character of the target string. If we find a match, load the second character of the target string, copy it 64 times within a register. Load 64 bytes from our input document, with an offset of one byte. Repeat as needed for the second, third, and so forth characters… Then advance in the input by 64 bytes and repeat. Using Intel intrinsic functions, the algorithm looks as follows: for (size_t i = 0; ...; i += 64) { __m512i comparator = _mm512_set1_epi8(needle[0]); __m512i input = _mm512_loadu_si512(in + i);…

https://lemire.me/blog/2022/12/15/checking-for-the-absence-of-a-string-naive-avx-512-edition/

Implementing ‘strlen’ using SVE

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 to load large registers at once and to do wide comparisons (comparing many bytes at once). Yet we do not want to read too much data. If you read beyond the string, you could hit another memory page and trigger a segmentation fault. This could crash your program. Thankfully, SVE comes with a load instruction that would only fault on the ‘first active element’: as long as the first element you are loading is valid, then there is no fault. With this in mind, a simple algorithm to compute the length of a C string is as follows: Load a register. Compare each byte in it to 0. If any comparison matches, then locate the match and return the corresponding length. If not, increment by…

https://lemire.me/blog/2022/12/19/implementing-strlen-using-sve/

Implementing ‘strlen’ using SVE

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 to load large registers at once and to do wide comparisons (comparing many bytes at once). Yet we do not want to read too much data. If you read beyond the string, you could hit another memory page and trigger a segmentation fault. This could crash your program. Thankfully, SVE comes with a load instruction that would only fault on the ‘first active element’: as long as the first element you are loading is valid, then there is no fault. With this in mind, a simple algorithm to compute the length of a C string is as follows: Load a register. Compare each byte in it to 0. If any comparison matches, then locate the match and return the corresponding length. If not, increment by…

https://lemire.me/blog/2022/12/19/implementing-strlen-using-sve/

Checking for tabs and newlines fast!

When parsing code, we sometimes need to identify whether a character falls within a class. Suppose you want to check whether a character is a tab, or a newline character. A reasonable C expression to do so might look as follows: c == 't' || c == 'n' || c == 'r' Under x64 processors, LLVM clang compiles this down to the following assembly… lea eax, [rdi - 9] cmp al, 2 setb cl cmp dil, 13 sete al or al, cl Can you do better? You might. We have that ‘t’ is represented as the byte value 9, ‘n’ is 10, and ‘r’ is 13. We can use an integer that the bits at indexes 9, 10 and 13 set to 1, and all other bits set to zero. This integer is 0x2600 or 9728. Thus the following expression should be equivalent to the above C expression: 0x2600&(uint64_t(1)

The size of things in bytes

storing 1 GiB/month on the cloud 0.02$US web site of my twitter profile (@lemire), HTML alone 296 KiB web site of my twitter profile (@lemire), all data 3.9 MiB Google result for ‘Canada’, HTML alone 848 KiB Google result for ‘Canada’, all data 3.7 MiB Node JS runtime 164 MiB Size of the Java (19) runtime 330 MiB LLVM/clang compiler runtime 5.5 GiB

https://lemire.me/blog/2022/12/21/the-size-of-things-in-bytes/

Fast base16 encoding

Given binary data, we often need to encode it as ASCII text. Email and much of the web effectively works in this manner. A popular format for this purpose is base64. With Muła, we showed that we could achieve excellent speed using vector instructions on commodity processors (2018, 2020). However, base64 is a bit tricky. A much simpler format is just base16. E.g., you just transcribe each byte into two bytes representing the value in hexadecimal notation. Thus the byte value 1 becomes the two bytes ’01’. The byte value 255 becomes ‘FF’, and so forth. In other words, you use one byte (or one character) per ‘nibble’: a byte is made of two nibbles: the most-significant 4 bits and the least-significant 4 bits. How could encode base16 quickly? A reasonable approach might be to use a table. You grab one byte from the input and you directly lookup the 2 bytes from the output which you immediately write out: void encode_scalar(const uint8_t *source, size_t len, char *target) { const uint16_t table[] = { 0x3030, 0x3130, 0x3230, 0x3330, 0x3430, ...…

https://lemire.me/blog/2022/12/23/fast-base16-encoding/

Science and Technology links (December 25 2022)

One of Elon Musk’s ventures, OpenAI, made public a new tool called ChatGPT. It is widely regarding as a practical breakthrough in artificial intelligence. Given a question, it can produce a coherent essay-length answer. Last week, my employer held a meeting to discuss how it will impact college classes. OpenAI expects to make a billion dollars in 2024 with ChatGPT. The US governments redistribute a greater share of the national income to low-income groups than any European country. People who report being good looking also report having a more meaningful life. Mushrooms might be highly effective against depression. Inside our microprocessors, we have very fast memory used for ‘caches’, so that repeatedly accessed data is readily available. For that purpose, chips vendor use SRAM technology. SRAM is very fast but also relatively expensive. Over time, we are generally able to make processors ever more denser and thus, we can design more powerful processors for more or less a fixed cost. Having more memory on the processor is a key ingredient for better performance. Sadly, it appears that SRAM density is…

https://lemire.me/blog/2022/12/25/science-and-technology-links-december-25-2022/

Quickly checking that a string belongs to a small set

Suppose that I give you a set of reference strings (“ftp”, “file”, “http”, “https”, “ws”, “wss”). Given a new string, you want to quickly tell whether it is part of this set. A sensible solution might be to create a set and then to ask whether the string is in the set. In C++, a default set type is the unordered_set thus your code might look as follows: static const std::unordered_set special_set = { "ftp", "file", "http", "https", "ws", "wss"}; bool hash_is_special(std::string_view input) { return special_set.find(input) != special_set.end(); } You might also be more direct about it, and just do several comparisons: bool direct_is_special(std::string_view input) { return (input == "https") | (input == "http") | (input == "ftp") | (input == "file") | (input == "ws") | (input == "wss"); } If you look at how the code gets compiled, you may notice that the compiler is forced to do comparisons and jumps, because it is not allowed to read in the provided string beyond its reported size. You might be able to do slightly better if you can tell…

https://lemire.me/blog/2022/12/30/quickly-checking-that-a-string-belongs-to-a-small-set/

Emojis in domain names, punycode and performance

Most domain names are encoded using ASCII (e.g., yahoo.com). However, you can register domain names with almost any character in them. For example, there is a web site at 💩.la called poopla. Yet the underlying infrastructure is basically pure ASCII. To make it work, the text of your domain is first translated into ASCII using a special encoding called ‘punycode‘. The poopla web site is actually at https://xn--ls8h.la/. Punycode is a tricky format. Thankfully, domain names are made of labels (e.g., in microsoft.com, microsoft is a label) and each label can use at most 63 bytes. In total, a domain name cannot exceed 255 bytes, and that is after encoding it to punycode if necessary. Some time ago, Colm MacCárthaigh asked to look at the performance impact of punycode. To answer the question, I quickly implemented a function that does the job. It is a single function without much fanfare. It is roughly derived from the code in the standard, but it looks simpler to me. Importantly, I do not claim that my implementation is particularly fast. As a dataset,…

https://lemire.me/blog/2023/01/04/emojis-in-domain-names-punycode-and-performance/

Transcoding Unicode with AVX-512: AMD Zen 4 vs. Intel Ice Lake

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 ‘transcoding’. In the last few years, we wrote a specialized library that process Unicode strings, with a focus on performance: the simdutf library. The library is used JavaScript runtimes (Node JS and bun). The simdutf library is able to benefit from the latest and most powerful instructions on your processors. In particular, it does well with recent processors with AVX-512 instructions (Intel Ice Lake, Rocket Lake, as well as AMD Zen 4). I do not yet have a Zen 4 processor, but Velu Erwan was kind of enough to benchmark it for me. A reasonable task is to transcode an Arabic file from UTF-8 to UTF-16: it is typically a non-trivial task because Arabic UTF-8 is a mix of one-byte and two-byte characters that we must convert to…

https://lemire.me/blog/2023/01/05/transcoding-unicode-with-avx-512-amd-zen-4-vs-intel-ice-lake/

Care is needed to use C++ std::optional with non-trivial objects

We often have to represent in software a value that might be missing. Different programming languages have abstraction for this purpose. A recent version of C++ (C++17) introduces std::optional templates. It is kind of neat. You can write code that prints a string, or a warning if no string is available as follows: void f(std::optional s) { std::cout