1 files changed, 49 insertions, 5 deletions

diff --git a/internal/dup/dup.go b/internal/dup/dup.go
index f7bc5af..a6154d2 100644
--- a/internal/dup/dup.go
+++ b/internal/dup/dup.go
@@ -44,6 +44,16 @@ type Index struct {
 	partial map[string][sha256.Size]byte // memoised partial hash, by path
 	full    map[string][sha256.Size]byte // memoised full hash, by path
 
+	// elected is the content class, memoised: candidate index -> the index
+	// of the original its class elected, itself when it is alone. Every
+	// member of a class elects the same original (see identicalTo), so the
+	// class is worth computing once; without this, N copies of one file
+	// cost N walks of an N-member size group, each taking mu at every step.
+	elected map[int]int
+
+	// walks counts identicalTo calls, for the test that pins the memo.
+	walks int
+
 	candErrs    []CandidateError
 	candErrSeen map[string]bool // path already recorded in candErrs
 }
@@ -166,14 +176,21 @@ func (x *Index) Lookup(path string) (original string, dup bool, err error) {
 		return path, false, nil
 	}
 
-	identical, err := x.identicalTo(idx, group)
-	if err != nil {
-		return "", false, err
+	origIdx, known := x.electedFor(idx)
+	if !known {
+		identical, err := x.identicalTo(idx, group)
+		if err != nil {
+			return "", false, err
+		}
+		// Alone in its class after hashing: remember that too, so asking
+		// again costs nothing.
+		origIdx = x.original(identical)
+		x.remember(identical, origIdx)
 	}
-	if len(identical) < 2 {
+	if origIdx == idx {
 		return path, false, nil
 	}
-	orig := x.candidates[x.original(identical)].path
+	orig := x.candidates[origIdx].path
 	if orig == path {
 		return orig, false, nil
 	}
@@ -216,6 +233,9 @@ func (x *Index) Lookup(path string) (original string, dup bool, err error) {
 // other failure is recorded on the Index (see recordCandidateError) so the
 // caller can warn about it once matching is done.
 func (x *Index) identicalTo(idx int, group []int) ([]int, error) {
+	x.mu.Lock()
+	x.walks++
+	x.mu.Unlock()
 	idxPartial, err := x.partialHash(x.candidates[idx].path)
 	if err != nil {
 		return nil, err
@@ -467,3 +487,27 @@ func computeFullHash(path string) ([sha256.Size]byte, error) {
 	copy(out[:], h.Sum(nil))
 	return out, nil
 }
+
+// electedFor returns the original candidates[idx]'s content class elected,
+// if that class has already been worked out.
+func (x *Index) electedFor(idx int) (int, bool) {
+	x.mu.Lock()
+	defer x.mu.Unlock()
+	orig, ok := x.elected[idx]
+	return orig, ok
+}
+
+// remember records the elected original for every member of a class. Every
+// member elects the same original, so one walk answers for all of them -
+// including the case of a file alone in its class, where the answer is
+// itself and the saving is the walk that found that out.
+func (x *Index) remember(class []int, orig int) {
+	x.mu.Lock()
+	defer x.mu.Unlock()
+	if x.elected == nil {
+		x.elected = make(map[int]int, len(class))
+	}
+	for _, j := range class {
+		x.elected[j] = orig
+	}
+}