SIMD, AVX, AVX2, AVX512, optimization, algorithms, data structures
My sampling of the real world is performed via X, formerly Twitter. And as of the end of 2025, it appears that Rust is the most hated language ever. I noticed that the C and C++ programmers constitute the majority of Rust critics. Despite the critics, Rust is having its momentum — more and more companies are adopting Rust, trying to create new pieces of software using it or just rewriting their…
Introduction Changing letters case is something that appear handy in many situations, for instance input normalization, parsing, and other text-related tasks. When we are dealing with ASCII, such conversion is straightforward. We check if a character code lies in the range 'a' .. 'z' (or 'A' .. 'Z') and when its true, we toggle the 5th bit (0x20). But in the case of Unicode-encoded strings it is…
Introduction I get back to work on simdutf recently, and noticed that the library gained support for LoongArch64 . This is a custom design and custom ISA by Loongson from China. They provide documentation for scalar ISA, but not for the vector extension. Despite that, GCC, binutils, QEMU and other tools already support the ISA. To our luck, Jiajie Chen did an impressive work of reverse engineering…
Introduction Binary heap is a binary tree data structure having some interesting properties. One of them is an array-friendly memory layout, achieved by building (almost) complete binary tree. A binary heap keeps at index 0 the maximum value, or the minimum one depending on convention — let's stick to maximum heaps . There is exactly one invariant: a child node, if exist, keep a value less…
Problem Printing 64-bit numbers in binary format can be done nicely with AVX-512 instructions. First, we populate each byte from the number into a separate 64-bit word of an AVX-512 register: ┌───┬───┬───┬───┬───┬───┬───┬───┐ x = │ h │ g │ f │ e │ d │ c │ b │ a │ └───┴───┴───┴───┴───┴───┴───┴───┘ | | | │ │ │ │ └──────────────────┐ │ │ └──────────┐ │ │ └──────────┐ │ │ └──┐ │ │ │ │ │ │ │ ├─╴┈┈┈╶─┐…
Problem We have a tree of any degree and depth. Each node has assigned a bounding box of its graphical representation. We want to draw such data structure, taking into account geometry of nodes.
Introduction I dedicated the last few days of 2024 on refreshing my website. The project started around 2002, when the Internet was not widespread, there was no GitHub, Wikipedia or anything we know right now. Thus the website served also as a hosting platform for my open-source software. I created custom python software to maintain both the articles and software. In the meantime things evolved. I…
Introduction The BMI2 extension introduced two complementary instructions: parallel bits deposit ( PDEP ) and parallel bits extract ( PEXT ). The PDEP scatters continuous set of bits to positions denoted by the mask. The PEXT does the opposite: gathers/compresses selected bits into a continuous word. SIMD instruction sets do not directly support this kind of operations. There is GF2P8AFFINEQB in…
Introduction This is a follow-up text for Dividing unsigned 8-bit numbers . We checked if dividing 16-bit unsigned numbers is also feasible for SIMD instructions. Apart from obvious path, where we use floating-point division ( DIVPS ), 8-bit numbers could also utilize the approximate reciprocal instruction RCPPS . Unfortunately, for 16-bit numbers the latter instruction cannot be used directly. To…
Introduction Division is quite an expensive operation. For instance, latency of the 32-bit division varies between 10 and 15 cycles on the Cannon Lake CPU, and for Zen4 this range is from 9 to 14 cycles. The latency of 32-bit multiplication is 3 or 4 cycles on both CPU models. None of commonly used SIMD ISAs (SSE, AVX, AVX-512, ARM Neon, ARM SVE) provides the integer division, only RISC-V Vector…
Myriad sequences The RISC-V assembler defines the pseudo-instruction li that load an immediate into a register. Unlike other pseudo-instructions, having one or a few expansions, li explodes into — as the spec says — myriad sequences . RISC-V opcodes have 32 bits, it's impossible to encode 64-bit immediates. It's impossible to encode 32-bit immediates too, as we need to have some spare…
Introduction The goal of this text is to provide an overview of RISC-V Vector extension ( RVV ), and compare — when applicable — with widespread SIMD vector instruction sets: SSE , AVX , AVX-512 , ARM Neon and SVE . The RISC-V architecture defines four basic modes (32-bit, 32-bit for embedded systems, 64-bit, 128-bit) and several extensions . For instance, the support for single…
Introduction One great feature that some of CLI applications and compilers recently gained is providing suggestions in the case of misspellings arguments or options. For instance, Python suggests possible method/fields names, like: >>> 'lower'.is_upper() Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: 'str' object has no attribute 'is_upper'. Did you mean:…
Introduction One of the hardest problem in SIMD is dealing with non-continuous data accesses, that appear pretty common. Data structures based on indices, like graphs or trees, are a good example. CPU vendors introduced instructions GATHER and SCATTER to address these needs. A gather instruction builds a SIMD vector from N values loaded from N addresses. A scatter instruction stores N values from…
Introduction Looking up in a static set of strings is a common problem we encounter when parsing any textual formats. Such sets are often keywords of a programming language or protocol. Parsing HTTP verbs appeared to be the fastest when we use a compile-time trie : a series of nested switch statements. I could not believe that a perfect hash function is not better, and that led to a novel hashing…
Introduction Just for recap, an IPv4 address written in the textual form consists four decimal numbers separated by the dot character. Each number represents an octet (byte), that is in range from 0 to 255. Here are some examples: "10.1.1.12", "127.0.0.1", "255.255.255.0". An IPv4 address is stored in the big-endian byte order . Parsing IPv4 addresses seems to be a trivial task. For example, the…
Introduction When I was browsing the source code of project Ada ( WHATWG-compliant and fast URL parser written in modern C++ ) the following procedure caught my attention: ada_really_inline size_t find_authority_delimiter_special ( std :: string_view view ) noexcept { auto has_zero_byte = []( uint64_t v ) { return (( v - 0x0101010101010101 ) & ~ ( v ) & 0x8080808080808080 ); }; auto…
Introduction The problem is defined as follows: we have separate lanes (32-bit or 64-bit) and want to find the position of the first occurrence of the given byte in each lane. For example, when we look for byte 0xaa in 32-bit lanes: lane 0 lane 1 lane 2 lane 4 ... [00|aa|aa|11] [aa|aa|aa|aa] [aa|11|11|22] [11|22|33|44] ^^ ^^ ^^ position 1 position 0 position 3 position 4 (not found) The result…
Introduction There are several approaches to find lowest common ancestor (LCA). The algorithm showed here does not need extra memory. There's an assumption that we can get the parent node of given node in constant time.
Introduction A well known method of calculating powers of integers is based on the binary representation of an exponent. Let's consider a simple example. Exponent equals y = 9 = 0b1001 ; its value can be expressed as 1 ⋅ 2 0 + 0 ⋅ 2 1 + 0 ⋅ 2 2 + 1 ⋅ 2 3 ; after constant folding it simplifies to 2 0 + 2 3 = 1 + 8 = 9 . Thus x 9 can be expanded into x 2 0 + 2 3 = x 2 0 ⋅ x…
Introduction Suppose we have a binary fraction, that is positive and less than 1: 0. 1 0 1 0 11 000┈┈┈ = 0.671875 | | |│ │ │ │└─╴ 1/2^6 │ │ └──╴ 1/2^5 │ └────╴ 1/2^3 └──────╴ 1/2^1 We want to express it as a ratio of two integer numbers.
Introduction AVX512 lacks of counting trailing zeros ; it supports counting of leading zeros via instruction VPLZCNTD in 32- and 64-bit words. There is the scalar instruction BSF (Bit Scan Forward). To recall how counting the leading zeros is supposed to work, let's see sample 32-bit word: bit 31 bit 0 | | [0000|0001|0111|1000|0011|1100|0000| ^^ ^^^^ 6 trailing zeros An obvious solution would be…
Introduction We want to check if a value belongs to a set. More formally, we want to evaluate the following expression: (x == word_0) or (x == word_1) or ... or (x == word_n) , where x is a vector of words, and word_i is a constant vector. For a four-element set, a naive version of AVX512 assembly code: VPCMPD.BCST $0, (AX), Z1, K1 // K1 = Z1 == word_0 VPCMPD.BCST $0, 4(AX), Z1, K2 // K2 = Z1 ==…
Introduction AVX512 code often needs constants that repeat in 64-, 32-, 16- or 8-bit lanes. Instead of pre-computing such constants as whole 64-byte arrays, we can reduce memory consumption by using explicit or implicit broadcasts. While broadcasts have high throughput, their latencies are quite high. According to uops.info , latencies are 5 cycles (on Skylake-X, Cannon Lake, Ice Lake, Adler…
Introduction At Sneller we had the following problem: there are sixteen 4-bit values, we need a histogram for that limited set. Since the input set has the fixed size of 64 bits, the problem is not that difficult as a generic case. The basic problem we solve is counting how many nibbles are present in the given 64-bit set. Then, the solution to the initial problem is performing the basic step for…
The other day I came across the following line: len * ( "11124811248484" [ type < 14 ? type : 0 ] - '0' ) > 4 ; My first reaction was "WTF", but later I realized that such a hackish code has to be a response to poor compiler optimizations. And taking into account that the code might be quite old, this is a perfect solution. Only a bit unreadable. In fact we have something like len *…
Introduction When we started to use boost::beast library at work, obviously I downloaded its source code. Can't say I am good at navigation across boost libraries, I was just opening random files waiting for compilation completion . My attention was caught by procedure string_to_verb , that translates a HTTP verb into a number, in fact an enum. The most common verbs are GET POST , PUT and DELETE ,…
Every year in January I download the Apache logs for my home page. I run a simple script on the logs to see which articles were popular last year. Sometimes I'm surprised that some old stuff is still being read. The script counts the total number of visits and the unique number of visitors. And this year something strange happened. Below is the head of list: total uniq 651522 7864…
Introduction A quite popular varuint format lets to save an arbitrary integer number on a sequence of bytes. Each byte stores seven bits of information, and the most significant bit indicates whether the given byte is the last one. Decoding such numbers is quite easy, but is not fast. This is the reason why Google came up with their packed varint format, that stores four numbers (from 1 to 4 byte…
Introduction A non-validating parsing from hexadecimal string can be vectorized: Using SSE to convert from hexadecimal ASCII to number . This text shows two validating and vectorized approaches. Parsing algorithms convert 16-byte inputs. They consists two major parts: Validate and convert ASCII digits and letters into 4-bit values (value [0..15]) stored on separate bytes. Merge the 4-bit words…
Problem The problem: there is a bitmask (16-, 32-, 64-bit). We need to scan it backward, starting from the most significant bit. We finish at the last set bit. For instance we scan bits from 15 to 11 in a 16-bit mask 0b1100'1000'0000'0000 . Depending on the bit's value we perform different tasks. Since x86 has instruction BTR it was obvious for me that I should use the idiom bit-test-and-reset.…
Introduction This is follow up to Daniel Lemire's Converting integers to fix-digit representations quickly . The method described here does not use multiplication nor division instructions. It relies only on addition and byte-level comparison. It's weird and slow, though. The main idea is to work directly on the BCD representation. First, we pre-calculate BCD images (16-byte arrays) for individual…
Problem We want to check if at least one integer value is zero. In other words, we are evaluating following expression (for reasonably small N): if ( x0 == 0 or x1 == 0 or ... or xN == 0 ) ... For a three-argument expression GCC 10.2 produces (with -O3 switch) the following x86 code: testl %esi, %esi ; esi == 0? sete %al ; al = 1 if the above condition is true, 0 otherwise testl %edx, %edx sete…
Introduction This year I re-checked the status of autovectorization in the latest GCC and Clang . MSVC was omitted because I didn't see any new version of this compiler on godbolt . More precisely, I didn't believe that there is a difference between versions 19.28 and 19.16 (that was tested two years ago ). Harold Aptroot pointed out that there are some differences in code generated for the AVX2…
Introduction This is a follow up to article SIMDized counting byte in byte stream . In this article only AVX512BW variants are discussed. Performance is analyzed only for the Skylake-X CPU. We want to count how many times given byte appears in a byte stream. The following C++ code shows the naive algorithm: size_t countbyte ( uint8_t * data , size_t size , uint8_t b ) { size_t result = 0 ; for (…
Introduction We want to detect if all bytes stored in a SIMD register (SSE, AVX2, AVX512, Neon etc.) are the same. For example for byte layout in an SSE register like this: [42|42|42|42|42|42|42|42|42|42|42|42|42|42|42|42] We see that all bytes are equal to 42. For this one not all bytes have the same value: [42|42|42|42|42|42|42|42|42|42|42|42|03|42|42|42] The algorithm which uses basic vector…
Introduction Almost two years ago I did an in-depth comparison of autovectorization abilities of popular compilers: GCC , clang , ICC and MSVC . In this text only GCC and clang are considered, as I don't see any new versions of ICC nor MSVC on godbolt.org (drop me a line if I got lost in the multitude of compiler versions). Update 2021-02-17 : MSVC 19.28 status . The question is: "what has changed…
Introduction The value of binomial coefficient k over n can be expressed as n !/( k ! ⋅ ( n − k )!) . This can be simplified to [( n − p ) ⋅ ( n − p + 1) ⋅ … ⋅ ( n )]/ p ! , where p = max( k , n − k ) . Daniel Lemire showed in article Fast divisionless computation of binomial coefficients how efficiently evaluate the latter expression. Can SIMD…
Introduction This article was inspired by Geoff Langdale's text Why Ice Lake is Important (a bit-basher’s perspective) . I'm also grateful Zach Wegner for an inspiring discussion. The AVX512 extension GFNI adds three instructions related to Galois field : VGF2P8MULB ( _mm512_gf2p8mul_epi8 ) — multiply 8-bit integers in the field GF(2 8 ) ; VGF2P8AFFINEINVQB ( _mm512_gf2p8affineinv_epi64_epi8…
Introduction Positional population count (pospopcnt) is a procedure that calculates the histogram for bits placed at given position in a byte, word or double word etc. from larger stream of such entities. This is a very naive implementation of 8-bit pospopcnt: void pospopcnt ( const uint8_t * data , size_t n , uint64_t histogram [ 8 ]) { for ( size_t i = 0 ; i < n ; i ++ ) { const uint8_t byte =…
Introduction There are two main purposes of a switch statement: Express simple function that translate from one set of values into another, like getting a string representation of enum values. Dispatch different code sequences based on switch argument, as an alternative to "if-ladder". Compilers usually transform switch statements using following approaches: Binary search on constant keys: a…
Introduction When we allocate memory using malloc or another interface, like operator new in C++, we get a pointer and promise that nobody else would acquire the same memory area. But underneath, more memory is needed. For instance the allocator has to keep the size of block to implement realloc . More important is that the allocator unlikely allocate the exact number of bytes we requested, rather…
Introduction Update 2021-02-17 : please check the newest status of GCC & Clang , and MSVC . The term "auto-vectorization" means the ability of a compiler to transform given scalar algorithm into vectorized one, i.e. express dominating operation(s) using SIMD instruction. I'm sure nobody would argue that auto-vectorization is as important as scalar optimizations performed by compilers. Now…
Introduction We want to count how many times given byte occurs in a byte stream; here is a C program doing this: #include <stdint.h> #include <stddef.h> size_t countbyte ( uint8_t * data , size_t size , uint8_t b ) { size_t result = 0 ; for ( size_t i = 0 ; i < size ; i ++ ) result += ( data [ i ] == b ); return result ; } GCC vectorization The current GCC vectorization algorithm is able to handle…
Overloaded functions Let us consider this simple use case, where we want to invoke a function: void invoke_callback ( std :: function < void ( int , int ) > ); Everything works fine when a callback is a lambda. auto callback = []( int , int ){}; invoke_callback ( callback ); When we have overloaded functions , there are problems, as the compiler is not able to select a proper overload. void…
Introduction pyahocorasick is a python module I started in 2011. That time I was interested in stringology and the Aho-Corasick algorithm appeared to be quite challenging. It was a sufficient reason to program it. However, I also decided that the result shouldn't be another proof-of-concept, that nobody --- except me — would use. Since I like Python, I chose form of a C extension, which…
Introduction To my surprise I quite often need to read the whole contents of a file into a string. Sometimes it's easier to generate data with an external program, sometimes unittests require to read generated file, etc. A signature of such loader function is: std :: string load_file ( const std :: string & path ); In C++ an official way to deal with files are streams. There are at least two…
Introduction Removing spaces from a string is a common task in text processing. Instead of removing single character we often want to remove all the white space characters or the punctuation characters etc. In this article I show an AVX512VBMI implementation. The algorithm is not faster than the scalar code for all cases. But for many it can be significantly faster, and what is more important, in…
I need to copy a file to another directory whenever it got changed. The easiest way to do this is to check the modification time of file, a number of seconds since epoch: import os def get_mtime ( path ) return os . stat ( path ) . st_mtime It's not the most reliable way, but in my case it was good enough. Up to the time when I noticed that sometimes files didn't get updated. I figured out that…
Introduction This is the second part of SIMDized sum of all bytes in the array . The first part describes summing unsigned bytes, here we're going to experiment with summing of signed bytes. The baseline C implementation is: int32_t sumbytes ( int8_t * array , size_t size ) { int32_t result = 0 ; for ( size_t i = 0 ; i < size ; i ++ ) result += int32_t ( array [ i ]); return result ; } And the C++…