You’re right that the size of types are statically known, but Go arrays are actually not small fixed sized structs.
In particular if x is an array of at least size one then &x==&x[0] (except for of course go not allowing this comparison based on different types). You can confirm with the below playground link which prints out the address of the array as well as the address of each item.
As in different types (can) have different sizes, as opposed to reference based languages where all types take a pointer and memory layout is only a concern for a type’s internal metadata.
Hence my surprise that they used a row layout, if all types have the same size then row v column is not (as much of) a concern, every value takes a pointer and there’s no padding or storage loss. But if the key and value can have different alignments then you generally want to segregate keys and values to avoid waste.
Go has no variable size types. Arrays, strings, slices, etc. are small fixed-size structs that point to variable-length blocks
I assume that cache coherency / locality of reference is the rationale for putting keys and values together. Performance trumps compactness. Also, the typical types you use in maps contain pointers or are at least pointer-sized, so they’ll have compatible alignment.
Swiss Tables do a lot less probing due to that cute little byte-array table.
As for the other points, I dunno, it’s clear Google should have had you in the room suggesting these things, since of course they wouldn’t bother to actually profile and compare different layouts.
The focus on deletion seems a little strange here. Since to delete a key you need to insert it, and the insert+delete time is less on the new map the overall performance should still improve even if you have a 1:1 insert to delete ratio. So the only place where this should be an issue is if you have latency requirements for deletes, rather than throughput for inserts and deletes overall.
Of course this benchmark is far too simplistic to draw conclusions from anyways. With any change the only real way to know is benchmarking your use case in the real world.
Huh. I thought Go had started to already incorporate some Swiss Table optimizations, not sure if that’s the case or not, but I guess there was still work left regardless. Swiss Table is 7 years old, I’m surprised something as core as a hash map would leave this much performance on the table for so long.
Also https://github.com/golang/go/issues/71368
Using KV rows seems like a terrible idea for a langage with variable type size, is abseil’s also laid out like that?
In both Go and C++ the key and value types are known at compile time so for any instance the key and value size are fixed.
(Go has no variable size types. Arrays, strings, slices, etc. are small fixed-size structs that point to variable-length blocks.)
You’re right that the size of types are statically known, but Go arrays are actually not small fixed sized structs.
In particular if x is an array of at least size one then &x==&x[0] (except for of course go not allowing this comparison based on different types). You can confirm with the below playground link which prints out the address of the array as well as the address of each item.
https://go.dev/play/p/TcbxqnjIuFo
Not variable size types, variable type size.
As in different types (can) have different sizes, as opposed to reference based languages where all types take a pointer and memory layout is only a concern for a type’s internal metadata.
Hence my surprise that they used a row layout, if all types have the same size then row v column is not (as much of) a concern, every value takes a pointer and there’s no padding or storage loss. But if the key and value can have different alignments then you generally want to segregate keys and values to avoid waste.
Not true of arrays, but not the point.
I assume that cache coherency / locality of reference is the rationale for putting keys and values together. Performance trumps compactness. Also, the typical types you use in maps contain pointers or are at least pointer-sized, so they’ll have compatible alignment.
Except now you’re losing that during probing, or when just iterating keys, especially if the value is not behind a pointer.
Unless compactness is what yields performances.
Unless they don’t because e.g. go not having sets means byte values are common.
Swiss Tables do a lot less probing due to that cute little byte-array table.
As for the other points, I dunno, it’s clear Google should have had you in the room suggesting these things, since of course they wouldn’t bother to actually profile and compare different layouts.
[Comment removed by author]
The focus on deletion seems a little strange here. Since to delete a key you need to insert it, and the insert+delete time is less on the new map the overall performance should still improve even if you have a 1:1 insert to delete ratio. So the only place where this should be an issue is if you have latency requirements for deletes, rather than throughput for inserts and deletes overall.
Of course this benchmark is far too simplistic to draw conclusions from anyways. With any change the only real way to know is benchmarking your use case in the real world.
Huh. I thought Go had started to already incorporate some Swiss Table optimizations, not sure if that’s the case or not, but I guess there was still work left regardless. Swiss Table is 7 years old, I’m surprised something as core as a hash map would leave this much performance on the table for so long.