Static B-Trees, a data structure for faster binary search - Algorithmica.org / HN

# see also

• 40x Faster Binary Search / slide - exploit everything that modern CPUs have to offer (SIMD, ILP, prefetching, efficient caching) in order to gain 40x increased throughput over the Rust standard library implementation.
• You can beat the binary search / HN - using SIMD
• B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
  • How B-trees can win is by taking advantage of the node children being sorted in an array. This allows a binary search to be used. Binary search makes B-tree more or less equivalent to a very balanced binary tree. - HN - linear search could even be more efficient and cache friendly (assuming small child array).
• Robots Are After Your Job: Exploring Generative AI for C++ - Andrei Alexandrescu - CppCon 2023 - now at NVidia
  • binary search invented in 1946, support odd size in 1957
  • std::lower_bound does not return early - but does only one comparison compared to binary_search
  • 50% improvement on std::equal_range
  • on creativity, judgement and skill (about chatGPT)
• Bug in Binary Search - when taking the middle (l+r)/2, what if m+r overflow your integer ? Rather use l+(r-l)/2.
• Beautiful branchless binary search / HN
• Eytzinger Binary Search / 2 - In addition to being branchless, it also has better cache properties than a standard binary search tree.
• 4K Aliasing - Intel uses 12-bit memory port quick addressing in their hardware, resulting in an issue known as “4K Aliasing” - HN

• cmov - make branches predictable, and only after, use CMOV for the remaining ones. His fundametnal assumption is that “even if you were to know that something is unpredictable, it’s going to be very rare.”. - HN

• Michael Abrash books - C ( and C++ ) does not match hardware anymore. - HN