diff options
| author | sentientwaffle <sentientwaffle@gmail.com> | 2021-12-17 11:38:13 -0800 |
|---|---|---|
| committer | Andrew Kelley <andrew@ziglang.org> | 2021-12-17 15:21:41 -0800 |
| commit | 11803a3a569205d640c7ec0b0aedba83f47a6e64 (patch) | |
| tree | 5c45e90777f3993a162dbfbd9adb368df6ba75fc /lib/std/Thread | |
| parent | e8b39960bbd88d73cfd0d853e8ca7383e300c58c (diff) | |
| download | zig-11803a3a569205d640c7ec0b0aedba83f47a6e64.tar.gz zig-11803a3a569205d640c7ec0b0aedba83f47a6e64.zip | |
std: optimize hash_map probe loop condition
See https://github.com/ziglang/zig/pull/10337 for context.
In #10337 the `available` tracking fix necessitated an additional condition on the probe loop in both `getOrPut` and `getIndex` to prevent an infinite loop. Previously, this condition was implicit thanks to the guaranteed presence of a free slot.
The new condition hurts the `HashMap` benchmarks (https://github.com/ziglang/zig/pull/10337#issuecomment-996432758).
This commit removes that extra condition on the loop. Instead, when probing, first check whether the "home" slot is the target key — if so, return it. Otherwise, save the home slot's metadata to the stack and temporarily "free" the slot (but don't touch its value). Then continue with the original loop. Once again, the loop will be implicitly broken by the new "free" slot. The original metadata is restored before the function returns.
`getOrPut` has one additional gotcha — if the home slot is a tombstone and `getOrPut` misses, then the home slot is is written with the new key; that is, its original metadata (the tombstone) is not restored.
Other changes:
- Test hash map misses.
- Test using `getOrPutAssumeCapacity` to get keys at the end (along with `get`).
Diffstat (limited to 'lib/std/Thread')
0 files changed, 0 insertions, 0 deletions