-
Notifications
You must be signed in to change notification settings - Fork 17.9k
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
cmd/compile: missed trivial bound check elimination #66826
Comments
It looks there is a workaround now: func nttMul(f, g nttElement) nttElement {
var h nttElement
for i := 0; i < 256; i += 2 {
a0, a1 := f[i],
f[i+1]
b0, b1 := g[i],
g[i+1]
_, _, _, _ = a0, a1, b0, b1
}
return h
} Not benchmark it yet. [edit] BTW, why not use slices as arguments: func nttMul(f, g []fieldElement) nttElement {
var h nttElement
f, g = f[:256], g[:256]
for i := 0; i < 256; i += 2 {
a0, a1 := f[i],
f[i+1]
b0, b1 := g[i],
g[i+1]
_, _, _, _ = a0, a1, b0, b1
}
return h
} |
That does indeed remove the bounds checks on Slices should in theory add overhead compared to const size arrays and remove information from the type system |
Yes, there are still several cases BCE fails to handle. Now, a workaround is to double the length of |
Interestingly, that benchmarks decidedly worse, eating between 10% and 20% of the speedup of dropping the |
It is possible. BCE will not always get positive effects. Another way to remove all bound checks is declare |
The test shows that double length of
|
Simple reproducer:
We should be able to get rid of the bounds check. Currently I think it fails because the prove pass can't tell that the math |
go: go1.22.2 goos: linux goarch: amd64 pkg: filippo.io/mlkem768 cpu: Intel(R) Core(TM) i5-7400 CPU @ 3.00GHz │ e10936b │ e10936b-dirty │ │ sec/op │ sec/op vs base │ KeyGen-4 65.46µ ± 1% 64.41µ ± 1% -1.61% (p=0.000 n=20) Encaps-4 98.63µ ± 1% 97.28µ ± 0% -1.37% (p=0.000 n=20) Decaps-4 98.16µ ± 0% 96.31µ ± 0% -1.88% (p=0.000 n=20) RoundTrip/Alice-4 172.4µ ± 0% 169.1µ ± 0% -1.90% (p=0.000 n=20) RoundTrip/Bob-4 98.76µ ± 0% 97.45µ ± 0% -1.32% (p=0.000 n=20) geomean 101.5µ 99.89µ -1.62% See golang/go#66826
Change https://go.dev/cl/599096 mentions this issue: |
Change https://go.dev/cl/599256 mentions this issue: |
Fixes #40704 Fixes #66826 Change-Id: Ia9c356e29b2ed6f2e3bc6e5eb9304cd4dccb4263 Reviewed-on: https://go-review.googlesource.com/c/go/+/599256 Reviewed-by: Michael Knyszek <mknyszek@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: David Chase <drchase@google.com>
Go version
go version go1.22.2 darwin/arm64
Output of
go env
in your module/workspace:What did you do?
I have this function in a fairly hot loop.
What did you see happen?
Both
f[2*i]
andf[2*i+1]
get aisInBounds()
.g[2*i]
andg[2*i+1]
don't.What did you expect to see?
One or zero bounds checks.
One if the compiler realized that if
f[2*i+1]
is in bounds withi
positive and small (0 to 127), thenf[2*i]
is clearly in bounds.Zero if the compiler figured out that i is 0 to 127, so
2*i+1
is 0 to 255, and the size of f is a constant 256.The text was updated successfully, but these errors were encountered: