perf(spanner): improve mutationProto allocations and performance

[rahul2393]

Fixes: #12680

[rahul2393]

The benchmark results indicate a significant performance improvement. The mutationsProto function is now approximately 81% faster, uses 57% less memory, and makes 16% fewer memory allocations on average.

goos: darwin
goarch: arm64
pkg: cloud.google.com/go/spanner
cpu: Apple M1 Pro
                                            │  before.txt  │              after.txt              │
                                            │    sec/op    │   sec/op     vs base                │
MutationsProto/small_number_of_mutations-10   13.778µ ± 1%   1.548µ ± 3%  -88.77% (p=0.000 n=20)
MutationsProto/large_number_of_mutations-10    43.83µ ± 1%   30.51µ ± 1%  -30.38% (p=0.000 n=20)
MutationsProto/mixed_type_of_mutations-10     13.289µ ± 1%   1.140µ ± 1%  -91.42% (p=0.000 n=20)
geomean                                        20.02µ        3.776µ       -81.14%

                                            │  before.txt  │              after.txt               │
                                            │     B/op     │     B/op      vs base                │
MutationsProto/small_number_of_mutations-10   8.844Ki ± 0%   2.961Ki ± 0%  -66.52% (p=0.000 n=20)
MutationsProto/large_number_of_mutations-10   67.10Ki ± 0%   59.16Ki ± 0%  -11.84% (p=0.000 n=20)
MutationsProto/mixed_type_of_mutations-10     7.979Ki ± 0%   2.164Ki ± 0%  -72.88% (p=0.000 n=20)
geomean                                       16.79Ki        7.237Ki       -56.90%

                                            │ before.txt  │              after.txt              │
                                            │  allocs/op  │  allocs/op   vs base                │
MutationsProto/small_number_of_mutations-10    84.00 ± 0%    67.00 ± 0%  -20.24% (p=0.000 n=20)
MutationsProto/large_number_of_mutations-10   1.343k ± 0%   1.321k ± 0%   -1.64% (p=0.000 n=20)
MutationsProto/mixed_type_of_mutations-10      64.00 ± 0%    49.00 ± 0%  -23.44% (p=0.000 n=20)
geomean                                        193.3         163.1       -15.63%

[rahul2393]

@codyoss quick review here is really appreciated.

[pbotros]

I like how we're avoiding allocs now, but one improvement here is to avoid doing the rand.Intn() in a tightloop. Would you consider doing an extra loop through the mutations? I'd imagine that may actually result in better performance since rand methods are relatively slow.

Suggested change

	if rand.Intn(nonInsertCount) == 0 {
	selectedNonInsertIdx = i
	}

and then later:

if nonInsertCount > 0 {
  selectedNonInsertIdx := rand.Intn(nonInsertCount)
  var selectedMutation *Mutation
	for i, outM := range out {
         inM := ms[i]
         if inM.op == opInsert {
			if selectedNonInsertIdx == 0 {
				selectedMutation = outM
                 break
			}
			selectedNonInsertIdx--
		}
      return out, selectedMutation, nil
	}
}

[pbotros]

Actually, tried out the diff on my local branch and it didn't seem to be any faster. So nevermind here.

[pbotros]

Actually, tried out the diff on my local branch and it didn't seem to be any faster. So nevermind here.

[pbotros]

nit: at first glance it's a bit surprising that this ends up being a uniform distribution, so perhaps a comment can help here:

Suggested change

	if rand.Intn(nonInsertCount) == 0 {
	selectedNonInsertIdx = i
	}
	// Pick a non-insert mutation uniformly at random.
	if rand.Intn(nonInsertCount) == 0 {
	selectedNonInsertIdx = i
	}

[olavloite]

This point will never be reached, right? Because we always have:

1. An empty input slice of mutations, which causes an empty return
2. At least one non-insert mutation.
3. Or one insert mutation.

[rahul2393]

Yes, this is here because Golang expects a return at the end of method.