3 ms·

Appreciate the attention to detail on the microbenchmarks. Skimming through, need to read in more detail later, but what I would love to see is a real world co

Appreciate the attention to detail on the microbenchmarks. Skimming through, need to read in more detail later, but what I would love to see is a real world comparison against just linear search in a vector. Either of associated pairs, or two vectors (one for key, one for value, with matching offsets). My hunch is that people in general are more often than not reaching for hash-tables (and sometimes trees) for the API convenience of an associative structure -- but that on modern architectures with decent cache sizes and for small(ish) data sets they can be outperformed by a simple O(N) lookup. For example, it would be an interesting experiment to take something like the Python runtime (or the JDK etc) and replace its dictionary type with vectors -- at least for small dictionaries -- and then run through some common applications and frameworks and see what impact this has.

SPascareli13 2y ago
I think I tested very casually some time ago with Go maps and up to like one hundred items the linear search on array was faster than map lookup. Considering that many times when we use Maps for convenience they will have less than a hundred items this could be useful. Unfortunately I don't have the results (or the test code) anymore, but it shouldn't be hard to do again (casually at least).
- hinkley 2y ago
  Trees can also be useful here but they have some of the same branching problems that hashes do and lists do not.
tialaramex 2y ago
I expect this experiment provides a small perf win for very small N, but that's swamped by the price of deciding whether to try this and in many applications it's also noise compared to the perf win from using hash tables for larger N. A hash table with a very cheap hash (remember in C++ out of the box their hash for integers is usually the identity function) well be cheaper for quite modest N because it's mostly just doing less work. I could believe N>=4 for example
- cmrdporcupine 2y ago
  I think N=>4 is woefully pessimistic. Contiguous, cached memory... it's just so much faster on modern machines. That and all the potential for branch prediction misses in a hashtable or tree vs a simple array lookup... Linear scan be stupid fast.
  - tialaramex 2y ago
    Linear scan is very fast, but it's not competing against a worse scan it's competing against not scanning which is what the hash table is going to do. At N=4, say we're mapping one 64-bit integer to another for some reason, so that's 16 bytes per entry, four entries, 64 bytes, conveniently sized linear scan table. The linear scan reads each of the four keys in turn, if one matches that's a hit, if none do we missed. Four 64-bit reads, four 64-bit compares & branches. A Swiss table big enough for N=4 has eight slots (128 butes) plus 16 bytes of metadata (total 144 bytes). Half of the slots are empty. We do a single arithmetic operation on the key, picking the only 16 bytes of metadata which exist, then we load that data, and a single SIMD instruction matches either zero or one entry, and if it wasn't zero we load and compare that entry. In practical systems you'll get more leeway because Swiss tables want a real hash, your keys probably aren't suitable so maybe there's a dozen or more ALU operations to hash a key - which is a substantial head start for a linear scan. But hey we're talking small amounts of data, who even cares about hash quality? But do measure, I too am interested, at least in a real shoot out between an actual linear scan and a decent hash table. If the "same API as a hash table but same implementation as linear scan" makes sense for some sizes maybe it's worth writing that collection type.
    - menaerus 2y ago
      > Linear scan is very fast, but it's not competing against a worse scan it's competing against not scanning which is what the hash table is going to do. Not sure I agree since "not scanning" would imply that we have a hash-table where no probing ever fails beyond the initial step. That is not a very realistic workload so I also think that N=4 is way pessimistic. Memory prefetchers, especially with linear access patterns in your code, will hide the latency so I would expect that N should be much much larger to show the diff.
hinkley 2y ago
Do we need TimSearch?

SPascareli13 2y ago

I think I tested very casually some time ago with Go maps and up to like one hundred items the linear search on array was faster than map lookup. Considering that many times when we use Maps for convenience they will have less than a hundred items this could be useful. Unfortunately I don't have the results (or the test code) anymore, but it shouldn't be hard to do again (casually at least).

hinkley 2y ago
Trees can also be useful here but they have some of the same branching problems that hashes do and lists do not.

tialaramex 2y ago

I expect this experiment provides a small perf win for very small N, but that's swamped by the price of deciding whether to try this and in many applications it's also noise compared to the perf win from using hash tables for larger N. A hash table with a very cheap hash (remember in C++ out of the box their hash for integers is usually the identity function) well be cheaper for quite modest N because it's mostly just doing less work. I could believe N>=4 for example

cmrdporcupine 2y ago
I think N=>4 is woefully pessimistic. Contiguous, cached memory... it's just so much faster on modern machines. That and all the potential for branch prediction misses in a hashtable or tree vs a simple array lookup... Linear scan be stupid fast.
- tialaramex 2y ago
  Linear scan is very fast, but it's not competing against a worse scan it's competing against not scanning which is what the hash table is going to do. At N=4, say we're mapping one 64-bit integer to another for some reason, so that's 16 bytes per entry, four entries, 64 bytes, conveniently sized linear scan table. The linear scan reads each of the four keys in turn, if one matches that's a hit, if none do we missed. Four 64-bit reads, four 64-bit compares & branches. A Swiss table big enough for N=4 has eight slots (128 butes) plus 16 bytes of metadata (total 144 bytes). Half of the slots are empty. We do a single arithmetic operation on the key, picking the only 16 bytes of metadata which exist, then we load that data, and a single SIMD instruction matches either zero or one entry, and if it wasn't zero we load and compare that entry. In practical systems you'll get more leeway because Swiss tables want a real hash, your keys probably aren't suitable so maybe there's a dozen or more ALU operations to hash a key - which is a substantial head start for a linear scan. But hey we're talking small amounts of data, who even cares about hash quality? But do measure, I too am interested, at least in a real shoot out between an actual linear scan and a decent hash table. If the "same API as a hash table but same implementation as linear scan" makes sense for some sizes maybe it's worth writing that collection type.
  - menaerus 2y ago
    > Linear scan is very fast, but it's not competing against a worse scan it's competing against not scanning which is what the hash table is going to do. Not sure I agree since "not scanning" would imply that we have a hash-table where no probing ever fails beyond the initial step. That is not a very realistic workload so I also think that N=4 is way pessimistic. Memory prefetchers, especially with linear access patterns in your code, will hide the latency so I would expect that N should be much much larger to show the diff.

hinkley 2y ago

Do we need TimSearch?