3 ms·

Of particular interest: Binary Search eliminates Branch Mispredictions http://www.pvk.ca/Blog/2012/07/03/binary-search-star-eliminates-star-branch-mispredictio

by franzb 12y ago

Of particular interest: Binary Search eliminates Branch Mispredictions http://www.pvk.ca/Blog/2012/07/03/binary-search-star-eliminates-star-branch-mispredictions/ http://www.pvk.ca/Blog/2012/07/03/binary-search-star-elimina...

corysama 12y ago
*When it compiles to CMOV intructions.
- pkhuong 12y ago
  I had two points in that post. The first, obvious, one is that binary search can be micro-optimised to combine decent algorithmic properties with an enviable constant factor. The second one is that, when linear search outperforms binary search, it does so by breaking out of the search, which needs conditional branches. Binary search, despite its bad reputation, has conditional branches that are easily converted to conditional moves or masks; even a loopy implementation is amenable to trip count prediction (it's a function of the log of the size of the array). If we must avoid mispredicted branches, binary search is intrinsically a better option than linear search.
  - dmpk2k 12y ago
    Wouldn't cache line misses dominate? Linear search benefits from prefetch.
    - ltta 12y ago
      Modern architectures really necessitate a good understanding of the instruction pipeline and caches to squeeze out the best performance. If I remember correctly, Python's hashtables are initialized with 8 buckets that are linearly searched and then switched to a real hashtable implementation when grown past that size. I have worked with the L4 microkernel where sooo much emphasis was put on keeping instruction and data footprints as small as possible every time the kernel is entered in order not to dirty i- and d-caches. And I have also seen game engine developers do amazing things in this regard. An interesting development in the gaming space is data-oriented-design that deviates from OOP among other things for performance and parallelization. See http://www.slideshare.net/mobile/cellperformance/data-oriented-design-and-c http://www.slideshare.net/mobile/cellperformance/data-orient... (though I don't agree with the three "lies" mentionened, I do like the data-centric approach).
    - pkhuong 12y ago
      True, if you're out of cache, there's a goldilocks zone where linear search works better. I mostly disregard that because *chotomic search is equivalent/quicker in cache and for small arrays, and quicker for large arrays.
scottlamb 12y ago
That (very interesting) pvk.ca blog post seems consistent with the schani.wordpress.com one. In particular, while pvk mentions preferring linear search and schani mentions preferring binary search, those preferences are for slightly different cases. schani says: > If you’re very, very serious about performance and know the array size statically, completely unroll the binary search. and pvk says: > I’ll focus on one specific case that is of interest to me: searching a short or medium-length sorted vector of known size. "Known" here means "known at compile time". And of course he concludes: > In general, I’d just stick to binary search: it’s easy to get good and consistent performance from a simple, portable implementation. Both bloggers use conditional moves to avoid conditional branches; use unrolled versions; and of course use benchmarks to arrive at their conclusions.

by franzb 12y ago

corysama 12y ago

*When it compiles to CMOV intructions.

pkhuong 12y ago
I had two points in that post. The first, obvious, one is that binary search can be micro-optimised to combine decent algorithmic properties with an enviable constant factor. The second one is that, when linear search outperforms binary search, it does so by breaking out of the search, which needs conditional branches. Binary search, despite its bad reputation, has conditional branches that are easily converted to conditional moves or masks; even a loopy implementation is amenable to trip count prediction (it's a function of the log of the size of the array). If we must avoid mispredicted branches, binary search is intrinsically a better option than linear search.
- dmpk2k 12y ago
  Wouldn't cache line misses dominate? Linear search benefits from prefetch.
  - ltta 12y ago
    Modern architectures really necessitate a good understanding of the instruction pipeline and caches to squeeze out the best performance. If I remember correctly, Python's hashtables are initialized with 8 buckets that are linearly searched and then switched to a real hashtable implementation when grown past that size. I have worked with the L4 microkernel where sooo much emphasis was put on keeping instruction and data footprints as small as possible every time the kernel is entered in order not to dirty i- and d-caches. And I have also seen game engine developers do amazing things in this regard. An interesting development in the gaming space is data-oriented-design that deviates from OOP among other things for performance and parallelization. See http://www.slideshare.net/mobile/cellperformance/data-oriented-design-and-c http://www.slideshare.net/mobile/cellperformance/data-orient... (though I don't agree with the three "lies" mentionened, I do like the data-centric approach).
  - pkhuong 12y ago
    True, if you're out of cache, there's a goldilocks zone where linear search works better. I mostly disregard that because *chotomic search is equivalent/quicker in cache and for small arrays, and quicker for large arrays.

scottlamb 12y ago

That (very interesting) pvk.ca blog post seems consistent with the schani.wordpress.com one. In particular, while pvk mentions preferring linear search and schani mentions preferring binary search, those preferences are for slightly different cases. schani says: > If you’re very, very serious about performance and know the array size statically, completely unroll the binary search. and pvk says: > I’ll focus on one specific case that is of interest to me: searching a short or medium-length sorted vector of known size. "Known" here means "known at compile time". And of course he concludes: > In general, I’d just stick to binary search: it’s easy to get good and consistent performance from a simple, portable implementation. Both bloggers use conditional moves to avoid conditional branches; use unrolled versions; and of course use benchmarks to arrive at their conclusions.