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.