Skip to content
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

cmd/go: Division by 2 is slow #45688

Closed
ghost opened this issue Apr 22, 2021 · 2 comments
Closed

cmd/go: Division by 2 is slow #45688

ghost opened this issue Apr 22, 2021 · 2 comments
Labels
FrozenDueToAge

Comments

@ghost
Copy link

ghost commented Apr 22, 2021 •
edited by ghost

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

$ go version
go version go1.16.3 linux/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
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/xxx/.cache/go-build"
GOENV="/home/xxx/.config/go/env"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/home/xxx/gocode/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/home/xxx/gocode"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/home/xxx/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/home/xxx/go/pkg/tool/linux_amd64"
GOVCS=""
GOVERSION="go1.16.3"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/dev/null"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build3657712911=/tmp/go-build -gno-record-gcc-switches"

What did you do?

Benchmarked this function

func binarySearch(key uint32, arr []uint32) int {
	low, high := 0, len(arr)
	for low < high {
		m := low + ((high - low) / 2) // <--
		if arr[m] < key {
			low = m + 1
		} else {
			high = m
		}
	}
	return low
}

then replaced

m := low + ((high - low) / 2)

with

m := low + ((high - low) >> 1)

and benchmarked again.

What did you expect to see?

Both functions are compiled to the same assembly and execute equally fast.

What did you see instead?

The one with division is a lot slower:

name       old time/op  new time/op  delta
Search1-4  34.0ns ± 0%  23.9ns ± 0%  -29.89%  (p=0.000 n=19+20)

https://play.golang.org/p/VU9rZYff9AA
@randall77
Copy link
Contributor

Try defining low and high to be unsigned. I suspect what you're seeing is the additional code required for signed division (signed /2 is not the same as >>1).

@ghost
Copy link
Author

ghost commented Apr 22, 2021

You're right. With unsigned low and high the functions are equally fast.

@ghost ghost closed this as completed Apr 22, 2021
@golang golang locked and limited conversation to collaborators Apr 22, 2022
This issue was closed.
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
2 participants
@randall77 @gopherbot