✳flâneur — a map of the web's best reading

Static B-Trees - Algorithmica

en.algorithmica.org · 5,367 words · saved by 1 readers

This section is a follow-up to the previous one, where we optimized binary search by the means of removing branching and improving the memory layout. Here, we will also be searching in sorted arrays, but this time we are not limited to fetching and comparing only one element at a time. In this section, we generalize the techniques we developed for binary search to static B-trees and accelerate them further using SIMD instructions. In particular, we develop two new implicit data structures: To distinguish them from B-trees — the structures with pointers, hundreds to thousands of keys per node, and empty spaces in them — we will use the names S-tree and S+ tree respectively to refer to these particular memory layouts1. To the best of my knowledge, this is a significant improvement over the existing approaches. As before, we are using Clang 10 targeting a Zen 2 CPU, but the performance improvements should approximately transfer to most other platforms, including Arm-based chips. Use this

This section is a follow-up to the previous one , where we optimized binary search by the means of removing branching and improving the memory layout. Here, we will also be searching in sorted arrays, but this time we are not limited to fetching and comparing only one element at a time. In this section, we generalize the techniques we developed for binary search to static B-trees and accelerate them further using SIMD instructions . In particular, we develop two new implicit data structures: The first is based on the memory layout of a B-tree, and, depending on the array size, it is up to 8x f

Explore this link on the map →

saved by

related reading