Science and Technology links (July 23rd 2022)

Compared to 1800, we eat less saturated fat and much more processed food and vegetable oils and it does not seem to be good for us: Saturated fats from animal sources declined while polyunsaturated fats from vegetable oils rose. Non-communicable diseases (NCDs) rose over the twentieth century in parallel with increased consumption of processed foods, including sugar, refined flour and rice, and vegetable oils. Saturated fats from animal sources were inversely correlated with the prevalence of non-communicable diseases. Kang et al. found that saturated fats reduce your risk of having a stroke: a higher consumption of dietary saturated fat is associated with a lower risk of stroke, and every 10 g/day increase in saturated fat intake is associated with a 6% relative risk reduction in the rate of stroke. Saturated fats come from meat and dairy products (e.g., butter). A low-fat diet can significantly increase the risk of coronary heart disease events. Leroy and Cofnas argues against a reduction of red meat consumption: The IARC’s (2015) claim that red meat is “probably carcinogenic” has never been substantiated. In fact, a…

https://lemire.me/blog/2022/07/21/science-and-techno/

Round a direction vector to an 8-way compass

Modern game controllers can point in a wide range of directions. Game designers sometimes want to convert the joystick direction to get 8-directional movement. A typical solution offered is to compute the angle, round it up and then compute back the direction vector. double angle = atan2(y, x); angle = (int(round(4 * angle / PI + 8)) % 8) * PI / 4; xout = cos(angle); yout = sin(angle); If you assume that the direction vector is in the first quadrant (both x and y are positive), then there is a direct way to compute the solution. Using 1/sqrt(2) or 0.7071 as the default solution, compare both x and y with cos(3*pi/8) and cos(pi/8), and only switch them to 1 or 0 if they are larger than cos(3*pi/8) or smaller than cos(pi/8). The full code looks as follows: xout = 0.7071067811865475; yout = 0.7071067811865475; if (x >= 0.923879532511286) {// cos(3*pi/8) xout = 1; } if (y >= 0.923879532511286) {// cos(3*pi/8) yout = 1; } if (x < 0.3826834323650898) {// cos(pi/8) xout = 0; } if (y < 0.3826834323650898) {// cos(pi/8) yout…

https://lemire.me/blog/2022/07/24/round-a-direction-vector-to-the-nearest-8-way-compass/

Comparing strtod with from_chars (GCC 12)

A reader (Richard Ebeling) invited me to revisit an older blog post: Parsing floats in C++: benchmarking strtod vs. from_chars. Back then I reported that switching from strtod to from_chars in C++ to parse numbers could lead to a speed increase (by 20%). The code is much the same, we go from… char * string = "3.1416"; char * string_end = string; double x = strtod(string, &string_end); if(string_end == string) { //you have an error! } … to something more modern in C++17… std::string st = "3.1416"; double x; auto [p, ec] = std::from_chars(st.data(), st.data() + st.size(), x); if (p == st.data()) { //you have an errors! } Back when I first reported on this result, only Visual Studio had support for from_chars. The C++ library in GCC 12 now has full support for from_chars. Let us run the benchmark again: strtod 270 MB/s from_chars 1 GB/s So it is almost four times faster! The benchmark reads random values in the [0,1] interval. Internally, GCC 12 adopted the fast_float library. Further reading: Number Parsing at a Gigabyte per Second, Software:…

https://lemire.me/blog/2022/07/27/comparing-strtod-with-from_chars-gcc-12/

Science and Technology links (August 7 2022)

Increase in computing performance explain up to 94% of the performance improvements in field such as weather prediction, protein folding, and oil exploration: information technology is a a driver of long-term performance improvement across society. If we stop improving our computing, the consequences could be dire. The coral cover of the Great Barrier Reef has reached its highest level since the Australian Institute of Marine Science (AIMS) began monitoring 36 years ago. Leading Alzheimer’s theory, the amyloid hypothesis, which motivated years of research, was built on fraud. The author of the fraud is professor Sylvain Lesné. His team appeared to have composed figures by piecing together parts of photos from different experiments. Effectively, they “photoshopped” their scientific papers. Not just one or two images, but at least 70. Note that all clinical trials of drugs developed (at high cost) on the amyloid hypothesis have failed. Meanwhile, competing theories and therapies have been sidelined by the compelling amyloid hypothesis. It will be interesting to watch what kind of penalty, if any, Lesné receives for his actions. You may read the testimonies…

https://lemire.me/blog/2022/08/07/science-and-technology-links-august-7-2022/

“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

“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/