Binary search is a pathological case for caches
1–10 of 17 posts
Re: Binary search is a pathological case for caches
#2b-trees
Re: Binary search is a pathological case for caches
#3...This is news? You've got a tight loop with a branch, and depending on which way the branch goes, you're going to touch completely different locations in memory.
The solution (at least for some problems) is just to lay your data out in memory better - optimal is a binary search tree in an array, like the way heaps are implemented.
That's what I did for bcache: http://evilpiepirate.org/git/linux-bcache.git/tree/drivers/m...
Re: Binary search is a pathological case for caches
#4...This is news? You've got a tight loop with a branch, and depending on which way the branch goes, you're going to touch completely different locations in memory. The solution (at least for some problems) is just to lay your data out in memory better - optimal is a binary search tree in an array, like the way heaps are implemented. That's what I did for bcache: http://evilpiepirate.org/git/linux-bcache.git/tree/driv…
Using the heap layout, you can sometimes even eliminate branch misspredictions and subsequent (expensive) pipeline flushes.
The basic idea is to allow your compiler to use predicated instructions. Do do this, you have to transform control dependencies (e.g., `if (a > b)`) to data dependencies on index computations (e.g., `j = 2*j + (a > b)`).
For a complete explanation, see http://algo2.iti.kit.edu/sanders/papers/ssss.ps.gz
Re: Binary search is a pathological case for caches
#5...This is news? You've got a tight loop with a branch, and depending on which way the branch goes, you're going to touch completely different locations in memory. The solution (at least for some problems) is just to lay your data out in memory better - optimal is a binary search tree in an array, like the way heaps are implemented. That's what I did for bcache: http://evilpiepirate.org/git/linux-bcache.git/tree/driv…
Good lord. You didn't read the article _at all_.
I have some really ugly things to say to a new poster who cannot be bothered to read an article before trying to show off, but I'll refrain. In the future, read first, think, then comment. You'll be doing everyone else a favor.
Re: Binary search is a pathological case for caches
#6...This is news? You've got a tight loop with a branch, and depending on which way the branch goes, you're going to touch completely different locations in memory. The solution (at least for some problems) is just to lay your data out in memory better - optimal is a binary search tree in an array, like the way heaps are implemented. That's what I did for bcache: http://evilpiepirate.org/git/linux-bcache.git/tree/driv…
Good lord. You didn't read the article _at all_. I have some really ugly things to say to a new poster who cannot be bothered to read an article before trying to show off, but I'll refrain. In the future, read first, think, then comment. You'll be doing everyone else a favor.
I did read it. And none of that stuff about cache behavior _matters_ when your data isn't in cache and you're spending 70 ns on every loop iteration waiting for the next key to fetch from dram.
One of the first things to learn about caches is how dependent modern processors are on prefetching, and a binary search just completely breaks prefetching.
Re: Binary search is a pathological case for caches
#7Earlier quoted context omitted.
Good lord. You didn't read the article _at all_. I have some really ugly things to say to a new poster who cannot be bothered to read an article before trying to show off, but I'll refrain. In the future, read first, think, then comment. You'll be doing everyone else a favor.
I did read it. And none of that stuff about cache behavior _matters_ when your data isn't in cache and you're spending 70 ns on every loop iteration waiting for the next key to fetch from dram. One of the first things to learn about caches is how dependent modern processors are on prefetching, and a binary search just completely breaks prefetching.
No, you did not. If you had, there is absolutely no way you could have written:
"optimal is a binary search tree in an array, like the way heaps are implemented."
I leave it to other people to read the article first, then your comment, then vote accordingly. For shame.
Re: Binary search is a pathological case for caches
#8Earlier quoted context omitted.
I did read it. And none of that stuff about cache behavior _matters_ when your data isn't in cache and you're spending 70 ns on every loop iteration waiting for the next key to fetch from dram. One of the first things to learn about caches is how dependent modern processors are on prefetching, and a binary search just completely breaks prefetching.
No, you did not. If you had, there is absolutely no way you could have written: "optimal is a binary search tree in an array, like the way heaps are implemented." I leave it to other people to read the article first, then your comment, then vote accordingly. For shame.
If I'm wrong, enlighten me.
Thus far all you've got is ad hominem arguments.
Anyways, I didn't come here to show off, but I did implement a b+ tree that can do > 1 million random lookups/second on a single core, on a > 100 mb tree. So believe it or not, I might know what I'm talking about.
Re: Binary search is a pathological case for caches
#9Earlier quoted context omitted.
Good lord. You didn't read the article _at all_. I have some really ugly things to say to a new poster who cannot be bothered to read an article before trying to show off, but I'll refrain. In the future, read first, think, then comment. You'll be doing everyone else a favor.
I did read it. And none of that stuff about cache behavior _matters_ when your data isn't in cache and you're spending 70 ns on every loop iteration waiting for the next key to fetch from dram. One of the first things to learn about caches is how dependent modern processors are on prefetching, and a binary search just completely breaks prefetching.
Ahem. It depends on the workload.
If you regularly search for the same stuff with binary search in a large array, at some size limit your set-associative caches will run out due to aliasing. At that point your data is then never in the cache, even though you could only be accessing 30 or 40 different words of memory.
Re: Binary search is a pathological case for caches
#10Earlier quoted context omitted.
No, you did not. If you had, there is absolutely no way you could have written: "optimal is a binary search tree in an array, like the way heaps are implemented." I leave it to other people to read the article first, then your comment, then vote accordingly. For shame.
If I'm wrong, enlighten me. Thus far all you've got is ad hominem arguments. Anyways, I didn't come here to show off, but I did implement a b+ tree that can do > 1 million random lookups/second on a single core, on a > 100 mb tree. So believe it or not, I might know what I'm talking about.
TL;DR - If your element sizes are powers of two, and your cache is set-associative, you run the risk of set aliasing. Caches always use lower bits of the address as the key, probably because it's really fast.
If you have more aliases than there are ways in each set, items will become evicted from the cache. If you do it just right, you can end up with the worst case, and you get 100% cache misses. Therefore even something that might on the face of it seem perfectly cacheable (well... if you don't know quite how the cache works), with a small working set (note that the test involves repeating the same search over and over again), can actually end up suffering from 100% cache misses.
The L2 and L3 caches use physical addresses rather than virtual ones, so you can't fully control this effect from user mode.
(Fingers crossed for my terminology...)