| Age | Commit message (Collapse) | Author |
|---|
|
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>
|
|
The _swiss.go files are identical to the originals (except build tag).
Later CLs will change them.
For #54766.
Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap
Change-Id: I9943e2d6f1cfa227ffbf27c9ddc9ce853695d225
Reviewed-on: https://go-review.googlesource.com/c/go/+/580778
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Keith Randall <khr@golang.org>
Auto-Submit: Michael Pratt <mpratt@google.com>
Commit-Queue: Michael Pratt <mpratt@google.com>
Reviewed-by: Keith Randall <khr@google.com>
|
|
Ignored these linknames which have not worked for a while:
github.com/xtls/xray-core:
context.newCancelCtx removed in CL 463999 (Feb 2023)
github.com/u-root/u-root:
funcPC removed in CL 513837 (Jul 2023)
tinygo.org/x/drivers:
net.useNetdev never existed
For #67401.
Change-Id: I9293f4ef197bb5552b431de8939fa94988a060ce
Reviewed-on: https://go-review.googlesource.com/c/go/+/587576
Auto-Submit: Russ Cox <rsc@golang.org>
Reviewed-by: Cherry Mui <cherryyz@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
|
|
For #67401.
Change-Id: Icc10ede72547d8020c0ba45e89d954822a4b2455
Reviewed-on: https://go-review.googlesource.com/c/go/+/587218
Auto-Submit: Russ Cox <rsc@golang.org>
Reviewed-by: Cherry Mui <cherryyz@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
|
|
Note that this depends on the revert of CL 581395 to move zeroVal back.
For #67401.
Change-Id: I507c27c2404ad1348aabf1ffa3740e6b1957495b
Reviewed-on: https://go-review.googlesource.com/c/go/+/587217
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Auto-Submit: Russ Cox <rsc@golang.org>
Reviewed-by: Cherry Mui <cherryyz@google.com>
|
|
This reverts CL 581395, commit 2f5b420fb5984842afab37a9c2e66e6599107483.
It breaks a linkname from github.com/ugorji/go/codec.
For #67401.
A followup CL will document this dependence.
Change-Id: I66d6c39c03e769ab829ca4c3f4f61277b93380d3
Reviewed-on: https://go-review.googlesource.com/c/go/+/587216
TryBot-Bypass: Russ Cox <rsc@golang.org>
Auto-Submit: Russ Cox <rsc@golang.org>
Reviewed-by: Cherry Mui <cherryyz@google.com>
|
|
Change-Id: I0e19e4aa2ea47a714e27b8d66c23c449e27861f2
GitHub-Last-Rev: 2d59b9589efcf4ade6cfd7c8feffc46bf9ba912c
GitHub-Pull-Request: golang/go#67014
Reviewed-on: https://go-review.googlesource.com/c/go/+/581395
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>
Reviewed-by: Joedian Reid <joedian@google.com>
|
|
CL 565515 introduced these non-gofmt'ed lines. Gofmt them.
Change-Id: Id64244c204b2d6a0bd6377caa17869284eb34f45
Reviewed-on: https://go-review.googlesource.com/c/go/+/570216
Auto-Submit: Russ Cox <rsc@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
|
|
Change-Id: Ib78c1513616089f4942297cd17212b1b11871fd5
GitHub-Last-Rev: f97fe5b5bffffe25dc31de7964588640cb70ec41
GitHub-Pull-Request: golang/go#65819
Reviewed-on: https://go-review.googlesource.com/c/go/+/565515
Reviewed-by: Jorropo <jorropo.pgm@gmail.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Auto-Submit: Keith Randall <khr@golang.org>
Reviewed-by: Michael Knyszek <mknyszek@google.com>
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
For #59670
Change-Id: I9265e033bf3a84c3dc7b4a5d52c0df9672435f0d
GitHub-Last-Rev: 8e4099095cec9e774abe9b72212a1eab6f6f9fdb
GitHub-Pull-Request: golang/go#64774
Reviewed-on: https://go-review.googlesource.com/c/go/+/550117
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Than McIntosh <thanm@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
|
|
Move ChaCha8 code into internal/chacha8rand and use it to implement
runtime.rand, which is used for the unseeded global source for
both math/rand and math/rand/v2. This also affects the calculation of
the start point for iteration over very very large maps (when the
32-bit fastrand is not big enough).
The benefit is that misuse of the global random number generators
in math/rand and math/rand/v2 in contexts where non-predictable
randomness is important for security reasons is no longer a
security problem, removing a common mistake among programmers
who are unaware of the different kinds of randomness.
The cost is an extra 304 bytes per thread stored in the m struct
plus 2-3ns more per random uint64 due to the more sophisticated
algorithm. Using PCG looks like it would cost about the same,
although I haven't benchmarked that.
Before this, the math/rand and math/rand/v2 global generator
was wyrand (https://github.com/wangyi-fudan/wyhash).
For math/rand, using wyrand instead of the Mitchell/Reeds/Thompson
ALFG was justifiable, since the latter was not any better.
But for math/rand/v2, the global generator really should be
at least as good as one of the well-studied, specific algorithms
provided directly by the package, and it's not.
(Wyrand is still reasonable for scheduling and cache decisions.)
Good randomness does have a cost: about twice wyrand.
Also rationalize the various runtime rand references.
goos: linux
goarch: amd64
pkg: math/rand/v2
cpu: AMD Ryzen 9 7950X 16-Core Processor
│ bbb48afeb7.amd64 │ 5cf807d1ea.amd64 │
│ sec/op │ sec/op vs base │
ChaCha8-32 1.862n ± 2% 1.861n ± 2% ~ (p=0.825 n=20)
PCG_DXSM-32 1.471n ± 1% 1.460n ± 2% ~ (p=0.153 n=20)
SourceUint64-32 1.636n ± 2% 1.582n ± 1% -3.30% (p=0.000 n=20)
GlobalInt64-32 2.087n ± 1% 3.663n ± 1% +75.54% (p=0.000 n=20)
GlobalInt64Parallel-32 0.1042n ± 1% 0.2026n ± 1% +94.48% (p=0.000 n=20)
GlobalUint64-32 2.263n ± 2% 3.724n ± 1% +64.57% (p=0.000 n=20)
GlobalUint64Parallel-32 0.1019n ± 1% 0.1973n ± 1% +93.67% (p=0.000 n=20)
Int64-32 1.771n ± 1% 1.774n ± 1% ~ (p=0.449 n=20)
Uint64-32 1.863n ± 2% 1.866n ± 1% ~ (p=0.364 n=20)
GlobalIntN1000-32 3.134n ± 3% 4.730n ± 2% +50.95% (p=0.000 n=20)
IntN1000-32 2.489n ± 1% 2.489n ± 1% ~ (p=0.683 n=20)
Int64N1000-32 2.521n ± 1% 2.516n ± 1% ~ (p=0.394 n=20)
Int64N1e8-32 2.479n ± 1% 2.478n ± 2% ~ (p=0.743 n=20)
Int64N1e9-32 2.530n ± 2% 2.514n ± 2% ~ (p=0.193 n=20)
Int64N2e9-32 2.501n ± 1% 2.494n ± 1% ~ (p=0.616 n=20)
Int64N1e18-32 3.227n ± 1% 3.205n ± 1% ~ (p=0.101 n=20)
Int64N2e18-32 3.647n ± 1% 3.599n ± 1% ~ (p=0.019 n=20)
Int64N4e18-32 5.135n ± 1% 5.069n ± 2% ~ (p=0.034 n=20)
Int32N1000-32 2.657n ± 1% 2.637n ± 1% ~ (p=0.180 n=20)
Int32N1e8-32 2.636n ± 1% 2.636n ± 1% ~ (p=0.763 n=20)
Int32N1e9-32 2.660n ± 2% 2.638n ± 1% ~ (p=0.358 n=20)
Int32N2e9-32 2.662n ± 2% 2.618n ± 2% ~ (p=0.064 n=20)
Float32-32 2.272n ± 2% 2.239n ± 2% ~ (p=0.194 n=20)
Float64-32 2.272n ± 1% 2.286n ± 2% ~ (p=0.763 n=20)
ExpFloat64-32 3.762n ± 1% 3.744n ± 1% ~ (p=0.171 n=20)
NormFloat64-32 3.706n ± 1% 3.655n ± 2% ~ (p=0.066 n=20)
Perm3-32 32.93n ± 3% 34.62n ± 1% +5.13% (p=0.000 n=20)
Perm30-32 202.9n ± 1% 204.0n ± 1% ~ (p=0.482 n=20)
Perm30ViaShuffle-32 115.0n ± 1% 114.9n ± 1% ~ (p=0.358 n=20)
ShuffleOverhead-32 112.8n ± 1% 112.7n ± 1% ~ (p=0.692 n=20)
Concurrent-32 2.107n ± 0% 3.725n ± 1% +76.75% (p=0.000 n=20)
goos: darwin
goarch: arm64
pkg: math/rand/v2
│ bbb48afeb7.arm64 │ 5cf807d1ea.arm64 │
│ sec/op │ sec/op vs base │
ChaCha8-8 2.480n ± 0% 2.429n ± 0% -2.04% (p=0.000 n=20)
PCG_DXSM-8 2.531n ± 0% 2.530n ± 0% ~ (p=0.877 n=20)
SourceUint64-8 2.534n ± 0% 2.533n ± 0% ~ (p=0.732 n=20)
GlobalInt64-8 2.172n ± 1% 4.794n ± 0% +120.67% (p=0.000 n=20)
GlobalInt64Parallel-8 0.4320n ± 0% 0.9605n ± 0% +122.32% (p=0.000 n=20)
GlobalUint64-8 2.182n ± 0% 4.770n ± 0% +118.58% (p=0.000 n=20)
GlobalUint64Parallel-8 0.4307n ± 0% 0.9583n ± 0% +122.51% (p=0.000 n=20)
Int64-8 4.107n ± 0% 4.104n ± 0% ~ (p=0.416 n=20)
Uint64-8 4.080n ± 0% 4.080n ± 0% ~ (p=0.052 n=20)
GlobalIntN1000-8 2.814n ± 2% 5.643n ± 0% +100.50% (p=0.000 n=20)
IntN1000-8 4.141n ± 0% 4.139n ± 0% ~ (p=0.140 n=20)
Int64N1000-8 4.140n ± 0% 4.140n ± 0% ~ (p=0.313 n=20)
Int64N1e8-8 4.140n ± 0% 4.139n ± 0% ~ (p=0.103 n=20)
Int64N1e9-8 4.139n ± 0% 4.140n ± 0% ~ (p=0.761 n=20)
Int64N2e9-8 4.140n ± 0% 4.140n ± 0% ~ (p=0.636 n=20)
Int64N1e18-8 5.266n ± 0% 5.326n ± 1% +1.14% (p=0.001 n=20)
Int64N2e18-8 6.052n ± 0% 6.167n ± 0% +1.90% (p=0.000 n=20)
Int64N4e18-8 8.826n ± 0% 9.051n ± 0% +2.55% (p=0.000 n=20)
Int32N1000-8 4.127n ± 0% 4.132n ± 0% +0.12% (p=0.000 n=20)
Int32N1e8-8 4.126n ± 0% 4.131n ± 0% +0.12% (p=0.000 n=20)
Int32N1e9-8 4.127n ± 0% 4.132n ± 0% +0.12% (p=0.000 n=20)
Int32N2e9-8 4.132n ± 0% 4.131n ± 0% ~ (p=0.017 n=20)
Float32-8 4.109n ± 0% 4.105n ± 0% ~ (p=0.379 n=20)
Float64-8 4.107n ± 0% 4.106n ± 0% ~ (p=0.867 n=20)
ExpFloat64-8 5.339n ± 0% 5.383n ± 0% +0.82% (p=0.000 n=20)
NormFloat64-8 5.735n ± 0% 5.737n ± 1% ~ (p=0.856 n=20)
Perm3-8 26.65n ± 0% 26.80n ± 1% +0.58% (p=0.000 n=20)
Perm30-8 194.8n ± 1% 197.0n ± 0% +1.18% (p=0.000 n=20)
Perm30ViaShuffle-8 156.6n ± 0% 157.6n ± 1% +0.61% (p=0.000 n=20)
ShuffleOverhead-8 124.9n ± 0% 125.5n ± 0% +0.52% (p=0.000 n=20)
Concurrent-8 2.434n ± 3% 5.066n ± 0% +108.09% (p=0.000 n=20)
goos: linux
goarch: 386
pkg: math/rand/v2
cpu: AMD Ryzen 9 7950X 16-Core Processor
│ bbb48afeb7.386 │ 5cf807d1ea.386 │
│ sec/op │ sec/op vs base │
ChaCha8-32 11.295n ± 1% 4.748n ± 2% -57.96% (p=0.000 n=20)
PCG_DXSM-32 7.693n ± 1% 7.738n ± 2% ~ (p=0.542 n=20)
SourceUint64-32 7.658n ± 2% 7.622n ± 2% ~ (p=0.344 n=20)
GlobalInt64-32 3.473n ± 2% 7.526n ± 2% +116.73% (p=0.000 n=20)
GlobalInt64Parallel-32 0.3198n ± 0% 0.5444n ± 0% +70.22% (p=0.000 n=20)
GlobalUint64-32 3.612n ± 0% 7.575n ± 1% +109.69% (p=0.000 n=20)
GlobalUint64Parallel-32 0.3168n ± 0% 0.5403n ± 0% +70.51% (p=0.000 n=20)
Int64-32 7.673n ± 2% 7.789n ± 1% ~ (p=0.122 n=20)
Uint64-32 7.773n ± 1% 7.827n ± 2% ~ (p=0.920 n=20)
GlobalIntN1000-32 6.268n ± 1% 9.581n ± 1% +52.87% (p=0.000 n=20)
IntN1000-32 10.33n ± 2% 10.45n ± 1% ~ (p=0.233 n=20)
Int64N1000-32 10.98n ± 2% 11.01n ± 1% ~ (p=0.401 n=20)
Int64N1e8-32 11.19n ± 2% 10.97n ± 1% ~ (p=0.033 n=20)
Int64N1e9-32 11.06n ± 1% 11.08n ± 1% ~ (p=0.498 n=20)
Int64N2e9-32 11.10n ± 1% 11.01n ± 2% ~ (p=0.995 n=20)
Int64N1e18-32 15.23n ± 2% 15.04n ± 1% ~ (p=0.973 n=20)
Int64N2e18-32 15.89n ± 1% 15.85n ± 1% ~ (p=0.409 n=20)
Int64N4e18-32 18.96n ± 2% 19.34n ± 2% ~ (p=0.048 n=20)
Int32N1000-32 10.46n ± 2% 10.44n ± 2% ~ (p=0.480 n=20)
Int32N1e8-32 10.46n ± 2% 10.49n ± 2% ~ (p=0.951 n=20)
Int32N1e9-32 10.28n ± 2% 10.26n ± 1% ~ (p=0.431 n=20)
Int32N2e9-32 10.50n ± 2% 10.44n ± 2% ~ (p=0.249 n=20)
Float32-32 13.80n ± 2% 13.80n ± 2% ~ (p=0.751 n=20)
Float64-32 23.55n ± 2% 23.87n ± 0% ~ (p=0.408 n=20)
ExpFloat64-32 15.36n ± 1% 15.29n ± 2% ~ (p=0.316 n=20)
NormFloat64-32 13.57n ± 1% 13.79n ± 1% +1.66% (p=0.005 n=20)
Perm3-32 45.70n ± 2% 46.99n ± 2% +2.81% (p=0.001 n=20)
Perm30-32 399.0n ± 1% 403.8n ± 1% +1.19% (p=0.006 n=20)
Perm30ViaShuffle-32 349.0n ± 1% 350.4n ± 1% ~ (p=0.909 n=20)
ShuffleOverhead-32 322.3n ± 1% 323.8n ± 1% ~ (p=0.410 n=20)
Concurrent-32 3.331n ± 1% 7.312n ± 1% +119.50% (p=0.000 n=20)
For #61716.
Change-Id: Ibdddeed85c34d9ae397289dc899e04d4845f9ed2
Reviewed-on: https://go-review.googlesource.com/c/go/+/516860
Reviewed-by: Michael Pratt <mpratt@google.com>
Reviewed-by: Filippo Valsorda <filippo@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
|
|
Change-Id: I1f031f0f83a94bebe41d3978a91a903dc5bcda66
Reviewed-on: https://go-review.googlesource.com/c/go/+/489276
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: David Chase <drchase@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
|
|
This touches a lot of files, which is bad, but it is also good,
since there's N copies of this information commoned into 1.
The new files in internal/abi are copied from the end of the stack;
ultimately this will all end up being used.
Change-Id: Ia252c0055aaa72ca569411ef9f9e96e3d610889e
Reviewed-on: https://go-review.googlesource.com/c/go/+/462995
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Carlos Amedee <carlos@golang.org>
Run-TryBot: David Chase <drchase@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
"User" throws are throws due to some invariant broken by the application.
"System" throws are due to some invariant broken by the runtime,
environment, etc (i.e., not the fault of the application).
This CL sends "user" throws through the new fatal. Currently this
function is identical to throw, but with a different name to clearly
differentiate the throw type in the stack trace, and hopefully be a bit
more clear to users what it means.
This CL changes a few categories of throw to fatal:
1. Concurrent map read/write.
2. Deadlock detection.
3. Unlock of unlocked sync.Mutex.
4. Inconsistent results from syscall.AllThreadsSyscall.
"Thread exhaustion" and "out of memory" (usually address space full)
throws are additional throws that are arguably the fault of user code,
but I've left off for now because there is no specific invariant that
they have broken to get into these states.
For #51485
Change-Id: I713276a6c290fd34a6563e6e9ef378669d74ae32
Reviewed-on: https://go-review.googlesource.com/c/go/+/390420
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Austin Clements <austin@google.com>
Run-TryBot: Michael Pratt <mpratt@google.com>
|
|
internal/goarch.PtrSize [generated]
[git-generate]
cd src/runtime/internal/math
gofmt -w -r "sys.PtrSize -> goarch.PtrSize" .
goimports -w *.go
cd ../..
gofmt -w -r "sys.PtrSize -> goarch.PtrSize" .
goimports -w *.go
Change-Id: I43491cdd54d2e06d4d04152b3d213851b7d6d423
Reviewed-on: https://go-review.googlesource.com/c/go/+/328337
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
|
|
At this point all funcPC references are ABIInternal functions.
Replace with the intrinsics.
Change-Id: I3ba7e485c83017408749b53f92877d3727a75e27
Reviewed-on: https://go-review.googlesource.com/c/go/+/321954
Trust: Cherry Mui <cherryyz@google.com>
Run-TryBot: Cherry Mui <cherryyz@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Michael Knyszek <mknyszek@google.com>
|
|
Fixes #45045
Change-Id: Ifcc7bd31591870446ce3e5127489a0b887d413f1
Reviewed-on: https://go-review.googlesource.com/c/go/+/305089
Trust: Cuong Manh Le <cuong.manhle.vn@gmail.com>
Run-TryBot: Cuong Manh Le <cuong.manhle.vn@gmail.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
1.Revise ambiguous comments: "all current buckets" means buckets in hmap.buckets, actually current bucket and all the overflow buckets connected to it are full
2.All the pointer address add use src/runtime/stubs.go:add, keep the code style uniform
Change-Id: Idc7224dbe6c391e1b03bf5d009c3734bc75187ce
Reviewed-on: https://go-review.googlesource.com/c/go/+/257979
Reviewed-by: Austin Clements <austin@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: Austin Clements <austin@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
|
|
Same thing as CL 253020 did for map clear idiom.
name old time/op new time/op delta
MapDelete/Int32/100-12 30.0ns ± 1% 30.7ns ± 3% ~ (p=0.400 n=3+3)
MapDelete/Int32/1000-12 26.6ns ± 2% 28.1ns ± 3% ~ (p=0.100 n=3+3)
MapDelete/Int32/10000-12 28.6ns ± 1% 31.9ns ± 1% ~ (p=0.100 n=3+3)
MapDelete/Int64/100-12 30.2ns ± 0% 32.1ns ± 3% ~ (p=0.100 n=3+3)
MapDelete/Int64/1000-12 26.5ns ± 1% 27.5ns ± 3% ~ (p=0.100 n=3+3)
MapDelete/Int64/10000-12 29.6ns ± 1% 29.3ns ± 1% ~ (p=0.300 n=3+3)
MapDelete/Str/100-12 19.5ns ± 3% 19.6ns ± 2% ~ (p=0.800 n=3+3)
MapDelete/Str/1000-12 31.6ns ± 1% 31.4ns ± 1% ~ (p=0.500 n=3+3)
MapDelete/Str/10000-12 37.8ns ± 1% 37.1ns ± 1% ~ (p=0.100 n=3+3)
MapDelete/Pointer/100-12 15.9ns ± 1% 16.8ns ± 9% ~ (p=0.200 n=3+3)
MapDelete/Pointer/1000-12 26.9ns ± 1% 26.2ns ± 2% ~ (p=0.200 n=3+3)
MapDelete/Pointer/10000-12 30.6ns ± 1% 30.7ns ± 4% ~ (p=0.700 n=3+3)
Fixes #25237
Change-Id: I353cf44a2f6158549f0ef563d867f0844fec7095
Reviewed-on: https://go-review.googlesource.com/c/go/+/252940
Run-TryBot: Cuong Manh Le <cuong.manhle.vn@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Emmanuel Odeke <emm.odeke@gmail.com>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
Right now we generate hash functions for all types, just in case they
are used as map keys. That's a lot of wasted effort and binary size
for types which will never be used as a map key. Instead, generate
hash functions only for types that we know are map keys.
Just doing that is a bit too simple, since maps with an interface type
as a key might have to hash any concrete key type that implements that
interface. So for that case, implement hashing of such types at
runtime (instead of with generated code). It will be slower, but only
for maps with interface types as keys, and maybe only a bit slower as
the aeshash time probably dominates the dispatch time.
Reorg where we keep the equals and hash functions. Move the hash function
from the key type to the map type, saving a field in every non-map type.
That leaves only one function in the alg structure, so get rid of that and
just keep the equal function in the type descriptor itself.
cmd/go now has 10 generated hash functions, instead of 504. Makes
cmd/go 1.0% smaller. Update #6853.
Speed on non-interface keys is unchanged. Speed on interface keys
is ~20% slower:
name old time/op new time/op delta
MapInterfaceString-8 23.0ns ±21% 27.6ns ±14% +20.01% (p=0.002 n=10+10)
MapInterfacePtr-8 19.4ns ±16% 23.7ns ± 7% +22.48% (p=0.000 n=10+8)
Change-Id: I7c2e42292a46b5d4e288aaec4029bdbb01089263
Reviewed-on: https://go-review.googlesource.com/c/go/+/191198
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Martin Möhrmann <moehrmann@google.com>
|
|
The spec carefully and consistently uses "key" and "element"
as map terminology. The implementation, not so much.
This change attempts to make the implementation consistently
hew to the spec's terminology. Beyond consistency, this has
the advantage of avoid some confusion and naming collisions,
since v and value are very generic and commonly used terms.
I believe that I found all everything, but there are a lot of
non-obvious places for these to hide, and grepping for them is hard.
Hopefully this change changes enough of them that we will start using
elem going forward. Any remaining hidden cases can be removed ad hoc
as they are discovered.
The only externally-facing part of this change is in package reflect,
where there is a minor doc change and a function parameter name change.
Updates #27167
Change-Id: I2f2d78f16c360dc39007b9966d5c2046a29d3701
Reviewed-on: https://go-review.googlesource.com/c/go/+/174523
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
|
|
We already have the ptrdata field in a type, which encodes exactly
the same information that kindNoPointers does.
My problem with kindNoPointers is that it often leads to
double-negative code like:
t.kind & kindNoPointers != 0
Much clearer is:
t.ptrdata == 0
Update #27167
Change-Id: I92307d7f018a6bbe3daca4a4abb4225e359349b1
Reviewed-on: https://go-review.googlesource.com/c/go/+/169157
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
|
|
When we delete an element, and it was the last element in the bucket,
update the slots between the new last element and the old last element
with the marker that says "no more elements beyond here".
Change-Id: I8efeeddf4c9b9fc491c678f84220a5a5094c9c76
Reviewed-on: https://go-review.googlesource.com/c/142438
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
|
|
Divide the "empty" slot state into two, "emptyOne" and "emptyRest".
emptyOne means just that slot is empty. emptyRest means all subsequent
slots in that bucket are empty and the overflow pointer is nil.
When scanning a bucket, we can often stop at emptyRest, reducing
the total work we have to do. (This is similar to how tombstones
work in open addressing.)
Ideally on delete we have to figure out whether to zero the slot
with an emptyOne or emptyRest marker. For now, we choose the safe
but non-optimal choice. (Fix in subsequent CL?)
This is a simpler CL than some others we've tried, including my
CL sequence 11835[5-8] and Ilya's CL 115616.
Update #19495
name old time/op new time/op delta
MegMap 8.96ns ± 2% 8.74ns ± 6% -2.44% (p=0.020 n=10+10)
MegOneMap 8.91ns ± 2% 5.53ns ± 2% -37.99% (p=0.000 n=10+10)
MegEqMap 46.0µs ± 1% 45.8µs ± 3% ~ (p=0.315 n=9+10)
MegEmptyMap 2.50ns ± 0% 2.50ns ± 2% ~ (p=0.957 n=8+10)
SmallStrMap 8.54ns ± 1% 8.71ns ± 2% +2.01% (p=0.000 n=10+10)
MapStringKeysEight_16 8.61ns ± 3% 8.71ns ± 3% +1.20% (p=0.026 n=9+9)
MapStringKeysEight_32 8.54ns ± 2% 8.97ns ± 1% +5.05% (p=0.000 n=10+9)
MapStringKeysEight_64 8.66ns ± 2% 8.99ns ± 2% +3.87% (p=0.000 n=10+10)
MapStringKeysEight_1M 8.57ns ± 2% 8.95ns ± 2% +4.51% (p=0.000 n=10+9)
IntMap 6.69ns ± 1% 7.46ns ± 1% +11.60% (p=0.000 n=9+9)
MapFirst/1 3.69ns ± 1% 3.63ns ± 3% -1.52% (p=0.040 n=10+10)
MapFirst/2 3.70ns ± 2% 3.63ns ± 2% -1.95% (p=0.001 n=9+9)
MapFirst/3 3.74ns ± 2% 3.66ns ± 2% -2.12% (p=0.000 n=8+10)
MapFirst/4 3.71ns ± 2% 3.66ns ± 4% ~ (p=0.073 n=9+10)
MapFirst/5 3.69ns ± 1% 3.62ns ± 2% -1.88% (p=0.000 n=9+10)
MapFirst/6 3.68ns ± 2% 3.62ns ± 1% -1.83% (p=0.001 n=10+9)
MapFirst/7 3.67ns ± 1% 3.60ns ± 1% -1.98% (p=0.000 n=10+8)
MapFirst/8 3.68ns ± 2% 3.61ns ± 2% -1.87% (p=0.000 n=10+10)
MapFirst/9 8.03ns ± 4% 7.89ns ± 2% -1.76% (p=0.007 n=10+10)
MapFirst/10 7.99ns ± 2% 7.86ns ± 3% -1.64% (p=0.009 n=9+10)
MapFirst/11 7.96ns ± 1% 7.80ns ± 2% -2.01% (p=0.000 n=10+10)
MapFirst/12 7.96ns ± 1% 7.82ns ± 1% -1.67% (p=0.000 n=10+10)
MapFirst/13 8.06ns ± 3% 7.92ns ± 3% ~ (p=0.055 n=10+10)
MapFirst/14 7.95ns ± 1% 7.80ns ± 1% -1.88% (p=0.000 n=10+9)
MapFirst/15 8.01ns ± 2% 7.80ns ± 2% -2.57% (p=0.000 n=10+10)
MapFirst/16 8.05ns ± 2% 7.90ns ± 2% -1.84% (p=0.005 n=9+10)
MapMid/1 4.00ns ± 1% 3.94ns ± 2% -1.30% (p=0.021 n=8+9)
MapMid/2 4.39ns ± 2% 4.32ns ± 4% ~ (p=0.128 n=10+10)
MapMid/3 4.40ns ± 2% 4.27ns ± 2% -2.93% (p=0.000 n=10+9)
MapMid/4 4.76ns ± 2% 4.65ns ± 1% -2.26% (p=0.000 n=10+9)
MapMid/5 4.76ns ± 1% 4.65ns ± 1% -2.27% (p=0.000 n=10+10)
MapMid/6 5.11ns ± 2% 4.98ns ± 2% -2.55% (p=0.000 n=10+10)
MapMid/7 5.12ns ± 1% 5.01ns ± 3% -2.02% (p=0.003 n=9+9)
MapMid/8 5.71ns ± 3% 5.97ns ± 1% +4.51% (p=0.000 n=10+9)
MapMid/9 8.72ns ±10% 8.89ns ±10% ~ (p=0.458 n=9+10)
MapMid/10 10.1ns ±15% 9.6ns ± 7% ~ (p=0.080 n=9+10)
MapMid/11 9.88ns ±10% 9.44ns ±11% ~ (p=0.065 n=10+10)
MapMid/12 9.90ns ±13% 10.04ns ± 9% ~ (p=1.000 n=10+8)
MapMid/13 9.67ns ±14% 10.23ns ±10% ~ (p=0.209 n=10+9)
MapMid/14 9.12ns ±14% 9.14ns ±13% ~ (p=0.927 n=10+10)
MapMid/15 9.16ns ±12% 9.15ns ±16% ~ (p=0.955 n=10+10)
MapMid/16 9.37ns ±11% 9.60ns ±23% ~ (p=0.825 n=9+10)
MapLast/1 4.08ns ± 1% 3.92ns ± 0% -3.91% (p=0.000 n=10+9)
MapLast/2 4.37ns ± 1% 4.28ns ± 1% -1.95% (p=0.000 n=10+10)
MapLast/3 4.94ns ± 2% 4.65ns ± 1% -5.79% (p=0.000 n=9+8)
MapLast/4 5.40ns ± 3% 5.02ns ± 2% -7.13% (p=0.000 n=9+9)
MapLast/5 5.88ns ± 2% 5.67ns ± 2% -3.57% (p=0.000 n=10+10)
MapLast/6 6.48ns ± 3% 5.90ns ± 2% -8.89% (p=0.000 n=10+10)
MapLast/7 7.01ns ± 2% 6.27ns ± 5% -10.56% (p=0.000 n=10+10)
MapLast/8 7.60ns ± 2% 6.62ns ± 2% -12.93% (p=0.000 n=9+10)
MapLast/9 10.6ns ± 9% 10.9ns ±15% ~ (p=0.344 n=9+10)
MapLast/10 11.0ns ±12% 10.9ns ±14% ~ (p=0.985 n=10+10)
MapLast/11 11.4ns ±12% 11.8ns ±22% ~ (p=0.671 n=10+10)
MapLast/12 11.6ns ±10% 12.1ns ±19% ~ (p=0.617 n=10+10)
MapLast/13 12.5ns ±23% 11.8ns ±13% ~ (p=0.827 n=10+9)
MapLast/14 10.5ns ±22% 10.4ns ± 5% ~ (p=0.797 n=10+9)
MapLast/15 10.0ns ±15% 10.3ns ±16% ~ (p=0.565 n=10+10)
MapLast/16 10.4ns ±12% 10.5ns ±13% ~ (p=0.889 n=10+9)
MapCycle 22.3ns ± 1% 22.0ns ± 2% -1.43% (p=0.002 n=9+10)
RepeatedLookupStrMapKey32 16.4ns ± 1% 16.6ns ± 1% +1.24% (p=0.000 n=10+9)
RepeatedLookupStrMapKey1M 35.6µs ± 0% 35.4µs ± 1% -0.62% (p=0.002 n=10+10)
NewEmptyMap 5.36ns ± 1% 9.05ns ± 1% +69.02% (p=0.000 n=10+8)
NewSmallMap 51.2ns ± 2% 33.7ns ± 1% -34.22% (p=0.000 n=10+9)
MapIter 83.8ns ± 1% 88.4ns ± 1% +5.55% (p=0.000 n=10+10)
MapIterEmpty 4.32ns ± 3% 5.54ns ± 3% +28.12% (p=0.000 n=10+10)
SameLengthMap 4.31ns ± 1% 4.59ns ± 2% +6.41% (p=0.000 n=9+10)
BigKeyMap 24.2ns ± 2% 24.3ns ± 1% ~ (p=0.432 n=10+10)
BigValMap 24.3ns ± 1% 24.4ns ± 2% ~ (p=0.200 n=10+9)
SmallKeyMap 17.5ns ± 1% 18.5ns ± 2% +5.81% (p=0.000 n=9+10)
MapPopulate/1 29.0ns ± 4% 18.8ns ± 1% -35.27% (p=0.000 n=10+9)
MapPopulate/10 736ns ± 5% 693ns ± 4% -5.92% (p=0.000 n=10+10)
MapPopulate/100 11.3µs ± 2% 10.8µs ± 3% -4.38% (p=0.000 n=10+10)
MapPopulate/1000 139µs ± 8% 132µs ± 4% -5.10% (p=0.002 n=10+10)
MapPopulate/10000 1.21ms ± 5% 1.16ms ± 5% -4.56% (p=0.002 n=10+10)
MapPopulate/100000 12.2ms ± 3% 11.8ms ± 5% ~ (p=0.052 n=10+10)
ComplexAlgMap 73.9ns ± 1% 74.4ns ± 2% ~ (p=0.161 n=9+10)
GoMapClear/Reflexive/1 36.0ns ± 1% 26.9ns ± 2% -25.31% (p=0.000 n=10+10)
GoMapClear/Reflexive/10 35.2ns ± 1% 24.4ns ± 1% -30.62% (p=0.000 n=10+10)
GoMapClear/Reflexive/100 69.6ns ± 2% 59.2ns ± 1% -14.92% (p=0.000 n=10+10)
GoMapClear/Reflexive/1000 1.06µs ± 2% 1.05µs ± 1% -1.16% (p=0.013 n=10+9)
GoMapClear/Reflexive/10000 11.7µs ± 1% 11.7µs ± 1% ~ (p=0.542 n=10+10)
GoMapClear/NonReflexive/1 96.3ns ± 1% 90.0ns ± 1% -6.52% (p=0.000 n=10+10)
GoMapClear/NonReflexive/10 110ns ± 2% 101ns ± 0% -8.10% (p=0.000 n=10+7)
GoMapClear/NonReflexive/100 270ns ± 2% 235ns ± 2% -12.94% (p=0.000 n=10+10)
GoMapClear/NonReflexive/1000 3.02µs ± 2% 2.48µs ± 1% -17.92% (p=0.000 n=10+10)
GoMapClear/NonReflexive/10000 23.7µs ± 1% 19.6µs ± 1% -17.30% (p=0.000 n=10+9)
MapPop100 9.65µs ± 6% 9.18µs ± 8% -4.82% (p=0.008 n=9+10)
MapPop1000 162µs ± 6% 148µs ± 4% -8.67% (p=0.000 n=9+9)
MapPop10000 3.05ms ± 8% 2.82ms ±15% -7.66% (p=0.023 n=10+10)
MapAssign/Int32/256 15.7ns ± 4% 14.6ns ± 2% -7.08% (p=0.000 n=10+10)
MapAssign/Int32/65536 29.8ns ± 1% 30.4ns ± 0% +2.04% (p=0.000 n=10+8)
MapAssign/Int64/256 14.9ns ± 5% 14.8ns ± 4% ~ (p=0.611 n=10+10)
MapAssign/Int64/65536 30.3ns ± 2% 30.4ns ± 1% +0.54% (p=0.046 n=10+9)
MapAssign/Str/256 17.8ns ± 3% 19.8ns ± 4% +11.08% (p=0.000 n=10+10)
MapAssign/Str/65536 35.7ns ± 1% 36.4ns ± 1% +1.82% (p=0.000 n=10+10)
MapOperatorAssign/Int32/256 18.8ns ± 5% 14.6ns ± 3% -22.57% (p=0.000 n=10+10)
MapOperatorAssign/Int32/65536 29.8ns ± 1% 30.5ns ± 1% +2.39% (p=0.000 n=10+10)
MapOperatorAssign/Int64/256 16.6ns ± 4% 15.0ns ± 6% -9.34% (p=0.000 n=10+10)
MapOperatorAssign/Int64/65536 30.1ns ± 1% 31.7ns ± 2% +5.21% (p=0.000 n=10+10)
MapOperatorAssign/Str/256 1.70µs ± 1% 1.61µs ± 2% -5.55% (p=0.000 n=10+8)
MapOperatorAssign/Str/65536 289ns ± 7% 294ns ± 4% ~ (p=0.425 n=10+10)
MapAppendAssign/Int32/256 34.3ns ± 2% 31.0ns ± 3% -9.59% (p=0.000 n=9+9)
MapAppendAssign/Int32/65536 51.8ns ± 3% 47.1ns ±13% -9.17% (p=0.002 n=9+10)
MapAppendAssign/Int64/256 32.5ns ± 8% 31.2ns ± 6% ~ (p=0.065 n=10+10)
MapAppendAssign/Int64/65536 51.4ns ± 4% 47.2ns ±10% -8.07% (p=0.005 n=9+10)
MapAppendAssign/Str/256 105ns ±12% 109ns ± 4% ~ (p=0.138 n=10+8)
MapAppendAssign/Str/65536 101ns ±14% 81ns ± 8% -19.82% (p=0.000 n=10+9)
MapDelete/Int32/100 32.0ns ± 1% 35.0ns ± 2% +9.59% (p=0.000 n=9+10)
MapDelete/Int32/1000 27.0ns ± 3% 30.3ns ± 1% +12.10% (p=0.000 n=10+9)
MapDelete/Int32/10000 29.2ns ± 1% 32.9ns ± 2% +12.80% (p=0.000 n=10+10)
MapDelete/Int64/100 31.5ns ± 1% 35.7ns ± 2% +13.16% (p=0.000 n=10+10)
MapDelete/Int64/1000 27.0ns ± 2% 30.6ns ± 1% +13.21% (p=0.000 n=10+10)
MapDelete/Int64/10000 30.3ns ± 1% 34.4ns ± 3% +13.47% (p=0.000 n=10+10)
MapDelete/Str/100 23.4ns ± 8% 26.7ns ± 6% +14.10% (p=0.000 n=10+9)
MapDelete/Str/1000 31.0ns ± 2% 35.1ns ± 3% +13.19% (p=0.000 n=10+9)
MapDelete/Str/10000 38.8ns ± 1% 43.4ns ± 2% +12.02% (p=0.000 n=9+10)
Change-Id: I564ce0f40936589f0f9b837f7f2bbcca4c4a1070
Reviewed-on: https://go-review.googlesource.com/c/142437
Reviewed-by: Giovanni Bajo <rasky@develer.com>
Reviewed-by: Martin Möhrmann <martisch@uos.de>
Run-TryBot: Martin Möhrmann <martisch@uos.de>
TryBot-Result: Gobot Gobot <gobot@golang.org>
|
|
If two goroutines are racing on a map, one of them will exit
cleanly, clearing the hashWriting bit, and the other will
likely notice and panic. If we use XOR instead of OR to
set the bit in the first place, even numbers of racers will
hopefully all see the bit cleared and panic simultaneously,
giving the full set of available stacks. If a third racer
sneaks in, we are no worse than the current code, and
the generated code should be no more expensive.
In practice, this catches most racing goroutines even in
very tight races. See the demonstration program posted
on https://github.com/golang/go/issues/26703 for an example.
Fixes #26703
Change-Id: Idad17841a3127c24bd0a659b754734f70e307434
Reviewed-on: https://go-review.googlesource.com/126936
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
Map delete must clear value every time because
newly added map optimizations of compound-assignment
operators (CL #91557) rely on this behavior of map delete.
It slows down map delete operation for non-reference types:
name old time/op new time/op delta
MapDelete/Int32/100 23.9ns ± 2% 27.8ns ± 4% +16.04% (p=0.000 n=20+20)
MapDelete/Int32/1000 21.5ns ± 2% 25.2ns ± 2% +17.06% (p=0.000 n=20+19)
MapDelete/Int32/10000 24.2ns ± 6% 27.2ns ± 5% +12.39% (p=0.000 n=19+19)
MapDelete/Int64/100 24.2ns ± 4% 27.7ns ± 2% +14.55% (p=0.000 n=20+20)
MapDelete/Int64/1000 22.1ns ± 2% 24.8ns ± 2% +12.36% (p=0.000 n=10+20)
Fixes #25936
Change-Id: I8499b790cb5bb019938161b3e50f3243d9bbb79c
Reviewed-on: https://go-review.googlesource.com/120255
Run-TryBot: Emmanuel Odeke <emm.odeke@gmail.com>
Reviewed-by: Keith Randall <khr@golang.org>
|
|
Overall code is unchanged.
The functions for different types (32, 64, str) of map fast routines
are collected in map_fast.go that has grown to ~1300 lines.
Moving the functions for each map fast type into a separate file
allows for an easier overview and navigation within the map code.
Change-Id: Ic09e4212f9025a66a10b11ef8dac23ad49d1d5ae
Reviewed-on: https://go-review.googlesource.com/90335
Run-TryBot: Martin Möhrmann <moehrmann@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
|
