[go] math/big: Int.ModInverse: pool temporary allocations to reduce allocations
Gerrit Bot (Gerrit)
Gerrit Bot has uploaded the change for review![]( "Open in Gerrit")
Commit message
math/big: Int.ModInverse: pool temporary allocations to reduce allocations
Before the changes, Int.ModInverse was doing several allocations for temporary variables, this PR added pooling for those, effectively reducing the total amount of allocations as the benchmarks below show.
Before:
```
$ go test ./math/big -v -count=1 -p=1 -run=NONE -bench=BenchmarkModInverse -benchmem -benchtime=100000x
goos: linux
goarch: amd64
pkg: math/big
cpu: Intel(R) Core(TM) i5-10310U CPU @ 1.70GHz
BenchmarkModInverse
BenchmarkModInverse-8 100000 907.2 ns/op 1080 B/op 11 allocs/op
PASS
ok math/big 0.110s
```
After:
```
$ go test ./math/big -v -count=1 -p=1 -run=NONE -bench=BenchmarkModInverse -benchmem -benchtime=100000x
goos: linux
goarch: amd64
pkg: math/big
cpu: Intel(R) Core(TM) i5-10310U CPU @ 1.70GHz
BenchmarkModInverse
BenchmarkModInverse-8 100000 537.7 ns/op 0 B/op 0 allocs/op
PASS
ok math/big 0.072s
```
As we can see, ModInverse is faster now.
This merge request Closes #79707
Change diff
diff --git a/src/math/big/int.go b/src/math/big/int.go
index f2331b5..91ed8d8 100644
--- a/src/math/big/int.go
+++ b/src/math/big/int.go
@@ -11,6 +11,7 @@
"io"
"math/rand"
"strings"
+ "sync"
)
// An Int represents a signed multi-precision integer.
@@ -829,6 +830,35 @@
return B, r, A, Ua, Ub
}
+type sixIntPool struct {
+ pool sync.Pool
+}
+
+func (t *sixIntPool) Put(data *[6]*Int) {
+ data[0].SetInt64(0)
+ data[1].SetInt64(0)
+ data[2].SetInt64(0)
+ data[3].SetInt64(0)
+ data[4].SetInt64(0)
+ data[5].SetInt64(0)
+ t.pool.Put(data)
+}
+
+func (t *sixIntPool) Get() *[6]*Int {
+ return t.pool.Get().(*[6]*Int)
+}
+
+var sixIntP = sixIntPool{
+ sync.Pool{
+ New: func() any {
+ data := [6]*Int{
+ &Int{}, &Int{}, &Int{}, &Int{}, &Int{}, &Int{},
+ }
+ return &data
+ },
+ },
+}
+
// lehmerGCD sets z to the greatest common divisor of a and b,
// which both must be != 0, and returns z.
// If x or y are not nil, their values are set such that z = a*x + b*y.
@@ -840,22 +870,22 @@
// The cosequences are updated according to Algorithm 10.45 from
// Cohen et al. "Handbook of Elliptic and Hyperelliptic Curve Cryptography" pp 192.
func (z *Int) lehmerGCD(x, y, a, b *Int) *Int {
- var A, B, Ua, Ub *Int
+ data := sixIntP.Get()
+ var A, B, Ua, Ub *Int = data[0], data[1], data[2], data[3]
- A = new(Int).Abs(a)
- B = new(Int).Abs(b)
+ A.Abs(a)
+ B.Abs(b)
extended := x != nil || y != nil
if extended {
// Ua (Ub) tracks how many times input a has been accumulated into A (B).
- Ua = new(Int).SetInt64(1)
- Ub = new(Int)
+ Ua.SetInt64(1)
}
// temp variables for multiprecision update
- q := new(Int)
- r := new(Int)
+ q := data[4]
+ r := data[5]
// ensure A >= B
if A.abs.cmp(B.abs) < 0 {
@@ -947,6 +977,8 @@
z.Set(A)
+ sixIntP.Put(data)
+
return z
}
@@ -966,6 +998,29 @@
return z
}
+type twoIntPool struct {
+ pool sync.Pool
+}
+
+func (t *twoIntPool) Put(data *[2]*Int) {
+ data[0].SetInt64(0)
+ data[1].SetInt64(0)
+ t.pool.Put(data)
+}
+
+func (t *twoIntPool) Get() *[2]*Int {
+ return t.pool.Get().(*[2]*Int)
+}
+
+var twoIntP = twoIntPool{
+ sync.Pool{
+ New: func() any {
+ data := [2]*Int{&Int{}, &Int{}}
+ return &data
+ },
+ },
+}
+
// ModInverse sets z to the multiplicative inverse of g in the ring ℤ/nℤ
// and returns z. If g and n are not relatively prime, g has no multiplicative
// inverse in the ring ℤ/nℤ. In this case, z is unchanged and the return value
@@ -980,8 +1035,10 @@
var g2 Int
g = g2.Mod(g, n)
}
- var d, x Int
- d.GCD(&x, nil, g, n)
+
+ data := twoIntP.Get()
+ var d, x *Int = data[0], data[1]
+ d.GCD(x, nil, g, n)
// if and only if d==1, g and n are relatively prime
if d.Cmp(intOne) != 0 {
@@ -991,10 +1048,13 @@
// x and y are such that g*x + n*y = 1, therefore x is the inverse element,
// but it may be negative, so convert to the range 0 <= z < |n|
if x.neg {
- z.Add(&x, n)
+ z.Add(x, n)
} else {
- z.Set(&x)
+ z.Set(x)
}
+
+ twoIntP.Put(data)
+
return z
}
Change information
- M src/math/big/int.go
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Gopher Robot (Gerrit)
Gopher Robot added 1 comment![]( "Open in Gerrit")
I spotted some possible problems with your PR:
1. The first word in the commit title after the package should be a lowercase English word (usually a verb).
2. You have a long 205 character line in the commit message body. Please add line breaks to long lines that should be wrapped. Lines in the commit message body should be wrapped at ~76 characters unless needed for things like URLs or tables. (Note: GitHub might render long lines as soft-wrapped, so double-check in the Gerrit commit message shown above.)
3. It looks like you are using markdown in the commit message. If so, please remove it. Be sure to double-check the plain text shown in the Gerrit commit message above for any markdown backticks, markdown links, or other markdown formatting.
4. Do you have the right bug reference format? For this repo, the format is usually 'Fixes #12345' or 'Updates #12345' at the end of the commit message.
Please address any problems by updating the GitHub PR.
When complete, mark this comment as 'Done' and click the [blue 'Reply' button](https://go.dev/wiki/GerritBot#i-left-a-reply-to-a-comment-in-gerrit-but-no-one-but-me-can-see-it) above. These findings are based on heuristics; if a finding does not apply, briefly reply here saying so.
To update the commit title or commit message body shown here in Gerrit, you must edit the GitHub PR title and PR description (the first comment) in the GitHub web interface using the 'Edit' button or 'Edit' menu entry there. Note: pushing a new commit to the PR will not automatically update the commit message used by Gerrit.
For more details, see:
- [how to update commit messages](https://go.dev/wiki/GerritBot/#how-does-gerritbot-determine-the-final-commit-message) for PRs imported into Gerrit.
- the Go project's [conventions for commit messages](https://go.dev/doc/contribute#commit_messages) that you should follow.
(In general for Gerrit code reviews, the change author is expected to [log in to Gerrit](https://go-review.googlesource.com/login/) with a Gmail or other Google account and then close out each piece of feedback by marking it as 'Done' if implemented as suggested or otherwise reply to each review comment. See the [Review](https://go.dev/doc/contribute#review) section of the Contributing Guide for details.)
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Gopher Robot (Gerrit)
Message from Gopher Robot![]( "Open in Gerrit")
Congratulations on opening your first change. Thank you for your contribution!
Next steps:
A maintainer will review your change and provide feedback. See
https://go.dev/doc/contribute#review for more info and tips to get your
patch through code review.
Most changes in the Go project go through a few rounds of revision. This can be
surprising to people new to the project. The careful, iterative review process
is our way of helping mentor contributors and ensuring that their contributions
have a lasting impact.
During May-July and Nov-Jan the Go project is in a code freeze, during which
little code gets reviewed or merged. If a reviewer responds with a comment like
R=go1.11 or adds a tag like "wait-release", it means that this CL will be
reviewed as part of the next development cycle. See https://go.dev/s/release
for more details.
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jorropo (Gerrit)
Jorropo voted Hold+1![]( "Open in Gerrit")
| Hold | +1 |
Related details
Code-Review
No-Holds
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jorropo (Gerrit)
Jorropo voted and added 4 comments![]( "Open in Gerrit")
Votes added by Jorropo
| Commit-Queue | +1 |
4 comments
Thanks
$ go test ./math/big -v -count=1 -p=1 -run=NONE -bench=BenchmarkModInverse -benchmem -benchtime=100000xCheckout https://pkg.go.dev/golang.org/x/perf/cmd/benchstat to make a table of statistical analysis results of your benchmarks.
sixIntP.Put(data)Any reason to not `defer` it when you `.Get` it ?
twoIntP.Put(data)Any reason to not `defer` it when you `.Get` it ?
Related details
- Robert Griesemer
Code-Review
No-Holds
No-Unresolved-Comments
No-Wait-Release
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Gerrit Bot (Gerrit)
Gerrit Bot uploaded new patchset![]( "Open in Gerrit")
- TryBots-Pass: LUCI-TryBot-Result+1 by golang...@luci-project-accounts.iam.gserviceaccount.com
Related details
- Jorropo
- Robert Griesemer
Code-Review
No-Holds
No-Unresolved-Comments
No-Wait-Release
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Gerrit Bot (Gerrit)
Gerrit Bot uploaded new patchset![]( "Open in Gerrit")
Related details
- Jorropo
- Robert Griesemer
Code-Review
No-Holds
No-Unresolved-Comments
No-Wait-Release
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mateusz Poliwczak (Gerrit)
Mateusz Poliwczak added 1 comment![]( "Open in Gerrit")
func (t *sixIntPool) Put(data *[6]*Int) {Potentially
```suggestion
func (t *sixIntPool) Put(data *[6]Int) {
```
Could be better, less indirection.
Related details
- Jorropo
- Robert Griesemer
Code-Review
No-Holds
No-Unresolved-Comments
No-Wait-Release
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan voted and added 2 comments![]( "Open in Gerrit")
Votes added by Alan Donovan
| Hold | +1 |
2 comments
Hold: since this is not a bug fix, it must wait till the tree thaws.
func (t *sixIntPool) Put(data *[6]*Int) {Potentially
```suggestion
func (t *sixIntPool) Put(data *[6]Int) {
```
Could be better, less indirection.
Once you do that, you can universally generalize the two and six variants over `[T any]`: the pool stores a *T, the New operation calls new(T), and the Put operation just does `*ptr = *new(T)` to zeros out whatever value is stored.
Related details
- Jorropo
- Robert Griesemer
Code-Review
No-Holds
No-Unresolved-Comments
No-Wait-Release
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan added 1 comment![]( "Open in Gerrit")
func (t *sixIntPool) Put(data *[6]*Int) {Alan DonovanPotentially
```suggestion
func (t *sixIntPool) Put(data *[6]Int) {
```
Could be better, less indirection.
Once you do that, you can universally generalize the two and six variants over `[T any]`: the pool stores a *T, the New operation calls new(T), and the Put operation just does `*ptr = *new(T)` to zeros out whatever value is stored.
(This assumes the goal of the CL is to amortize the allocation of the Ints themselves. If it is to recycle multi-word limb arrays, zeroing out won't do that. But I suspect the Ints are more important since most values are small and fit in a single limb.)
Mateusz Poliwczak (Gerrit)
Mateusz Poliwczak added 1 comment![]( "Open in Gerrit")
func (t *sixIntPool) Put(data *[6]*Int) {Alan DonovanPotentially
```suggestion
func (t *sixIntPool) Put(data *[6]Int) {
```
Could be better, less indirection.
Once you do that, you can universally generalize the two and six variants over `[T any]`: the pool stores a *T, the New operation calls new(T), and the Put operation just does `*ptr = *new(T)` to zeros out whatever value is stored.
and the Put operation just does *ptr = *new(T) to zeros out whatever value is stored.
But you might want to re-use the `[]word` slices, `SetInt64` does that.
allocz (Gerrit)
allocz voted and added 5 comments![]( "Open in Gerrit")
Votes added by allocz
| Code-Review | +1 |
5 comments
The code fixes the main issue that is allocations in hot loops. Looks good to me.
$ go test ./math/big -v -count=1 -p=1 -run=NONE -bench=BenchmarkModInverse -benchmem -benchtime=100000xCheckout https://pkg.go.dev/golang.org/x/perf/cmd/benchstat to make a table of statistical analysis results of your benchmarks.
Ok, I've updated the github PR message with the latest output of benchstat. Thanks.
func (t *sixIntPool) Put(data *[6]*Int) {Alan DonovanPotentially
```suggestion
func (t *sixIntPool) Put(data *[6]Int) {
```
Could be better, less indirection.
Mateusz PoliwczakOnce you do that, you can universally generalize the two and six variants over `[T any]`: the pool stores a *T, the New operation calls new(T), and the Put operation just does `*ptr = *new(T)` to zeros out whatever value is stored.
and the Put operation just does *ptr = *new(T) to zeros out whatever value is stored.
But you might want to re-use the `[]word` slices, `SetInt64` does that.
Firstly, thanks for the review, guys.
I ran the benchmarks with less indirection `*[6]Int` instead of `*[6]*Int` and the results became slightly worse.
In this case, the main goal is to avoid allocations of the internal Int `[]word`, in the ECDSA library that I'm optimizing, the Ints are in the order of 256 bits, so the generic version of the `twoIntPool` and `sixIntPool` causes allocations and because of that I will keep both pool implementations.
I think that this is already good enough. Thanks again for the review.
```
goos: linux
goarch: amd64
pkg: math/big
cpu: Intel(R) Core(TM) i5-10310U CPU @ 1.70GHz
│ /tmp/arrayofpointerofint │ /tmp/arrayofint │
│ sec/op │ sec/op vs base │
ModInverse-8 543.0n ± 0% 548.1n ± 8% +0.95% (p=0.004 n=100)
│ /tmp/arrayofpointerofint │ /tmp/arrayofint │
│ B/op │ B/op vs base │
ModInverse-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=100) ¹
¹ all samples are equal
│ /tmp/arrayofpointerofint │ /tmp/arrayofint │
│ allocs/op │ allocs/op vs base │
ModInverse-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=100) ¹
¹ all samples are equal
```
Any reason to not `defer` it when you `.Get` it ?
Solved, I usually tend to avoid defer where performance matters because sometimes it prevents inlining or causes allocations, but this is not the case, thanks.
Any reason to not `defer` it when you `.Get` it ?
- Alan Donovan
- Jorropo
- Mateusz Poliwczak
- Robert Griesemer
Code-Review
No-Holds
No-Unresolved-Comments
No-Wait-Release
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mateusz Poliwczak (Gerrit)
Mateusz Poliwczak added 1 comment![]( "Open in Gerrit")
```
[mateusz@arch go ((4a1da811b9...))]$ benchstat /tmp/before /tmp/after
goos: linux
goarch: amd64
pkg: math/big
cpu: 11th Gen Intel(R) Core(TM) i7-1185G7 @ 3.00GHz
│ /tmp/before │ /tmp/after │
│ sec/op │ sec/op vs base │
ModInverse-8 342.7n ± 1% 337.8n ± 1% -1.43% (p=0.000 n=25)
```
On my system a reverse thing happens, but since it is a low difference i am fine.
Related details
- Alan Donovan
- Jorropo
- Robert Griesemer
- allocz
Gerrit Bot (Gerrit)
Gerrit Bot uploaded new patchset![]( "Open in Gerrit")
Related details
- Alan Donovan
- Jorropo
- Robert Griesemer
- allocz
Code-Review
No-Holds
No-Unresolved-Comments
No-Wait-Release
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan voted and added 1 comment![]( "Open in Gerrit")
Votes added by Alan Donovan
| Hold | +1 |
1 comment
Please document that the purpose of the optimization is to recycle limbs, not just Int variables.
Even if you keep the SetInt64 operations in Put, you can still remove the indirection from *Int, which should reduce allocation, improve locality, and simplify the New function.
Related details
- Jorropo
- Robert Griesemer
- allocz
Code-Review
No-Holds
No-Unresolved-Comments
No-Wait-Release
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Gerrit Bot (Gerrit)
Gerrit Bot uploaded new patchset![]( "Open in Gerrit")
- Alan Donovan
- Jorropo
- Robert Griesemer
- allocz
Code-Review
No-Holds
No-Unresolved-Comments
No-Wait-Release
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jorropo (Gerrit)
Jorropo voted and added 1 comment![]( "Open in Gerrit")
Votes added by Jorropo
| Hold | +1 |
The code fixes the main issue that is allocations in hot loops. Looks good to me.
- Alan Donovan
- Robert Griesemer
- allocz
Code-Review
No-Holds
No-Unresolved-Comments
No-Wait-Release
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Gerrit Bot (Gerrit)
Gerrit Bot uploaded new patchset![]( "Open in Gerrit")
- Alan Donovan
- Jorropo
- Robert Griesemer
- allocz
Code-Review
No-Holds
No-Unresolved-Comments
No-Wait-Release
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
allocz (Gerrit)
allocz voted and added 1 comment![]( "Open in Gerrit")
Votes added by allocz
| Code-Review | +1 |
1 comment
Ok, I reduced the indirection `*[N]Int` instead of `*[N]*Int` and also added comments in the `ModInverse` and `lehmerGCD` procedures, explaining that the reason of the Int recycling is to reuse the limbs, which reduces allocations.
Related details
- Alan Donovan
- Jorropo
- Robert Griesemer
Code-Review
No-Holds
No-Unresolved-Comments
No-Wait-Release
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
allocz (Gerrit)
allocz added 3 comments![]( "Open in Gerrit")
I spotted some possible problems with your PR:
1. The first word in the commit title after the package should be a lowercase English word (usually a verb).
2. You have a long 205 character line in the commit message body. Please add line breaks to long lines that should be wrapped. Lines in the commit message body should be wrapped at ~76 characters unless needed for things like URLs or tables. (Note: GitHub might render long lines as soft-wrapped, so double-check in the Gerrit commit message shown above.)
3. It looks like you are using markdown in the commit message. If so, please remove it. Be sure to double-check the plain text shown in the Gerrit commit message above for any markdown backticks, markdown links, or other markdown formatting.
4. Do you have the right bug reference format? For this repo, the format is usually 'Fixes #12345' or 'Updates #12345' at the end of the commit message.Please address any problems by updating the GitHub PR.
When complete, mark this comment as 'Done' and click the [blue 'Reply' button](https://go.dev/wiki/GerritBot#i-left-a-reply-to-a-comment-in-gerrit-but-no-one-but-me-can-see-it) above. These findings are based on heuristics; if a finding does not apply, briefly reply here saying so.
To update the commit title or commit message body shown here in Gerrit, you must edit the GitHub PR title and PR description (the first comment) in the GitHub web interface using the 'Edit' button or 'Edit' menu entry there. Note: pushing a new commit to the PR will not automatically update the commit message used by Gerrit.
For more details, see:
- [how to update commit messages](https://go.dev/wiki/GerritBot/#how-does-gerritbot-determine-the-final-commit-message) for PRs imported into Gerrit.
- the Go project's [conventions for commit messages](https://go.dev/doc/contribute#commit_messages) that you should follow.
(In general for Gerrit code reviews, the change author is expected to [log in to Gerrit](https://go-review.googlesource.com/login/) with a Gmail or other Google account and then close out each piece of feedback by marking it as 'Done' if implemented as suggested or otherwise reply to each review comment. See the [Review](https://go.dev/doc/contribute#review) section of the Contributing Guide for details.)
Done
JorropoThe code fixes the main issue that is allocations in hot loops. Looks good to me.
You can't review your own patches 😐
Sorry, my bad.
func (t *sixIntPool) Put(data *[6]*Int) {- Alan Donovan
- Jorropo
- Mateusz Poliwczak
- Robert Griesemer
Code-Review
No-Holds
No-Unresolved-Comments
No-Wait-Release
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Gerrit Bot (Gerrit)
Gerrit Bot uploaded new patchset![]( "Open in Gerrit")
Related details
- Alan Donovan
- Jorropo
- Mateusz Poliwczak
- Robert Griesemer
Code-Review
No-Holds
No-Unresolved-Comments
No-Wait-Release
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |