News for hackers. Stuff that matters.
Re:Assault by GC by dpark on Monday October 24, 2011 @04:08PM (#3151360)
> 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.

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. :)

Re:Assault by GC by beagle3 on Monday October 24, 2011 @04:37PM (#3151476)
> Why would you have 4 cache misses for a 128-byte record?

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? :) )

Re:Assault by GC by dpark on Monday October 24, 2011 @06:00PM (#3151809)
> 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 see what you mean, now. You're right that it's a constant multiplier.