3 ms·

Though, just spitballing here - I'd guess that, in practice, a linear search still tends to handily outperform a binary search (and, by extension, a well-balanc

Though, just spitballing here - I'd guess that, in practice, a linear search still tends to handily outperform a binary search (and, by extension, a well-balanced binary tree) whenever the keys are stored in a compact array. Due to better interaction with the cache and speculative execution.

sam0x17 2y ago
yeah locality of reference is way better as you're traversing the array than as you follow links in the tree
shpongled 2y ago
Definitely depends on the branching factor! There are other encodings like Eytzinger that can provide further improves over "standard" binary search too [1]. [1] https://en.algorithmica.org/hpc/data-structures/binary-search/ https://en.algorithmica.org/hpc/data-structures/binary-searc...
kazinator 2y ago
Suppose the key comparisons are much more expensive than the array or pointer navigation. Like the article does: it says that it is about theory, and it is looking at number of comparisons as the performance measure. The fact that we can search a B-tree node that has, say, 256 children in 8 steps means that the node effectively contains the equivalent of a small balanced binary tree.
kevin_thibedeau 2y ago
It does. The break even point varies by platform but linear will win for sufficiently short arrays.
torginus 2y ago
I remember reading a blogpost about this, they compared binary search on integer keys with a highly-optimized unrolled SIMD linear search. The takeaway was that the break-even point was suprising small - just tens of elements, which is crazy considering a CPU can do like 2x 8-wide AVX2 integer comparisons in a single cycle. Modern CPUs are just that good at executing branchy code. But with B-trees we can have the best of both worlds - trees with a relatively high branch factor, like 16, that can still be tested in one go using SIMD. Another advantage is cache locality - which is one of the reasons B-trees are favored when implementing filesystems - much of the tree doesn't need to be fetched into memory while the parts that do are contiguous in memory.

sam0x17 2y ago

yeah locality of reference is way better as you're traversing the array than as you follow links in the tree

shpongled 2y ago

Definitely depends on the branching factor! There are other encodings like Eytzinger that can provide further improves over "standard" binary search too [1]. [1] https://en.algorithmica.org/hpc/data-structures/binary-search/ https://en.algorithmica.org/hpc/data-structures/binary-searc...

kazinator 2y ago

Suppose the key comparisons are much more expensive than the array or pointer navigation. Like the article does: it says that it is about theory, and it is looking at number of comparisons as the performance measure. The fact that we can search a B-tree node that has, say, 256 children in 8 steps means that the node effectively contains the equivalent of a small balanced binary tree.

kevin_thibedeau 2y ago

It does. The break even point varies by platform but linear will win for sufficiently short arrays.

torginus 2y ago

I remember reading a blogpost about this, they compared binary search on integer keys with a highly-optimized unrolled SIMD linear search. The takeaway was that the break-even point was suprising small - just tens of elements, which is crazy considering a CPU can do like 2x 8-wide AVX2 integer comparisons in a single cycle. Modern CPUs are just that good at executing branchy code. But with B-trees we can have the best of both worlds - trees with a relatively high branch factor, like 16, that can still be tested in one go using SIMD. Another advantage is cache locality - which is one of the reasons B-trees are favored when implementing filesystems - much of the tree doesn't need to be fetched into memory while the parts that do are contiguous in memory.