Re:Dense bitpacking
by eloff on Sunday August 09, 2015 @10:26AM
(#10030357)
If you're reading sequentially in a loop, the prefetcher will detect that and the cache lines will be loaded ahead of the accesses and the cost for straddling will be almost nothing. If you're doing random access of misaligned 64bit words, roughly 1/8 of your accesses will need two cache lines, which we can naively say is twice as slow as the other 7/8ths, so your runtime would be 9/8ths. That's a bit of a hit, but still not that bad.
[ Parent
| on HN ]
If the words are just unaligned, you not only run into issues spanning cache lines, but spanning pages as well. The prefetcher can detect general linear patterns (+/-c, etc..) after a couple misses, but it can't prefetch across pages. Misses are still an order of magnitude slower than hits though, and this would imply at least two misses per page (~100 cycles), plus at least the number of pages you span. Assuming they were tightly packed, and depending on the number of instructions per value, it can nearly double the cycle count. Thankfully, unalinged access is generally as fast as aligned access with Intel though.
When you span the word size (e.g. add a single bit), you not only add two (dependent) instructions to access the value (consume a register), but without a linear access pattern (i.e. id index access), you can add anything up to ~200 cycles per value access. So, depending on the number of instructions per value, this could be anywhere up to 200x slower. This also doesn't consider the other possible issues like polluting the cache.