4 ms·

Cool! I wonder if you can improve things even more by running several binary searches at once, by interleaving several of them together, then combine the result

Cool! I wonder if you can improve things even more by running several binary searches at once, by interleaving several of them together, then combine the results. This way there is work for the CPU to do during the data load latencies (or write back if it's not fully bypassed).

seattlewag 12y ago
That does sound like a pretty powerful optimization!
readerrrr 12y ago
I'm not an expert, but I think cpu can't do anything during a stall.
- sliverstorm 12y ago
  You can schedule another thread, if you have SMT. You can execute out-of-order to try avoiding the stall. But in general you are right in that once a stall happens, you aren't going anywhere.
  - jhallenworld 12y ago
    >You can execute out-of-order to try avoiding the stall. Exactly. By running multiple interleaved branch-free binary searches at once you offer independent work to the out of order engine.
qwerta 12y ago
Why? Do you have a task which requires that? What you want is called fork & join, pretty much standard in Java 8 and Scala.
- jhallenworld 12y ago
  I doubt it's worth forking to parallelize a small search.
  - qwerta 12y ago
    fork join framework takes care of that.
a_e_k 12y ago
You could perhaps implement std::equal_range() [0] that way. It behaves somewhat similarly to doing two slightly different binary searches (to find both the lower and upper bounds on where a key could be legally inserted into a sorted range). [0] http://en.cppreference.com/w/cpp/algorithm/equal_range http://en.cppreference.com/w/cpp/algorithm/equal_range
jhallenworld 12y ago
Well I tried it on an IvyBridge Xeon E5-2680-V2, gcc version 4.4.3 with -O3, table size = 32. Single table at a time ends up being faster: 155 M searches / sec for one table at a time. 108 M searches / sec for two tables at a time. 88 M searches / sec for four tables at a time. The interleaved version of the code looks like this (for two at a time): #define LOGSIZE 5 unsigned dsearch (unsigned key, unsigned * vector) { unsigned size = (1 << LOGSIZE) / 2; unsigned * low1 = vector; unsigned * low2 = vector + ((1 << LOGSIZE) / 2); unsigned i; for (i = LOGSIZE - 1; i != 0; i--) { size /= 2; unsigned mid1 = low1[size]; unsigned mid2 = low2[size]; if (mid1 <= key) low1 += size; if (mid2 <= key) low2 += size; } if (*low2 == key) low1 = low2; return low1 - vector; } The compiled code ends up branch free (gcc does a good job), but is 30 instructions instead of 18. Oh well, was worth a shot..
- nkurz 12y ago
  Excellent for doing the the actual test! My interpretation might be the opposite of yours: it's not that the interleaved version fails to overcome the latency, rather the apparently one-at-a-time version is already able to issue all the loads speculatively, and thus isn't being hurt (much?) by latency. If the addresses are known ahead of time, processors are great about issuing loads as soon as possible. They 'retire' them in order, but if the situation is right they can 'execute' them dozens of cycles ahead of time, even across loop iterations. My guess would be that the slowdown from the interleaved searches is because spreading the loads across multiple cachelines actually works against you, since stalls become more rather than less frequent. Ivy Bridge can have (about?) 10 outstanding L1 requests, which it can issue two per cycle. With a 5 cycle (I think?) L1 latency, this is enough to cover up the latency. Sustaining the two loads per cycle is hard, though, since only 4 ops per cycle can retired. But there are not many other operations here, so the unrolled loop may come close.
- tjpoutanen 12y ago
  I think the reason it's slower for you is that the CPU pipeline is starved for data... even when it is in the same cache line. Since we are geeking out on binary search on a Saturday night, here's an approach I developed for traversing multiple binary trees in parallel with SIMD instructions, no branches and data prefetching. It's used at Bing to calculate the document score that ranks Web search results, and traverses thousands of Machine Learning derived decision trees. It resulted in a 4x speedup over the naive approach. http://web.cse.ohio-state.edu/~ren/papers/CGO13_BinRen.pdf http://web.cse.ohio-state.edu/~ren/papers/CGO13_BinRen.pdf

seattlewag 12y ago

That does sound like a pretty powerful optimization!

readerrrr 12y ago

I'm not an expert, but I think cpu can't do anything during a stall.

sliverstorm 12y ago
You can schedule another thread, if you have SMT. You can execute out-of-order to try avoiding the stall. But in general you are right in that once a stall happens, you aren't going anywhere.
- jhallenworld 12y ago
  >You can execute out-of-order to try avoiding the stall. Exactly. By running multiple interleaved branch-free binary searches at once you offer independent work to the out of order engine.

qwerta 12y ago

Why? Do you have a task which requires that? What you want is called fork & join, pretty much standard in Java 8 and Scala.

jhallenworld 12y ago
I doubt it's worth forking to parallelize a small search.
- qwerta 12y ago
  fork join framework takes care of that.

a_e_k 12y ago

You could perhaps implement std::equal_range() [0] that way. It behaves somewhat similarly to doing two slightly different binary searches (to find both the lower and upper bounds on where a key could be legally inserted into a sorted range). [0] http://en.cppreference.com/w/cpp/algorithm/equal_range http://en.cppreference.com/w/cpp/algorithm/equal_range

jhallenworld 12y ago

Well I tried it on an IvyBridge Xeon E5-2680-V2, gcc version 4.4.3 with -O3, table size = 32. Single table at a time ends up being faster: 155 M searches / sec for one table at a time. 108 M searches / sec for two tables at a time. 88 M searches / sec for four tables at a time. The interleaved version of the code looks like this (for two at a time): #define LOGSIZE 5 unsigned dsearch (unsigned key, unsigned * vector) { unsigned size = (1 << LOGSIZE) / 2; unsigned * low1 = vector; unsigned * low2 = vector + ((1 << LOGSIZE) / 2); unsigned i; for (i = LOGSIZE - 1; i != 0; i--) { size /= 2; unsigned mid1 = low1[size]; unsigned mid2 = low2[size]; if (mid1 <= key) low1 += size; if (mid2 <= key) low2 += size; } if (*low2 == key) low1 = low2; return low1 - vector; } The compiled code ends up branch free (gcc does a good job), but is 30 instructions instead of 18. Oh well, was worth a shot..

nkurz 12y ago
Excellent for doing the the actual test! My interpretation might be the opposite of yours: it's not that the interleaved version fails to overcome the latency, rather the apparently one-at-a-time version is already able to issue all the loads speculatively, and thus isn't being hurt (much?) by latency. If the addresses are known ahead of time, processors are great about issuing loads as soon as possible. They 'retire' them in order, but if the situation is right they can 'execute' them dozens of cycles ahead of time, even across loop iterations. My guess would be that the slowdown from the interleaved searches is because spreading the loads across multiple cachelines actually works against you, since stalls become more rather than less frequent. Ivy Bridge can have (about?) 10 outstanding L1 requests, which it can issue two per cycle. With a 5 cycle (I think?) L1 latency, this is enough to cover up the latency. Sustaining the two loads per cycle is hard, though, since only 4 ops per cycle can retired. But there are not many other operations here, so the unrolled loop may come close.
tjpoutanen 12y ago
I think the reason it's slower for you is that the CPU pipeline is starved for data... even when it is in the same cache line. Since we are geeking out on binary search on a Saturday night, here's an approach I developed for traversing multiple binary trees in parallel with SIMD instructions, no branches and data prefetching. It's used at Bing to calculate the document score that ranks Web search results, and traverses thousands of Machine Learning derived decision trees. It resulted in a 4x speedup over the naive approach. http://web.cse.ohio-state.edu/~ren/papers/CGO13_BinRen.pdf http://web.cse.ohio-state.edu/~ren/papers/CGO13_BinRen.pdf