Re:Ask HN: What are some cool but obscure data structures yo...
by robalni on Saturday July 23, 2022 @04:01AM
(#32201341)
Interestingly I get more cache misses with the gray code solution but still fewer switches between cache lines. This has to be because the cache line prefetcher can predict the memory usage in the simple version but it's harder to predict in the gray code or de-interleave version.
Also, I have never thought about de-interleaving bits without using gray code but that seems to work similarly. The main reason I used gray code is that then we don't have to switch memory blocks as often since only one of the indexes changes every time so one of the current memory blocks can always stay the same as in the previous iteration.
FYI this also extends to higher dimensions. I once used it to split a single loop variable into 3 for a "normal" matrix multiplication to get a huge speedup. Unrolling the inner 3 bits is possible too but a bit painful.
Also used it in ray tracing to scan pixels in Z-order, which gave about 10 percent performance improvement at the time.
But yes, I must look at this grey code step to see if it makes sense to me and understand why its not helping you even with reduced cache misses.