File StaticSearch.h

↰ Parent directory (ADS/search)

The engineered searches of a sorted array that does not change, beyond the book [see File BinarySearch.h for the binary search of section 1.2]: the place of the first item not smaller than a key, the lower bound, in the fewest misses of the cache and with no branch that the processor may mispredict.

Definition (ADS/search/StaticSearch.h)

Detailed Description

  • branchlessLowerBound() is the binary search with no branch of Khuong and Morin: the part still to examine is a base and a length, the length halves at each step whatever the comparison, which only decides whether the base moves (a conditional move rather than a jump), and the two items that the next step may compare are prefetched, so that the misses of the cache of two steps overlap; :math:` lceil log_2 n rceil + 1 ` comparisons on an array of n > 0 items (the length goes from n to :math:` lceil n / 2 rceil ` at each step, down to 1, and a last comparison decides), none of them mispredicted.

  • SPlusTree is the static B+-tree of Slotin (the S+ tree), the sorted items themselves being its leaves: the items are cut into blocks of B items, B the items of 64 bytes, a line of cache (16 of 32 bits, 8 of 64 bits), and each internal node has B keys and B + 1 children, its key j being the first item below its child j + 1; the nodes of a level are stored one after the other, the children of the node k being the nodes k ( B + 1 ) , … , k ( B + 1 ) + B of the next level, so that no pointer is stored, and the levels one after the other, the leaves last. The level of the leaves has :math:` s_{H-1} = lceil n / B rceil ` nodes and each level above :math:` s_ell = lceil s_{ell+1} / ( B + 1 ) rceil `, up to the root, so that there are :math:`[

    H = 1 + Biglceil log_{B+1} Biglceil frac{n}{B} Bigrceil Bigrceil

    ` levels, and a search reads one line per level, H in all (3 for a million keys of 32 bits, against the 20 probes of the binary search, of which the last 4 share a line). In a node the search counts the keys smaller than the key looked for, which is the child to take: on the arithmetic keys under std::less the count runs on the whole line with no branch, the places past the last item holding the largest value of the type, as one or two comparisons of vectors [see File CountLess.h]; on the others it is a scan of the keys in use. The space is :math:` B sum_ell s_ell approx n ( 1 + frac{1}{B+1} + frac{1}{(B+1)^2} + dots ) = n frac{B+1}{B} ` items, on huge pages when they are at least 2 MB [see File HugePageAllocator.h], so that a search misses the TLB at most once, and the building takes O( n ) time.

Compared with the literature: the layout of Eytzinger (a heap order of the items) also reads one line for the last 4 levels of the binary search, and with the prefetch of the 16 descendants 4 levels down it hides the latency of the misses rather than avoiding them, at the price of the bandwidth; Khuong and Morin found it the fastest of the layouts of the binary search, and the B-tree layout, with a node per line, faster on the arrays that do not fit in the cache. The S+ tree removes from the B-tree of Khuong and Morin the comparison with the key at every level (the leaves are the array, and the internal keys only route), and counts instead of searching in a node; the FAST trees of Kim et al. lay out a binary tree in blocks of lines and pages and search a block with SIMD comparisons, and the comparative study of Bellomo et al. finds the B-trees with SIMD searches the fastest in a lookup among the classic, the compressed and the learned indexes [see File PGMIndex.h] of integers.

The contracts [see File Contract.h]: the array sorted, an audit; each result r is such that the items before r are smaller than the key and those from r on are not, a postcondition checked as an audit. The functions are defined in StaticSearch.tpp. The items of an SPlusTree are trivially copyable.

P.-V. Khuong, P. Morin, Array layouts for comparison-based searching, ACM Journal of Experimental Algorithmics 22, 1.3:1-1.3:39, 2017, doi:10.1145/3053370

  1. Slotin, Algorithms for Modern Hardware, 2022, chapter 13.8 (Static B-trees, the S+ tree), https://en.algorithmica.org/hpc/data-structures/s-tree/

  1. Rao, K. A. Ross, Cache conscious indexing for decision-support in main memory, Proceedings of VLDB 1999, 78-89, 1999 (the CSS trees, B-trees with no pointers)

  1. Kim, J. Chhugani, N. Satish, E. Sedlar, A. D. Nguyen, T. Kaldewey, V. W. Lee, S. A. Brandt, P. Dubey, FAST: fast architecture sensitive tree search on modern CPUs and GPUs, Proceedings of SIGMOD 2010, 339-350, 2010, doi:10.1145/1807167.1807206

  1. Bellomo, G. Cianci, L. de Rosa, P. Ferragina, M. Odorisio, A comparative study of compressed, learned, and traditional indexing methods for integer data, Proceedings of SEA 2025, LIPIcs 338, 5:1-5:23, 2025, doi:10.4230/LIPIcs.SEA.2025.5

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Functions