runtime: use SwissTable #54766
Description
Abstract
From ByteDance Programming Language Team
We suggest using SwissTable in the runtime to replace the original implementation of the hashmap.
SwissTable is now used in abseil and rust by default. We borrowed ideas from the two implementations and combined some optimization ideas of Go's original hashmap to construct the current implementation.
See the following comment for performance comparison(the GitHub issue has a character limit).
Motivations
-
We need to improve the performance of the hashmap as much as possible. At ByteDance, our Go service consumes about 4% of the CPU on hashmap. It is worth noting that on many services, the CPU consumption of
mapassignandmapaccessare almost 1:1, so the improvement of insertion performance is equally important. -
Support dynamic adjustment of the capacity of the hashmap. Some Go services will make a map too large due to burst traffic, which will cause a lot of pressure on the memory, but the map does not shrink after elements removal. We found that there are also many related discussions in the community:
Implementations
-
Basic version: https://go-review.googlesource.com/c/go/+/426614
-
SIMD version: TODO
Tasks
- Basic version: without SIMD, follow the original memory layout.Add SIMD support for x86: WIP, in the following CL.Aggregates all tophash into an array: In the plan, it requires more performance comparison data.Support hashmap resizing: More discussion is needed.Set bucketCnt to 4 on 32-bit platforms: More discussion is needed.
Advantages compared to the original implementation
-
The overall performance is better, and we can also use SIMD to improve performance.
-
SwissTable's LoadFactor can be set higher to save some memory.
-
Open-addressing and making dynamic adjustments to the capacity is easier to implement.
-
After allocating a fixed-size hashmap, if the number of inserted elements does not exceed the capacity, no additional memory is required, and the performance will be significantly improved, which has a greater advantage over reused fixed-size hashmap. (The original hashmap may still allocate additional memory even when the limit is not exceeded)
Disadvantages compared to the original implementation
-
The rehash is done at once, so
- Some services that are sensitive to latency may experience performance degradation. (but we do not observe this for now)
- In some cases, when the hashmap needs to grow, it may consume more CPU than the original implementation. (The previous implementation uses incremental rehash)
-
Since SwissTable needs to ensure that each bucket has at least one empty slot, it will cause performance degradation in some cases. For example, if we insert an element when there are seven elements in the hashmap, the CPU consumption will significantly increase because the hashmap needs to grow.
Implementation details
Here is an overview of the basic version. For more detailed implementation, you can read the code. Before reading the code, it is recommended to check the video or the article in the references to get a general idea of how it works.
Differences with SwissTable
- Move
tophashinto the bucket, not as an array alone.
The classic SwissTable aggregates all tophash into an array (also called control bytes array, here we follow the convention, called tophash), while the original hashmap of Go puts tophash and items in the same bucket.
Our experiments outside the runtime found that if tophash is used as an array alone, we couldn’t find any performance wins. This is probably because we need two memory allocations when initializing the hashmap.
So we use the bucket memory layout almost the same as the original in the current version. In the future, we may consider aggregating all tophash into an array, using a data structure similar to sync.Pool, so that all tophash of the hashmap can be reused to improve performance.
Due to this change, when we delete a key/value, we only need to determine whether the current bucket still has empty slots, because the location where we access the bucket is relatively fixed, unlike the classic implementation, which can be accessed from different addresses.
Differences with the original implementation
For hashmap header (hmap) and hiter
- Removed fields about overflow and incremental rehash.
For bucket (bmap)
-
The tophash is still 8-bit(uint8), but 7-bit for hash info and 1-bit as flags.
-
Removed overflow pointer.
For the way of querying
- The query process changes from querying the overflow pointer to finding the next bucket (using triangular probing) until the first empty slot is found. SwissTable theoretically guarantees that there is at least one empty slot.
For initializing bucket arrays
- The initial state of the tophash is
0xffinstead of0;0xffrepresents the empty slot now.
References
Metadata
Metadata
Assignees
Labels
Type
Projects
Status
Relationships
Development
Participants
Activity
zhangyunhao116 commentedon Aug 30, 2022
Performance comparison
Here the SwissTable is just a basic version. To avoid a CL bringing too many changes, it does not use SIMD and is compatible with the previous hashmap memory layout(it means many optimizations are not included in this version). Its performance still has room for improvement; we will add these optimizations in subsequent CLs.
In general, the performance changes for the basic version of SwissTable are as follows.
There is a significant improvement (20% ~ 50%) when querying a large hashmap or querying an element that does not exist in the hashmap. When querying a hashmap with fewer elements, performance degradation is up to 20%.
Insertions and deletions have been significantly improved in almost all cases (20% ~ 50%).
The performance of iterate is improved by about 10%.
Memory usage is reduced by 0% ~ 25% in most cases. Reusing a fixed-size hashmap no longer consumes any extra memory.
Since the growth is done at once, the CPU usage is significantly reduced in the case of continuous growth, but in some cases, the CPU consumption may also increase significantly.
Platform
GO: linux/amd64
CPU: AMD 3700x(8C16T)
OS: Ubuntu 22.04.1 LTS (GNU/Linux 5.15.0-43-generic x86_64)
MEMORY: 16G x 2 (DDR4 3200MHz)
Benchmark-1
Located in https://github.com/zhangyunhao116/gomapbench
This benchmark contains performance comparisons of common operations of common types in different situations.
INFO
Benchmark-2
The benchmarks from runtime.
INFO
gopherbot commentedon Aug 30, 2022
Change https://go.dev/cl/426614 mentions this issue:
runtime: use SwissTableseankhliao commentedon Aug 30, 2022
cc @golang/runtime
prattmic commentedon Aug 30, 2022
cc @randall77
Overall this sounds great. The main concern I have up front here is that growing happens all at once rather than incrementally. Could you explain more why that is and if it is possible to do so incrementally?
aaronbee commentedon Aug 30, 2022
Do iterators get invalidated when the map is modified? This is common for open-addressing hash tables. An important feature of the current map is that you can modify the map while iterating and the iterator still works.
aaronbee commentedon Aug 30, 2022
I checked the implementation and it does look like iterators stay valid when the map is modified.
randall77 commentedon Aug 30, 2022
The semantics of Go iterators basically mean you can't move items in the map data structure once you've placed them. So, for instance, you can't move a valid item to fill in a deleted one - you need to always use a tombstone. But other than that, iterators don't add much of a restriction to the implementation.
aclements commentedon Aug 31, 2022
This is really exciting. Thanks for doing all of this work.
There are many slowdowns in these benchmarks, some quite significant. Do you understand the source of these slowdowns? Is it something that can be fixed?
This is an important property to maintain because it can significantly impact the tail latency of services. We've done a lot of work throughout the Go runtime over the years to avoid unpredictable performance spikes and it would be a shame to regress here.
I'm not personally familiar with the details of SwissTable. Is incremental rehashing something that can be done and just hasn't been implemented yet, or is it fundamentally difficult?
If it's fundamentally difficult to do directly in SwissTable, I've been kickaround the the idea of adopting aspects of extendible hashing for a while, which could be a general solution to incremental resizing. I should probably just file an "idea" issue about this, but I'll try to lay it out here.
The idea is that, once a hash table grows beyond some size threshold based on bounding how long it takes to resize a map, you switch to a two-level scheme. I'm guessing that threshold would be around 4MiB, but that would have to be determined experimentally. In the two-level scheme, the top level is an index array keyed by the top k bits of the hash, which then points to map shards, which are individual SwissTables. The Wikipedia article I linked has some good diagrams for visualizing this. Each shard s contains only the items whose top js <= k bits are all identical, and multiple index entries will point to the same shard if that shard's js < k. When an individual shard overflows the threshold size, you split just that shard into two new shards s1 and s2 with js1 = js2 = js+1, and update the index. If js1 > k, then you also double the index array in order to increase k by 1.
This would enable incremental growth and bound the resize cost paid by any single map operation. Iterators can continue to work while a map is resized by holding on to the pre-resize shard they are currently iterating (let the GC collect this once all iterators have moved past it). It would also reduce overall memory footprint because the total memory size of a map doesn't have to be a power of two (even if each individual shard is). It would result in less memory fragmentation caused by large maps because it limits the size of each individual allocation. And it would address problems with our current map resizing algorithm where, if a map is grown to a size that puts it into resizing mode, but then modifications stop and the application switches to only reading from the map, accesses are relatively slow and the map continues to consume additional memory (#51410).
227 remaining items