Computing Incremented UUID

uuid_incr.go

package main

import (
	"encoding/binary"
	"math/big"
	"math/rand"
	"reflect"
	"testing"
	"testing/quick"
)

type uuid [16]byte

func uuidFromInts(hi, lo uint64) uuid {
	var u uuid
	binary.BigEndian.PutUint64(u[0:8], hi)
	binary.BigEndian.PutUint64(u[8:16], lo)
	return u
}

func uuidFromBytes(b []byte) uuid {
	var u uuid
	copy(u[16-len(b):], b)
	return u
}

func (u uuid) GetBytes() []byte {
	return u[:]
}

func (u uuid) AsInts() (hi, lo uint64) {
	return binary.BigEndian.Uint64(u[0:8]), binary.BigEndian.Uint64(u[8:16])
}

// avoid alloc.
var bigOne = big.NewInt(1)

func nextBig(u uuid) uuid {
	i := new(big.Int).SetBytes(u.GetBytes())
	return uuidFromBytes(i.Add(i, bigOne).Bytes())
}

func prevBig(u uuid) uuid {
	i := new(big.Int).SetBytes(u.GetBytes())
	return uuidFromBytes(i.Sub(i, bigOne).Bytes())
}

func nextBinary(u uuid) uuid {
	hi, lo := u.AsInts()
	lo = lo + 1
	if lo == 0 {
		hi = hi + 1
	}
	return uuidFromInts(hi, lo)
}

func prevBinary(u uuid) uuid {
	hi, lo := u.AsInts()
	if lo == 0 {
		hi = hi - 1
	}
	lo = lo - 1
	return uuidFromInts(hi, lo)
}

var one = uuid{1}

func BenchmarkNextBig(b *testing.B) {
	x := one
	for i := 0; i < b.N; i++ {
		x = nextBig(x)
	}
}
func BenchmarkNextBinary(b *testing.B) {
	x := one
	for i := 0; i < b.N; i++ {
		x = nextBinary(x)
	}
}
func BenchmarkPrevBig(b *testing.B) {
	x := one
	for i := 0; i < b.N; i++ {
		x = prevBig(x)
	}
}
func BenchmarkPrevBinary(b *testing.B) {
	x := one
	for i := 0; i < b.N; i++ {
		x = prevBinary(x)
	}
}
func TestBigMatchesBinary(t *testing.T) {
	conf := &quick.Config{
		Values: func(args []reflect.Value, r *rand.Rand) {
			u := uuid{}
			_, _ = rand.Read(u[:])
			args[0] = reflect.ValueOf(u)
		},
	}
	t.Run("prevBig(nextBig(x)) == x", func(t *testing.T) {
		if err := quick.Check(func(u uuid) bool {
			return prevBig(nextBig(u)) == u
		}, conf); err != nil {
			t.Fatal(err)
		}
	})

	t.Run("nextBig(prevBig(x)) == x", func(t *testing.T) {
		if err := quick.Check(func(u uuid) bool {
			return nextBinary(prevBinary(u)) == u
		}, conf); err != nil {
			t.Fatal(err)
		}
	})

	t.Run("next(x) != x", func(t *testing.T) {
		if err := quick.Check(func(u uuid) bool {
			return nextBinary(u) != u
		}, conf); err != nil {
			t.Fatal(err)
		}
	})

	t.Run("nextBig == nextBinary", func(t *testing.T) {
		if err := quick.CheckEqual(nextBig, nextBinary, conf); err != nil {
			t.Error(err)
		}
	})
	t.Run("prevBinary == prevBig", func(t *testing.T) {
		if err := quick.CheckEqual(prevBinary, prevBig, conf); err != nil {
			t.Error(err)
		}
	})
}

pulling the big.NewInt(1) into a re-used var and reusing i in the Add and Sub calls sheds 3 of the 5 allocs in the big methods, but it is still not even close:

go test -bench . -benchmem
BenchmarkNextBig-4      	10000000	       159 ns/op	      64 B/op	       2 allocs/op
BenchmarkNextBinary-4   	100000000	        22.0 ns/op	       0 B/op	       0 allocs/op
BenchmarkPrevBig-4      	10000000	       156 ns/op	      64 B/op	       2 allocs/op
BenchmarkPrevBinary-4   	100000000	        22.4 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	github.com/cockroachdb/cockroach/meh	7.996s