In https://go-review.googlesource.com/c/go/+/815960, I improved x86_64 benchmarks for small key maps by a pretty significant margin by switching AES off for very small keys.
The bakeoff benchmark I added actually measures two variants of this: a "latency" benchmark, where each call into memhash has a data dependency on the previous, and a "throughput" benchmark, where they do not. Currently, the tuning parameter I added selects for throughput, simply because I did not want to regress benchmarks. However, I believe these benchmarks are not realistic, and I would like to discuss more realistic benchmarks so we can tune this a little better.
So whats the deal with this discrepancy? Let's talk about hash collisions. SwissTable is cleverly designed so that you almost always find what you're looking for in the first group, so we can assume we never need to look at other groups and the BTB learns that. However, whether we need to make a key comparison is largely data-dependent, not code-path dependent, so it cannot be predicted. For example, filling a map with unique keys will never make key comparisons so this branch will be learned, but filling a map with a variety of overlapping keys will slam the breaks on the pipeline half the time because of mis-speculation.
Let's talk about AESNI. AESNI is a collection of vector instructions, which means that getting their results into a GPR requires porting the result from one register file to another, which is slow. The cost is constant per hash, so the relative cost drops off with key length. However, some workloads do much better, because they happen to predict the above key comparison very well, meaning that speculation can reorder things such that nothing stalls on this vector->gpr copy. This is why the runtime benchmarks seem to get worse when we switch to latency tuning: they happen to work!
So what are some realistic map use cases we should study? Here's some ideas.
- RMW aggregation, e.g.
m[k].acc += v. The address written to depends on the hash; latency-bound, especially in a loop, since all future RMWs might depend on the one we just did.
- Deduplication:
if _, ok := seen[k]; !ok { seen[k] = v }. Essentially equivalent to m[k] = v, so mostly throughput-bound.
- Traversal through a map-based graph:
v = v.children[e]. Which map we look at next depends on the hash, so this is extremely latency-bound.
- Membership filter:
for _, x := range xs { v, ok := m[k]; if !ok { continue } ... }. Can go either way, depending on whether the branch is 50-50 or 10-90, since in the latter case it can be predicted and we go into throughput land.
I would argue that most cases where maps are used are going to be leaning in the latency direction, so I think that biasing the tuning parameter towards the throughput end seems wise.
Now, how on earth do we macro-benchmark this effectively? I'm interested in ideas. The classic of course would be turning it on, waiting for Google to pick it up, and see what GWP says.
In https://go-review.googlesource.com/c/go/+/815960, I improved x86_64 benchmarks for small key maps by a pretty significant margin by switching AES off for very small keys.
The bakeoff benchmark I added actually measures two variants of this: a "latency" benchmark, where each call into memhash has a data dependency on the previous, and a "throughput" benchmark, where they do not. Currently, the tuning parameter I added selects for throughput, simply because I did not want to regress benchmarks. However, I believe these benchmarks are not realistic, and I would like to discuss more realistic benchmarks so we can tune this a little better.
So whats the deal with this discrepancy? Let's talk about hash collisions. SwissTable is cleverly designed so that you almost always find what you're looking for in the first group, so we can assume we never need to look at other groups and the BTB learns that. However, whether we need to make a key comparison is largely data-dependent, not code-path dependent, so it cannot be predicted. For example, filling a map with unique keys will never make key comparisons so this branch will be learned, but filling a map with a variety of overlapping keys will slam the breaks on the pipeline half the time because of mis-speculation.
Let's talk about AESNI. AESNI is a collection of vector instructions, which means that getting their results into a GPR requires porting the result from one register file to another, which is slow. The cost is constant per hash, so the relative cost drops off with key length. However, some workloads do much better, because they happen to predict the above key comparison very well, meaning that speculation can reorder things such that nothing stalls on this vector->gpr copy. This is why the runtime benchmarks seem to get worse when we switch to latency tuning: they happen to work!
So what are some realistic map use cases we should study? Here's some ideas.
m[k].acc += v. The address written to depends on the hash; latency-bound, especially in a loop, since all future RMWs might depend on the one we just did.if _, ok := seen[k]; !ok { seen[k] = v }. Essentially equivalent tom[k] = v, so mostly throughput-bound.v = v.children[e]. Which map we look at next depends on the hash, so this is extremely latency-bound.for _, x := range xs { v, ok := m[k]; if !ok { continue } ... }. Can go either way, depending on whether the branch is 50-50 or 10-90, since in the latter case it can be predicted and we go into throughput land.I would argue that most cases where maps are used are going to be leaning in the latency direction, so I think that biasing the tuning parameter towards the throughput end seems wise.
Now, how on earth do we macro-benchmark this effectively? I'm interested in ideas. The classic of course would be turning it on, waiting for Google to pick it up, and see what GWP says.