Trying to speed up binary search • Hacker News Board

Re: Trying to speed up binary search

#21

Post by derf_ » Thu, Dec 17, 2015, 2:16 AM UTC

nkurz wrote: post #16

acqq wrote: post #7

"Apparently the conditional move is good to avoid branch mispredictions, but cannot hide memory latency as much as the regular implementation." Anybody knows what actually happens there? For a real analysis I'd like to see the generated assembly in a classic and conditional move case, and also an example of the indexes accessed in one and another algorithm.

I did some preliminary testing on this a few months ago, which we might pick up again someday and try to publish as a short paper. I haven't looked closely yet at what the author did, and I've forgotten some details of what I did, but I can speak generally to our implementation comparing branching and branchless. For repeated lookups, the first couple levels will all be hit in L1 cache regardless of which way the com…

You can also change the memory layout to that of a binary heap, instead of the usual sorted order. That puts the next index at either (2i + 1) or (2i + 2). With proper alignment, those will be in the same cache line up to 4 iterations in the future, regardless of which way you descend the tree. So you can do a branchless prefetch version with much better than a 50% prefetch accuracy. This only helps once you're hitting L3 cache, though.

See https://news.ycombinator.com/item?id=10410676 for previous discussion.

Re: Trying to speed up binary search

#22

Post by gfody » Thu, Dec 17, 2015, 2:23 AM UTC

acqq wrote: post #7

"Apparently the conditional move is good to avoid branch mispredictions, but cannot hide memory latency as much as the regular implementation." Anybody knows what actually happens there? For a real analysis I'd like to see the generated assembly in a classic and conditional move case, and also an example of the indexes accessed in one and another algorithm.

I experimented with cmov for a lot of cpu-bound graphics routines years ago and found that it was rarely faster than branching and never faster than a branchless version w/o cmov. The folks on c.l.a.x said this was due to cmov being microcoded on modern CPUs and so under the hood your still just branching and the only benefit really was instruction cache.

Re: Trying to speed up binary search

#23

Post by nkurz » Thu, Dec 17, 2015, 3:00 AM UTC

gfody wrote: post #22

acqq wrote: post #7

"Apparently the conditional move is good to avoid branch mispredictions, but cannot hide memory latency as much as the regular implementation." Anybody knows what actually happens there? For a real analysis I'd like to see the generated assembly in a classic and conditional move case, and also an example of the indexes accessed in one and another algorithm.

I experimented with cmov for a lot of cpu-bound graphics routines years ago and found that it was rarely faster than branching and never faster than a branchless version w/o cmov. The folks on c.l.a.x said this was due to cmov being microcoded on modern CPUs and so under the hood your still just branching and the only benefit really was instruction cache.

I don't know when the change was made, but conditional moves are fast and efficient on the last several generations of AMD and Intel processors. Usually, you are trading 1 or 2 extra cycles of latency against the chance of a ~15 cycle mispredicted branch penalty. If your branch cannot be predicted correctly ~85% of the time, this can be a significant win.

Re: Trying to speed up binary search

#24

Post by gpderetta » Thu, Dec 17, 2015, 8:39 AM UTC

nkurz wrote: post #20

acqq wrote: post #18

Earlier quoted context omitted.

OK, but binary search shouldn't have predictable patterns? So in a classic example, if the search isn't "obvious" 50% of the time we'd have an "unconditional" MOV, removing dependencies but also 50% of the time we'd have wrongly predicted branch. Maybe the testing was on a too obvious example?

Sorry, my phrasing was poor. The searched for elements are indeed random, but the first few (and last few) accesses will hit cache. Depending on the size of the total array, the relative importance of the different access times vary. We were actually comparing some different memory layouts besides the standard "sorted" ( http://cglab.ca/~morin/misc/arraylayout/ ). Our conclusion was essentially that with proper imple…

Another way to see this is that the 'branchy' version can have multiple loads pending at the same time. This is a big win for non L1-cached loads.

Cmov forces each load to depend on the previous one, so you will have only one load pending at any time.

With a 50% misprediction rate, the Nth load has only 0.5N probability of actually committing, but it is still better than just having a single load in flight.

Re: Trying to speed up binary search

#25

Post by susi22 » Thu, Dec 17, 2015, 11:12 AM UTC

acqq wrote: post #7

"Apparently the conditional move is good to avoid branch mispredictions, but cannot hide memory latency as much as the regular implementation." Anybody knows what actually happens there? For a real analysis I'd like to see the generated assembly in a classic and conditional move case, and also an example of the indexes accessed in one and another algorithm.

It's because the computation complexity increased:

http://cs.stackexchange.com/questions/29755/why-is-binary-se...