Optimize Diff for frequent equality (#204)

Diff is most often used in tests where the expected outcome
is equality (and thus no reported difference). Optimize for this
situation by performing a fast-pass equality check and only fall
back on constructing a report if inequal.

1 files changed, 45 insertions, 25 deletions

diff --git a/cmp/compare.go b/cmp/compare.go
index 7ad400f..a58ada5 100644
--- a/cmp/compare.go
+++ b/cmp/compare.go
@@ -90,30 +90,8 @@ import (
 // If there is a cycle, then the pointed at values are considered equal
 // only if both addresses were previously visited in the same path step.
 func Equal(x, y interface{}, opts ...Option) bool {
-	vx := reflect.ValueOf(x)
-	vy := reflect.ValueOf(y)
-
-	// If the inputs are different types, auto-wrap them in an empty interface
-	// so that they have the same parent type.
-	var t reflect.Type
-	if !vx.IsValid() || !vy.IsValid() || vx.Type() != vy.Type() {
-		t = reflect.TypeOf((*interface{})(nil)).Elem()
-		if vx.IsValid() {
-			vvx := reflect.New(t).Elem()
-			vvx.Set(vx)
-			vx = vvx
-		}
-		if vy.IsValid() {
-			vvy := reflect.New(t).Elem()
-			vvy.Set(vy)
-			vy = vvy
-		}
-	} else {
-		t = vx.Type()
-	}
-
 	s := newState(opts)
-	s.compareAny(&pathStep{t, vx, vy})
+	s.compareAny(rootStep(x, y))
 	return s.result.Equal()
 }
 
@@ -132,15 +110,57 @@ func Equal(x, y interface{}, opts ...Option) bool {
 // Do not depend on this output being stable. If you need the ability to
 // programmatically interpret the difference, consider using a custom Reporter.
 func Diff(x, y interface{}, opts ...Option) string {
+	s := newState(opts)
+
+	// Optimization: If there are no other reporters, we can optimize for the
+	// common case where the result is equal (and thus no reported difference).
+	// This avoids the expensive construction of a difference tree.
+	if len(s.reporters) == 0 {
+		s.compareAny(rootStep(x, y))
+		if s.result.Equal() {
+			return ""
+		}
+		s.result = diff.Result{} // Reset results
+	}
+
 	r := new(defaultReporter)
-	eq := Equal(x, y, Options(opts), Reporter(r))
+	s.reporters = append(s.reporters, reporter{r})
+	s.compareAny(rootStep(x, y))
 	d := r.String()
-	if (d == "") != eq {
+	if (d == "") != s.result.Equal() {
 		panic("inconsistent difference and equality results")
 	}
 	return d
 }
 
+// rootStep constructs the first path step. If x and y have differing types,
+// then they are stored within an empty interface type.
+func rootStep(x, y interface{}) PathStep {
+	vx := reflect.ValueOf(x)
+	vy := reflect.ValueOf(y)
+
+	// If the inputs are different types, auto-wrap them in an empty interface
+	// so that they have the same parent type.
+	var t reflect.Type
+	if !vx.IsValid() || !vy.IsValid() || vx.Type() != vy.Type() {
+		t = reflect.TypeOf((*interface{})(nil)).Elem()
+		if vx.IsValid() {
+			vvx := reflect.New(t).Elem()
+			vvx.Set(vx)
+			vx = vvx
+		}
+		if vy.IsValid() {
+			vvy := reflect.New(t).Elem()
+			vvy.Set(vy)
+			vy = vvy
+		}
+	} else {
+		t = vx.Type()
+	}
+
+	return &pathStep{t, vx, vy}
+}
+
 type state struct {
 	// These fields represent the "comparison state".
 	// Calling statelessCompare must not result in observable changes to these.