3 ms·

Also worth noting that storing them in a long probably means 2 memory reads per access on most modern architectures, whereas storing them in bitfields will allo

Also worth noting that storing them in a long probably means 2 memory reads per access on most modern architectures, whereas storing them in bitfields will allow the compiler to select the containing CPU word, which will be 1 read. I would be interested to see actual performance measurements (maybe a performance vs memory usage chart).

TheLoneWolfling 11y ago
I thought that modern architectures tend to read in an entire cache line at once? In which case bit packing can be problematic as it can stretch across a cache boundary?
- eloff 11y ago
  The 65bit packing would straddle cache boundaries, but it won't affect performance noticeably on Intel CPUs since Ivy Bridge. Packing into 61 bits without padding will do the same.
- uxcn 11y ago
  No, memory bus transfers happen in word sizes. This is why caches sometimes use critical word first. However, straddling word boundaries is problematic.
  - thrownaway2424 11y ago
    It is impossible for an Intel CPU to load less than a line of cache, no matter how small the access. "Critical word first" only allows the register load to complete before the cache line is fully loaded. The memory bus word size is irrelevant. A cache line fill requires multiple words but DDR memory is designed to efficiently do exactly that.
    - uxcn 11y ago
      After re-reading what I wrote, it is kind of misleading. Yes, CPUs generally can't work with anything smaller than a cache line (see coherence). Although, you don't need to wait for an entire cache line to transfer before you can use a word on the cache line. So, where values fall on (across) cache lines does matter. Straddling word sizes has additional problems, and generally implies straddling the cache line size as well (unless it's a multiple).
  - eloff 11y ago
    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.
    - uxcn 11y ago
      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.
- thrownaway2424 11y ago
  You are correct, mainstream CPUs load in cache line quanta. They can't do anything smaller. If your value straddles a cache line boundary then you load two lines. That's why cache-aligned values are sometimes critical to performance of certain codes. Intel will soon be marketing CPUs with 512-bit registers. At that time the register width and the cache line width will be the same. That will be novel.
- asQuirreL 11y ago
  But not into a register right? Given my (flawed) assumption that there would be two reads, whilst the first might load the second into the cache, it wouldn't load into a register without another instruction telling it to. This costs a lot less than the cache fetch but it still has a cost.
eloff 11y ago
By most modern architectures you mean 32bit, since you seem to think accessing a 64bit "long" (it's 32bits on windows btw) takes two memory accesses. 32bit architectures are not "modern"... Maybe you meant unaligned 64bit accesses, which will be 2 reads, but those are pretty cheap since Sandy Bridge or earlier.

TheLoneWolfling 11y ago

I thought that modern architectures tend to read in an entire cache line at once? In which case bit packing can be problematic as it can stretch across a cache boundary?

eloff 11y ago
The 65bit packing would straddle cache boundaries, but it won't affect performance noticeably on Intel CPUs since Ivy Bridge. Packing into 61 bits without padding will do the same.
uxcn 11y ago
No, memory bus transfers happen in word sizes. This is why caches sometimes use critical word first. However, straddling word boundaries is problematic.
- thrownaway2424 11y ago
  It is impossible for an Intel CPU to load less than a line of cache, no matter how small the access. "Critical word first" only allows the register load to complete before the cache line is fully loaded. The memory bus word size is irrelevant. A cache line fill requires multiple words but DDR memory is designed to efficiently do exactly that.
  - uxcn 11y ago
    After re-reading what I wrote, it is kind of misleading. Yes, CPUs generally can't work with anything smaller than a cache line (see coherence). Although, you don't need to wait for an entire cache line to transfer before you can use a word on the cache line. So, where values fall on (across) cache lines does matter. Straddling word sizes has additional problems, and generally implies straddling the cache line size as well (unless it's a multiple).
- eloff 11y ago
  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.
  - uxcn 11y ago
    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.
thrownaway2424 11y ago
You are correct, mainstream CPUs load in cache line quanta. They can't do anything smaller. If your value straddles a cache line boundary then you load two lines. That's why cache-aligned values are sometimes critical to performance of certain codes. Intel will soon be marketing CPUs with 512-bit registers. At that time the register width and the cache line width will be the same. That will be novel.
asQuirreL 11y ago
But not into a register right? Given my (flawed) assumption that there would be two reads, whilst the first might load the second into the cache, it wouldn't load into a register without another instruction telling it to. This costs a lot less than the cache fetch but it still has a cost.

eloff 11y ago

By most modern architectures you mean 32bit, since you seem to think accessing a 64bit "long" (it's 32bits on windows btw) takes two memory accesses. 32bit architectures are not "modern"... Maybe you meant unaligned 64bit accesses, which will be 2 reads, but those are pretty cheap since Sandy Bridge or earlier.