3 ms·
> It turns out that in practice, parallel arrays are often significantly faster, because more often than not you _do_ access a lot of (memory consecutive) recor
by dpark 15y ago
> It turns out that in practice, parallel arrays are often significantly faster, because more often than not you _do_ access a lot of (memory consecutive) records, and you _don't_ access all the fields.
This doesn't hold if you're doing random access (which it sounds like they are, given that they're passing around lists of indices). In the random-access scenario, parallel arrays will require roughly O(M) times as many trips to main memory as the struct array, where M is the number of fields accessed.
- beagle3 15y agoO(L/M) times as many trips, where L is the <average cache line size> divided by <average field size>. With 64 byte cache lines and 8 byte fields, this is at most 8, even if you have 200 fields in your object. In my experience, when I was still doubting this myself, I was unable to ever measure more than 20% slowdown on the least favorable (for columnar storage) workload, and I was able to measure about 200% speedup on a favorable workload. Note that even if they do pass around a list of indices, accesses are often (in practice) batched - because records that arrived together tend to be needed together. And the indices are often sorted (because of how they were generated, or because they are easy to sort) which then produces a very predictable access pattern for memory and disk. We can theorize about probable and improbable access patterns until tomorrow. My experience, and everyone that used column-major order that I'm aware of, is that in practice it almost always wins against row-major ("common") ordering, whether on disk or in memory. The fastest databases around (kdb+, vertica) use column major order. That should tell you something (about disk, but also about memory)
- dpark 15y ago> O(L/M) times as many trips Sorry, I'm really confused. Is this supposed to be "O(M/L)"? The note about clumped records is valid. That is often the case. Without knowing more about their workload, it's difficult to say whether they have that behavior, but it's quite likely. As for the fastest DBs, they use column order for a number of reasons. The big thing is that their access patterns are rarely random. They're optimized for scanning on keys. DBs like Fastbit can be extremely fast for whole-table scans. 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.
- beagle3 15y ago> Sorry, I'm really confused. Is this supposed to be "O(M/L)"? 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.
- dpark 15y ago> 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. :)
- beagle3 15y ago