runtime: enhance map cacheline efficiency

[simonhf]

Looking at the Golang source code for how map is implemented [1], there seems to be a possible opportunity to enhance cacheline efficiency:

The current algorithm appears to work as follows for looking up a key in a map:

• Hash the key [2] and find the associated bucket [3].
• Search along bucket .tophash array [4] for a key candidate <-- cacheline fetch 1
• Binary compare key in key array [5] <-- cacheline fetch 2
• Grab associated element address in element array [6] <-- cacheline fetch 3 (when caller uses element address)

So there are 3 arrays in a bucket; .tophash array, key array, and element (value) array. Each array has the same hard-coded bucketCnt length of 8 elements [7]. A key array item size is typically 16 bytes. This means a typical total key array size is 8 items * 16 byte size = 128 bytes long, or 2x (typically sized) 64 byte cachelines. The total key array size means the associated element array item is usually located in a different cacheline.

This can also be seen (added padding and comments to make it easier to read) from the way the key and element addresses are calculated in the source code:

k  :=  add(unsafe.Pointer(b), dataOffset+i        *uintptr(t.keysize)                      ) // <-- [8]
e  :=  add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) // <-- [9]
//                                                                    ^^^^^^^^^^^^^^^^^^^^^ element array
//                                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ key array
//                            ^^^^^^^^^^ skip .tophash array

Possible optimization:

If the key and element arrays would be interleaved (instead of separate arrays) then this would not guarantee that the associated key[n] and element[n] are always in the same cacheline, but often they would be :-)

As an example, the interleaved version of the above k and e assignments would look something like this:

k  :=  add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize+t.elemsize)+uintptr(0)        )
e  :=  add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize+t.elemsize)+uintptr(t.keysize))

In theory, performance would more often be better due to less CPU cacheline fetches, and otherwise the same performance as before?

[1] https://github.com/golang/go/blob/go1.17.1/src/runtime/map.go#L532
[2] https://github.com/golang/go/blob/go1.17.1/src/runtime/map.go#L515
[3] https://github.com/golang/go/blob/go1.17.1/src/runtime/map.go#L517
[4] https://github.com/golang/go/blob/go1.17.1/src/runtime/map.go#L532
[5] https://github.com/golang/go/blob/go1.17.1/src/runtime/map.go#L542
[6] https://github.com/golang/go/blob/go1.17.1/src/runtime/map.go#L543
[7] https://github.com/golang/go/blob/go1.17.1/src/runtime/map.go#L66
[8] https://github.com/golang/go/blob/go1.17.1/src/runtime/map.go#L538
[9] https://github.com/golang/go/blob/go1.17.1/src/runtime/map.go#L543

[ianlancetaylor]

This is not an API change so taking it out of the proposal process.

CC @randall77

[ianlancetaylor]

I'm not sure you are considering the cache line advantages when the first key comparison fails but the second or third one succeeds. The current layout makes it more likely that the second and third key comparisons will be in the same cacheline.

[randall77]

The trouble with interleaving key/value in the bucket is it may require more alignment padding.
I experimented a while back with doing the optimal packing (e.g. map[int16]int64 would use k0 k1 k2 k3 v0 v1 v2 v3 k4 k5 k6 k7 v4 v5 v6 v7). It required a more complicated indexing scheme and ended up not helping performance-wise, especially for small maps. I'm open to changing the current scheme if someone can demonstrate a performance improvement.

[randall77]

I'm not sure you are considering the cache line advantages when the first key comparison fails but the second or third one succeeds. The current layout makes it more likely that the second and third key comparisons will be in the same cacheline.

The hope is that only one tophash comparison matches, so you only have to look at a single key.

[simonhf]

cache line advantages when the first key comparison fails but the second or third one succeeds

@ianlancetaylor, you mean because the .tophash array and the key array can share the same cache line, and .tophash is not necessarily unique?

If so, I assume non-unique .tophash values occur in a tiny minority of cases. As an example experiment below, 80 million keys are hashed into the equivalent of the .tophash array with 8 elements. The number of times a 'collision' occurs (where the tophash byte is non-unique) is counted. And yes, I know is not exactly the same as the Golang map algorithm; which does not use SHA256 to calculate the hash value (a non-cryptographic hashing algorithm might result in more collisions), and the .tophash arrays are not necessarily completely full either like they are in the experiment.

