a content class is worked out once, not once per copy

Lookup walked the whole size group for every file in it, so N copies of
one file cost N walks of an N-member group, each taking the index's
lock at every step - which is why more workers made it slower rather
than faster. Every member of a class elects the same original (the
invariant identicalTo already documents and a test already pins), so
the class is memoised on the first walk and every later member is a
map lookup.

Measured over identical files, invented data, same machine:

  500 files   0.17s -> 0.12s
  2000 files  1.89s -> 0.58s

and the plans are byte-identical once the sandbox path is normalised.
The test counts walks: one per content class, not one per file.

2 files changed, 98 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
+	}
+}
diff --git a/internal/dup/dup_test.go b/internal/dup/dup_test.go
index 8984336..a616118 100644
--- a/internal/dup/dup_test.go
+++ b/internal/dup/dup_test.go
@@ -577,3 +577,52 @@ func TestThreeCopiesWithOverlappingExtraDirKeepOne(t *testing.T) {
 		}
 	}
 }
+
+// TestLookupWalksAClassOnce: every member of a content class elects the
+// same original, so the class is worth computing once. Walking the size
+// group again for every member makes a directory of N copies cost N^2
+// comparisons - 8000 identical files took 35 s of it - and the walk takes
+// the index's lock at every step, so more workers made it slower rather
+// than faster. This counts the walks: one per class, not one per file.
+func TestLookupWalksAClassOnce(t *testing.T) {
+	d := t.TempDir()
+	const n = 12
+	var files []scan.File
+	for i := 0; i < n; i++ {
+		// Two classes of one size, so the size group cannot be the thing
+		// being memoised.
+		body := "the same bytes for all of these"
+		if i%2 == 1 {
+			body = "different bytes, identical size"
+		}
+		files = append(files, put(t, d, fmt.Sprintf("f%02d.bin", i), []byte(body), i))
+	}
+	x, errs := NewIndex(files, nil)
+	if len(errs) > 0 {
+		t.Fatal(errs)
+	}
+	for _, f := range files {
+		lookup(t, x, f)
+	}
+	if x.walks > 2 {
+		t.Errorf("identicalTo ran %d times for 2 content classes over %d files; want one walk per class", x.walks, n)
+	}
+
+	// The answers must be what they were before memoising: one original
+	// per class, and that original is not itself a duplicate.
+	dups := 0
+	origs := map[string]int{}
+	for _, f := range files {
+		orig, isDup := lookup(t, x, f)
+		if isDup {
+			dups++
+		}
+		origs[orig]++
+	}
+	if dups != n-2 {
+		t.Errorf("%d duplicates over two classes of %d files, want %d", dups, n, n-2)
+	}
+	if len(origs) != 2 {
+		t.Errorf("the two classes elected %d originals, want 2", len(origs))
+	}
+}