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.

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}}
+}