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/

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/