Trying to speed up binary search
databasearchitects.blogspot.com
Trying to speed up binary search
1–10 of 25 posts
Re: Trying to speed up binary search
#2What 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.
Re: Trying to speed up binary search
#3You can improve the best case to log log n by choosing optimal cut points instead of always cutting in half.
Re: Trying to speed up binary search
#4You can improve the best case to log log n by choosing optimal cut points instead of always cutting in half.
This is called an interpolation search[0]. Works well on data with a known distribution and is useful especially useful when reading is expensive.
Re: Trying to speed up binary search
#5What 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.
this 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).
Re: Trying to speed up binary search
#6What 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.
[deleted]
Re: Trying to speed up binary search
#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.
Re: Trying to speed up binary search
#8"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.
With 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.
Re: Trying to speed up binary search
#9"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.
This 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.
Re: Trying to speed up binary search
#10"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.
With 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.
But the writer claims that his CMOV version takes more time than the one with the branch for big arrays. I'd expect that the access to the non-cached RAM dominates, and we see that for short arrays CMOV is faster, which is what is to be expected.