4 ms·
Full array in L1 is not a typical scenario for binary search. Binary search is usually for large data sets, that are in DRAM.
by alain94040 3y ago
Full 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.