3 ms·
If the array is fully in L1 cache, isn't the cost of the branch mis-predict much greater than the memory fetches?
by returningfory2 3y ago
If the array is fully in L1 cache, isn't the cost of the branch mis-predict much greater than the memory fetches?
- alain94040 3y agoFull array in L1 is not a typical scenario for binary search. Binary search is usually for large data sets, that are in DRAM.
- thefifthsetpin 3y agoBinary search reduces the search space exponentially as it proceeds, so actually quite a lot of the total comparisons can hit L1d cache. (Maybe half of them for a ~250GB dataset.) Of course, you could keep a cacheable partial index of your huge dataset to accelerate the early part of your search as well.
- Bognar 3y agoSounds like we're just reinventing B-trees.
- thefifthsetpin 3y agoYep. I considered phrasing my answer that way.