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

see also

• 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