7 ms·

The article author talks of the number of CPU ops, as if they were all the same. Since he's using compile time constants, he probably never noticed that divisio

by eloff 11y ago

The article author talks of the number of CPU ops, as if they were all the same. Since he's using compile time constants, he probably never noticed that division (20-100 cycles) is so horribly slow. The compiler uses a trick like in Hacker's Delight to convert division into multiplication (4 cycles). But shifts and masks are cheap (1 cycle each). This kind of trickery is rarely worth the small space savings (to be fair, the author seems aware of that, by calling it immature optimization.)

hywel 11y ago
Yeah, definitely aware that it's slower - I was severely bounded my memory when I came up with this, as I was trying to get my training data and all the variables in my model into 8GB of RAM for a machine learning project. Without the trick, swap was killing the speed; with the trick everything sailed along :)
- eloff 11y ago
  I'm surprised saving 4 bits made such a difference, it's about 6% smaller. But I guess that depends on how much of your memory these things are taking up. 6% of 8GB is 500 MB, which could easily be the difference between swapping and not.
  - Someone 11y ago
    It's probably not really more about getting every item in 64 bits than about memory use. That allows one to index each item without doing further bit twiddling: you can simply declare the data as unsigned int64_t *datapoints; Because of that, I think I would have combined two 5-valued fields (need 3 bits each) rating and user area into a single 25-valued one (fits in 5 bits), and stored the others as proper bit fields. That gains you the single bit you need to put each item in a 64 bit value, and only complicates accessing two of the fields.
    - eloff 11y ago
      That's how I would have done it too. He had 65 bits to start with, so just combining two fields with the trick in the article would have been enough to save that one bit. Or one could have just extracted one boolean field into a separate bit array (even simpler.) Since the article makes a big deal about getting down to 61 bits, I assume every bit saved helped and that they were all packed together with no padding. It's a lot of assumptions.
      - Someone 11y ago
        Of course, it needs benchmarking, but "one int64_t and a boolean" is bad, cache-wise, so I would expect it to slow down the code more than putting those two fields in 5 bits. Also, I doubt he needed to pack below 64 bits, as the article states "which fits into 61 bits (8 bytes).".
        eloff 11y ago
        It depends, as always, if you access it sequentially, iterating two separate arrays vs one is similar in performance, the prefetcher will help with both. If it's random access, then you really want things to fit into 64 bits.
asQuirreL 11y ago
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).

by eloff 11y ago

hywel 11y ago

Yeah, definitely aware that it's slower - I was severely bounded my memory when I came up with this, as I was trying to get my training data and all the variables in my model into 8GB of RAM for a machine learning project. Without the trick, swap was killing the speed; with the trick everything sailed along :)

eloff 11y ago
I'm surprised saving 4 bits made such a difference, it's about 6% smaller. But I guess that depends on how much of your memory these things are taking up. 6% of 8GB is 500 MB, which could easily be the difference between swapping and not.
- Someone 11y ago
  It's probably not really more about getting every item in 64 bits than about memory use. That allows one to index each item without doing further bit twiddling: you can simply declare the data as unsigned int64_t *datapoints; Because of that, I think I would have combined two 5-valued fields (need 3 bits each) rating and user area into a single 25-valued one (fits in 5 bits), and stored the others as proper bit fields. That gains you the single bit you need to put each item in a 64 bit value, and only complicates accessing two of the fields.
  - eloff 11y ago
    That's how I would have done it too. He had 65 bits to start with, so just combining two fields with the trick in the article would have been enough to save that one bit. Or one could have just extracted one boolean field into a separate bit array (even simpler.) Since the article makes a big deal about getting down to 61 bits, I assume every bit saved helped and that they were all packed together with no padding. It's a lot of assumptions.
    - Someone 11y ago
      Of course, it needs benchmarking, but "one int64_t and a boolean" is bad, cache-wise, so I would expect it to slow down the code more than putting those two fields in 5 bits. Also, I doubt he needed to pack below 64 bits, as the article states "which fits into 61 bits (8 bytes).".
      - eloff 11y ago
        It depends, as always, if you access it sequentially, iterating two separate arrays vs one is similar in performance, the prefetcher will help with both. If it's random access, then you really want things to fit into 64 bits.

asQuirreL 11y ago

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