Huh? Why would you have 4 cache misses for a 128-byte record? If you need to access 4 fields and they all fall onto the same cache line, you get only one cache miss. If your fields are spread far apart, you might have 4 cache misses, but that isn't a given. With parallel arrays, the fields will be in separate arrays and necessitate 4 cache misses.
> That's true for almost all programs, almost all of the time, actually -- which is why I was willing to be the other side of your original wager.
I didn't make the original wager. :)
I wrote earlier "if your cache line is 32 bytes".
If you need all the fields - you will have 4 cache misses. If you need only some of the fields, and they all fall into 1 cache line, then -- as you said, you will only have one cache miss.
My point (poorly worded, upon rereading, but I didn't have much time, dayjob and all...) was that the potential advantage of record-major does NOT increase beyond what is packed into one cache line -- so it is a small constant, rather than deserving of O() notation.
> I didn't make the original wager. :)
Ah, apologies. (But maybe you'd still let me take your money? :) )
I see what you mean, now. You're right that it's a constant multiplier.
No. As soon as you need to read more than <cache line bytes>, it no longer matters that that the the fields are near each other. So, e.g., if your record is 128 bytes but your cache line is 32 bytes, you have 4 cache misses per record. If you use only 4 fields from the record, you have 4 cache misses per record -- so, we're on parity.
As M increases beyond the cache line size, the advantage (compared to column major) no longer increases. So it is at most a constant in practice.
> The big thing is that their access patterns are rarely random.
That's true for almost all programs, almost all of the time, actually -- which is why I was willing to be the other side of your original wager.
> They aren't so fast if you need to find a specific entry. For maximum speed there, you need a dedicated index, and then it doesn't really matter whether the data is stored row-major or column-major.
And again, that's true for many workloads as well.
The main advantage of row-major is simpler appending; if you write a lot and read little, row-major is faster; this is usually the case for e.g. audit logs.
In most typical cases, column major is equal or better.