3 ms·
I don't think the trick of checking each end of the cache line helps much, except perhaps at the very end of the search (where there are say low 100s of bytes l
by BeeOnRope 6y ago
I don't think the trick of checking each end of the cache line helps much, except perhaps at the very end of the search (where there are say low 100s of bytes left in the region).
When the region is large it just doesn't cut the search space down almost at all: it's a rounding error.
Now you might think it's basically free, but clogging up the OOOE structures with instructions can hurt MLP because fewer memory accesses fit in the window, even if the instructions always completely execute in the shadow of existing misses.
There is a similar trick with pages: you might try to favor not touching more pages than necessary, so it might be worth moving probe points slightly to avoid touching a new page. For example, if you just probed at bytes 0 and 8200, the middle is 4100, but that's a new 4k page (bytes 4096 thru 8191), so maybe you adjust it slightly to probe at 4090 since you already hit that page with your 0 probe.
Making all of these calculations dynamically is a bit annoying and maybe slow, so it's best if the whole search is unrolled so the probe points according to whatever rules can be calculated at compile time and embedded into the code.
Much more important than either of these things is avoiding overloading the cache sets. Some implementations have this habit of choosing their probe points such that only a very small number of sets in the L1, L2 are used so the caching behavior is terrible. Paul Khuong talks about this in detail on pvk.ca.
Doing a linear walk at the end definitely helps a bit though: SIMD is fastest for this part.
- londons_explore 6y agoIf you want to optimize a data structure for binary search, it sounds like it might be best to reorder the data itself in memory to make caching more effective. For example the first access in a binary search will be the middle element, followed by the lower quartile or upper quartile. If you store all of those together in memory, a single cache line fetch can serve all those requests.
- aktau 6y agoSee user `fluffything`'s comment on this same thread: https://news.ycombinator.com/item?id=23895629 https://news.ycombinator.com/item?id=23895629, describing this approach (Eytzinger layout).
- BeeOnRope 6y agoYes, although the design space explodes once you can reorder, so it's also interesting to consider the restricted problem where you can't reorder. This is still realistic since in many scenarios the layout may be fixed by an external constraint.
- hansvm 6y agoA levelwise traversal usually performs well without much effort if you want to optimize for cache friendliness. It's not optimal iirc, but it's dead-simple and much easier on the prefetcher than an inorder traversal. Edit: Oops, TIL the eytzinger layout other comments have mentioned _is_ a levelwise traversal. Anywho, it's usually a good starting point for this kind of thing.
- kazinator 6y agoBinary search is used when you can't optimize the data structure. You have a sorted array, and have to work with that. If you store the middle element together with its first two quartiles, you're making a B-tree. You will need indirection (pointers) to locate the other chunks that are not stored together and so it goes. "Binary search" usually refers to the sorted array algorithm, though of course in the abstract sense of subdivision, any subdivision-by-two search is binary and in that sense we have the term "binary search tree".