4 ms·

The readme doesn't describe why it's faster. Looking at the code of the variant that is the fastest: https://github.com/scandum/binary_search/blob/master/binary

by ghj 6y ago

The readme doesn't describe why it's faster. Looking at the code of the variant that is the fastest: https://github.com/scandum/binary_search/blob/master/binary-search.c#L201 https://github.com/scandum/binary_search/blob/master/binary-... It seems like it's a quaternary search which seems like an arbitrary "magic number" of interior points. It's easy to understand what it does if you already know other variants like ternary search (cut search space into 3 to pick 2 interior points) or golden section search (same thing as ternary except in golden ratio). Here, quaternary search is just picking 3 interior points after dividing into 4 parts. So the speed up is the same as how b-trees get their speedup: increase branching factor which costs more comparisons but reduces the depth. I might be wrong, but instead of quaternary it could also be 5-ary or 8-ary or any B-ary and any of these variants can also have the potential to perform better. Just a tradeoff between: cost_of_divide * log_B(N) + cost_of_compare * (B - 1) * log_B(N) EDIT: Thinking about it more, the divison doesn't seem like it should be the most expensive operation (especially relative to compares/branching). Anyone have any better ideas on why you would prefer more compares? Is it some pipelining thing?

BeeOnRope 6y ago
Wider branching factors (3-ary, 4-ary, etc) are less efficient in the total number of comparisons, but give you more memory level parallelism, and large searches are dominated by memory access behavior and critical paths, not total comparisons or instruction throughput. So better MLP can make up for the inefficiency of higher arity searches... to a point. E.g., with 4-ary search, your search tree is half the depth of binary search (effectively, you are doing two levels of binary search in one level), but you do 3x the number of comparisons, so 1.5x more in total. However, the comparison (1 cycle) is very fast compared to the time to fetch the element from memory (5, ~12, ~40, ~200+ cycles for L1, L2, L3 and DRAM hit respectively). The 4-ary search can issue the 3 probes in parallel, and so if the total time is dominated by the memory access, you might expect it to be ~2x faster. In practice, things like branch mispredictions (if the search is branchy) complicate the picture.
- viraptor 6y ago
  Sounds right. I think the fastest solution (of this approach) would do something like: get the Lx-cache-row sized batch; check upper/lower end; depending on result: choose next batch by binary division, or do linear walk to find the match. Not sure if doing it precisely would be an improvement over the magic numbers in the example though. Then again, I'd like to experiment with prefetch here as well. It may be possible to squeeze out even more performance.
  - BeeOnRope 6y ago
    I don't think the trick of checking each end of the cache line helps much, except perhaps at the very end of the search (where there are say low 100s of bytes left in the region). When the region is large it just doesn't cut the search space down almost at all: it's a rounding error. Now you might think it's basically free, but clogging up the OOOE structures with instructions can hurt MLP because fewer memory accesses fit in the window, even if the instructions always completely execute in the shadow of existing misses. There is a similar trick with pages: you might try to favor not touching more pages than necessary, so it might be worth moving probe points slightly to avoid touching a new page. For example, if you just probed at bytes 0 and 8200, the middle is 4100, but that's a new 4k page (bytes 4096 thru 8191), so maybe you adjust it slightly to probe at 4090 since you already hit that page with your 0 probe. Making all of these calculations dynamically is a bit annoying and maybe slow, so it's best if the whole search is unrolled so the probe points according to whatever rules can be calculated at compile time and embedded into the code. Much more important than either of these things is avoiding overloading the cache sets. Some implementations have this habit of choosing their probe points such that only a very small number of sets in the L1, L2 are used so the caching behavior is terrible. Paul Khuong talks about this in detail on pvk.ca. Doing a linear walk at the end definitely helps a bit though: SIMD is fastest for this part.
    - londons_explore 6y ago
      If you want to optimize a data structure for binary search, it sounds like it might be best to reorder the data itself in memory to make caching more effective. For example the first access in a binary search will be the middle element, followed by the lower quartile or upper quartile. If you store all of those together in memory, a single cache line fetch can serve all those requests.