The experimental results show that non-unique values in the .tophash array only occur 1,070,210 + 8,433 + 23 = 1,078,666 times or for 1.3% of all keys. However, the chance of the .tophash array and the collided keys all being in the same cacheline is even less than 1.35%, because only the first 3 of 8 possible keys can possibly be in the same cacheline as the .tophash array itself, e.g. 8 bytes for .tophash plus 3 x 16 = 48 bytes for the first 3 keys is 56 bytes... nearly the 64 bytes of the cacheline.

Whereas, with the interleaving of keys and elements, presumably most if not all (assuming good alignment to cacheline boundaries) associated keys and elements would end up in the same cacheline, but not necessarily the same cacheline as .tophash?

$ perl -e 'use Digest::SHA; $keys=10_000_000; $tophash=8; foreach $k(1..$keys){ undef $h; foreach $i(1..$tophash){ $hex = Digest::SHA::sha256_hex($k.$i); $top = substr($hex, 0, 2); $h->{$top}++; if(0){ printf qq[- k=%d i=%d hex=%s top=%s\n], $k, $i, $hex, $top; } } foreach $top(keys %{$h}){ $f=$h->{$top}; $hf->{$f}++; } } sub END{ foreach $f(sort keys %{$hf}){ printf qq[- %d keys hashed into n x tophash[%d]; 8 bits exists in any array %d time(s) occurred %8d times\n], $keys * $tophash, $tophash, $f, $hf->{$f}; } }'
- 80000000 keys hashed into n x tophash[8]; 8 bits exists in any array 1 time(s) occurred 77834169 times
- 80000000 keys hashed into n x tophash[8]; 8 bits exists in any array 2 time(s) occurred  1070210 times
- 80000000 keys hashed into n x tophash[8]; 8 bits exists in any array 3 time(s) occurred     8433 times
- 80000000 keys hashed into n x tophash[8]; 8 bits exists in any array 4 time(s) occurred       28 times

The hope is that only one tophash comparison matches, so you only have to look at a single key.

@randall77, the experiment above seems to validate that ~ 98.65% of the time only one .tophash value does match :-)

Interestingly, the same experiment shows that if .tophash would be extended to 16 items (and I'm not suggesting it should be) then the the 1.35% turns into 2.83%.

$ perl -e 'use Digest::SHA; $keys=5_000_000; $tophash=16; foreach $k(1..$keys){ undef $h; foreach $i(1..$tophash){ $hex = Digest::SHA::sha256_hex($k.$i); $top = substr($hex, 0, 2); $h->{$top}++; if(0){ printf qq[- k=%d i=%d hex=%s top=%s\n], $k, $i, $hex, $top; } } foreach $top(keys %{$h}){ $f=$h->{$top}; $hf->{$f}++; } } sub END{ foreach $f(sort keys %{$hf}){ printf qq[- %d keys hashed into n x tophash[%d]; 8 bits exists in any array %d time(s) occurred %8d times\n], $keys * $tophash, $tophash, $f, $hf->{$f}; } }'
- 80000000 keys hashed into n x tophash[16]; 8 bits exists in any array 1 time(s) occurred 75437834 times
- 80000000 keys hashed into n x tophash[16]; 8 bits exists in any array 2 time(s) occurred  2218711 times
- 80000000 keys hashed into n x tophash[16]; 8 bits exists in any array 3 time(s) occurred    40900 times
- 80000000 keys hashed into n x tophash[16]; 8 bits exists in any array 4 time(s) occurred      506 times
- 80000000 keys hashed into n x tophash[16]; 8 bits exists in any array 5 time(s) occurred        4 times

Perhaps more interesting would be to extend .tophash items from 8 bits to 16 bits? Which also adds 8 bytes to the size of every map. The experiment below shows that the 1.35% turns into 0.00535%, i.e. there is now very much hope that only one .tophash comparison matches :-)

