From 78d8313791f05defc9e0a9f2bad8e9710f741a60 Mon Sep 17 00:00:00 2001 From: Lukasz Kasprzak Date: Thu, 17 Sep 2026 13:50:01 +0200 Subject: the suffix search continues instead of starting again at _1 Every file renamed onto one name probed stem_1, stem_2, ... from the beginning, so N files cost N^2/2 Exists calls - a test here counts 1890 of them for 60 files. The search now continues from the highest suffix already tried for that stem. Within one plan that is the same answer: the taken set only grows while a plan is built and the disk is not being written to, so a suffix taken once stays taken. Proved rather than argued - with same_1 and same_3 already on disk and same_2 free, both versions put a file in the gap, and the two plans are byte-identical. 1500 files renamed to one name: 2.63s -> 0.05s --- internal/plan/chain.go | 10 ++++---- internal/plan/conflict.go | 34 ++++++++++++++++++++++---- internal/plan/conflict_test.go | 54 +++++++++++++++++++++++++++++++++++++++++- internal/plan/enum_test.go | 4 ++-- 4 files changed, 89 insertions(+), 13 deletions(-) (limited to 'internal') diff --git a/internal/plan/chain.go b/internal/plan/chain.go index b8a95f6..7c95d9b 100644 --- a/internal/plan/chain.go +++ b/internal/plan/chain.go @@ -25,13 +25,13 @@ type Claims struct { // NewClaims returns an empty Claims, ready to pass to Build. func NewClaims() *Claims { - return &Claims{taken: claimed{}} + return &Claims{taken: newClaimed()} } // Claim marks path as spoken for: a later Build call of the run treats it // as another step's result, never displacing it (spec §7.4). func (c *Claims) Claim(path string) { - c.taken[path] = true + c.taken.taken[path] = true } // Input is one file and the rules that matched it, in match order. @@ -80,7 +80,7 @@ func Build(root string, in []Input, now time.Time, d Disk, claims *Claims) []Cha // takes a free name there, exactly as suffix already did for a path that // exists on disk. for _, x := range in { - claims.taken[x.File.Path] = true + claims.taken.taken[x.File.Path] = true } chains := make([]Chain, len(in)) for _, i := range order { @@ -152,7 +152,7 @@ func buildOne(root string, in Input, now time.Time, d Disk, claim claimed) Chain // a name be claimed before its file has actually // vacated it - and stays; do not "fix" it by weakening // the disk check. - claim[resolved] = true + claim.taken[resolved] = true if a.Kind == config.Move { cur = resolved moves++ @@ -184,7 +184,7 @@ func buildOne(root string, in Input, now time.Time, d Disk, claim claimed) Chain step.Displaces = displaces if skip == "" { cur = resolved - claim[resolved] = true + claim.taken[resolved] = true } case config.Delete, config.DeletePermanent: diff --git a/internal/plan/conflict.go b/internal/plan/conflict.go index f5c1224..e1cd6bf 100644 --- a/internal/plan/conflict.go +++ b/internal/plan/conflict.go @@ -53,7 +53,22 @@ func (NoDisk) SameContent(string, string) (bool, error) { return false, nil } // claimed is the set of destination paths already spoken for by an earlier // step of this plan. -type claimed map[string]bool +type claimed struct { + // taken is the set of destination paths already spoken for. + taken map[string]bool + + // next is the highest suffix already tried for a stem, so filling one + // directory with one name does not begin at _1 for every file. Within + // a plan that is the same answer as starting from 1: the taken set + // only grows while a plan is built, and the disk is not being written + // to, so a suffix taken once stays taken. + next map[string]int +} + +// newClaimed returns an empty claimed, both maps ready. +func newClaimed() claimed { + return claimed{taken: map[string]bool{}, next: map[string]int{}} +} // resolveConflict decides what a step whose destination is contested does, // per spec §7.4. src is the step's source (its current path, before this @@ -89,7 +104,7 @@ func resolveConflict(kind Kind, policy config.Conflict, src, dst string, d Disk, } } - if !onDisk && !c[dst] { + if !onDisk && !c.taken[dst] { return dst, "", "" } @@ -97,7 +112,7 @@ func resolveConflict(kind Kind, policy config.Conflict, src, dst string, d Disk, case config.ConflictSkip: return dst, "target exists", "" case config.ConflictOverwrite: - if onDisk && !c[dst] { + if onDisk && !c.taken[dst] { // Only a regular file is ever trashed to make room: a // directory or link of the same name stays, and so does the // step - skipped, saying why. @@ -141,9 +156,18 @@ const maxSuffixAttempts = 10000 func suffixed(dst string, d Disk, c claimed) (resolved, skip string) { dir, base := filepath.Split(dst) stem, ext := splitExt(base) - for n := 1; n <= maxSuffixAttempts; n++ { + key := dir + "\x00" + stem + "\x00" + ext + start := c.next[key] + if start < 1 { + start = 1 + } + for n := start; n <= maxSuffixAttempts; n++ { candidate := filepath.Join(dir, fmt.Sprintf("%s_%d%s", stem, n, ext)) - if !d.Exists(candidate) && !c[candidate] { + if !d.Exists(candidate) && !c.taken[candidate] { + // n itself, not n+1: the caller claims this candidate, so the + // next search sees it taken and moves on. Recording n+1 would + // skip a suffix that is still free if this step is dropped. + c.next[key] = n return candidate, "" } } diff --git a/internal/plan/conflict_test.go b/internal/plan/conflict_test.go index ba415d5..ba111f8 100644 --- a/internal/plan/conflict_test.go +++ b/internal/plan/conflict_test.go @@ -3,6 +3,7 @@ package plan import ( + "fmt" "os" "path/filepath" "testing" @@ -232,7 +233,7 @@ func TestSuffixedCapsAttempts(t *testing.T) { func TestOverwriteNeverDisplacesADirectory(t *testing.T) { dir := "/home/x/Documents/Invoices" d := fakeDisk{exists: map[string]bool{dir: true}, dirs: map[string]bool{dir: true}} - _, skip, displaces := resolveConflict(Move, config.ConflictOverwrite, "/r/Invoices", dir, d, claimed{}) + _, skip, displaces := resolveConflict(Move, config.ConflictOverwrite, "/r/Invoices", dir, d, newClaimed()) if displaces != "" || skip != "target is not a regular file" { t.Errorf("skip %q displaces %q; want skipped, nothing displaced", skip, displaces) } @@ -252,3 +253,54 @@ func TestOverwriteNeverDisplacesAnotherScannedFile(t *testing.T) { t.Errorf("Displaces %q Dst %q Skip %q; want no displacement and /r/b_1.pdf", s.Displaces, s.Dst, s.Skip) } } + +// countingDisk counts Exists calls, so a test can pin how much probing a +// plan does rather than only what it produces. +type countingDisk struct { + fakeDisk + calls int +} + +func (d *countingDisk) Exists(p string) bool { + d.calls++ + return d.fakeDisk.Exists(p) +} + +// TestSuffixedDoesNotRescanFromOne: every file renamed to one name probes +// stem_1, stem_2, ... for a free suffix. Starting each file's search at 1 +// makes N files into N^2/2 Exists calls - 4000 files were eight million of +// them - so the search continues from the highest suffix already tried for +// that name. Within one plan that is the same answer: the taken set only +// grows while a plan is built, so a suffix taken once stays taken. +func TestSuffixedDoesNotRescanFromOne(t *testing.T) { + const n = 60 + in := make([]Input, 0, n) + for i := 0; i < n; i++ { + in = append(in, Input{File: file("/r", fmt.Sprintf("f%02d.pdf", i)), Rules: []RuleMatch{ + {Name: "one", Actions: []config.Action{act(config.Move, "Work"), act(config.Rename, "same.pdf")}}}}) + } + d := &countingDisk{fakeDisk: fakeDisk{exists: map[string]bool{}}} + chains := Build("/r", in, time.Now(), d, NewClaims()) + + // Every file must still land on its own name, the lowest free one. + seen := map[string]bool{} + for _, c := range chains { + last := c.Steps[len(c.Steps)-1] + if last.Dst == "" { + t.Fatalf("%s was skipped: %q", c.File.Rel, last.Skip) + } + if seen[last.Dst] { + t.Errorf("two files planned onto %s", last.Dst) + } + seen[last.Dst] = true + } + if len(seen) != n { + t.Errorf("%d distinct destinations for %d files", len(seen), n) + } + // Quadratic probing would be about n*n/2 = 1800 here; linear is a few + // per file. The bound is loose on purpose - it must fail on n^2 and + // pass on anything sane. + if d.calls > 6*n { + t.Errorf("%d Exists calls for %d files: the suffix search is rescanning from _1", d.calls, n) + } +} diff --git a/internal/plan/enum_test.go b/internal/plan/enum_test.go index 21f6a63..fee279e 100644 --- a/internal/plan/enum_test.go +++ b/internal/plan/enum_test.go @@ -62,7 +62,7 @@ func TestEveryConflictPolicyIsPlanned(t *testing.T) { t.Errorf("config.%s is not planned: %v", name, r) } }() - resolveConflict(Move, config.Conflict(i), "/r/a.pdf", "/r/b.pdf", d, claimed{}) + resolveConflict(Move, config.Conflict(i), "/r/a.pdf", "/r/b.pdf", d, newClaimed()) }() } defer func() { @@ -70,5 +70,5 @@ func TestEveryConflictPolicyIsPlanned(t *testing.T) { t.Error("an unknown conflict policy did not panic") } }() - resolveConflict(Move, config.Conflict(len(policies)), "/r/a.pdf", "/r/b.pdf", d, claimed{}) + resolveConflict(Move, config.Conflict(len(policies)), "/r/a.pdf", "/r/b.pdf", d, newClaimed()) } -- cgit v1.3