gnolang/overflow: optimise package for common architectures #1844
Labels
Comments
|
This issue is stale because it has been open 6 months with no activity. Remove stale label or comment or this will be closed in 3 months. |
6 tasks
mvertes
added a commit
that referenced
this issue
Jan 9, 2025
I propose that we implement overflow checking directly in gnovm opcodes,
and that gnovm always enforces overflow checking. Overflow checking
becomes a capacity of the Gno language and the Gno virtual machine.
It's important for a smart contract platform to offer by default, and
without user or developer effort, the strongest guarantees on numerical
operations.
In that topic, Gno would be superior to the standard Go runtime which,
like C and most other languages, don't address this internally beside
constants (to preserve the best possible native performances), and rely
on external user code.
It would also simplify the user code and avoid to use specific
libraries.
For example, in `gnovm/stdlibs/std/coins.go`, for the `Coin.Add` method:
Before:
```go
import "math/overflow"
func (c Coin) Add(other Coin) Coin {
mustMatchDenominations(c.Denom, other.Denom)
sum, ok := overflow.Add64(c.Amount, other.Amount)
if !ok {
panic("coin add overflow/underflow: " +
strconv.Itoa(int(c.Amount)) + " +/- " +
strconv.Itoa(int(other.Amount)))
}
c.Amount = sum
return c
}
```
After:
```go
func (c Coin) Add(other Coin) Coin {
mustMatchDenominations(c.Denom, other.Denom)
c.Amount += other.Amount
return c
}
```
with the same behaviour for overflow checking. Note also that the new
version, is not only simpler, but also faster, because overflow checking
is performed natively, and not interpreted.
Integer overflow handling is only implemented for signed integers.
Unsigned integers, on purpose, just wrap around when reaching their
maximum or minimum values. This is intended to support all crypto, hash
and bitwise operations which may rely on that wrap around property.
Division by zero is still handled both in signed and unsigned integers.
Note: from now, on security level, the use of unsigned integers for
standard numeric operations should be probably considered suspicious.
## Benchmark
To measure the impact of overflow, I execute the following benchmarks:
First a micro benchmark comparing an addition of 2 ints, with and
without overflow:
```go
//go:noinline
func AddNoOverflow(x, y int) int { return x + y }
func BenchmarkAddNoOverflow(b *testing.B) {
x, y := 4, 3
c := 0
for range b.N {
c = AddNoOverflow(x, y)
}
if c != 7 {
b.Error("invalid result")
}
}
func BenchmarkAddOverflow(b *testing.B) {
x, y := 4, 3
c := 0
for range b.N {
c = overflow.Addp(x, y)
}
if c != 7 {
b.Error("invalid result")
}
}
```
The implementation of overflow checking is taken from
http://github.com/gnolang/overflow, already used in tm2.
It gives the following results:
```console
$ go test -v- run=^# -benchmem -bench=Overflow
goos: darwin
goarch: arm64
pkg: github.com/gnolang/gno/gnovm/pkg/gnolang
cpu: Apple M1
BenchmarkAddNoOverflow
BenchmarkAddNoOverflow-8 1000000000 0.9392 ns/op 0 B/op 0 allocs/op
BenchmarkAddOverflow
BenchmarkAddOverflow-8 568881582 2.101 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/gnolang/gno/gnovm/pkg/gnolang 2.640s
```
Checking overflow doubles the execution time of an addition from 1 ns/op
to 2 ns/op.
But at 2 ns, the total time is still an order of magnitude lower than
the cost of running the VM.
The impact of overflow check doesn't even appear when benchmarking at VM
level with the following:
```go
func BenchmarkOpAdd(b *testing.B) {
m := NewMachine("bench", nil)
x := TypedValue{T: IntType}
x.SetInt(4)
y := TypedValue{T: IntType}
y.SetInt(3)
b.ResetTimer()
for range b.N {
m.PushOp(OpHalt)
m.PushExpr(&BinaryExpr{})
m.PushValue(x)
m.PushValue(y)
m.PushOp(OpAdd)
m.Run()
}
}
```
Which gives something like:
```console
$ go test -v -benchmem -bench=OpAdd -run=^#
goos: darwin
goarch: arm64
pkg: github.com/gnolang/gno/gnovm/pkg/gnolang
cpu: Apple M1
BenchmarkOpAdd
BenchmarkOpAdd-8 16069832 74.41 ns/op 163 B/op 1 allocs/op
PASS
ok github.com/gnolang/gno/gnovm/pkg/gnolang 1.526
```
Where the execution time varie from 60 ns/op to 100 ns/op for both
versions of addition, with or without overflow.
## Related PRs and issues
- PRs:
- #3197
- #3192
- #3117
- #2983
- #2905
- #2698
- Issues:
- #2873
- #1844
- #1729
<!-- please provide a detailed description of the changes made in this
pull request. -->
<details><summary>Contributors' checklist...</summary>
- [ ] Added new tests, or not needed, or not feasible
- [ ] Provided an example (e.g. screenshot) to aid review or the PR is
self-explanatory
- [ ] Updated the official documentation or not needed
- [ ] No breaking changes were made, or a `BREAKING CHANGE: xxx` message
was included in the description
- [ ] Added references to related issues and PRs
- [ ] Provided any useful hints for running manual tests
</details>
albttx
pushed a commit
that referenced
this issue
Jan 10, 2025
I propose that we implement overflow checking directly in gnovm opcodes,
and that gnovm always enforces overflow checking. Overflow checking
becomes a capacity of the Gno language and the Gno virtual machine.
It's important for a smart contract platform to offer by default, and
without user or developer effort, the strongest guarantees on numerical
operations.
In that topic, Gno would be superior to the standard Go runtime which,
like C and most other languages, don't address this internally beside
constants (to preserve the best possible native performances), and rely
on external user code.
It would also simplify the user code and avoid to use specific
libraries.
For example, in `gnovm/stdlibs/std/coins.go`, for the `Coin.Add` method:
Before:
```go
import "math/overflow"
func (c Coin) Add(other Coin) Coin {
mustMatchDenominations(c.Denom, other.Denom)
sum, ok := overflow.Add64(c.Amount, other.Amount)
if !ok {
panic("coin add overflow/underflow: " +
strconv.Itoa(int(c.Amount)) + " +/- " +
strconv.Itoa(int(other.Amount)))
}
c.Amount = sum
return c
}
```
After:
```go
func (c Coin) Add(other Coin) Coin {
mustMatchDenominations(c.Denom, other.Denom)
c.Amount += other.Amount
return c
}
```
with the same behaviour for overflow checking. Note also that the new
version, is not only simpler, but also faster, because overflow checking
is performed natively, and not interpreted.
Integer overflow handling is only implemented for signed integers.
Unsigned integers, on purpose, just wrap around when reaching their
maximum or minimum values. This is intended to support all crypto, hash
and bitwise operations which may rely on that wrap around property.
Division by zero is still handled both in signed and unsigned integers.
Note: from now, on security level, the use of unsigned integers for
standard numeric operations should be probably considered suspicious.
## Benchmark
To measure the impact of overflow, I execute the following benchmarks:
First a micro benchmark comparing an addition of 2 ints, with and
without overflow:
```go
//go:noinline
func AddNoOverflow(x, y int) int { return x + y }
func BenchmarkAddNoOverflow(b *testing.B) {
x, y := 4, 3
c := 0
for range b.N {
c = AddNoOverflow(x, y)
}
if c != 7 {
b.Error("invalid result")
}
}
func BenchmarkAddOverflow(b *testing.B) {
x, y := 4, 3
c := 0
for range b.N {
c = overflow.Addp(x, y)
}
if c != 7 {
b.Error("invalid result")
}
}
```
The implementation of overflow checking is taken from
http://github.com/gnolang/overflow, already used in tm2.
It gives the following results:
```console
$ go test -v- run=^# -benchmem -bench=Overflow
goos: darwin
goarch: arm64
pkg: github.com/gnolang/gno/gnovm/pkg/gnolang
cpu: Apple M1
BenchmarkAddNoOverflow
BenchmarkAddNoOverflow-8 1000000000 0.9392 ns/op 0 B/op 0 allocs/op
BenchmarkAddOverflow
BenchmarkAddOverflow-8 568881582 2.101 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/gnolang/gno/gnovm/pkg/gnolang 2.640s
```
Checking overflow doubles the execution time of an addition from 1 ns/op
to 2 ns/op.
But at 2 ns, the total time is still an order of magnitude lower than
the cost of running the VM.
The impact of overflow check doesn't even appear when benchmarking at VM
level with the following:
```go
func BenchmarkOpAdd(b *testing.B) {
m := NewMachine("bench", nil)
x := TypedValue{T: IntType}
x.SetInt(4)
y := TypedValue{T: IntType}
y.SetInt(3)
b.ResetTimer()
for range b.N {
m.PushOp(OpHalt)
m.PushExpr(&BinaryExpr{})
m.PushValue(x)
m.PushValue(y)
m.PushOp(OpAdd)
m.Run()
}
}
```
Which gives something like:
```console
$ go test -v -benchmem -bench=OpAdd -run=^#
goos: darwin
goarch: arm64
pkg: github.com/gnolang/gno/gnovm/pkg/gnolang
cpu: Apple M1
BenchmarkOpAdd
BenchmarkOpAdd-8 16069832 74.41 ns/op 163 B/op 1 allocs/op
PASS
ok github.com/gnolang/gno/gnovm/pkg/gnolang 1.526
```
Where the execution time varie from 60 ns/op to 100 ns/op for both
versions of addition, with or without overflow.
## Related PRs and issues
- PRs:
- #3197
- #3192
- #3117
- #2983
- #2905
- #2698
- Issues:
- #2873
- #1844
- #1729
<!-- please provide a detailed description of the changes made in this
pull request. -->
<details><summary>Contributors' checklist...</summary>
- [ ] Added new tests, or not needed, or not feasible
- [ ] Provided an example (e.g. screenshot) to aid review or the PR is
self-explanatory
- [ ] Updated the official documentation or not needed
- [ ] No breaking changes were made, or a `BREAKING CHANGE: xxx` message
was included in the description
- [ ] Added references to related issues and PRs
- [ ] Provided any useful hints for running manual tests
</details>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The overflow package, soon to be used not just for coin addition but also for hot paths in the code, currently implements its overflow checks by checking the result to have some expected characteristic (ie. multiplying two negative numbers should yield a positive number; if it's negative, an overflow occurred).
However, it should be noted that x86, ARM and possibly other architectures have flags to mark when an operation has under/overflowed already: on x86 -- the OF and CF flags.
Since we're starting to use this code in very hot paths, we should consider adding this optimisation, at least for x86 and ARM.
The text was updated successfully, but these errors were encountered: