aboutsummaryrefslogtreecommitdiff
path: root/src/internal/runtime/maps/map.go
AgeCommit message (Collapse)Author
2025-10-24runtime: use 32-bit hash for maps on WasmCherry Mui
Currently we use 64-bit hash calculations on Wasm. The 64-bit hash calculation make intensive uses of 64x64->128 bit multiplications, which on many 64-bit platforms are compiler intrinsics and can be compiled to one or two instructions. This is not the case on Wasm, so it is not very performant. This CL makes it use 32-bit hashes on Wasm, just like other 32-bit architectures. The 32-bit hash calculation only uses 32x32->64 bit multiplications, which can be compiled efficiently on Wasm. Using 32-bit hashes may increase the chance of collisions. But it is the same as 32-bit architectures like 386. And our Wasm port supports only 32-bit address space (like 386), so this is not too bad. Runtime Hash benchmark results goos: js goarch: wasm pkg: runtime │ 0h.txt │ 1h.txt │ │ sec/op │ sec/op vs base │ Hash5 20.45n ± 9% 14.06n ± 2% -31.21% (p=0.000 n=10) Hash16 22.34n ± 7% 17.52n ± 1% -21.62% (p=0.000 n=10) Hash64 47.47n ± 3% 28.68n ± 1% -39.59% (p=0.000 n=10) Hash1024 475.4n ± 1% 271.4n ± 0% -42.92% (p=0.000 n=10) Hash65536 28.42µ ± 1% 16.66µ ± 0% -41.40% (p=0.000 n=10) HashStringSpeed 40.07n ± 7% 29.23n ± 1% -27.05% (p=0.000 n=10) HashBytesSpeed 62.01n ± 3% 46.11n ± 4% -25.64% (p=0.000 n=10) HashInt32Speed 24.31n ± 2% 20.39n ± 1% -16.13% (p=0.000 n=10) HashInt64Speed 25.48n ± 7% 20.81n ± 7% -18.29% (p=0.000 n=10) HashStringArraySpeed 87.69n ± 4% 76.65n ± 2% -12.58% (p=0.000 n=10) FastrandHashiter 87.65n ± 1% 87.65n ± 1% ~ (p=0.896 n=10) geomean 90.82n 67.03n -26.19% Map benchmarks are too many to post here. The speedups are around 0-40%. Change-Id: I2f7a68cfc446ab5a547fdb6a40aea07854516d51 Reviewed-on: https://go-review.googlesource.com/c/go/+/714600 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Michael Pratt <mpratt@google.com>
2025-07-30all: remove redundant Swiss prefixesMichael Pratt
Now that there is only one map implementation we can simplify names. For #54766. Change-Id: I6a6a636cc6a8fc5e7712c27782fc0ced7467b939 Reviewed-on: https://go-review.googlesource.com/c/go/+/691596 Reviewed-by: Keith Randall <khr@google.com> Auto-Submit: Michael Pratt <mpratt@google.com> Reviewed-by: Keith Randall <khr@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
2025-07-30all: remove GOEXPERIMENT=swissmapMichael Pratt
For #54766. Change-Id: I6a6a636c40b5fe2e8b0d4a5e23933492bc8bb76e Reviewed-on: https://go-review.googlesource.com/c/go/+/691595 Reviewed-by: Keith Randall <khr@google.com> Auto-Submit: Michael Pratt <mpratt@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@golang.org>
2025-07-29internal/abi: move direct/indirect flag from Kind to TFlagKeith Randall
This info makes more sense in the flags instead of as a high bit of the kind. This makes kind access simpler because we now don't need to mask anything. Cleaned up most direct field accesses to use methods instead. (reflect making new types is the only remaining direct accessor.) IfaceIndir -> !IsDirectIface everywhere. gocore has been updated to handle the new location. So has delve. TODO: any other tools need updating? Change-Id: I123f97a4d4bdd0bff1641ee7e276d1cc0bd7e8eb Reviewed-on: https://go-review.googlesource.com/c/go/+/681936 Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: David Chase <drchase@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
2025-07-28internal/runtime/maps: fix spelling errors in commentsRuihua Wen
Change-Id: I289d26f75bb556b46699159f06ce7eb03d34656d GitHub-Last-Rev: 10ce76df1d4951e021d460808c9d477cfbcf7c5c GitHub-Pull-Request: golang/go#74733 Reviewed-on: https://go-review.googlesource.com/c/go/+/690095 Reviewed-by: Keith Randall <khr@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Mark Freeman <mark@golang.org> Reviewed-by: Keith Randall <khr@golang.org>
2025-05-07internal/runtime/maps: make clear also erase tombstoneskhr@golang.org
This will make future uses of the map faster because the probe sequences will likely be shorter. Change-Id: If10f3af49a5feaff7d1b82337bbbfb93bcd9dcb5 Reviewed-on: https://go-review.googlesource.com/c/go/+/633076 Auto-Submit: Keith Randall <khr@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Michael Pratt <mpratt@google.com> Reviewed-by: Keith Randall <khr@google.com>
2025-04-22runtime, internal/runtime/maps: speed-up empty/zero map lookupsMateusz Poliwczak
This lets the inliner do a better job optimizing the mapKeyError call. goos: linux goarch: amd64 pkg: runtime cpu: AMD Ryzen 5 4600G with Radeon Graphics │ /tmp/before2 │ /tmp/after3 │ │ sec/op │ sec/op vs base │ MapAccessZero/Key=int64-12 1.875n ± 0% 1.875n ± 0% ~ (p=0.506 n=25) MapAccessZero/Key=int32-12 1.875n ± 0% 1.875n ± 0% ~ (p=0.082 n=25) MapAccessZero/Key=string-12 1.902n ± 1% 1.902n ± 1% ~ (p=0.256 n=25) MapAccessZero/Key=mediumType-12 2.816n ± 0% 1.958n ± 0% -30.47% (p=0.000 n=25) MapAccessZero/Key=bigType-12 2.815n ± 0% 1.935n ± 0% -31.26% (p=0.000 n=25) MapAccessEmpty/Key=int64-12 1.942n ± 0% 2.109n ± 0% +8.60% (p=0.000 n=25) MapAccessEmpty/Key=int32-12 2.110n ± 0% 1.940n ± 0% -8.06% (p=0.000 n=25) MapAccessEmpty/Key=string-12 2.024n ± 0% 2.109n ± 0% +4.20% (p=0.000 n=25) MapAccessEmpty/Key=mediumType-12 3.157n ± 0% 2.344n ± 0% -25.75% (p=0.000 n=25) MapAccessEmpty/Key=bigType-12 3.054n ± 0% 2.115n ± 0% -30.75% (p=0.000 n=25) geomean 2.305n 2.011n -12.75% Change-Id: Iee83930884dc4c8a791a711aa189a1c93b68d536 Reviewed-on: https://go-review.googlesource.com/c/go/+/663495 Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Michael Pratt <mpratt@google.com>
2025-03-30internal/runtime/maps: speed up small map lookups ~1.7x for unpredictable keysthepudds
On master, lookups on small Swiss Table maps (<= 8 elements) for non-specialized key types are seemingly a performance regression compared to the Go 1.23 map implementation (reported in #70849). Currently, a linear scan is used for gets in these cases. This CL changes (*Map).getWithKeySmall to instead use the SIMD or SWAR match on the control bytes to then jump to candidate matching slots, with sample results below for a 16-byte key. This especially helps the hit case when the key is unpredictable, which previously had to scan an unpredictable number of control bytes to find a candidate slot when the key is unpredictable. Separately, other CLs in this stack modify the main Swiss Table benchmarks to randomize lookup key order (vs. previously most of the benchmarks had a repeating lookup key ordering, which likely is predictable until the map is too big). We have sample results for the randomized key order benchmarks followed by results from the older benchmarks. The first table below is with randomized key order. For hits, the older results get slower as there are more elements. With this CL, we see hits for unpredictable key ordering (sizes 2-8) get a ~1.7x speedup from ~25ns to ~14ns, with a now consistent lookup time for the different sizes. (The 1 element size map has a predictable key ordering because there is only one key, and that reports a modest ~0.5ns or ~3% performance penalty). Misses for unpredictable key order get a ~1.3x speedup, from ~13ns to ~10ns, with similar results for the 1 element size. │ no-fix-new-bmarks │ fix-with-new-bmarks │ │ sec/op │ sec/op vs base │ MapSmallAccessHit/Key=smallType/Elem=int32/len=1-4 13.26n ± 0% 13.64n ± 0% +2.90% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=2-4 19.47n ± 0% 13.62n ± 0% -30.05% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=3-4 22.23n ± 0% 13.64n ± 0% -38.68% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=4-4 23.98n ± 0% 13.64n ± 0% -43.11% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=5-4 25.02n ± 0% 13.67n ± 0% -45.35% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=6-4 25.77n ± 1% 13.68n ± 2% -46.89% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=7-4 26.38n ± 0% 13.64n ± 0% -48.28% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=8-4 26.31n ± 0% 13.71n ± 21% -47.90% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=1-4 13.055n ± 0% 9.815n ± 0% -24.82% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=2-4 13.070n ± 0% 9.813n ± 0% -24.92% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=3-4 13.060n ± 0% 9.819n ± 0% -24.82% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=4-4 13.075n ± 0% 9.816n ± 0% -24.92% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=5-4 13.060n ± 0% 9.826n ± 0% -24.76% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=6-4 13.095n ± 19% 9.834n ± 31% -24.90% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=7-4 13.075n ± 19% 9.822n ± 27% -24.88% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=8-4 13.11n ± 16% 12.14n ± 19% -7.43% (p=0.000 n=20) The next table uses the original benchmarks from just before this CL stack (i.e., without shuffling lookup keys). With this CL, we see improvement that is directionally similar to the above results but not as large, presumably because the branches in the linear scan are fairly predictable with predictable keys. (The numbers here also include the time from a mod in the benchmark code, which seemed to take around ~1/3 of CPU time based on spot checking a couple of examples, vs. the modified benchmarks shown above have removed that mod). │ master-8c3e391573 │ just-fix-with-old-bmarks │ │ sec/op │ sec/op vs base │ MapSmallAccessHit/Key=smallType/Elem=int32/len=1-4 20.85n ± 0% 21.69n ± 0% +4.03% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=2-4 21.22n ± 0% 21.70n ± 0% +2.24% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=3-4 21.73n ± 0% 21.71n ± 0% ~ (p=0.158 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=4-4 22.06n ± 0% 21.71n ± 0% -1.56% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=5-4 22.41n ± 0% 21.73n ± 0% -3.01% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=6-4 22.71n ± 0% 21.72n ± 0% -4.38% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=7-4 22.98n ± 0% 21.71n ± 0% -5.53% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=8-4 23.20n ± 0% 21.72n ± 0% -6.36% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=1-4 19.95n ± 0% 17.30n ± 0% -13.28% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=2-4 19.96n ± 0% 17.31n ± 0% -13.28% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=3-4 19.95n ± 0% 17.29n ± 0% -13.33% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=4-4 19.95n ± 0% 17.30n ± 0% -13.29% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=5-4 19.96n ± 25% 17.32n ± 0% -13.22% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=6-4 19.99n ± 24% 17.29n ± 0% -13.51% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=7-4 19.97n ± 20% 17.34n ± 16% -13.14% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=8-4 20.02n ± 11% 17.33n ± 14% -13.44% (p=0.000 n=20) geomean 21.02n 19.39n -7.78% See #70849 for additional benchmark results, including results for arm64 (which also means without SIMD support). Updates #54766 Updates #70700 Fixes #70849 Change-Id: Ic2361bb6fc15b4436d1d1d5be7e4712e547f611b Reviewed-on: https://go-review.googlesource.com/c/go/+/634396 Reviewed-by: Michael Pratt <mpratt@google.com> Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
2025-03-27maps: implement faster cloneKeith Randall
│ base │ experiment │ │ sec/op │ sec/op vs base │ MapClone-24 66.802m ± 7% 3.348m ± 2% -94.99% (p=0.000 n=10) Fixes #70836 Change-Id: I9e192b1ee82e18f5580ff18918307042a337fdcc Reviewed-on: https://go-review.googlesource.com/c/go/+/660175 Reviewed-by: Michael Pratt <mpratt@google.com> Auto-Submit: Keith Randall <khr@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@google.com>
2024-12-21cmd/compile: load map length with the right typeCherry Mui
len(map) is lowered to loading the first field of the map structure, which is the length. Currently it is a load of an int. With the old map, the first field is indeed an int. With Swiss map, however, it is a uint64. On big-endian 32-bit machine, loading an (32-bit) int from a uint64 would load just the high bits, which are (probably) all 0. Change to a load with the proper type. Fixes #70248. Change-Id: I39cf2d1e6658dac5a8de25c858e1580e2a14b894 Reviewed-on: https://go-review.googlesource.com/c/go/+/638375 Run-TryBot: Cherry Mui <cherryyz@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: Keith Randall <khr@golang.org>
2024-11-18internal/runtime/maps: don't copy indirect key/elem when growing mapsKeith Randall
We can reuse the same indirect storage when growing, so we don't need an additional allocation. Change-Id: I57adb406becfbec648188ec66f4bb2e94d4b9cab Reviewed-on: https://go-review.googlesource.com/c/go/+/625902 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Michael Pratt <mpratt@google.com> Reviewed-by: Keith Randall <khr@google.com>
2024-11-17internal/runtime/maps: eliminate a load from the hot pathKeith Randall
typ.Group.Size involves two loads. Instead cache GroupSize as a separate fields of the map type so we can get to it in just one load. Change-Id: I10ffdce1c7f75dcf448da14040fda78f0d75fd1d Reviewed-on: https://go-review.googlesource.com/c/go/+/627716 Reviewed-by: Cherry Mui <cherryyz@google.com> Reviewed-by: Michael Pratt <mpratt@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
2024-11-11internal/runtime/maps: don't hash twice when deletingKeith Randall
│ baseline │ experiment │ │ sec/op │ sec/op vs base │ MapDeleteLargeKey-24 312.0n ± 6% 162.3n ± 5% -47.97% (p=0.000 n=10) Change-Id: I31f1f8e3c344cf8abf2e9eb4b51b78fcd67b93c4 Reviewed-on: https://go-review.googlesource.com/c/go/+/625906 Reviewed-by: Michael Pratt <mpratt@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@google.com>
2024-11-01internal/runtime/maps: return after fatal to help register allocatorkhr@golang.org
Seems simple, but putting the return after fatal ensures that at the point of the small group loop, no call has happened so the key is still in a register. This ensures that we don't have to restore the key from the stack before the comparison on each iteration. That gets rid of a load from the inner loop. name old time/op new time/op delta MapAccessHit/Key=int64/Elem=int64/len=6-8 4.01ns ± 6% 3.85ns ± 3% -3.92% (p=0.001 n=10+10) Change-Id: Ia23ac48e6c5522be88f7d9be0ff3489b2dfc52fc Reviewed-on: https://go-review.googlesource.com/c/go/+/624255 Reviewed-by: Michael Pratt <mpratt@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@google.com>
2024-11-01internal/runtime/maps: use matchEmptyOrDeleted instead of matchEmptykhr@golang.org
It's a bit more efficient. Change-Id: If813a597516c41fdac6f60e586641d0ee1cde025 Reviewed-on: https://go-review.googlesource.com/c/go/+/623818 Reviewed-by: Michael Pratt <mpratt@google.com> Reviewed-by: Carlos Amedee <carlos@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
2024-10-30cmd/compile,internal/runtime/maps: stack allocated maps and small allocMichael Pratt
The compiler will stack allocate the Map struct and initial group if possible. Stack maps are initialized inline without calling into the runtime. Small heap allocated maps use makemap_small. These are the same heuristics as existing maps. For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: I6c371d1309716fd1c38a3212d417b3c76db5c9b9 Reviewed-on: https://go-review.googlesource.com/c/go/+/622042 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@golang.org> Reviewed-by: Keith Randall <khr@google.com> Auto-Submit: Michael Pratt <mpratt@google.com>
2024-10-30internal/runtime/maps: use uintptr instead of uint32 for index in groupMichael Pratt
This avoids some zero-extension ops on 64-bit machines. Based on khr@'s CL 619479. For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: Ie9a56da26382dc9e515c613abc8cf6fec3767671 Reviewed-on: https://go-review.googlesource.com/c/go/+/620216 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@golang.org> Reviewed-by: Keith Randall <khr@google.com> Auto-Submit: Michael Pratt <mpratt@google.com>
2024-10-30internal/runtime/maps: cleanup seed usageMichael Pratt
Keep only a single seed; initialize it; and reset it when the map is empty. For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: Icc231f70957337a2d0dcd9c7daf9bd3cb4354d71 Reviewed-on: https://go-review.googlesource.com/c/go/+/616466 Auto-Submit: Michael Pratt <mpratt@google.com> Reviewed-by: Keith Randall <khr@golang.org> Reviewed-by: Keith Randall <khr@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
2024-10-30runtime,internal/runtime/maps: specialized swissmapsMichael Pratt
Add all the specialized variants that exist for the existing maps. Like the existing maps, the fast variants do not support indirect key/elem. Note that as of this CL, the Get and Put methods on Map/table are effectively dead. They are only reachable from the internal/runtime/maps unit tests. For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: I95297750be6200f34ec483e4cfc897f048c26db7 Reviewed-on: https://go-review.googlesource.com/c/go/+/616463 Reviewed-by: Keith Randall <khr@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Auto-Submit: Michael Pratt <mpratt@google.com> Reviewed-by: Keith Randall <khr@google.com>
2024-10-30cmd/compile,runtime: add indirect key/elem to swissmapMichael Pratt
We use the same heuristics as existing maps. For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: I44bb51483cae2c1714717f1b501850fb9e55a39a Reviewed-on: https://go-review.googlesource.com/c/go/+/616461 Auto-Submit: Michael Pratt <mpratt@google.com> Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: Keith Randall <khr@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
2024-10-30runtime: add concurrent write checks to swissmapMichael Pratt
This is the same design as existing maps. For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: I5f6ef5fea1e0f0616bcd90eaae7faee4cdac58c6 Reviewed-on: https://go-review.googlesource.com/c/go/+/616460 Reviewed-by: Keith Randall <khr@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Auto-Submit: Michael Pratt <mpratt@google.com> Reviewed-by: Keith Randall <khr@google.com>
2024-10-30internal/runtime/maps: proper capacity hint handlingMichael Pratt
When given a hint size, set the initial capacity large enough to avoid requiring growth in the average case. When not given a hint (or given 0), don't allocate anything at all. For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: I8844fc652b8d2d4e5136cd56f7e78999a07fe381 Reviewed-on: https://go-review.googlesource.com/c/go/+/616457 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@golang.org> Reviewed-by: Keith Randall <khr@google.com> Auto-Submit: Michael Pratt <mpratt@google.com>
2024-10-29internal/runtime/maps: remove type fieldsMichael Pratt
Rather than storing the same type pointer in multiple places, just pass it around. For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: Ia6c74805c7a44125ae473177b317f16c6688e6de Reviewed-on: https://go-review.googlesource.com/c/go/+/622377 Auto-Submit: Michael Pratt <mpratt@google.com> Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: Keith Randall <khr@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
2024-10-28internal/runtime/maps: shift optimizationsMichael Pratt
Masking the shift lets the compiler elide a few instructions for handling a shift of > 63 bits. For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: I669fe01caa1de1b8521f1f56b6906f3e9066a39b Reviewed-on: https://go-review.googlesource.com/c/go/+/611190 Auto-Submit: Michael Pratt <mpratt@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@golang.org> Reviewed-by: Keith Randall <khr@google.com>
2024-10-28internal/runtime/maps: avoid passing unused key returnMichael Pratt
For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: Idee1e021e3cef8f0c031e8f06efbcf6e88918d8a Reviewed-on: https://go-review.googlesource.com/c/go/+/622376 Auto-Submit: Michael Pratt <mpratt@google.com> Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: Keith Randall <khr@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
2024-10-28internal/runtime/maps: linear scan of small mapMichael Pratt
We still use the hash and control word, but loop over all 8 bytes instead of doing the match operation, which ends up being slightly faster when there is only one group. Note that specialized variants added later will avoid hashing at all. For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: I3bb353b023dd6120b6585e87d3efe2f18ac9e1ef Reviewed-on: https://go-review.googlesource.com/c/go/+/611189 Reviewed-by: Keith Randall <khr@golang.org> Auto-Submit: Michael Pratt <mpratt@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@google.com>
2024-10-28internal/runtime/maps: small maps point directly to a groupMichael Pratt
If the map contains 8 or fewer entries, it is wasteful to have a directory that points to a table that points to a group. Add a special case that replaces the directory with a direct pointer to a group. We could theoretically do similar for single table maps (no directory, just point directly to a table), but that is left for later. For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: I6fc04dfc11c31dadfe5b5d6481b4c4abd43d48ed Reviewed-on: https://go-review.googlesource.com/c/go/+/611188 Reviewed-by: Keith Randall <khr@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Auto-Submit: Michael Pratt <mpratt@google.com> Reviewed-by: Keith Randall <khr@google.com>
2024-10-28internal/runtime/maps: reuse deleted slots on insertMichael Pratt
While walking the probe sequence, Put keeps track of the first deleted slot it encountered. If it reaches the end of the probe sequence without finding a match, then it will prefer to use the deleted slot rather than a new empty slot. For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: I19356ef6780176506f57b42990ac15dc426f1b14 Reviewed-on: https://go-review.googlesource.com/c/go/+/618016 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@google.com> Auto-Submit: Michael Pratt <mpratt@google.com> Reviewed-by: Keith Randall <khr@golang.org>
2024-10-21cmd/compile,internal/runtime/maps: add extendible hashingMichael Pratt
Extendible hashing splits a swisstable map into many swisstables. This keeps grow operations small. For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-ppc64_power10,gotip-linux-amd64-longtest-swissmap Change-Id: Id91f34af9e686bf35eb8882ee479956ece89e821 Reviewed-on: https://go-review.googlesource.com/c/go/+/604936 Reviewed-by: Keith Randall <khr@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@google.com>
2024-10-08internal/runtime/maps: initial swiss table map implementationMichael Pratt
Add a new package that will contain a new "Swiss Table" (https://abseil.io/about/design/swisstables) map implementation, which is intended to eventually replace the existing runtime map implementation. This implementation is based on the fabulous github.com/cockroachdb/swiss package contributed by Peter Mattis. This CL adds an hash map implementation. It supports all the core operations, but does not have incremental growth. For #54766. Change-Id: I52cf371448c3817d471ddb1f5a78f3513565db41 Reviewed-on: https://go-review.googlesource.com/c/go/+/582415 Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: Keith Randall <khr@golang.org> Auto-Submit: Michael Pratt <mpratt@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Michael Knyszek <mknyszek@google.com>
generated by cgit v1.3 (git 2.53.0) at 2026-04-16 09:56:29 +0000