File CountLess.h

↰ Parent directory (ADS/search)

The count of the items of a short array smaller than a key, the search in a node of the B-trees in main memory [see File BTreeMap.h and File StaticSearch.h]: on a sorted array of N items it is the place of the key, found with no branch.

Definition (ADS/search/CountLess.h)

Detailed Description

countLess< N >( a , x ) and countLess< N , true >( a , x ), the items not larger than x, read all the N items, which must be there (the unused places of a node are padded with the largest value). greaterBits< N >( a , x ) gives the items larger than x as the bits of a word, N <= 64 [see File WordRangeMinimum.h].

On the integers of 32 and 64 bits and on the floating types they are a few comparisons of vectors, each giving a mask of bits that a count of the bits sums: of AVX-512 (16 items of 32 bits at once) if the target has it, else of AVX2 (8 items), the unsigned integers being compared as signed ones after flipping their top bit; elsewhere, and on the other types, the loop of the comparisons, which the compiler may vectorize or not (GCC 13 does not: it chains the carries of the comparisons, one item per cycle and a dependence from each to the next).

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • bit

  • cstddef

  • cstdint

  • type_traits

Included By

Namespaces

Functions