aboutsummaryrefslogtreecommitdiff
path: root/src/internal/runtime/maps
AgeCommit message (Collapse)Author
2025-07-15runtime/maps: fix typo in group.go comment (instrinsified -> intrinsified)dyma solovei
Several comments refer to bitset as 'instrinsified', which is likely a typo, because it refers to the output of the intrinsics implemented with SIMD. Change-Id: I00f26b8d8128592ee0e9dc8a1b1480c93a9542d6 GitHub-Last-Rev: 8a4236710979f2f969210e0b261bdb9ae44f3321 GitHub-Pull-Request: golang/go#74624 Reviewed-on: https://go-review.googlesource.com/c/go/+/688016 Reviewed-by: Keith Randall <khr@golang.org> Auto-Submit: Keith Randall <khr@golang.org> Reviewed-by: Cherry Mui <cherryyz@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@google.com>
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-04-18internal/runtime/maps: move tombstone test to swiss fileMichael Pratt
This test fails on GOEXPERIMENT=noswissmap as it is testing behavior specific to swissmaps. Move it to map_swiss_test.go to skip it on noswissmap. We could also switch the test to use NewTestMap, which provides a swissmap even in GOEXPERIMENT=noswissmap, but that is tedious to use and noswissmap is going away soon anyway. For #70886. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-noswissmap Change-Id: I6a6a636c5ec72217d936cd01e9da36ae127ea2c5 Reviewed-on: https://go-review.googlesource.com/c/go/+/666437 Reviewed-by: Keith Randall <khr@golang.org> 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>
2025-04-17internal/runtime/maps: prune tombstones in maps before growingKeith Randall
Before growing, if there are lots of tombstones try to remove them. If we can remove enough, we can continue at the given size for a while longer. Fixes #70886 Change-Id: I71e0d873ae118bb35798314ec25e78eaa5340d73 Reviewed-on: https://go-review.googlesource.com/c/go/+/640955 Reviewed-by: Michael Pratt <mpratt@google.com> Reviewed-by: Keith Randall <khr@google.com> Auto-Submit: Keith Randall <khr@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
2025-04-08internal/runtime/maps: pass proper func PC to race.WritePC/race.ReadPCMateusz Poliwczak
Fixes #73191 Change-Id: I0f8a5a19faa745943a98476c7caf4c97ccdce184 Reviewed-on: https://go-review.googlesource.com/c/go/+/663175 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Michael Pratt <mpratt@google.com> Auto-Submit: Michael Pratt <mpratt@google.com> Reviewed-by: Dmitri Shuralyov <dmitshur@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>
2025-02-16runtime/maps: fix typo in group.go comment (H1 -> H2)Artyom Litovets
Fixes a typo to correctly describe the hash bits of the control word. Change-Id: Id3c2ae0bd529e579a95258845f9d8028e23d10d2 GitHub-Last-Rev: 1baa81be5d292d5625d5d7788b8ea090453f962c GitHub-Pull-Request: golang/go#71730 Reviewed-on: https://go-review.googlesource.com/c/go/+/649416 Reviewed-by: Keith Randall <khr@golang.org> Auto-Submit: 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> Reviewed-by: Ian Lance Taylor <iant@google.com>
2025-01-14internal/runtime/maps: re-enable some testsKeith Randall
Re-enable tests for stack-allocated maps and fast map accessors. Those are implemented now. Update #54766 Change-Id: I8c019702bd9fb077b2fe3f7c78e8e9e10d2263a6 Reviewed-on: https://go-review.googlesource.com/c/go/+/642376 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: Michael Pratt <mpratt@google.com> Auto-Submit: Keith Randall <khr@golang.org>
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-21all: fix some function names and typos in commentcuishuang
Change-Id: I07e7c8eaa5bd4bac0d576b2f2f4cd3f81b0b77a4 Reviewed-on: https://go-review.googlesource.com/c/go/+/630055 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Commit-Queue: Ian Lance Taylor <iant@google.com> Reviewed-by: Ian Lance Taylor <iant@google.com> Reviewed-by: Russ Cox <rsc@golang.org> Auto-Submit: Ian Lance Taylor <iant@google.com>
2024-11-20cmd/compile: intrinsify swissmap match calls with SIMD on amd64Michael Pratt
Use similar SIMD operations to the ones used in Abseil. We still using 8-slot groups (even though the XMM registers could handle 16-slot groups) to keep the implementation simpler (no changes to the memory layout of maps). Still, the implementations of matchH2 and matchEmpty are shorter than the portable version using standard arithmetic operations. They also return a packed bitset, which avoids the need to shift in bitset.first. That said, the packed bitset is a downside in cognitive complexity, as we have to think about two different possible representations. This doesn't leak out of the API, but we do need to intrinsify bitset to switch to a compatible implementation. The compiler's intrinsics don't support intrinsifying methods, so the implementations move to free functions. This makes operations between 0-3% faster on my machine. e.g., MapGetHit/impl=runtimeMap/t=Int64/len=6-12 12.34n ± 1% 11.42n ± 1% -7.46% (p=0.000 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=12-12 15.14n ± 2% 14.88n ± 1% -1.72% (p=0.009 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=18-12 15.04n ± 6% 14.66n ± 2% -2.53% (p=0.000 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=24-12 15.80n ± 1% 15.48n ± 3% ~ (p=0.444 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=30-12 15.55n ± 4% 14.77n ± 3% -5.02% (p=0.004 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=64-12 15.26n ± 1% 15.05n ± 1% ~ (p=0.055 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=128-12 15.34n ± 1% 15.02n ± 2% -2.09% (p=0.000 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=256-12 15.42n ± 1% 15.15n ± 1% -1.75% (p=0.001 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=512-12 15.48n ± 1% 15.18n ± 1% -1.94% (p=0.000 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=1024-12 17.38n ± 1% 17.05n ± 1% -1.90% (p=0.000 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=2048-12 17.96n ± 0% 17.59n ± 1% -2.06% (p=0.000 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=4096-12 18.36n ± 1% 18.18n ± 1% -0.98% (p=0.013 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=8192-12 18.75n ± 0% 18.31n ± 1% -2.35% (p=0.000 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=65536-12 26.25n ± 0% 25.95n ± 1% -1.14% (p=0.000 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=262144-12 44.24n ± 1% 44.06n ± 1% ~ (p=0.181 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=1048576-12 85.02n ± 0% 85.35n ± 0% +0.39% (p=0.032 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=4194304-12 98.87n ± 1% 98.85n ± 1% ~ (p=0.799 n=25) For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-ppc64_power10,gotip-linux-amd64-goamd64v3 Change-Id: Ic1b852f02744404122cb3672900fd95f4625905e Reviewed-on: https://go-review.googlesource.com/c/go/+/626277 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-11-19internal/runtime/maps: hash copy of key instead of key itselfKeith Randall
Hashing the key means we have to take the address of it. That inhibits subsequent optimizations on the key variable. By hashing a copy, we incur an extra store at the hash callsite, but we no longer need a load of the key in the inner loop. It can live in a register throughout. (Technically, it gets spilled around the call to the hasher, but it gets restored outside the loop.) Maybe one day we can have special hash functions that take int64/int32/string instead of *int64/*int32/*string. Change-Id: Iba3133f6e82328f53c0abcb5eec13ee47c4969d1 Reviewed-on: https://go-review.googlesource.com/c/go/+/629419 Reviewed-by: Russ Cox <rsc@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Michael Pratt <mpratt@google.com>
2024-11-19internal/runtime/maps: assume constant elem offset with int64 and string keysKeith Randall
Note this doesn't work with int32 keys because alignment padding can change the offset of the element. Change-Id: I27804d3cfc7cc1b7f995f7e29630f0824f0ee899 Reviewed-on: https://go-review.googlesource.com/c/go/+/629418 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Michael Pratt <mpratt@google.com> Reviewed-by: Russ Cox <rsc@golang.org>
2024-11-19internal/runtime/maps: use simpler calculation for slot elementKeith Randall
This reduces the adds required at the return point from 3 to 1. (The multiply inside g.elem() does get CSE'd with the one inside g.key(), but the rest of the adds don't.) Instead, compute the element as just a fixed offset from the key. Change-Id: Ia4d7664efafcdca5e9daeb77d270651bb186232c Reviewed-on: https://go-review.googlesource.com/c/go/+/629535 Reviewed-by: Russ Cox <rsc@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Michael Pratt <mpratt@google.com>
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-18internal/runtime/maps: fix noswiss builderkhr@golang.org
Missed initializing a field in the stub that lets the noswiss builder test the swiss implementation. Change-Id: Ie093478ad3e4301e4fe88ba65c132a9dbccd89a9 Reviewed-on: https://go-review.googlesource.com/c/go/+/628895 Auto-Submit: Keith Randall <khr@golang.org> Reviewed-by: Cherry Mui <cherryyz@google.com> Reviewed-by: Keith Randall <khr@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
2024-11-17runtime/internal/maps: remove entryMaskKeith Randall
It is easily recomputed as capacity-1. This reduces a table from 40 to 32 bytes (on 64-bit archs). That gets us down one sizeclass. Change-Id: Icb74fb2de50baa18ca62052c7b2fe8e6af4c8837 Reviewed-on: https://go-review.googlesource.com/c/go/+/625198 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Auto-Submit: Keith Randall <khr@golang.org> Reviewed-by: Michael Pratt <mpratt@google.com> Reviewed-by: Keith Randall <khr@google.com>
2024-11-17internal/runtime/maps: simplify small group lookupKeith Randall
We don't really need the index of the slot we're looking at. Just keep looking until there are no more filled slots. This particularly helps when there are only a few filled entries (packed at the bottom), and we're looking for something that isn't there. We exit earlier than we would otherwise. goos: darwin goarch: arm64 pkg: runtime cpu: Apple M2 Ultra │ baseline │ experiment │ │ sec/op │ sec/op vs base │ MapSmallAccessHit/Key=int64/Elem=int64/len=1-24 2.759n ± 0% 2.779n ± 2% ~ (p=0.055 n=10) MapSmallAccessHit/Key=int64/Elem=int64/len=2-24 2.862n ± 1% 2.922n ± 1% +2.08% (p=0.000 n=10) MapSmallAccessHit/Key=int64/Elem=int64/len=3-24 3.003n ± 0% 3.061n ± 1% +1.91% (p=0.000 n=10) MapSmallAccessHit/Key=int64/Elem=int64/len=4-24 3.170n ± 1% 3.188n ± 1% +0.57% (p=0.030 n=10) MapSmallAccessHit/Key=int64/Elem=int64/len=5-24 3.387n ± 1% 3.391n ± 1% ~ (p=0.362 n=10) MapSmallAccessHit/Key=int64/Elem=int64/len=6-24 3.601n ± 1% 3.584n ± 0% -0.49% (p=0.009 n=10) MapSmallAccessHit/Key=int64/Elem=int64/len=7-24 3.785n ± 1% 3.778n ± 3% ~ (p=0.987 n=10) MapSmallAccessHit/Key=int64/Elem=int64/len=8-24 3.960n ± 1% 3.946n ± 1% ~ (p=0.256 n=10) MapSmallAccessMiss/Key=int64/Elem=int64/len=0-24 2.004n ± 1% MapSmallAccessMiss/Key=int64/Elem=int64/len=1-24 5.145n ± 1% 2.411n ± 1% -53.14% (p=0.000 n=10) MapSmallAccessMiss/Key=int64/Elem=int64/len=2-24 5.128n ± 0% 3.313n ± 1% -35.40% (p=0.000 n=10) MapSmallAccessMiss/Key=int64/Elem=int64/len=3-24 5.159n ± 1% 3.690n ± 1% -28.48% (p=0.000 n=10) MapSmallAccessMiss/Key=int64/Elem=int64/len=4-24 5.117n ± 1% 4.466n ± 6% -12.73% (p=0.000 n=10) MapSmallAccessMiss/Key=int64/Elem=int64/len=5-24 5.115n ± 1% 4.308n ± 1% -15.79% (p=0.000 n=10) MapSmallAccessMiss/Key=int64/Elem=int64/len=6-24 5.111n ± 1% 4.538n ± 2% -11.19% (p=0.000 n=10) MapSmallAccessMiss/Key=int64/Elem=int64/len=7-24 4.896n ± 4% 4.831n ± 1% -1.33% (p=0.001 n=10) MapSmallAccessMiss/Key=int64/Elem=int64/len=8-24 4.905n ± 1% 5.121n ± 1% +4.40% (p=0.000 n=10) geomean 3.917n 3.631n -11.11% Change-Id: Ife26ac457a513af24fa0921b839ee6cd5fed6fba Reviewed-on: https://go-review.googlesource.com/c/go/+/627717 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: Michael Pratt <mpratt@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-17runtime/internal/maps: optimize long string keys for small mapsKeith Randall
For large strings, do a quick equality check on all the slots. Only if more than one passes the quick equality check do we resort to hashing. │ baseline │ experiment │ │ sec/op │ sec/op vs base │ MegMap-24 16609.50n ± 1% 13.91n ± 3% -99.92% (p=0.000 n=10) MegOneMap-24 16655.00n ± 0% 12.27n ± 1% -99.93% (p=0.000 n=10) MegEqMap-24 41.31µ ± 1% 25.03µ ± 1% -39.40% (p=0.000 n=10) MegEmptyMap-24 2.034n ± 0% 2.027n ± 2% ~ (p=0.541 n=10) MegEmptyMapWithInterfaceKey-24 5.931n ± 2% 5.599n ± 1% -5.60% (p=0.000 n=10) MapStringKeysEight_16-24 8.473n ± 7% 8.224n ± 5% ~ (p=0.315 n=10) MapStringKeysEight_32-24 8.441n ± 2% 8.147n ± 1% -3.48% (p=0.002 n=10) MapStringKeysEight_64-24 8.769n ± 1% 8.517n ± 1% -2.87% (p=0.000 n=10) MapStringKeysEight_128-24 10.73n ± 4% 13.57n ± 8% +26.57% (p=0.000 n=10) MapStringKeysEight_256-24 12.97n ± 2% 14.35n ± 4% +10.64% (p=0.001 n=10) MapStringKeysEight_1M-24 17359.50n ± 3% 13.92n ± 4% -99.92% (p=0.000 n=10) Change-Id: I4cc2ea4edab12a4b03236de626c7bcf0f96b6cc0 Reviewed-on: https://go-review.googlesource.com/c/go/+/625905 Reviewed-by: Keith Randall <khr@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Michael Pratt <mpratt@google.com>
2024-11-13internal/runtime/maps: use match to skip non-full slots in iterationMichael Pratt
Iteration over swissmaps with low load (think map with large hint but only one entry) is signicantly regressed vs old maps. See noswiss vs swiss-tip below (+60%). Currently we visit every single slot and individually check if the slot is full or not. We can do much better by using the control word to find all full slots in a group in a single operation. This lets us skip completely empty groups for instance. Always using the control match approach is great for maps with low load, but is a regression for mostly full maps. Mostly full maps have the majority of slots full, so most calls to mapiternext will return the next slot. In that case, doing the full group match on every call is more expensive than checking the individual slot. Thus we take a hybrid approach: on each call, we first check an individual slot. If that slot is full, we're done. If that slot is non-full, then we fall back to doing full group matches. This trade-off works well. Both mostly empty and mostly full maps perform nearly as well as doing all matching and all individual, respectively. The fast path is placed above the slow path loop rather than combined (with some sort of `useMatch` variable) into a single loop to help the compiler's code generation. The compiler really struggles with code generation on a combined loop for some reason, yielding ~15% additional instructions/op. Comparison with old maps prior to this CL: │ noswiss │ swiss-tip │ │ sec/op │ sec/op vs base │ MapIter/Key=int64/Elem=int64/len=6-12 11.53n ± 2% 10.64n ± 2% -7.72% (p=0.002 n=6) MapIter/Key=int64/Elem=int64/len=64-12 10.180n ± 2% 9.670n ± 5% -5.01% (p=0.004 n=6) MapIter/Key=int64/Elem=int64/len=65536-12 10.78n ± 1% 10.15n ± 2% -5.84% (p=0.002 n=6) MapIterLowLoad/Key=int64/Elem=int64/len=6-12 6.116n ± 2% 6.840n ± 2% +11.84% (p=0.002 n=6) MapIterLowLoad/Key=int64/Elem=int64/len=64-12 2.403n ± 2% 3.892n ± 0% +61.95% (p=0.002 n=6) MapIterLowLoad/Key=int64/Elem=int64/len=65536-12 1.940n ± 3% 3.237n ± 1% +66.81% (p=0.002 n=6) MapPop/Key=int64/Elem=int64/len=6-12 66.20n ± 2% 60.14n ± 3% -9.15% (p=0.002 n=6) MapPop/Key=int64/Elem=int64/len=64-12 97.24n ± 1% 171.35n ± 1% +76.21% (p=0.002 n=6) MapPop/Key=int64/Elem=int64/len=65536-12 826.1n ± 12% 842.5n ± 10% ~ (p=0.937 n=6) geomean 17.93n 20.96n +16.88% After this CL: │ noswiss │ swiss-cl │ │ sec/op │ sec/op vs base │ MapIter/Key=int64/Elem=int64/len=6-12 11.53n ± 2% 10.90n ± 3% -5.42% (p=0.002 n=6) MapIter/Key=int64/Elem=int64/len=64-12 10.180n ± 2% 9.719n ± 9% -4.53% (p=0.043 n=6) MapIter/Key=int64/Elem=int64/len=65536-12 10.78n ± 1% 10.07n ± 2% -6.63% (p=0.002 n=6) MapIterLowLoad/Key=int64/Elem=int64/len=6-12 6.116n ± 2% 7.022n ± 1% +14.82% (p=0.002 n=6) MapIterLowLoad/Key=int64/Elem=int64/len=64-12 2.403n ± 2% 1.475n ± 1% -38.63% (p=0.002 n=6) MapIterLowLoad/Key=int64/Elem=int64/len=65536-12 1.940n ± 3% 1.210n ± 6% -37.67% (p=0.002 n=6) MapPop/Key=int64/Elem=int64/len=6-12 66.20n ± 2% 61.54n ± 2% -7.02% (p=0.002 n=6) MapPop/Key=int64/Elem=int64/len=64-12 97.24n ± 1% 110.10n ± 1% +13.23% (p=0.002 n=6) MapPop/Key=int64/Elem=int64/len=65536-12 826.1n ± 12% 504.7n ± 6% -38.91% (p=0.002 n=6) geomean 17.93n 15.29n -14.74% For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-ppc64_power10 Change-Id: Ic07f9df763239e85be57873103df5007144fdaef Reviewed-on: https://go-review.googlesource.com/c/go/+/627156 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> Reviewed-by: Keith Randall <khr@google.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-11internal/runtime/maps: get rid of a few obsolete TODOsKeith Randall
Change-Id: I7b3d95c0861ae2b6e0721b65aa75cda036435e9c Reviewed-on: https://go-review.googlesource.com/c/go/+/625903 Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: Michael Pratt <mpratt@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.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: clean up put slot callskhr@golang.org
Use matchEmptyOrDeleted instead of matchEmpty. Streamline the code a bit. TODO: replicate in all the _fast files. Change-Id: I4df16a13a19df3aaae0c42e0c12f20552f08ead6 Reviewed-on: https://go-review.googlesource.com/c/go/+/624055 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: Michael Pratt <mpratt@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-11-01internal/runtime/maps: removed unused convertNonFullToEmptyAndFullToDeletedKeith Randall
I don't think we have any code that uses this function. Unless it is something for the future. Change-Id: I7e44634f7a9c1d4d64d84c358447ccf213668d92 Reviewed-on: https://go-review.googlesource.com/c/go/+/622077 Reviewed-by: Keith Randall <khr@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Michael Pratt <mpratt@google.com>
2024-11-01internal/runtime/maps: simplify emptyOrDeleted conditionKeith Randall
Change-Id: I37e5bba9cd62b2d970754ac24da7e1397ef12fd4 Reviewed-on: https://go-review.googlesource.com/c/go/+/622076 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: store group across Iter.Next callsMichael Pratt
A previous CL kept it across loop iterations, but those are more rare than call iterations. For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: Ieea0f1677e357f5e451650b1c697da7f63f3bca1 Reviewed-on: https://go-review.googlesource.com/c/go/+/621116 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>
2024-10-30internal/runtime/maps: avoid table lookup on most Iter.Next callsMichael Pratt
Speeds up iteration by about 3%. For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: I3406376fb8db87306d52e665fcee1f33cf610f24 Reviewed-on: https://go-review.googlesource.com/c/go/+/621115 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: optimize small map lookups with int keysMichael Pratt
Load the field we need from the type once outside the search loop. Get rid of the multiply to compute the slot position. Instead compute the slot position incrementally using addition. Move the hashing later in access2. Based on khr@'s CL 618959. For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: Id11b5479fa5bc0130a1d8d9e664d0206d24942ea Reviewed-on: https://go-review.googlesource.com/c/go/+/620217 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> 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: enable race for map functions in internal/runtime/mapsMichael Pratt
For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: Iebc7f5482299cb7c4ecccc4c2eb46b4bc42c5fc3 Reviewed-on: https://go-review.googlesource.com/c/go/+/616459 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>
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-29runtime: move mapaccess1 and mapassign to internal/runtime/mapsMichael Pratt
This enables manual inlining Map.Get/table.getWithoutKey to create a simple fast path with no calls. For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: Ic208dd4c02c7554f312b85b5fadccaf82b23545c Reviewed-on: https://go-review.googlesource.com/c/go/+/616455 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: speed up moduloMichael Pratt
For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: Ic47721e101f6fee650e6825a5a241fcd12fa0009 Reviewed-on: https://go-review.googlesource.com/c/go/+/611185 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Auto-Submit: Michael Pratt <mpratt@google.com> Reviewed-by: Michael Knyszek <mknyszek@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-28internal/runtime/maps: merge Iter.groupIdx and Iter.slotIdxMichael Pratt
For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap Change-Id: Ie21ef0f33f42735eadccd75eeebb3b5e81c2f459 Reviewed-on: https://go-review.googlesource.com/c/go/+/618535 Auto-Submit: Michael Pratt <mpratt@google.com> Reviewed-by: Michael Knyszek <mknyszek@google.com> Commit-Queue: Michael Pratt <mpratt@google.com> Reviewed-by: David Chase <drchase@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
generated by cgit v1.3 (git 2.53.0) at 2026-04-15 12:18:34 +0000