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

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

Catching sanitizer errors programmatically

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

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

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

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

Science and Technology links (September 12 2022)

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

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

Escaping strings faster with AVX-512

When programming, we often have to ‘escape’ strings. A standard way to do it is to insert the backslash character () before some characters such as the double quote. For example, the string my title is "La vie" becomes my title is "La vie" A simple routine in C++ to escape a string might look as follows: for (...) { if ((*in == '\') || (*in == '"')) { *out++ = '\'; } *out++ = *in; } Such a character-by-character approach is unlikely to provide the best possible performance on modern hardware. Recent Intel processors have fast instructions (AVX-512) that are well suited for such problems. I decided to sketch a solution using Intel intrinsic functions. The routine goes as follows: I use two constant registers containing 64 copies of the backslash character and 64 copies of the quote characters. I start a loop by loading 32 bytes from the input. I expands these 32 bytes into a 64 byte register, interleaving zero bytes. I copy these bytes with the quotes and backslash characters. From the resulting mask, I then…

https://lemire.me/blog/2022/09/14/escaping-strings-faster-with-avx-512/

Science and Technology links (September 16 2022)

Attractive female students get better grades. They lose this benefit when courses move online. A research paper is much more likely to be highly ranked if the author is famous. The USA has many more prisoners than police officers (three prisoners for every police officer), while every other developed country has the reverse ratio. Diluting the blood plasma of older human beings rejuvenate them. Saturated fat, as found in meat and dairy products, is not associated with bad cardiovascular health. In other words, eating butter does not harm your heart. An electric car has reportedly about half the carbon footprint as that of a conventional car.

https://lemire.me/blog/2022/09/17/science-and-technology-links-september-16-2022/

A review of elementary data types : numbers and strings

Computer programming starts with the organization of the data into data structures. In almost all cases, we work with strings or numbers. It is critical to understand these building blocks to become an expert programmer. Words We often organize data using fixed blocks of memory. When these blocks are relatively small (e.g., 8 bits, 16 bits, 32 bits, 64 bits), we commonly call them ‘words’. The notion of ‘word’ is important because processors do not operate over arbitrary data types. For practical reasons, processors expect data to fit in hardware registers having some fixed size (usually 64-bit registers). Most modern processors accommodate 8-bit, 16-bit, 32-bit and 64-bit words with fast instructions. It is typical to have the granularity of the memory accesses to be no smaller than the ‘byte’ (8 bits) so bytes are, in a sense, the smallest practical words. Variable-length data structures like strings might be made of a variable number of words. Historically, strings have been made of lists of bytes, but other alternatives are common (e.g., 16-bit or 32-bit words). Boolean values The simplest type is…

https://lemire.me/blog/2022/09/30/a-review-of-elementary-data-types-numbers-and-strings/

The number of comparisons needed to sort a shuffled array: qsort versus std::sort

Given an array of N numbers of type double, the standard way to sort it in C is to invoke the qsort function qsort(array, N, sizeof(double), compare); where compare is a function which returns an integer less than, equal to, or greater than zero if the first argument is less than, equal to, or greater than the second. Because it is a C function, it takes in void pointers which we must convert back to actual values. One safe way to achieve such a conversion is through the memcpy function. The following is a reasonable implementation of a comparison function: int compare(const void *a, const void *b) { double x, y; memcpy(&x, a, sizeof(x)); memcpy(&y, b, sizeof(y)); counter++; if(x < y) { return -1; } if(x == y) { return 0; } return 1; } Though the function appears to have branches, optimizing compilers can generate binary code without any jumps in this case. Though the name suggests that qsort might be implemented using the textbook algorithm Quicksort, the actual implementation depends on the standard library. The standard approach in…

https://lemire.me/blog/2022/10/11/the-number-of-comparisons-needed-to-sort-a-shuffled-array-qsort-versus-stdsort/

The number of comparisons needed to sort a shuffled array: qsort versus std::sort

Given an array of N numbers of type double, the standard way to sort it in C is to invoke the qsort function qsort(array, N, sizeof(double), compare); where compare is a function which returns an integer less than, equal to, or greater than zero if the first argument is less than, equal to, or greater than the second. Because it is a C function, it takes in void pointers which we must convert back to actual values. One safe way to achieve such a conversion is through the memcpy function. The following is a reasonable implementation of a comparison function: int compare(const void *a, const void *b) { double x, y; memcpy(&x, a, sizeof(x)); memcpy(&y, b, sizeof(y)); counter++; if(x < y) { return -1; } if(x == y) { return 0; } return 1; } Though the function appears to have branches, optimizing compilers can generate binary code without any jumps in this case. Though the name suggests that qsort might be implemented using the textbook algorithm Quicksort, the actual implementation depends on the standard library. The standard approach in…

https://lemire.me/blog/2022/10/11/the-number-of-comparisons-needed-to-sort-a-shuffled-array-qsort-versus-stdsort/

Science and Technology links (October 16 2022)

Doctors in Israel are toying with polygenic screening: it is a way to make it more likely that your baby will grow up to be healthy. In 2021, 337 million prescriptions were written for antidepressants in US, according to the New York Times. Students in private schools do better in India than those attending government-run schools, even in districts where 70% of all students attend private schools. People who participate in free markets are more moral toward strangers. In Japan 400 years ago, the sea level was 2 meters higher than the current level.

https://lemire.me/blog/2022/10/16/science-and-technology-links-october-16-2022/

Book Review : Template Metaprogramming with C++

I have spent the last few years programming often in C++. The C++ langage is probably one of the hardest to master. I still learn something new every week. Furthermore, C++ is getting upgrades all the time: C++17 was a great step forward and C++20 brings even more exiting improvments. In C++, we often use ‘templates’. As the name suggests, they allow us to create C++ functions and classes from a generic recipe. For example, the following template allows us to create functions that sum up two values: template T f(T x, T y) { return x + y; } It gets automatically instantiated when you need it. The following function will return the sum of two integers. int g(int x, int y) { return f(x,y); } Templates are very powerful. They allow us to create highly efficient code, because everything happens at compile time: the optimizer can do it is work. With great power, comes great responsibility: templates can be infuriating since they may lead to unreadability error

Modern vector programming with masked loads and stores

When you start a program, it creates a ‘process’ which own its memory. Memory is allocated to a software process in blocks called ‘pages’. These pages might span 4kB, 16kB or more. For a given process, it is safe to read and write within these pages. In your code, you might allocate a 32-byte array. How much memory does the array require? The answer is that the allocation of the array might require no extra memory because the process had already the room needed in its pages, or else, the array might entice the operating system to grant the process many more pages. Similarly, ‘freeing’ the array does not (generally) reclaim the memory. In general, the operating system and the processor do not care when your program reads and writes anywhere within the pages allocated to it. These pages are the ‘segment’ that the process owns. When you do access a forbidden page, one that was not allocated to your process, then you normally get a segmentation fault. Most of the time, it means that your program crashes. Interestingly,  if…

https://lemire.me/blog/2022/11/08/modern-vector-programming-with-masked-loads-and-stores/

Measuring the memory usage of your C++ program

In C++, we might implement dynamic lists using the vector template. The int-valued constructor of the vector template allocates at least enough memory to store the provided number of elements in a contiguous manner. How much memory does the following code use? std::vector v1(10); std::vector v2(1000000); The naive answer is 1000010 bytes or slightly less than 1 MB, but if you think a bit about it, you quickly realize that 1000010 bytes might be a lower bound. Indeed, the vector might allocate more memory and there is unavoidably some overhead for the vector instance. Thankfully, it is easy to measure it. I wrote a little C++ program to measure actual memory usage in terms of allocated pages attributed to the program. We find that we use far more memory (2x or 4x more) than a naive analysis might suggest. start of the program after the first vector at the end ARM-based macOS 1.25 MB 1.25 MB 2.25 MB Intel-based Linux 1.94 MB 1.94 MB 4.35 MB Further reading: Measuring memory usage: virtual versus real memory

https://lemire.me/blog/2022/11/10/measuring-the-memory-usage-of-your-c-program/

A fast function to check your floating-point rounding mode

For speed, we use finite-precision number types in software. When doing floating-point computations in software, the results are usually not exact. For example, you can have the number 1.0 and the number 1e-100 (1 over 10 to the power 100). They can both be represented using standard IEEE floating-point numbers. However, you cannot represent their sum or difference exactly. So what does a compute do when you ask it to compute (1.0 + 1e-100) or (1.0 – 1e-100) ? It usually outputs the nearest approximation, that 1.0. In other words, it looks at all the numbers that it can represent and picks one that is nearest to the exact value. This works for most basic operations like addition, multiplication, division, subtraction. However, it is possible to ask the processor to change the rounding mode. In some cases, you can request a specific rounding mode per instruction (e.g., with some AVX-512 instructions), but most times there is one setting valid for all instructions within the current thread. In C/C++, you can change the rounding mode to round upward (fesetround(FE_UPWARD)), downward (fesetround(FE_DOWNWARD)),…

https://lemire.me/blog/2022/11/16/a-fast-function-to-check-your-floating-point-rounding-mode/

std::from_chars versus strtod/strtof

A recent C++ standard (C++17) introduced new functions to parse floating-point numbers std::from_chars, from strings (e.g., ASCII text) to binary numbers. How should such a function parse values that cannot be represented exactly? The specification states that the resulting value rounded to nearest. This means that 1.0000000000000000001 and 0.999999999999999999 become exactly 1.0. The C language has its own functions (strtod/strtof). I could not find a reference in the standard as to how it should round, but the source code suggests that the functions round according to the current floating-point rounding mode, as determined by the fegetround() function. One can round toward zero, up, down or to nearest. I have written a small command utility to test it out. And indeed, I get the following results under LLVM and GCC: string result (FE_UPWARD) result (FE_DOWNWARD) result (FE_TONEAREST) 1.0000000000000000001 1.00001 1.0 1.0 0.999999999999999999 1.0 0.999999 0.999999 Thus you cannot assume that, in general, std::from_chars will agree with strtod/strtof even for just boring strings such as 0.999999999999999999. Thankfully, you can check the rounding mode efficiently.

https://lemire.me/blog/2022/11/17/stdfrom_chars-versus-strtod-strtof/

What is the size of a byte[] array in Java?

Java allows you to create an array just big enough to contain 4 bytes, like so: byte[] array = new byte[4]; How much memory does this array take? If you have answered “4 bytes”, you are wrong. A more likely answer is 24 bytes. I wrote a little Java program that relies on the jamm library to print out some answers, for various array sizes: size of the array estimated memory usage 0 16 bytes 1 24 bytes 2 24 bytes 3 24 bytes 4 24 bytes 5 24 bytes 6 24 bytes 7 24 bytes 8 24 bytes 9 32 bytes This is not necessarily the exact memory usage on your system, but it is a reasonable guess.

https://lemire.me/blog/2022/11/22/what-is-the-size-of-a-byte-array-in-java/

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/