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.

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

slices: redundant comparison in BinarySearchFunc #70846

Open
rothelius opened this issue Dec 14, 2024 · 7 comments
Open

slices: redundant comparison in BinarySearchFunc #70846

rothelius opened this issue Dec 14, 2024 · 7 comments
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided.
Milestone

Comments

@rothelius
Copy link

Go version

go version go1.23.4 windows/amd64

Output of go env in your module/workspace:

set GO111MODULE=
set GOARCH=amd64
set GOBIN=
set GOCACHE=C:\Users\telic\AppData\Local\go-build
set GOENV=C:\Users\telic\AppData\Roaming\go\env
set GOEXE=.exe
set GOEXPERIMENT=aliastypeparams
set GOFLAGS=
set GOHOSTARCH=amd64
set GOHOSTOS=windows
set GOINSECURE=
set GOMODCACHE=C:\Users\telic\go\pkg\mod
set GONOPROXY=
set GONOSUMDB=
set GOOS=windows
set GOPATH=C:\Users\telic\go
set GOPRIVATE=
set GOPROXY=https://proxy.golang.org,direct
set GOROOT=C:\Program Files\Go
set GOSUMDB=sum.golang.org
set GOTMPDIR=
set GOTOOLCHAIN=auto
set GOTOOLDIR=C:\Program Files\Go\pkg\tool\windows_amd64
set GOVCS=
set GOVERSION=go1.23.4
set GODEBUG=gotypesalias=1
set GOTELEMETRY=local
set GOTELEMETRYDIR=C:\Users\telic\AppData\Roaming\go\telemetry
set GCCGO=gccgo
set GOAMD64=v1
set AR=ar
set CC=gcc
set CXX=g++
set CGO_ENABLED=1
set GOMOD=C:\Code\Go\playground\go.mod
set GOWORK=C:\Code\Go\go.work
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 -mthreads -Wl,--no-gc-sections -fmessage-length=0 -ffile-prefix-map=C:\Users\telic\AppData\Local\Temp\go-build1876904163=/tmp/go-build -gno-record-gcc-switches

What did you do?

Ran this code.

What did you see happen?

Three comparisons being made.

What did you expect to see?

Two comparisons.

BinarySearchFunc always does a final comparison for its boolean return value, even though the slice element in question and the target might already have been compared. Since the comparison function could potentially be costly, this should be avoided.

@gabyhelp
Copy link

Related Code Changes

(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)

@adonovan
Copy link
Member

adonovan commented Dec 14, 2024

It's true, the final comparison to test whether the target element is actually present in the sequence is redundant about 50% of the time. It could be avoided by retaining the result of the last comparison performed within the loop: if it was zero, the final comparison isn't needed. This would cost just a register, and an extra conditional branch at the end.

	n := len(x)
	// Define cmp(x[-1], target) < 0 and cmp(x[n], target) >= 0 .
	// Invariant: cmp(x[i - 1], target) < 0, cmp(x[j], target) >= 0.
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1) // avoid overflow when computing h
		// i ≤ h < j
// Idea 1: retain cmp result here
		if cmp(x[h], target) < 0 {
			i = h + 1 // preserves cmp(x[i - 1], target) < 0
		} else {
// Idea 2: check cmp==0 and return early here
			j = h // preserves cmp(x[j], target) >= 0
		}
	}
	// i == j, cmp(x[i-1], target) < 0, and cmp(x[j], target) (= cmp(x[i], target)) >= 0  =>  answer is i.
	return i, i < n && cmp(x[i], target) == 0

Equivalently, you could handle the three cases (+ve, -ve, 0) of the comparison within the loop distinctly, returning when zero, though this would add an extra conditional branch to 50% of loop iterations.

However: this algorithm is deceptively hard to get right. Famously it was first published in 1946, but it wasn't till 1962 that the first correct version was published. That's why BinarySearch is among the most heavily commented functions in the entire Go project. Casual tweaks to it should be carefully weighed in light of that fact.

@seankhliao
Copy link
Member

what about:

	n := len(x)
	// Define cmp(x[-1], target) < 0 and cmp(x[n], target) >= 0 .
	// Invariant: cmp(x[i - 1], target) < 0, cmp(x[j], target) >= 0.
	i, j, found := 0, n, false
	for i < j {
		h := int(uint(i+j) >> 1) // avoid overflow when computing h
		// i ≤ h < j
// Idea 1: retain cmp result here
		if c := cmp(x[h], target); c < 0 {
			i = h + 1 // preserves cmp(x[i - 1], target) < 0
		} else {
// Idea 2: check cmp==0 and return early here
			j = h // preserves cmp(x[j], target) >= 0
                        found = found || c == 0
		}
	}
	// i == j, cmp(x[i-1], target) < 0, and cmp(x[j], target) (= cmp(x[i], target)) >= 0  =>  answer is i.
	return i, i < n && found

@ianlancetaylor
Copy link
Member

CC @eliben

@robpike
Copy link
Contributor

robpike commented Dec 15, 2024

I agree with @adonovan that this code is notoriously tricky and is best left alone, doubly so when the issue is about a single O(1) comparison per call, triply so when the "fixes" require O(log(n)) more work.

@dr2chase
Copy link
Contributor

dr2chase commented Dec 23, 2024

For what it's worth, I compiled both versions of the code, and the extra gunk to avoid that last call to compare was a little more than I expected (">" marks branch targets, "+" marks extra code in the loop):

  JMP 9(PC)
> MOVD 104(RSP), R4
  MOVD 112(RSP), R5
  MOVD 88(RSP), R1
  MOVD 80(RSP), R7
  MOVD R7, R1
  MOVD R2, R6
  MOVD R0, R2
  MOVD 88(RSP), R0
> CMP R3, R2
  BLE 29(PC)
  ADD R2, R3, R7
  LSR $1, R7, R8
  CMP R7>>1, R0
  BLS 32(PC)
+ MOVD R3, 40(RSP)
  MOVD R2, 32(RSP)
  MOVD R8, 48(RSP)
+ MOVB R6, 31(RSP)
  MOVD (R5), R2
  MOVD (R1)(R8<<3), R0
  MOVD R4, R1
  MOVD R5, R26
  CALL (R2)
  TBZ $63, R0, 6(PC)
  MOVD 48(RSP), R4
  ADD $1, R4, R3
  MOVD 32(RSP), R0
+ MOVBU 31(RSP), R2
  JMP -28(PC)
+ MOVBU 31(RSP), R1
+ TBZ $0, R1, 3(PC)
+ ORR $1, ZR, R2
+ JMP 3(PC)
+ CMP $0, R0
+ CSET EQ, R2
> MOVD 48(RSP), R0
  MOVD 40(RSP), R3
  JMP -37(PC)

Makes me wonder whether we should get serious about callee-save, at least for not-pointers.
If you notice the janky loop rotation, yeah, I looked at that earlier this year and benchmarked doing it "right" and it was apparently slower in general, no I do not know why.

@cherrymui
Copy link
Member

Agree with @adonovan and @robpike . Any change here, if at all, should be driven by benchmark results showing improvements on real workload.

@cherrymui cherrymui added Performance NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Dec 23, 2024
@cherrymui cherrymui added this to the Unplanned milestone Dec 23, 2024
@cherrymui cherrymui changed the title slices: Redundant comparison in BinarySearchFunc slices: redundant comparison in BinarySearchFunc Dec 23, 2024
@seankhliao seankhliao added the WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided. label Jan 16, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance WaitingForInfo Issue is not actionable because of missing required information, which needs to be provided.
Projects
None yet
Development

No branches or pull requests

8 participants