Binary search is a pathological case for caches (opens in new tab)

(pvk.ca)

80 pointskinetik13y ago13 comments

13 comments

Here's a fun and relevant paper:

A Comparison of Cache Aware and Cache Oblivious Static Search Trees Using Program Instrumentation

http://www.cs.amherst.edu/~ccm/cs34/papers/ladnerbst.pdf

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

dmpk2k13y ago

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.

koverstreet13y ago

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.

2 more replies

steerb13y ago

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

keenerd13y ago

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

koverstreet13y ago

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 < 20 ns.

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.

j / k navigate · click thread line to collapse

13 comments

brooksbp13y ago

Here's a fun and relevant paper:

A Comparison of Cache Aware and Cache Oblivious Static Search Trees Using Program Instrumentation

http://www.cs.amherst.edu/~ccm/cs34/papers/ladnerbst.pdf

koverstreet13y ago

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

dmpk2k13y ago

Good lord. You didn't read the article _at all_.

koverstreet13y ago

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.

2 more replies

steerb13y ago

Using the heap layout, you can sometimes even eliminate branch misspredictions and subsequent (expensive) pipeline flushes.

For a complete explanation, see http://algo2.iti.kit.edu/sanders/papers/ssss.ps.gz

keenerd13y ago

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

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.

koverstreet13y ago

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

That means that if nothing is in cache, worst case each loop iteration will take < 20 ns.

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.

j / k navigate · click thread line to collapse