keymone 6y ago
So why is it called binary if it’s not binary?
- DudeInBasement 6y ago
  to grab headlines.
thomasahle 6y ago
If you have some sort of chip that can do B comparisons in parallel, you can search in log(N)/log(B) time.
- BeeOnRope 6y ago
  Any modern chip with SIMD can do comparisons in parallel. For example, almost recent Intel chip can do 16x 32-bit comparisons in a single cycle. The bottleneck is not usually the comparison itself, however, but the data movement needed to gather all the elements to be compared. This cannot be vectorized efficiently since SIMD gathers tend to be inefficient. The story is probably different on GPUs.
deleted 6y ago
[deleted]

by ghj 6y ago

BeeOnRope 6y ago

Wider branching factors (3-ary, 4-ary, etc) are less efficient in the total number of comparisons, but give you more memory level parallelism, and large searches are dominated by memory access behavior and critical paths, not total comparisons or instruction throughput. So better MLP can make up for the inefficiency of higher arity searches... to a point. E.g., with 4-ary search, your search tree is half the depth of binary search (effectively, you are doing two levels of binary search in one level), but you do 3x the number of comparisons, so 1.5x more in total. However, the comparison (1 cycle) is very fast compared to the time to fetch the element from memory (5, ~12, ~40, ~200+ cycles for L1, L2, L3 and DRAM hit respectively). The 4-ary search can issue the 3 probes in parallel, and so if the total time is dominated by the memory access, you might expect it to be ~2x faster. In practice, things like branch mispredictions (if the search is branchy) complicate the picture.

viraptor 6y ago
Sounds right. I think the fastest solution (of this approach) would do something like: get the Lx-cache-row sized batch; check upper/lower end; depending on result: choose next batch by binary division, or do linear walk to find the match. Not sure if doing it precisely would be an improvement over the magic numbers in the example though. Then again, I'd like to experiment with prefetch here as well. It may be possible to squeeze out even more performance.
- BeeOnRope 6y ago
  I don't think the trick of checking each end of the cache line helps much, except perhaps at the very end of the search (where there are say low 100s of bytes left in the region). When the region is large it just doesn't cut the search space down almost at all: it's a rounding error. Now you might think it's basically free, but clogging up the OOOE structures with instructions can hurt MLP because fewer memory accesses fit in the window, even if the instructions always completely execute in the shadow of existing misses. There is a similar trick with pages: you might try to favor not touching more pages than necessary, so it might be worth moving probe points slightly to avoid touching a new page. For example, if you just probed at bytes 0 and 8200, the middle is 4100, but that's a new 4k page (bytes 4096 thru 8191), so maybe you adjust it slightly to probe at 4090 since you already hit that page with your 0 probe. Making all of these calculations dynamically is a bit annoying and maybe slow, so it's best if the whole search is unrolled so the probe points according to whatever rules can be calculated at compile time and embedded into the code. Much more important than either of these things is avoiding overloading the cache sets. Some implementations have this habit of choosing their probe points such that only a very small number of sets in the L1, L2 are used so the caching behavior is terrible. Paul Khuong talks about this in detail on pvk.ca. Doing a linear walk at the end definitely helps a bit though: SIMD is fastest for this part.
  - londons_explore 6y ago
    If you want to optimize a data structure for binary search, it sounds like it might be best to reorder the data itself in memory to make caching more effective. For example the first access in a binary search will be the middle element, followed by the lower quartile or upper quartile. If you store all of those together in memory, a single cache line fetch can serve all those requests.

keymone 6y ago

So why is it called binary if it’s not binary?

DudeInBasement 6y ago
to grab headlines.

thomasahle 6y ago

If you have some sort of chip that can do B comparisons in parallel, you can search in log(N)/log(B) time.

BeeOnRope 6y ago
Any modern chip with SIMD can do comparisons in parallel. For example, almost recent Intel chip can do 16x 32-bit comparisons in a single cycle. The bottleneck is not usually the comparison itself, however, but the data movement needed to gather all the elements to be compared. This cannot be vectorized efficiently since SIMD gathers tend to be inefficient. The story is probably different on GPUs.

deleted 6y ago

[deleted]