3 ms·

Is rapidhash cache-friendly?

by wpollock 1y ago

wmf 1y ago
Hash functions don't have any data reuse so none of them are cache-friendly.
- benwills 1y ago
  I think they may be asking about the CPU cache.
  - Dylan16807 1y ago
    You have to go out of your way to make a hash that doesn't fit into L1, so again they're all basically the same. You'll probably end up fitting entirely inside the reorder buffer plus a sequential stream from memory, with the actual caches almost irrelevant.
    - benwills 1y ago
      Sure. Any worthwhile hash function will fit in the instruction cache. But there are ways to make more or less efficient use of the data cache.
      - Dylan16807 1y ago
        > Any worthwhile hash function will fit in the instruction cache. Yes, I'm talking about the data cache. > But there are ways to make more or less efficient use of the data cache. How? You need to touch every byte of input, and nothing should be faster than going right through from start to end.
        benwills 1y ago
        I don't know you're experience with hash functions, so you may already know what I'm about to say. This is a minor example, but since you asked... https://github.com/Cyan4973/xxHash/blob/dev/xxhash.h#L6432 https://github.com/Cyan4973/xxHash/blob/dev/xxhash.h#L6432 That's an example of a fair number of accumulators that are stored as XXHash goes through its input buffer. Many modern hash functions store more state/accumulators than they used to. Previous generations of hash functions would often just have one or two accumulators and run through the data. Many modern hash functions might even store multiple wider SIMD variables for better mixing. And if you're storing enough state that it doesn't fit in your registers, the CPU will put it into the data cache.
        Dylan16807 1y ago
        > And if you're storing enough state that it doesn't fit in your registers, the CPU will put it into the data cache. And there's 150+ registers in the actual chip. But my argument is more that there isn't really an efficient or inefficient way to use L1. So unless you have an enormous amount of state, the question is moot. And if you have so much state you're spilling to L2, that's not when you worry about good or bad cache use, that's a weird bloat problem.
      - Sesse__ 1y ago
        _Fitting_ in the instruction cache isn't hard, but you'd also ideally let there be room for some other code as well :-) For a hash map lookup, where the hashing is frequently inlined a couple of times, code size matters.
- Retr0id 1y ago
  You can have cache-unfriendly hash functions, though. For example, a common optimisation for CRC implementation involves lookup tables. If your lookup table exceeds L1 then you're going to have a bad time. If your lookup table fits exactly in L1, your benchmarks might look great, while real-world performance suffers (because your other code wants to be making use of L1, too). I'd imagine rapidhash avoids lookup tables but the question of cache-friendliness is still pertinent.

Is rapidhash cache-friendly?

wmf 1y ago

Hash functions don't have any data reuse so none of them are cache-friendly.

benwills 1y ago
I think they may be asking about the CPU cache.
- Dylan16807 1y ago
  You have to go out of your way to make a hash that doesn't fit into L1, so again they're all basically the same. You'll probably end up fitting entirely inside the reorder buffer plus a sequential stream from memory, with the actual caches almost irrelevant.
  - benwills 1y ago
    Sure. Any worthwhile hash function will fit in the instruction cache. But there are ways to make more or less efficient use of the data cache.
    - Dylan16807 1y ago
      > Any worthwhile hash function will fit in the instruction cache. Yes, I'm talking about the data cache. > But there are ways to make more or less efficient use of the data cache. How? You need to touch every byte of input, and nothing should be faster than going right through from start to end.
      - benwills 1y ago
        I don't know you're experience with hash functions, so you may already know what I'm about to say. This is a minor example, but since you asked... https://github.com/Cyan4973/xxHash/blob/dev/xxhash.h#L6432 https://github.com/Cyan4973/xxHash/blob/dev/xxhash.h#L6432 That's an example of a fair number of accumulators that are stored as XXHash goes through its input buffer. Many modern hash functions store more state/accumulators than they used to. Previous generations of hash functions would often just have one or two accumulators and run through the data. Many modern hash functions might even store multiple wider SIMD variables for better mixing. And if you're storing enough state that it doesn't fit in your registers, the CPU will put it into the data cache.
        Dylan16807 1y ago
        > And if you're storing enough state that it doesn't fit in your registers, the CPU will put it into the data cache. And there's 150+ registers in the actual chip. But my argument is more that there isn't really an efficient or inefficient way to use L1. So unless you have an enormous amount of state, the question is moot. And if you have so much state you're spilling to L2, that's not when you worry about good or bad cache use, that's a weird bloat problem.
    - Sesse__ 1y ago
      _Fitting_ in the instruction cache isn't hard, but you'd also ideally let there be room for some other code as well :-) For a hash map lookup, where the hashing is frequently inlined a couple of times, code size matters.
Retr0id 1y ago
You can have cache-unfriendly hash functions, though. For example, a common optimisation for CRC implementation involves lookup tables. If your lookup table exceeds L1 then you're going to have a bad time. If your lookup table fits exactly in L1, your benchmarks might look great, while real-world performance suffers (because your other code wants to be making use of L1, too). I'd imagine rapidhash avoids lookup tables but the question of cache-friendliness is still pertinent.