Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Binary search is a pathological case for caches

pvk.ca

Post reply on HN
Print view View original

11–17 of 17 posts

Re: Binary search is a pathological case for caches

#11

Post by [deleted] »

dmpk2k wrote: post #5
koverstreet wrote: post #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/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.

[deleted]

Re: Binary search is a pathological case for caches

#12

Post by koverstreet »

to3m wrote: post #10
koverstreet wrote: post #8

Earlier quoted context omitted.

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 some…

Yeah, I get that. What I was getting at is that binary searches are terrible in general are _terrible_ as soon as you're not hitting cache anymore - and for any problem worth optimizing that's what happens, if nothing else because your data set doesn't fit in l2 anymore.

Worrying about stuff not being cached because of associativity is pointless when the last 5-10 levels aren't going to be in cache anyways because they don't fit; those last 5-10 cache misses are going to _utterly dominate_ your search time.

IOW, even if associativity isn't a problem at all, binary searches suck w.r.t. caches - I'm not at all saying they're wrong, just that it's not terribly relevant - if performance matters you need to be doing something other than a binary search.

Re: Binary search is a pathological case for caches

#13

Post by keenerd »

koverstreet wrote: post #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/driv…

> Optimal is a binary search tree in an array, like the way heaps are implemented.

Not quite. The heap layout has bad spatial locality. Think about the last row of leaves - it occupies the last 50% of the array. The next-to-last-row (all their parents) is in the middle 25%-50%. All those leaves are far away from their parents, and thus the heap is not optimal.

Better is to cluster parents and children into small groups. With clusters of three, two thirds of the time a child will adjacent to its parent.

Re: Binary search is a pathological case for caches

#14

Post by koverstreet »

keenerd wrote: post #13
koverstreet wrote: post #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/driv…

> Optimal is a binary search tree in an array, like the way heaps are implemented. Not quite. The heap layout has bad spatial locality. Think about the last row of leaves - it occupies the last 50% of the array. The next-to-last-row (all their parents) is in the middle 25%-50%. All those leaves are far away from their parents, and thus the heap is not optimal. Better is to cluster parents and children into small grou…

There's a tradeoff between latency and amount of memory touched.

The beautiful thing about the heap layout is that you can prefetch more than one level ahead. If your keys are 4 bytes, 16 of them fit on a cacheline, and you can prefetch 4 levels ahead with a single cacheline.

That means that if nothing is in cache, worst case each loop iteration will take With any kind of clustering (really, it's just a variation on B-trees) you touch less memory but you can't prefetch as far ahead.

In practice I suspect a 4-ary heap would perform better than a binary heap for my application, but there's a bunch of math I'd have to work out again that was hard enough for the binary tree version.

Not quite sure how what you're describing would work, but I can't see offhand how you'd implement it without losing the prefetching the heap layout gives you.

Re: Binary search is a pathological case for caches

#15

Post by chiraagj »

koverstreet wrote: post #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/driv…

So i think the whole point of the exercise was that he doesn't care about the first iteration. Only the subsequent ones when the keys are already cached. In these scenarios the misses on attempt 1 don't count, which is what you are optimizing. Look at the way he generates data 10 runs of 100k each and then selects 1000 points. Only 10 runs out of 1M incur the misses. Thus they almost never show up. Which brings to my very own comment - "Why not pre-allocate the future log(n) keys in a separate array and fill it up on run 1?". This is the natural way of looking at the solution. You are just helping the cache, store exactly what you need.

Re: Binary search is a pathological case for caches

#17

Post by saurik »

dmpk2k wrote: post #7
koverstreet wrote: post #6

Earlier 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.

So, a "binary search tree in an array, like the way heaps are implemented" actually would not experience the problem described in this article. The typical layout of the tree for a heap is "breadth-first, level-order" as opposed to the "depth-first, in-order" tree that is implicit to a sorted array. This means that your accesses to the first couple levels are in the same cache line, and your subsequence accesses as you move down the tree are less likely to line up. This is definitely not to say this is "optimal", however.
Post reply on HN