5 ms·
Trying to speed up binary search
- geophile 11y agoWhat about stopping when the ends of the range are "close enough" and switching to a linear search? All the data should be in the cache, and it should be possible to avoid branches.
- trhway 11y agothis is why in real db the indexes aren't in pure binary tree, it is a variation of B-tree instead. So a billion rows table will have only 4 levels deep index (ie. 4 disk reads worse case).
- deleted 11y ago[deleted]
- gfody 11y agoYou can improve the best case to log log n by choosing optimal cut points instead of always cutting in half.
- ryan-c 11y agoThis is called an interpolation search[0]. Works well on data with a known distribution and is useful especially useful when reading is expensive. 0. https://en.wikipedia.org/wiki/Interpolation_search https://en.wikipedia.org/wiki/Interpolation_search
- acqq 11y ago"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.
- bertr4nd 11y agoThis is just an educated guess, but the cmov is probably going to stall the execution stage of the pipeline, which could end up backing up the front-to-back-end queue, the reorder buffer, and perhaps even fetch itself. You're getting no help from the branch predictor at this point since the dependency runs through an ALU instruction, whereas in the branchy code, you at least have a coinflip chance of predicting the right direction.
- acqq 11y agoSee my answer to the other post. I still don't see what's going on. I'd expect that the access to the non-cached RAM dominates in big arrays, and we see that for short arrays CMOV is faster. There are tools to actually figure out what's going on, Intel can measure cache misses etc. But I'd like at least ASM codes and the example of indexes in one and another case, if they are very different that's the best explanation.
- bertr4nd 11y agoI think the other poster had it backwards. I'd expect CMOV to perform worse with high memory access latencies (which it does), because it stalls the pipeline. With low access latencies the pipe doesn't stall (for long) anyways, and you avoid the branch miss overhead.
- acqq 11y agoThanks, you motivated me to find this Linus' take about the CMOV stalls: http://yarchive.net/comp/linux/cmov.html http://yarchive.net/comp/linux/cmov.html Basically, if the direction is predictable, jump can be faster because the mov is then "unconditional." The strange thing is that the binary search on average shouldn't be predictable. So it's still the question what was measured there. Maybe always an element on the position a[0], even when the array was big?
- mdergosits 11y agoWith a conditional move the processor executes both sides of the branch, but only "commits" the side that actually should be taken. Mis-predicting a branch on a modern OOO superscalar processor can be much more expensive than executing both sides.
- yorhel 11y agoI'm surprised that even the fastest implementation needs 20+ms to search a 1000-element array. I would expect even a linear search to finish within 1 or 2ms with such a small data set. How large are the array elements? How were the times measured? EDIT: Oh the time measured is the total of 1,000,000 random lookups? Nevermind my confusion then, that would certainly explain it.
- acqq 11y agoYes, it's very strange article. No asm code, not presented what's actually accessed.
- imaginenore 11y agoIf you're looking up 4-byte integers, you can simply create a hash table, or even a dumb array as an "index", which gives you 1-operation lookup. Can't get much faster than that.