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/compile: missing BCE optimization cases #64272

Open
go101 opened this issue Nov 20, 2023 · 2 comments
Open

cmd/compile: missing BCE optimization cases #64272

go101 opened this issue Nov 20, 2023 · 2 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone
Unplanned

Comments

@go101
Copy link

go101 commented Nov 20, 2023 •
edited

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

$ go version
go version go1.21.4 linux/amd64

Does this issue reproduce with the latest release?

Yes

What did you do?

https://github.com/golang/go/blob/go1.21.4/src/slices/slices.go#L346-L385

func Compact[S ~[]E, E comparable](s S) S {
	if len(s) < 2 {
		return s
	}
	i := 1
	for k := 1; k < len(s); k++ {
		if s[k] != s[k-1] {
			if i != k {
				s[i] = s[k] // Found IsInBounds
			}
			i++
		}
	}
	clear(s[i:]) // Found IsSliceInBounds
	return s[:i]
}

func CompactFunc[S ~[]E, E any](s S, eq func(E, E) bool) S {
	if len(s) < 2 {
		return s
	}
	i := 1
	for k := 1; k < len(s); k++ {
		if !eq(s[k], s[k-1]) {
			if i != k {
				s[i] = s[k] // Found IsInBounds
			}
			i++
		}
	}
	clear(s[i:]) // Found IsSliceInBounds
	return s[:i]
}

And

func DeleteFunc[S ~[]E, E any](s S, del func(E) bool) S {
	i := IndexFunc(s, del)
	if i == -1 {
		return s
	}
	// Don't start copying elements until we find one to delete.
	for j := i + 1; j < len(s); j++ {
		if v := s[j]; !del(v) { // Found IsInBounds
			s[i] = v // Found IsInBounds
			i++
		}
	}
	clear(s[i:]) // Found IsSliceInBounds
	return s[:i]
}

What did you expect to see?

No bound checks.

What did you see instead?

Many bound checks.

This problem might have been reported before, but I couldn't find it now.
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Nov 20, 2023
@go101 go101 mentioned this issue Nov 20, 2023
Closed
@gopherbot
Copy link

Change https://go.dev/cl/543661 mentions this issue: slices: optimize Compact and CompactFunc

@mknyszek
Copy link
Contributor

CC @golang/compiler

@mknyszek mknyszek added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Nov 20, 2023
@mknyszek mknyszek added this to the Backlog milestone Nov 20, 2023
@mknyszek mknyszek modified the milestones: Backlog, Unplanned Nov 29, 2023
gopherbot pushed a commit that referenced this issue Apr 26, 2024
@TapirLiu @gopherbot
slices: optimize Compact and CompactFunc
4370cfb 
Try to save a comparison in the loop bodies of Compact and CompactFunc.

Note: due to #64272, some bound checks still fail to be removed.

                            │ old.txt  │             new.txt              │
                            │   sec/op    │   sec/op     vs base                │
Compact/nil-4                 4.191n ± 9%   3.402n ± 1%  -18.84% (p=0.000 n=10)
Compact/one-4                 5.289n ± 2%   4.553n ± 2%  -13.93% (p=0.000 n=10)
Compact/sorted-4              9.865n ± 0%   6.882n ± 1%  -30.24% (p=0.000 n=10)
Compact/2_items-4             11.10n ± 2%   12.11n ± 2%   +9.00% (p=0.000 n=10)
Compact/unsorted-4            9.831n ± 3%   6.918n ± 2%  -29.62% (p=0.000 n=10)
Compact/many-4                16.40n ± 4%   14.90n ± 1%   -9.20% (p=0.000 n=10)
Compact/dup_start-4           29.87n ± 0%   28.06n ± 3%   -6.04% (p=0.001 n=10)
Compact_Large/all_dup-4       13.11µ ± 0%   13.12µ ± 0%        ~ (p=0.971 n=10)
Compact_Large/no_dup-4        6.972µ ± 0%   5.806µ ± 0%  -16.73% (p=0.000 n=10)
CompactFunc/nil-4             5.300n ± 0%   5.309n ± 1%        ~ (p=0.289 n=10)
CompactFunc/one-4             6.051n ± 1%   6.442n ± 3%   +6.46% (p=0.000 n=10)
CompactFunc/sorted-4          16.24n ± 1%   12.79n ± 2%  -21.24% (p=0.000 n=10)
CompactFunc/2_items-4         17.89n ± 1%   17.75n ± 0%   -0.75% (p=0.000 n=10)
CompactFunc/unsorted-4        16.26n ± 0%   12.83n ± 1%  -21.07% (p=0.000 n=10)
CompactFunc/many-4            30.71n ± 1%   29.07n ± 0%   -5.32% (p=0.000 n=10)
CompactFunc/dup_start-4       78.94n ± 1%   67.19n ± 1%  -14.89% (p=0.000 n=10)
CompactFunc_Large/all_dup-4   3.277m ± 0%   3.692m ± 2%  +12.67% (p=0.000 n=10)
CompactFunc_Large/no_dup-4    4.019m ± 0%   2.826m ± 1%  -29.68% (p=0.000 n=10)
geomean                       109.6n        96.99n       -11.47%

Change-Id: Ia4c78fa62e7e9f4ff6a39d0e0a0a84cecf79b9cb
GitHub-Last-Rev: cea3d93
GitHub-Pull-Request: #64273
Reviewed-on: https://go-review.googlesource.com/c/go/+/543661
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>
Auto-Submit: Keith Randall <khr@golang.org>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
Go Compiler / Runtime
Status: Todo
Milestone
Unplanned
Development

No branches or pull requests
3 participants
@mknyszek @gopherbot @go101