When profiling a certain compiler I found a O(n^2) algorithm which literally did almost exactly what you said. 1 cacheline accessed for every 3 iterations due t

When profiling a certain compiler I found a O(n^2) algorithm which literally did almost exactly what you said. 1 cacheline accessed for every 3 iterations due to some enormous structs, whose members index other arrays etc. Etc. It turned out 87% of all straight-to-DRAM accesses happened on one line.