Performance Issue Comparing Array Types

[lmittmann]

I ran into an issue where the comparison of a struct type containing lots of arrays took super long. After adding cmpopts.EquateComparable to the check the comparison is more than 10x faster. I think it should be okay to compare arrays of basic types (e.g. [32]byte) using == by default.

Example Benchmark:

func BenchmarkCmp(b *testing.B) {
	var v0, v1 [32]byte
	b.Run("plain", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			cmp.Diff(v0, v1)
		}
	})

	b.Run("comparable", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			cmp.Diff(v0, v1, cmpopts.EquateComparable([32]byte{}))
		}
	})

	type S struct {
		A [32]byte
		B [32]byte
		C [32]byte
		D []struct {
			E [32]byte
			F [32]byte
		}
	}
	var s0, s1 S
	b.Run("struct_plain", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			cmp.Diff(s0, s1)
		}
	})

	b.Run("struct_comparable", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			cmp.Diff(s0, s1, cmpopts.EquateComparable([32]byte{}))
		}
	})
}

Results:

                        │    sec/op    │
Cmp/plain-8               7.451µ ±  3%
Cmp/comparable-8          4.816µ ±  6%
Cmp/struct_plain-8        32.92µ ± 29%
Cmp/struct_comparable-8   13.56µ ±  5%

[dsnet]

This is not specific to [N]byte but also []byte.

As a point of semantic correctness we have to descend into each individual byte element if there were any options that are possibly applicable. However, we could short-circuit the evaluation if we detect that no option could possibly be applicable. Note that if the caller passes in any cmp.FilterPath options, then we cannot do the short-circuit since this option is Turing complete and we cannot prove that it wouldn't match on individual byte values.