File FastBitwise.h

↰ Parent directory (ADS/combinatorial)

The engineered operations on words and on arrays of words, beyond the book [see File Bitwise.h for the broadword tricks of Knuth, which compute the same results by the identities of 7.1.3 alone].

Definition (ADS/combinatorial/FastBitwise.h)

Detailed Description

  • popcount( w , n ) counts the 1 bits of n words by the method of Harley and Seal: 16 vectors at a time are added by a tree of carry-save adders, each a full adder of three vectors of bits in two operations (one ternary logic each on AVX-512), and only the vector of the sixteens is counted, so that a block of 16 vectors costs one count instead of 16; a vector is counted by the instruction of the processor if it has one (AVX-512 VPOPCNTDQ), and otherwise by the table of the 16 nibbles in a shuffle of bytes and the sums of 8 bytes by psadbw (Mula, Kurz and Lemire). The arrays shorter than a block, and every array on a machine without AVX2, are counted by the population count of the processor in four independent sums;

  • popcountAnd( a , b , n ) the 1 bits of the intersection of two arrays in the same way, the size of the intersection of two sets of bits;

  • pdep() and pext() scatter the low bits of x to the 1 bits of a mask and gather them back, by one instruction of BMI2, and otherwise by a loop over the 1 bits of the mask;

  • select( x , r ), the place of the 1 of rank r of x, is the trailing zeros of pdep( 2^r , x ) with BMI2, and otherwise the byte of the 1 by the sums of the bytes of sidewaysSum() and a comparison of the 8 bytes in parallel (Vigna), then the 1 in the byte;

  • mortonEncode() and mortonDecode() are interleave() and deinterleave() of File Bitwise.h by pdep() and pext(), two instructions each way.

The contracts [see File Contract.h]: select( x , r ) needs r < the 1 bits of x. The functions are defined in FastBitwise.tpp.

  1. Mula, N. Kurz, D. Lemire, Faster population counts using AVX2 instructions, The Computer Journal 61(1), 111-120, 2018, doi:10.1093/comjnl/bxx046

  1. Vigna, Broadword implementation of rank/select queries, WEA 2008, LNCS 5038, 154-168, doi:10.1007/978-3-540-68552-4_12

  1. Pandey, M. A. Bender, R. Johnson, A fast x86 implementation of select, arXiv:1706.00990, 2017

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/combinatorial/Bitwise.h (File Bitwise.h)

  • ADS/combinatorial/impl/FastBitwise.tpp

  • bit

  • cstddef

  • cstdint

  • utility

Namespaces

Functions