Skip to content

runtime: map's loadFactor is actually 6, not 6.5 #63438

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
xiangxu126 opened this issue Oct 7, 2023 · 10 comments
Closed

runtime: map's loadFactor is actually 6, not 6.5 #63438

xiangxu126 opened this issue Oct 7, 2023 · 10 comments
Labels
FrozenDueToAge

Comments

@xiangxu126
Copy link

What version of Go are you using (go version)?

$ go version
go version go1.21rc3 windows/amd64

Does this issue reproduce with the latest release?

Yes.

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
set GO111MODULE=on
set GOARCH=amd64
set GOBIN=
set GOCACHE=C:\Users\xiangxu\AppData\Local\go-build
set GOENV=C:\Users\xiangxu\AppData\Roaming\go\env
set GOEXE=.exe
set GOEXPERIMENT=
set GOFLAGS=
set GOHOSTARCH=amd64
set GOHOSTOS=windows
set GOINSECURE=
set GOMODCACHE=C:\Users\xiangxu\go\pkg\mod
set GONOPROXY=
set GONOSUMDB=
set GOOS=windows
set GOPATH=C:\Users\xiangxu\go
set GOPRIVATE=
set GOPROXY=https://proxy.golang.org,direct
set GOROOT=C:/Users/xiangxu/sdk/go1.21rc3
set GOSUMDB=sum.golang.org
set GOTMPDIR=
set GOTOOLCHAIN=auto
set GOTOOLDIR=C:\Users\xiangxu\sdk\go1.21rc3\pkg\tool\windows_amd64
set GOVCS=
set GOVERSION=go1.21rc3
set GCCGO=gccgo
set GOAMD64=v1
set AR=ar
set CC=gcc
set CXX=g++
set CGO_ENABLED=0
set GOMOD=C:\Users\xiangxu\GolandProjects\fastSlice\go.mod
set GOWORK=
set CGO_CFLAGS=-O2 -g
set CGO_CPPFLAGS=
set CGO_CXXFLAGS=-O2 -g
set CGO_FFLAGS=-O2 -g
set CGO_LDFLAGS=-O2 -g
set PKG_CONFIG=pkg-config
set GOGCCFLAGS=-m64 -fno-caret-diagnostics -Qunused-arguments -Wl,--no-gc-sections -fmessage-length=0 -ffile-prefix-map=C:\Users\xiangxu\AppData\Local\Te
mp\go-build3346316506=/tmp/go-build -gno-record-gcc-switches

What did you do?

I found that due to integer arithmetic , loadFactorNum was incorrectly calculated as 12, resulting map triggers growth when
count > 6*(1<<B) , instead of the expected count > 6.5*(1<<B) .
The code related to the bug I mentioned can be found: code
You can verify this point easily with the following code:

package bench

import "testing"

var m map[int]int

func Benchmark1(b *testing.B) {
	for i := 0; i < b.N; i++ {
		m = make(map[int]int, 6*(1<<10))
	}
}
func Benchmark2(b *testing.B) {
	for i := 0; i < b.N; i++ {
		m = make(map[int]int, 6*(1<<10)+1)
	}
}

What did you expect to see?

The results of these two benchmark tests should be close.

What did you see instead?

In fact, this first benchmark test only takes half the time each time compared to the second benchmark test. It indicates that map triggers growth, but at this time, count < 6.5*(1<<B) still holds true.

goos: windows
goarch: amd64
pkg: fastSlice/bench
cpu: AMD Ryzen 9 7940HS w/ Radeon 780M Graphics
Benchmark1
Benchmark1-16              95134             12748 ns/op
Benchmark2
Benchmark2-16              45301             26307 ns/op
PASS
@xiangxu126 xiangxu126 changed the title runtime: loadFactor of map is 6 instead of 6.5 Runtime: map's loadFactor is actually 6, not 6.5 Oct 7, 2023
@randall77
Copy link
Contributor

This looks like it was broken in CL 462115. @dr2chase

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/533279 mentions this issue: map: use correct load factor for deciding when to grow

@seankhliao seankhliao changed the title Runtime: map's loadFactor is actually 6, not 6.5 runtime: map's loadFactor is actually 6, not 6.5 Oct 8, 2023
yunginnanet pushed a commit to yunginnanet/go that referenced this issue Oct 20, 2023
@randall77 @yunginnanet
map: use correct load factor for deciding when to grow
a3d5d53 
The correct load factor is 6.5, not 6.
This got broken by accident in CL 462115.

Fixes golang#63438

Change-Id: Ib07bb6ab6103aec87cb775bc06bd04362a64e489
Reviewed-on: https://go-review.googlesource.com/c/go/+/533279
Reviewed-by: David Chase <drchase@google.com>
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
@zhexuany
Copy link

@gopherbot I believe this should be cherry-pick to 1.21.

@randall77
Copy link
Contributor

I don't think this qualifies for a backport. It would need to be a serious problem with no workaround. A minor performance difference does not qualify.

https://go.dev/wiki/MinorReleases

@zhexuany
Copy link

It's not just a minor performance issue, it basically changes the way how a map grows.

As the issue mentions, the load factor becomes 6 rather than 6.5 anymore. I already test on 1.20 and 1.22 beta and find that their load factor of map is 6.5 not 6. If we do not cherry-pick this fix to 1.21, only 1.21 becomes an outlier.

If any program tracks the memory usage depends on one assumption: the load factor of map in golang is 6.5 not 6. It causes a lot of troubles.

@randall77
Copy link
Contributor

Sorry, we've made the call that it just isn't worth the risk to backport fixes like this.

@zhexuany
Copy link

Can I know more details behind the scenes? To me, I could not see any risk, maybe you can help me to understand a little deeper. The load factor number of map in golang is always 6.5, I just could not understand changing back from 6 to 6.5 causses any potential risk.

@randall77
Copy link
Contributor

It's not anything about the particular CL or how safe it is (although if a CL is particularly risky, we get even more cautious). We just have a policy that we don't backport anything that isn't for a serious problem.
"Serious problems" do not include performance changes that otherwise adhere to the spec. Map growth thresholds are not any kind of spec-level guarantee.

@zhexuany
Copy link

It's nice to know how the decision was made. Thanks for your time, I really appreciate this. @randall77

This was referenced Jan 18, 2024
Closed
Closed
Merged
@ti-chi-bot ti-chi-bot mentioned this issue Jan 18, 2024
Closed
13 tasks
@zhexuany zhexuany mentioned this issue Jan 19, 2024
Merged
13 tasks
@markus-wa
Copy link
Contributor

appreciate the decision to not backport this btw - it seems like it somehow caused a regression (which is quite bizarre) #65706

@golang golang locked and limited conversation to collaborators Feb 13, 2025
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
5 participants
@markus-wa @randall77 @gopherbot @zhexuany @xiangxu126