| Age | Commit message (Collapse) | Author |
|---|
|
Map groups are currently:
type group struct {
ctrl uint64
slots [8]slot
}
type slot struct {
key K
elem E
}
If the element type is struct{}, the slot will be padded so that the
address of the elem is unique rather than pointing outside the alloc.
This has the effect of map[K]struct{} wasting space due to the extra
byte and padding, making it no better than map[K]bool.
This CL changes the group layout to instead place keys and elems
together, as they used to be before swiss maps:
type group struct {
ctrl uint64
keys [8]K
elems [8]V
}
This is an alternative to CL 701976, which I suspect will have better
performance. Keys placed together should lead to better cache behavior,
at the cost of more expensive elem lookups, since the elems are not a
fixed offset from their keys.
This change is locked behind GOEXPERIMENT=mapsplitgroup.
Updates #70835
Updates #71368
Change-Id: Ide8d1406ae4ab636f86edc40e0640cc80653197c
Reviewed-on: https://go-review.googlesource.com/c/go/+/711560
Reviewed-by: Michael Pratt <mpratt@google.com>
Auto-Submit: Michael Pratt <mpratt@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
|
|
This change improves performance of specialized maps and opens opportunity for further improvement by inlining hashing calls in the future (right now we can't inline functions from GOASM).
MapAccessBenchmarks
goos: linux
goarch: amd64
pkg: runtime
cpu: Intel(R) Xeon(R) CPU E5-2690 v3 @ 2.60GHz
│ base-randlayout-meged.stat │ devirt-randlayout-merged.stat │
│ sec/op │ sec/op vs base │
MapAccessHit/Key=int32/Elem=int32/len=6-4 21.35n ± 1% 21.72n ± 0% +1.73% (p=0.000 n=45)
MapAccessHit/Key=int32/Elem=int32/len=64-4 25.74n ± 1% 25.37n ± 2% -1.44% (p=0.006 n=45)
MapAccessHit/Key=int32/Elem=int32/len=65536-4 41.56n ± 0% 41.07n ± 0% -1.18% (p=0.000 n=45)
MapAccessHit/Key=int64/Elem=int64/len=6-4 21.53n ± 0% 21.56n ± 0% +0.14% (p=0.000 n=45)
MapAccessHit/Key=int64/Elem=int64/len=64-4 25.56n ± 0% 25.32n ± 2% ~ (p=0.651 n=45)
MapAccessHit/Key=int64/Elem=int64/len=65536-4 44.47n ± 0% 44.42n ± 0% ~ (p=0.645 n=45)
MapAccessHit/Key=string/Elem=string/len=6-4 30.54n ± 0% 30.83n ± 0% +0.95% (p=0.000 n=45)
MapAccessHit/Key=string/Elem=string/len=64-4 33.94n ± 0% 32.58n ± 0% -4.01% (p=0.000 n=45)
MapAccessHit/Key=string/Elem=string/len=65536-4 60.75n ± 1% 59.22n ± 0% -2.52% (p=0.000 n=45)
MapAccessHit/Key=int32/Elem=bigType/len=6-4 104.7n ± 0% 104.2n ± 0% -0.48% (p=0.000 n=45)
MapAccessHit/Key=int32/Elem=bigType/len=64-4 176.9n ± 2% 169.8n ± 1% -4.01% (p=0.000 n=45)
MapAccessHit/Key=int32/Elem=bigType/len=65536-4 603.3n ± 0% 604.6n ± 0% +0.22% (p=0.000 n=45)
MapAccessHit/Key=int32/Elem=*int32/len=6-4 21.75n ± 1% 21.90n ± 0% +0.69% (p=0.000 n=45)
MapAccessHit/Key=int32/Elem=*int32/len=64-4 26.28n ± 0% 25.74n ± 0% -2.05% (p=0.000 n=45)
MapAccessHit/Key=int32/Elem=*int32/len=65536-4 45.42n ± 0% 45.10n ± 0% -0.70% (p=0.000 n=45)
MapAccessMiss/Key=int32/Elem=int32/len=6-4 23.49n ± 0% 23.56n ± 1% +0.30% (p=0.000 n=45)
MapAccessMiss/Key=int32/Elem=int32/len=64-4 24.93n ± 3% 24.85n ± 2% ~ (p=0.144 n=45)
MapAccessMiss/Key=int32/Elem=int32/len=65536-4 37.68n ± 0% 37.20n ± 0% -1.27% (p=0.000 n=45)
MapAccessMiss/Key=int64/Elem=int64/len=6-4 23.49n ± 0% 23.44n ± 1% ~ (p=0.587 n=45)
MapAccessMiss/Key=int64/Elem=int64/len=64-4 25.66n ± 2% 25.02n ± 2% -2.49% (p=0.032 n=45)
MapAccessMiss/Key=int64/Elem=int64/len=65536-4 38.19n ± 0% 37.83n ± 0% -0.94% (p=0.000 n=45)
MapAccessMiss/Key=string/Elem=string/len=6-4 31.29n ± 0% 31.55n ± 0% +0.83% (p=0.000 n=45)
MapAccessMiss/Key=string/Elem=string/len=64-4 31.28n ± 3% 30.81n ± 2% -1.50% (p=0.025 n=45)
MapAccessMiss/Key=string/Elem=string/len=65536-4 46.76n ± 0% 45.81n ± 0% -2.03% (p=0.000 n=45)
MapAccessMiss/Key=int32/Elem=bigType/len=6-4 128.0n ± 0% 128.0n ± 0% ~ (p=0.647 n=45)
MapAccessMiss/Key=int32/Elem=bigType/len=64-4 129.7n ± 0% 130.2n ± 0% ~ (p=0.069 n=45)
MapAccessMiss/Key=int32/Elem=bigType/len=65536-4 154.3n ± 0% 154.3n ± 0% ~ (p=0.058 n=45)
MapAccessMiss/Key=int32/Elem=*int32/len=6-4 23.38n ± 1% 23.87n ± 1% +2.10% (p=0.000 n=45)
MapAccessMiss/Key=int32/Elem=*int32/len=64-4 25.52n ± 2% 25.41n ± 2% ~ (p=0.321 n=45)
MapAccessMiss/Key=int32/Elem=*int32/len=65536-4 38.28n ± 0% 37.95n ± 0% -0.86% (p=0.000 n=45)
MapAccessZero/Key=int64-4 2.708n ± 0% 3.095n ± 0% +14.29% (p=0.000 n=45)*
MapAccessZero/Key=int32-4 2.708n ± 0% 3.095n ± 0% +14.29% (p=0.000 n=45)*
MapAccessZero/Key=string-4 3.481n ± 0% 3.095n ± 0% -11.09% (p=0.000 n=45)*
MapAccessEmpty/Key=int64-4 3.095n ± 0% 3.096n ± 0% ~ (p=0.087 n=45)*
MapAccessEmpty/Key=int32-4 3.095n ± 0% 3.482n ± 0% +12.50% (p=0.000 n=45)*
MapAccessEmpty/Key=string-4 3.869n ± 0% 3.483n ± 0% -9.98% (p=0.000 n=45)*
geomean 28.04n 28.00n -0.12%
* MapAccess(Empy|Zero) shows weird results due to basic block alignment changes
Fixes: #77892
Change-Id: I43913ae5dfa2d3e0cd173a766614ca4341774761
Reviewed-on: https://go-review.googlesource.com/c/go/+/750580
Auto-Submit: Keith Randall <khr@golang.org>
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>
Reviewed-by: Michael Pratt <mpratt@google.com>
|
|
mapaccess2*
mapaccess1* and mapaccess2* functions share the same implementation and differ only in whether the boolean "found" is returned.
This change replaces mapaccess1* calls with mapaccess2*.
We can do this transparently, since the call site can safely discard the second (boolean) result.
Ideally, mapacces1* functions could be removed entirely, but this change keeps them as thin wrappers for compatibility.
Fixes #73196
Change-Id: I07c3423d22ed1095ac3666d00e134c2747b2f9c1
Reviewed-on: https://go-review.googlesource.com/c/go/+/736020
Reviewed-by: Keith Randall <khr@google.com>
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@golang.org>
|
|
Change-Id: I0cd9763aeedfe326bc566da39b8be0d0ebd113ec
GitHub-Last-Rev: 1ec88644148deb41eea2ae89f7f1fb1759b37c27
GitHub-Pull-Request: golang/go#74952
Reviewed-on: https://go-review.googlesource.com/c/go/+/694016
Auto-Submit: Michael Pratt <mpratt@google.com>
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
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@golang.org>
|
|
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>
|
|
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>
|
|
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>
|
|
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>
|
|
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>
|
