diff options
author | alandonovan <adonovan@google.com> | 2020-06-17 14:27:56 -0400 |
---|---|---|
committer | GitHub <noreply@github.com> | 2020-06-17 14:27:56 -0400 |
commit | c6daab680f283fdf16a79c99d8e86a1562400761 (patch) | |
tree | 3a69918222b2653c9f7fd98f2ed22b846b6a1756 /starlark/int_generic.go | |
parent | fd77f1382f3580e9991b1b20a9985b14dd670dda (diff) | |
download | starlark-go-c6daab680f283fdf16a79c99d8e86a1562400761.tar.gz |
int: reduce allocation by representing small ints as pointers (#280)
* int: consolidate field accessors
This change defines low-level accessors for the small and big
arms of the int union so that the representation can be easily
changed in a follow-up.
Change-Id: I7c4ae279a6d2e7b76e102ba5d01a3cd1c56fb368
* int: improve performance by avoiding allocation
This change defines a new representation for Int on 64-bit machines
running a POSIX operating system, by reserving a 4GB portion of the
address space.
Pointers to addresses in this region represent int32 values,
and are disjoint from all *big.Int pointers,
allowing us to represent the union in a single pointer.
This means the conversion from Int to Value does not allocate.
The gauss benchmark (added in this CL) shows -40% ns, -48% bytes, -63% allocs:
Benchmark/bench_gauss-12 84 13648744 ns/op 3175816 B/op 105862 allocs/op (before)
Benchmark/bench_gauss-12 55 24283703 ns/op 6119844 B/op 289862 allocs/op (after)
On 32-bit machines, or those running a non-POSIX system,
we continue to use the old representation.
Diffstat (limited to 'starlark/int_generic.go')
-rw-r--r-- | starlark/int_generic.go | 33 |
1 files changed, 33 insertions, 0 deletions
diff --git a/starlark/int_generic.go b/starlark/int_generic.go new file mode 100644 index 0000000..a472a4c --- /dev/null +++ b/starlark/int_generic.go @@ -0,0 +1,33 @@ +//+build !linux,!darwin !amd64,!arm64,!mips64x,!ppc64x + +package starlark + +// generic Int implementation as a union + +import "math/big" + +type intImpl struct { + // We use only the signed 32-bit range of small to ensure + // that small+small and small*small do not overflow. + small_ int64 // minint32 <= small <= maxint32 + big_ *big.Int // big != nil <=> value is not representable as int32 +} + +// --- low-level accessors --- + +// get returns the small and big components of the Int. +// small is defined only if big is nil. +// small is sign-extended to 64 bits for ease of subsequent arithmetic. +func (i Int) get() (small int64, big *big.Int) { + return i.small_, i.big_ +} + +// Precondition: math.MinInt32 <= x && x <= math.MaxInt32 +func makeSmallInt(x int64) Int { + return Int{intImpl{small_: x}} +} + +// Precondition: x cannot be represented as int32. +func makeBigInt(x *big.Int) Int { + return Int{intImpl{big_: x}} +} |