Comment by JonChesterfield
14 hours ago
Random access is catastrophically slower because of the successive cache misses when the prefetcher fails to guess what you're doing.
One hint in the same article that random access is not cheap, in contrast with the conclusion, was noticing that the shuffle was unacceptably slow on large data sets.
Still, good to see peformance measurements, especially where the curves look roughly like you'd hope them to.
The shuffle was only unacceptably slow for data too big to fit in memory. For data that fits in memory, Fisher-Yates is totally fine; this is why it's fine for the two-pass shuffle to use buckets that fit in RAM but not in cache.