One thing I miss (but that maybe comes later) is the effect of all this on
common-sense optimizations such as binary search. E.g., it would
be interesting for what kind of working sets binary search (having to look
random to even current prefetchers) actually starts to perform better than
It would be a nice example of how a O(N) algorithm can dramatically
outperform a O(log N) algorithm, due to memory effects. I'm sure there's
lots more of common wisdom that turns into a lie on modern processors.