From b596085d2391ce3701fa6820a6728ba634ac453b Mon Sep 17 00:00:00 2001 From: Lukasz Kasprzak Date: Thu, 17 Sep 2026 13:47:35 +0200 Subject: 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. --- internal/dup/dup.go | 54 +++++++++++++++++++++++++++++++++++++++++++----- internal/dup/dup_test.go | 49 +++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 98 insertions(+), 5 deletions(-) (limited to 'internal/dup') 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)) + } +} -- cgit v1.3