`cmp.Diff` hangs for deeply nested slices

[seehuhn]

I have been using cmp.Diff inside a fuzzing function to check whether my code gives the correct results. When the fuzz test failed, it turned out the fuzzer had brokem cmp.Diff instead of my code. Here is a simplified version, to show how cmp.Diff hangs when the arguments are deeply nested slices:

package main

import (
	"fmt"

	"github.com/google/go-cmp/cmp"
)

func main() {
	a := []interface{}{}
	for i := 0; i < 50; i++ {
		a = []interface{}{a}
	}
	fmt.Println(cmp.Diff(a, a)) // this takes an extremely long time
}

(playground version). Since reflect.DeepEqual works for the same inputs (playground), I believe this may be a bug in cmp.Diff.

[dsnet]

There's clearly some quadratic behavior (relative to tree depth) going on here, which needs investigation.

[seehuhn]

I think the runtime increases exponentially with the nesting depth. When I time cmp.Diff() and plot the runtime vs. nesting depth on a plot with logarithmic y-axis, I get an approximately straight line. (Maybe it even curves upward a bit?)

That's the code I used to time the calls:

package main

import (
	"fmt"
	"os"
	"time"

	"github.com/google/go-cmp/cmp"
)

func main() {
	a := []interface{}{}
	for i := 0; ; i++ {
		start := time.Now()
		var d time.Duration
		n := 0
		for ; n < 1000; n++ {
			_ = cmp.Diff(a, a)
			d = time.Since(start)
			if d > 5*time.Second {
				os.Exit(0)
			}
		}
		fmt.Printf("%d %.1f\n", i, 1e6*d.Seconds()/float64(n))

		a = []interface{}{a}
	}
}