Our computer hardware exchange data using a standard called PCI Express. Your disk, your network and your GPU are limited by what PCI Express can do. Currently, it means that you are limited to a...
https://lemire.me/blog/2024/04/13/science-and-technology-links-april-13-2024/
We sometimes need to find the greatest common divisor between two integers in software. The fastest way to compute the greatest common divisor might be the binary Euclidean algorithm. In C++20, i...
A reader asked me for some help in computing (1 – sqrt(0.5)) to an arbitrary precision, from scratch. A simpler but equivalent problem is to compute the square root of an integer (e.g., 2). The...
Last year, I looked at writing small “hello world” web applications in various programming languages (Go, JavaScript, Nim…). Go, using nothing but the standard library, did well. In these b...
https://lemire.me/blog/2024/04/06/c-web-app-with-crow-early-scalability-results/
Large language models (e.g., ChatGPT) do better at legal questions than lawyers: Our empirical analysis benchmarks LLMs against a ground truth set by Senior Lawyers, uncovering that advanced mode...
https://lemire.me/blog/2024/03/31/science-and-technology-links-march-31-2024/
Sometimes you need to filter out or filter in data quickly. Suppose that your employer maintains a list of forbidden passwords or URLs or words. You may store them in a relational database and qu...
https://lemire.me/blog/2024/03/31/fast-and-concise-probabilistic-filters-in-python/
In modern C++, as in many popular languages, you can create ‘lambdas’. Effectively, they are potentially anonymous function instances that you can create on the fly as you are programming, po...
https://lemire.me/blog/2024/03/22/passing-recursive-c-lambdas-as-function-pointers/
When programming software, we are working over an abstraction over a system. The computer hardware may not know about your functions, your variables, and your data. It may only see bits and instr...
https://lemire.me/blog/2024/03/17/measuring-your-systems-performance-using-software-go-edition/
Suppose you need to read several files on a server using JavaScript. There are many ways to read files in JavaScript with a runtime like Node.js. Which one is best? Let us consider the various ap...
https://lemire.me/blog/2024/03/12/how-to-read-files-quickly-in-javascript/
Canada has several political parties with elected member of parliament: the Liberals, the Conservatives, the Bloc Québecois, de NDP and the Green. But do they behave as distinct political partie...
https://lemire.me/blog/2024/03/08/how-many-political-parties-rule-canada-fun-with-statistics/
When I was young, science fiction was the genre of choice for many engineers and scientists. But the genre declined significantly in recent years. Part of the problem is the rise dystopian fictio...
https://lemire.me/blog/2024/02/24/book-review-theft-of-fire-by-devon-eriksen/
Modern processor have fancy instructions that can do many operations at one using wide registers: SIMD instructions. Intel and AMD have 512-bit registers and associated instructions under AVX-512...
https://lemire.me/blog/2024/02/19/measuring-energy-usage-regular-code-vs-simd-code/
Intel has release a new generation of server processors (Sapphire Rapids) while the latest AMD technology (Zen 4) is now broadly available. There are extensive comparisons available. Of particula...
https://lemire.me/blog/2024/02/09/json-parsing-intel-sapphire-rapids-versus-amd-zen-4/
A hash function maps values (e.g., strings) into a fixed number of strings, typically smaller than the original. It is useful to compare quickly two long strings, for example. Instead of comparin...
https://lemire.me/blog/2024/02/04/how-fast-is-rolling-karp-rabin-hashing/
One of the established and most popular programming languages is the C programming language. It is relatively easy to learn, and highly practical. Maybe surprisingly, the C programming language k...
In my previous post, I described how you can write a C++ program to estimate your read memory bandwidth. It is not very difficult: you allocate a large memory region and you read it as fast as yo...
https://lemire.me/blog/2024/01/18/how-much-memory-bandwidth-do-large-amazon-instances-offer/
One of the limitations of a compute is the memory bandwidth. For the scope of this article, I define “memory bandwidth” as the maximal number of bytes you can bring from memory to the CPU per...
https://lemire.me/blog/2024/01/13/estimating-your-memory-bandwidth/
Intel and AMD have expanded the x64 instruction sets over time. In particular, the SIMD (Single instruction, multiple data) instructions have become progressively wider and more general: from 64 ...
https://lemire.me/blog/2024/01/11/implementing-the-missing-sign-instruction-in-avx-512/
Parenting does not appear to be able to determine the personality traits of a child. When the last ice age ended, 12,000 years ago, the Sahara was green and full of life. It turned into a desert ...
https://lemire.me/blog/2023/12/30/science-and-technology-links-december-30th-2023/
Our computers do not read or write memory in units of bits or even bytes. Rather memory is accessed in small blocks of memory called “cache lines”. For a given system, the cache line size is ...
https://lemire.me/blog/2023/12/12/measuring-the-size-of-the-cache-line-empirically/
When programming in a JavaScript environment such as Node.js, you might recover raw data from the network and need to convert the bytes into strings. In a system such as Node.js, you may represen...
When you recover textual content from the disk or from the network, you may expect it to be a Unicode string in UTF-8. It is the most common format. Unfortunately, not all sequences of bytes are ...
https://lemire.me/blog/2023/12/05/how-fast-can-you-validate-utf-8-strings-in-javascript/
Suppose that you want to parse quickly 8-bit integers (0, 1, 2, …, 254, 255) from an ASCII/UTF-8 string. The problem comes up in the simdzone project lead by Jeroen Koekkoek (NLnet Labs). You a...
https://lemire.me/blog/2023/11/28/parsing-8-bit-integers-quickly/
Modern web applications often use the http/https protocols. However, when the server and client needs to talk to each other in a symmetrical fashion, the WebSocket protocol might be preferable. F...
https://lemire.me/blog/2023/11/28/a-simple-websocket-benchmark-in-python/
Conventional web applications use the http protocol (or the https variant). The http protocol is essentially asymmetrical: a client application such as a browser issues requests and the server re...
https://lemire.me/blog/2023/11/25/a-simple-websocket-benchmark-in-javascript-node-js-versus-bun/
Vitamin K2 supplements might reduce the risk of myocardial infarction (heart attacks) and of all-cause death (Hasific et al. 2022). You find vitamin K2 in some Gouda cheeses and in eggs. Most of ...
https://lemire.me/blog/2023/11/12/science-and-technology-links-november-12-2023/
Suppose that you want to check whether a character in C++ belongs to a fixed set, such as ‘’, ‘x09’, ‘x0a’,’x0d’, ‘ ‘, ‘#’, ‘/’, ‘:’, ‘<‘, ‘>’, ‘?’, �...
https://lemire.me/blog/2023/11/07/generating-arrays-at-compile-time-in-c-with-lambdas/
In C++, suppose that you append to a string one character at a time: while(my_string.size() <= 10'000'000) { my_string += "a"; } In theory, it might be possible for the C++ runtime library to imp...
The C++ library has long been organized around stream classes, at least when it comes to reading and parsing strings. But streams can be surprisingly slow. For example, if you want to parse numbe...
https://lemire.me/blog/2023/10/19/for-processing-strings-streams-in-c-can-be-slow/
In about 10 years, Apple has multiplied by 19 the number of transistors in its mobile processors. It corresponds roughly to a steady rate of improvement of 34% per year on the number of transisto...
https://lemire.me/blog/2023/10/18/how-many-billions-of-transistors-in-your-iphone-processor/
Computer software is typically deterministic on paper: if you run twice the same program with the same inputs, you should get the same outputs. In practice, the complexity of modern computing mak...
https://lemire.me/blog/2023/10/17/randomness-in-programming-with-go-code/
The Web is a convenient interface to your software. Many times, if you have an existing application, you may want to allow Web access to it using HTTP. Or you may want to build a small specialize...
https://lemire.me/blog/2023/10/07/web-server-hello-world-benchmark-go-vs-node-js-vs-nim-vs-bun/
If I give a programmer a string such as "9223372036854775808" and I ask them to convert it to an integer, they might do the following in C++: std::string s = .... uint64_t val; auto = std::from_...
https://lemire.me/blog/2023/09/22/parsing-integers-quickly-with-avx-512/
In software, we store strings of text as arrays of bytes in memory using one of the Unicode Transformation Formats (UTF), the most popular being UTF-8 and UTF-16. Windows, Java, C# and other syst...
https://lemire.me/blog/2023/09/13/transcoding-unicode-strings-at-crazy-speeds-with-avx-512/
A common problem in parsing is that you want to find all identifiers (e.g., variable names, function names) in a document quickly. There are typically some fixed rules. For example, it is common ...
https://lemire.me/blog/2023/09/04/locating-identifiers-quickly-arm-neon-edition/
Physicists have a published a paper with 5154 authors. The list of authors takes 24 pages out of the 33 pages. The lesson is that if someone tell you that they have published an important paper, ...
https://lemire.me/blog/2023/09/02/science-and-technology-links-september-2-2023/
Though most strings online today follow the Unicode standard (e.g., using UTF-8), the Latin 1 standard is still in widespread inside some systems (such as browsers) as JavaScript strings are ofte...
Given a set of r random values from a large set (of size N), I have been using the formula 1-exp(-r**2/(2N)) to approximate the probability of a collision. It assumes that r is much smaller than ...
https://lemire.me/blog/2023/08/15/how-accurate-is-the-birthdays-paradox-formula/
Most strings online are Unicode strings in the UTF-8 format. Other systems (e.g., Java, Microsoft) might prefer UTF-16. However, Latin 1 is still a common encoding (e.g., within JavaScript runtim...
When you enter in your browser the domain name lemire.me, it eventually gets encoded into a so-called wire format. The name lemire.me contains two labels, one of length 6 (lemire) and one of leng...
https://lemire.me/blog/2023/08/10/coding-of-domain-names-to-wire-format-at-gigabytes-per-second/