Memory Layouts for Binary Search

One of the main points from Herb Sutter's talk is your prefetcher is a cache of infinite size. This is why Radix destroys other in-memory sorting algorithms and why the way you access data is the most critical performance thing you should focus on.

It's also incredibly hard to retrofit when you find out you really need that performance back.

flgr3• 11 years ago

Or phrased with a bit more seasoning:

"Reading from L1 cache is like grabbing a piece of paper from your desk (3 seconds), L2 cache is picking up a book from a nearby shelf (14 seconds), main system memory is taking a 4-minute walk down the hall to buy a Twix bar, and waiting for a hard drive seek is like leaving the building to roam the earth for one year and three months." — Gustavo Duarte (http://duartes.org/gustavo/blog/post/what-your-computer-does...)

lorenzhs2• 11 years ago

Another thing that matters enormously is branch misprediction. For example, super scalar sample sort beats GNU's (stupefyingly fast) std::sort by 35-50% on average. I benchmarked skewed quicksort vs std::sort vs super scalar sample sort in a totally artificial setting (sorting a permutation of 0 to n-1) for a lecture: https://github.com/lorenzhs/quicksort-pivot-imbalance

(Repository does not contain the super scalar sample sort code, I don't have the rights to publish that unfortunately. I used the authors' old Pentium 4 optimized code from the paper linked at the bottom (incl PDF).)

Edit: super scalar sample sort also has large data locality benefits over quicksort, the "wavy" line for ssssort shows the caches' impact. I haven't studied that aspect in detail yet.

nicknash2• 11 years ago

Very cool. In my experience, using a skewed pivot doesn't actually help in practice. Outside of the case you mention (where the input is a random permutation), sampling must be used to choose a skewed pivot, which has a fairly significant overhead.

danbruc• 11 years ago

Here is a really good article on the topic [1], »Binary Search Is a Pathological Case for Caches«.

[1] http://www.pvk.ca/Blog/2012/07/30/binary-search-is-a-patholo...

gsg• 11 years ago

Interesting.

A while back I did some rough tests on search of arrays in depth first order. The hope was that the better contiguity (the next element in the array is the next element to test 50% of the time) would lead to better search performance, but I wasn't able to observe much of a difference in practice.

I also found that while writing the search operation was very easy for arrays in this order, insertion was much more difficult.

codepie• 11 years ago

Deciding memory layout is a sub-task of designing cache-oblivious algorithms. Cache-oblivious algorithms optimize the number of memory transfers. I found this very interesting http://erikdemaine.org/papers/BRICS2002/paper.pdf

agumonkey• 11 years ago

Everything Demaine works on look so new, simple and interesting. Succint DS, origami/folds proofs, now this.

flgr3• 11 years ago

Sorry for the blatant plug, but it might be relevant — in my M.Sc. thesis I surveyed main memory optimized index techniques and also provided some background for why traditional binary search is not very optimized for modern hardware. There's lots of illustrations and I cite some great material. :)

See here: https://www.researchgate.net/profile/Florian_Gross/publicati...

Along those lines:

* CSS Trees: Pointerless b-Trees with a layout optimized for cache lines (http://www.vldb.org/conf/1999/P7.pdf)

* Intel & Oracle's fast architecture-sensitive tree search (combines huge pages, cache line blocking, and SIMD in an optimal layout): http://www.researchgate.net/profile/Jatin_Chhugani/publicati...

* Adaptive radix trees (http://codematch.muehe.org/~leis/papers/ART.pdf)

misframer• 11 years ago

ResearchGate is currently down for maintenance, but we'll be back online very soon.

Do you have a mirror?

flgr3• 11 years ago

Since I haven't set up any other domain to put it right now (should get to that), I put it here:

http://webclonk.flgr.me/index-search-modern-cpus.pdf

Memory Layouts for Binary Search

Related Stories