On Monday, 30 July 2012 at 15:40:32 UTC, bearophile wrote:
This author writes very detailed analyses of low-level
computational matters, that appear on Reddit. This blog post he
suggests to introduce "offseted binary" or "quaternary search"
instead of binary search in Phobos:
http://www.pvk.ca/Blog/2012/07/30/binary-search-is-a-pathological-case-for-caches/
Bye,
bearophile
My stable sort makes heavy use of binary searches [1], so just
for fun, I tried inserting a ternary search before the binary
search. After some optimizing, I found it ideal to use ternary
search on ranges larger than 8KiB (with 32KiB L1D cache) and
binary search on anything less. While sorting using additional
space saw no improvement, in-place sorting went from 408ms to
371ms. As well, there's a very negligible increase in the number
of comparisons.
[1] https://github.com/Xinok/XSort/blob/master/stablesort.d#L331