$ perl -e 'use Digest::SHA; $keys=10_000_000; $tophash=8; foreach $k(1..$keys){ undef $h; foreach $i(1..$tophash){ $hex = Digest::SHA::sha256_hex($k.$i); $top = substr($hex, 0, 4); $h->{$top}++; if(0){ printf qq[- k=%d i=%d hex=%s top=%s\n], $k, $i, $hex, $top; } } foreach $top(keys %{$h}){ $f=$h->{$top}; $hf->{$f}++; } } sub END{ foreach $f(sort keys %{$hf}){ printf qq[- %d keys hashed into n x tophash[%d]; 8 bits exists in any array %d time(s) occurred %8d times\n], $keys * $tophash, $tophash, $f, $hf->{$f}; } }'
- 80000000 keys hashed into n x tophash[8]; 8 bits exists in any array 1 time(s) occurred 79991440 times
- 80000000 keys hashed into n x tophash[8]; 8 bits exists in any array 2 time(s) occurred     4280 times

And just for completeness, extending .tophash items from 8 bits to 24 bits? Which also adds 16 bytes to the size of every map. The experiment below shows that the 1.35% turns into 0.00002625%. Doesn't seem to be worth it for the advantage over 16 bits?

$ perl -e 'use Digest::SHA; $keys=10_000_000; $tophash=8; foreach $k(1..$keys){ undef $h; foreach $i(1..$tophash){ $hex = Digest::SHA::sha256_hex($k.$i); $top = substr($hex, 0, 6); $h->{$top}++; if(0){ printf qq[- k=%d i=%d hex=%s top=%s\n], $k, $i, $hex, $top; } } foreach $top(keys %{$h}){ $f=$h->{$top}; $hf->{$f}++; } } sub END{ foreach $f(sort keys %{$hf}){ printf qq[- %d keys hashed into n x tophash[%d]; 8 bits exists in any array %d time(s) occurred %8d times\n], $keys * $tophash, $tophash, $f, $hf->{$f}; } }'
- 80000000 keys hashed into n x tophash[8]; 8 bits exists in any array 1 time(s) occurred 79999958 times
- 80000000 keys hashed into n x tophash[8]; 8 bits exists in any array 2 time(s) occurred       21 times

I experimented a while back with doing the optimal packing (e.g. map[int16]int64 would use k0 k1 k2 k3 v0 v1 v2 v3 k4 k5 k6 k7 v4 v5 v6 v7). It required a more complicated indexing scheme and ended up not helping performance-wise, especially for small maps.

Did you check to see if NOT packing / aligning / padding results in performance issues, e.g. "On recent Intel processors (Sandy Bridge and Nehalem), there is no performance penalty for reading or writing misaligned memory operands" [1] (admittedly a little old for these days) ?

Or, maybe opportunistically only use the simple interleaving (i.e. where k0 k1 k2 k3 v0 v1 v2 v3 is complicated interleaving) for map schemes which don't require special packing, which would still be a larger number of all maps, or?

I'm open to changing the current scheme if someone can demonstrate a performance improvement.

Hmmm... I might have a crack myself at demonstrating an improvement. Have never compiled Golang from scratch (in order to change map.go) but there's a first time for everything :-)

[1] https://lemire.me/blog/2012/05/31/data-alignment-for-speed-myth-or-reality/

[randall77]

Did you check to see if NOT packing / aligning / padding results in performance issues, e.g. "On recent Intel processors (Sandy Bridge and Nehalem), there is no performance penalty for reading or writing misaligned memory operands" [1] (admittedly a little old for these days) ?

No, I didn't. It is kind of a moot point because there are architectures we run on that do not allow misaligned accesses at all. And we do not want to have different implementations on different architectures, if we can avoid it.

Or, maybe opportunistically only use the simple interleaving (i.e. where k0 k1 k2 k3 v0 v1 v2 v3 is complicated interleaving) for map schemes which don't require special packing, which would still be a larger number of all maps, or?

map[T]bool is a relatively common map type.

We could simply interleave only for types which require no padding, but then we need to somehow fork the code based on what packing would happen. Again, not ideal code size and maintenance-wise.

We could interleave always, with padding if needed, which would waste space but allow a single implementation. Maybe the space wasted wouldn't be too bad (map[int64]bool is probably the worst common case, which is a 63% expansion).

[randall77]

Did you check to see if NOT packing / aligning / padding results in performance issues, e.g. "On recent Intel processors (Sandy Bridge and Nehalem), there is no performance penalty for reading or writing misaligned memory operands" [1] (admittedly a little old for these days) ?

Also the garbage collector requires aligned pointers.