[elliptic]

Is this claim correct? "You do four of these sequential scans, and in each you write sequentially to one of 256 locations. Four passes, no random access. This is great. I don't even see a log n there, do you?"

You're writing to one of 256 (presumably far apart) memory locations - why isn't this considered random access?

[frankmcsherry]

The cost of writing to some number of unrelated locations is mostly determined by the level of cache where your working set can stay resident. You'll be doing random access to that level of cache, but it can exchange data with the next level cache in larger contiguous blocks.

In this case, 256 cache lines fit in the L1 cache, so while it does look like "random access" to the L1, this can end up looking more like "sequential access" to main memory. There are addition complications, like the L1 data cache being only 8-way associative, a quite small TLB cache sitting in front of the L2 and up, etc. So in practice this ends up somewhere between random access to L1 and random access to L3, with sequential access to main memory, I think.