Cache-friendly binary search

#1

Post by joaquintides » Wed, Jun 24, 2015, 11:15 PM UTC

Cache-friendly binary search
bannalia.blogspot.com

Re: Cache-friendly binary search

#2

Post by serialx » Thu, Jun 25, 2015, 4:15 AM UTC

Or you can use binary search with slightly off-center binary or quaternary (four-way) searches to provide more consistent lookup times:

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

Re: Cache-friendly binary search

#3

Post by kwantam » Thu, Jun 25, 2015, 4:20 AM UTC

A "simple" memory layout for cache friendliness (assuming you don't have to do updates on your tree; there exists a more complicated cache-friendly dynamic tree structure, too) is a recursive van Emde Boas layout. This memory layout will achieve performance no more than a (small) constant multiple worse than an omniscent cache in terms of the number of cache misses, and it requires almost no tuning to work in any caching hierarchy.

http://supertech.csail.mit.edu/cacheObliviousBTree.html

More generally: in the last 10-15 years there has been a lot of work on developing algorithms that are compatible with caching, but which do not need to be tuned to the details of a particular cache hierarchy on which they run. For more info, see

Demaine, Erik D. "Cache-Oblivious Algorithms and Data Structures." http://erikdemaine.org/papers/BRICS2002/paper.pdf

Erik Demaine's 6.046 lectures on this topic are available on YouTube: https://www.youtube.com/watch?v=cJOHERGcGm4 and https://www.youtube.com/watch?v=zjUDy6a5vx4

One cache-oblivious dynamic tree structure is also due to Demaine: http://erikdemaine.org/papers/CacheObliviousBTrees_SICOMP/

Re: Cache-friendly binary search

#4

Post by opcvx » Thu, Jun 25, 2015, 4:44 AM UTC

Sure this is marginally better if you have a static structure, in all other cases you lose.

Re: Cache-friendly binary search

#5

Post by deathy » Thu, Jun 25, 2015, 5:53 AM UTC

Somewhat related maybe? "Memory Layouts for Binary Search" https://news.ycombinator.com/item?id=9511939

I also really liked the nice package there for testing it out yourself, creating results package and clear email instructions for contributing the results.

Is there any good way of running these kinds of experiments on a variety of hardware possibly with other people's help?

Re: Cache-friendly binary search

#6

Post by ntoshev » Thu, Jun 25, 2015, 7:11 AM UTC

kwantam wrote: post #3

A "simple" memory layout for cache friendliness (assuming you don't have to do updates on your tree; there exists a more complicated cache-friendly dynamic tree structure, too) is a recursive van Emde Boas layout. This memory layout will achieve performance no more than a (small) constant multiple worse than an omniscent cache in terms of the number of cache misses, and it requires almost no tuning to work in any cac…

vEB layout has expensive index calculation though, BFS might still be faster.

Re: Cache-friendly binary search

#7

Post by cbsmith » Thu, Jun 25, 2015, 8:05 AM UTC

kwantam wrote: post #3

A "simple" memory layout for cache friendliness (assuming you don't have to do updates on your tree; there exists a more complicated cache-friendly dynamic tree structure, too) is a recursive van Emde Boas layout. This memory layout will achieve performance no more than a (small) constant multiple worse than an omniscent cache in terms of the number of cache misses, and it requires almost no tuning to work in any cac…

Don't discount cache conscious structures like HAT-trie's either. Very zippy.

Re: Cache-friendly binary search

#8

Post by lorenzhs » Thu, Jun 25, 2015, 8:07 AM UTC

kwantam wrote: post #3

A "simple" memory layout for cache friendliness (assuming you don't have to do updates on your tree; there exists a more complicated cache-friendly dynamic tree structure, too) is a recursive van Emde Boas layout. This memory layout will achieve performance no more than a (small) constant multiple worse than an omniscent cache in terms of the number of cache misses, and it requires almost no tuning to work in any cac…

van Emde Boas trees need quite a few tricks in order for an implementation to be truly competitive, but then they can be really quick: "Engineering a Sorted List Data Structure for 32 Bit Keys", Roman Dementiev, Lutz Kettner, Jens Mehnert, Peter Sanders. http://algo2.iti.kit.edu/dementiev/files/veb.pdf - code: http://people.mpi-inf.mpg.de/~kettner/proj/veb/

Re: Cache-friendly binary search

#9

Post by enigmo » Thu, Jun 25, 2015, 3:00 PM UTC

Taken to it's logical extreme: k-Ary Search on Modern Processors

https://people.mpi-inf.mpg.de/~rgemulla/publications/schlege...

As SSE/AVX registers get wider and wider you might as well compare an entire cache line (or two) at a time. But the overhead of building the level order k-tree means you need to do a whole lot of lookups for each insert... so it doesn't apply to that many problems. Unless you're building a search engine. Then it applies a lot.

Re: Cache-friendly binary search

#10

Post by TheLoneWolfling » Thu, Jun 25, 2015, 3:24 PM UTC

Binary search doesn't make much sense on modern processors anyways.

We tend to end up comparing keys that are much smaller than the cache lines - and the memory access takes so long compared to the actual calculation that you may as well check everything in the cacheline "while you're at it".

Which ends up meaning that in practice, you may as well do a k-ary search.

I wonder how much, if any, this can be improved by prefetching the indexes you might access next step?