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/
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/
Daniel Lemire's blog
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. The implementation is algorithmically…
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/
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/
Daniel Lemire's blog
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. The implementation is algorithmically…
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/
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/
Daniel Lemire's blog
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. The implementation is algorithmically…
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/
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/
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)
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/
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/
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/
Daniel Lemire's blog
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…
A popular format for this purpose is base64. With Muła, we showed that we could achieve excellent speed using vector instructions on…
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/
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/
Daniel Lemire's blog
Science and Technology links (December 25 2022)
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…
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/
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/
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/
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/
Daniel Lemire's blog
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…
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
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
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
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
Science and technology links (January 15 2022)
For under $600, one can buy a 20-terabyte disk on Amazon. Unless you work professionally in multimedia, it is more storage than you need. However, having much storage it, by itself, of little use if you cannot access it. Thankfully, you can buy a 1-terabyte “disk” for $200 that provides over 6 GB/s of bandwidth. I have a similar disk in my game console. Is this as good as it gets? Researchers show that we can transmit data over a distance at more than a petabit per second. According to some estimates, that is more than the total data size of the books in the library of congress, per second. Transplanting rejuvenated blood stem cells extends lifespan of aged immunocompromised mice. Amazon is using drones for deliveries in California and Texas. People who think themselves as less attractive are more likely willing to wear surgical masks. Conversations rarely end when they should. Using legal restrictions, manufacturers are able to prevent their customers from repairing their own products. There may be hope. Farmers in the US will be allowed to repair…
https://lemire.me/blog/2023/01/15/science-and-technology-links-january-15-2022/
For under $600, one can buy a 20-terabyte disk on Amazon. Unless you work professionally in multimedia, it is more storage than you need. However, having much storage it, by itself, of little use if you cannot access it. Thankfully, you can buy a 1-terabyte “disk” for $200 that provides over 6 GB/s of bandwidth. I have a similar disk in my game console. Is this as good as it gets? Researchers show that we can transmit data over a distance at more than a petabit per second. According to some estimates, that is more than the total data size of the books in the library of congress, per second. Transplanting rejuvenated blood stem cells extends lifespan of aged immunocompromised mice. Amazon is using drones for deliveries in California and Texas. People who think themselves as less attractive are more likely willing to wear surgical masks. Conversations rarely end when they should. Using legal restrictions, manufacturers are able to prevent their customers from repairing their own products. There may be hope. Farmers in the US will be allowed to repair…
https://lemire.me/blog/2023/01/15/science-and-technology-links-january-15-2022/
Year 2022: Scientific progress
The year 2022 is over. As with every year that passes, we have made some scientific progress. I found the following achievements interesting: Diluting the blood plasma of older human beings rejuvenate them. In a nuclear reactor, we have technically produced more energy than we put in. You can rejuvenate old human skins by grafting it on young mice. ChatGPT is widely regarded as an AI breakthrough: it can produce full length English essays that could pass as high school work.
https://lemire.me/blog/2023/01/15/year-2022-scientific-progress/
The year 2022 is over. As with every year that passes, we have made some scientific progress. I found the following achievements interesting: Diluting the blood plasma of older human beings rejuvenate them. In a nuclear reactor, we have technically produced more energy than we put in. You can rejuvenate old human skins by grafting it on young mice. ChatGPT is widely regarded as an AI breakthrough: it can produce full length English essays that could pass as high school work.
https://lemire.me/blog/2023/01/15/year-2022-scientific-progress/
Daniel Lemire's blog
Year 2022: Scientific progress
The year 2022 is over. As with every year that passes, we have made some scientific progress. I found the following achievements interesting:
Diluting the blood plasma of older human beings rejuvenate them.
In a nuclear fusion reactor, we have technically…
Diluting the blood plasma of older human beings rejuvenate them.
In a nuclear fusion reactor, we have technically…
International domain names: where does https://meßagefactory.ca lead you?
Originally, the domain part of a web address was all ASCII (so no accents, no emojis, no Chinese characters). This was extended a long time ago thanks to something called internationalized domain name (IDN). Today, in theory, you can use any Unicode character you like as part of a domain name, including emojis. Whether that is wise is something else. What does the standard says? Given a domain name, we should identify its labels. They are normally separated by dots (.) into labels: www.microsoft.com has three labels. But you may also use other Unicode characters as separators ( ., ．, 。, ｡). Each label is further processed. If it is all ASCII, then it is left as is. Otherwise, we must convert it to an ASCII code called “punycode” after doing the following according to RFC 3454: Map characters (section 3 of RFC 3454), Normalize (section 4 of RFC 3454), Reject forbidden characters, Optionally reject based on unassigned code points (section 7). And then you get to the punycode algorithm. There are further conditions to be satisfied, such as the domain…
https://lemire.me/blog/2023/01/23/international-domain-names-where-does-https-mesagefactory-ca-lead-you/
Originally, the domain part of a web address was all ASCII (so no accents, no emojis, no Chinese characters). This was extended a long time ago thanks to something called internationalized domain name (IDN). Today, in theory, you can use any Unicode character you like as part of a domain name, including emojis. Whether that is wise is something else. What does the standard says? Given a domain name, we should identify its labels. They are normally separated by dots (.) into labels: www.microsoft.com has three labels. But you may also use other Unicode characters as separators ( ., ．, 。, ｡). Each label is further processed. If it is all ASCII, then it is left as is. Otherwise, we must convert it to an ASCII code called “punycode” after doing the following according to RFC 3454: Map characters (section 3 of RFC 3454), Normalize (section 4 of RFC 3454), Reject forbidden characters, Optionally reject based on unassigned code points (section 7). And then you get to the punycode algorithm. There are further conditions to be satisfied, such as the domain…
https://lemire.me/blog/2023/01/23/international-domain-names-where-does-https-mesagefactory-ca-lead-you/
Move or copy your strings? Possible performance impacts
You sometimes want to add a string to an existing data structure. For example, the C++17 template ‘std::optional’ may be used to represent a possible string value. You may copy it there, as this code would often do… std::string mystring; std::optional myoption; myoption = mystring; Or you can move it: std::string mystring; std::optional myoption; myoption = std::move(mystring); In C++, when ‘moving’ a value, the compiler does not need to create a whole new copy of the string. So it is often cheaper. I wrote a little benchmark to assess the performance difference. It is a single test, but it should illustrate. Firstly, for relatively long strings (a phrase or a sentence), the move is 5 times to 20 times faster. copy move Apple LLVM 14, M2 processor 24 ns/string 1.2 ns/string GCC 11, Intel Ice Lake 19 ns/string 4 ns/string Secondly, for short strings (a single word), the move is 1.5 times to 3 times faster. copy move Apple LLVM 14, M2 processor 2.0 ns/string 1.2 ns/string GCC 11, Intel Ice Lake 7 ns/string 2.6 ns/string My results illustrate that…
https://lemire.me/blog/2023/01/30/move-or-copy-your-strings-possible-performance-impacts/
You sometimes want to add a string to an existing data structure. For example, the C++17 template ‘std::optional’ may be used to represent a possible string value. You may copy it there, as this code would often do… std::string mystring; std::optional myoption; myoption = mystring; Or you can move it: std::string mystring; std::optional myoption; myoption = std::move(mystring); In C++, when ‘moving’ a value, the compiler does not need to create a whole new copy of the string. So it is often cheaper. I wrote a little benchmark to assess the performance difference. It is a single test, but it should illustrate. Firstly, for relatively long strings (a phrase or a sentence), the move is 5 times to 20 times faster. copy move Apple LLVM 14, M2 processor 24 ns/string 1.2 ns/string GCC 11, Intel Ice Lake 19 ns/string 4 ns/string Secondly, for short strings (a single word), the move is 1.5 times to 3 times faster. copy move Apple LLVM 14, M2 processor 2.0 ns/string 1.2 ns/string GCC 11, Intel Ice Lake 7 ns/string 2.6 ns/string My results illustrate that…
https://lemire.me/blog/2023/01/30/move-or-copy-your-strings-possible-performance-impacts/
Daniel Lemire's blog
Move or copy your strings? Possible performance impacts
You sometimes want to add a string to an existing data structure. For example, the C++17 template 'std::optional' may be used to represent a possible string value. You may copy it there, as this code would often do...
std::string mystring;
std::optio…
std::string mystring;
std::optio…
Serializing IPs quickly in C++
On the Internet, we often use 32-bit addresses which we serialize as strings such as 192.128.0.1. The string corresponds to the Integer address 0xc0800001 (3229614081 in decimal). How might you serialize, go from the integer to the string, efficiently in C++? The simplest code in modern C++ might look as follows: std::string output = std::to_string(address >> 24); for (int i = 2; i >= 0; i--) { output.append(std::to_string((address >> (i * 8)) % 256) + "."); } At least symbolically, it will repeatedly create small strings that are appended to an initial string. Can we do better? We have new functions in C++ (std::to_chars) which are dedicated to writing quickly to a string buffer. So we might try to allocate a single buffer and write to it using buffers. The result is not pretty: std::string output(4 * 3 + 3, ''); // allocate just one big string char *point = output.data(); char *point_end = output.data() + output.size(); point = std::to_chars(point, point_end, uint8_t(address >> 24)).ptr; for (int i = 2; i >= 0; i--) { *point++ = '.'; point = std::to_chars(point,…
https://lemire.me/blog/2023/02/01/serializing-ips-quickly-in-c/
On the Internet, we often use 32-bit addresses which we serialize as strings such as 192.128.0.1. The string corresponds to the Integer address 0xc0800001 (3229614081 in decimal). How might you serialize, go from the integer to the string, efficiently in C++? The simplest code in modern C++ might look as follows: std::string output = std::to_string(address >> 24); for (int i = 2; i >= 0; i--) { output.append(std::to_string((address >> (i * 8)) % 256) + "."); } At least symbolically, it will repeatedly create small strings that are appended to an initial string. Can we do better? We have new functions in C++ (std::to_chars) which are dedicated to writing quickly to a string buffer. So we might try to allocate a single buffer and write to it using buffers. The result is not pretty: std::string output(4 * 3 + 3, ''); // allocate just one big string char *point = output.data(); char *point_end = output.data() + output.size(); point = std::to_chars(point, point_end, uint8_t(address >> 24)).ptr; for (int i = 2; i >= 0; i--) { *point++ = '.'; point = std::to_chars(point,…
https://lemire.me/blog/2023/02/01/serializing-ips-quickly-in-c/
Daniel Lemire's blog
Serializing IPs quickly in C++
On the Internet, we often use 32-bit addresses which we serialize as strings such as 192.128.0.1. The string corresponds to the Integer address 0xc0800001 (3229614081 in decimal).
How might you serialize, go from the integer to the string, efficiently…
How might you serialize, go from the integer to the string, efficiently…
Bit Hacking (with Go code)
At a fundamental level, a programmer needs to manipulate bits. Modern processors operate over data by loading in ‘registers’ and not individual bits. Thus a programmer must know how to manipulate the bits within a register. Generally, we can do so while programming with 8-bit, 16-bit, 32-bit and 64-bit integers. For example, suppose that I want to set an individual bit to value 1. Let us pick the bit an index 12 in a 64-bit words. The word with just the bit at index 12 set is 1
At a fundamental level, a programmer needs to manipulate bits. Modern processors operate over data by loading in ‘registers’ and not individual bits. Thus a programmer must know how to manipulate the bits within a register. Generally, we can do so while programming with 8-bit, 16-bit, 32-bit and 64-bit integers. For example, suppose that I want to set an individual bit to value 1. Let us pick the bit an index 12 in a 64-bit words. The word with just the bit at index 12 set is 1
Science and Technology links (February 12 2023)
Kenny finds that the returns due to education are declining. Rich countries are spending more on education, with comparatively weaker test results. It costs more than ever to train a PhD student, but it takes ever longer for them to complete their studies. There 25 times more crop researchers today than in the 1970s, but rate of progress remains constant. Researchers are better at producing patents, but the quality of these patents may be decreasing.Furthermore, there aren’t more people to educate: 2012 was “peak child”. It is the year in history when we had the most births. We are now in decline. Fertility levels are below replacement levels in much of the high-income countries. Exercise prevents muscle aging at the gene-expression level. 28% of people in Japan are 65 years old or older. People who undergo colonoscopies reduce their risk of death by 0.01% in absolute terms. Jupiter has 92 Moons while Saturn has 83 Moons, however the number increases over time. Most Moons are tiny objects. Homo erectus beings could still be found 100,000 years ago in Indonesia. They…
https://lemire.me/blog/2023/02/12/science-and-technology-links-february-12-2023/
Kenny finds that the returns due to education are declining. Rich countries are spending more on education, with comparatively weaker test results. It costs more than ever to train a PhD student, but it takes ever longer for them to complete their studies. There 25 times more crop researchers today than in the 1970s, but rate of progress remains constant. Researchers are better at producing patents, but the quality of these patents may be decreasing.Furthermore, there aren’t more people to educate: 2012 was “peak child”. It is the year in history when we had the most births. We are now in decline. Fertility levels are below replacement levels in much of the high-income countries. Exercise prevents muscle aging at the gene-expression level. 28% of people in Japan are 65 years old or older. People who undergo colonoscopies reduce their risk of death by 0.01% in absolute terms. Jupiter has 92 Moons while Saturn has 83 Moons, however the number increases over time. Most Moons are tiny objects. Homo erectus beings could still be found 100,000 years ago in Indonesia. They…
https://lemire.me/blog/2023/02/12/science-and-technology-links-february-12-2023/
Daniel Lemire's blog
Science and Technology links (February 12 2023)
Kenny finds that the returns due to education are declining. Rich countries are spending more on education, with comparatively weaker test results. It costs more than ever to train a PhD student, but it takes ever longer for them to complete their studies.…