Cache checksums between runs so unchanged files are never re-hashed

[fahadsiddiqui]

Summary

Persist checksums between runs, keyed by file identity, so an unchanged file is never hashed twice. This originally came up as a memory concern; measurement says memory is not the problem, but a persistent cache is worth building for a different and stronger reason.

Memory is not the motivation

Measured peak RSS with the two-pass scan (#12):

files	peak RSS
20,000 (unique sizes, nothing hashed)	19.7 MB
50,000 (every file hashed — worst case)	55.8 MB

That is roughly 0.6 KB per file net of Go's ~8 MB runtime baseline: ~70 MB at 100k files, ~600 MB at 1M. For the current non-recursive scan of a single directory this is a non-issue, and a database would be slower than a map for the common case while adding a dependency to a tool that currently has none.

Memory only becomes interesting once -r (#14) lands and a whole home directory is in scope. See "Bounding memory" below, which is mostly solvable without a database.

The actual motivation: never hash the same bytes twice

Cache checksum keyed by file identity, and a rescan skips hashing anything unchanged.

This matters most on cloud-backed directories. Per #19, an iCloud placeholder must be downloaded to be hashed — measured at ~2.2 s/file, ~168 MB and ~8 minutes for one real Desktop. #12 avoids most of that, but only because screenshots happen to have unique sizes; a size collision between two placeholders still triggers a download.

A cache is strictly stronger:

• A file that collides on size is hashed once, ever.
• Eviction does not invalidate the entry. When macOS returns a file to the cloud, its size, mtime and inode are unchanged — only st_blocks goes to 0. So the cached checksum stays valid and the rescan does not re-download it.

That turns repeat scans from accidentally fast (because sizes happened to be unique) into reliably free.

Cache key

(device, inode, size, mtime_nsec) → checksum

• device + inode identify the file across renames and distinguish hard links.
• size + mtime detect modification. Standard, and what make, rsync and most build caches rely on.
• Path is stored for diagnostics but must not be part of the key, so a renamed file keeps its entry.

Deliberately not hashing to validate — that would defeat the purpose.

Known limitation to document: a file modified within the same mtime granularity as a previous scan can go undetected. Real risk, universally accepted by tools of this kind, and mitigated by nanosecond timestamps on APFS/ext4.

Storage options

The tool currently has zero dependencies and installs cleanly with go install. That is worth protecting.

option	pros	cons
Plain index file (gob/JSON in ~/.cache/dedup/)	zero deps, trivial, fast to load	whole index in memory; no partial reads
modernc.org/sqlite	pure Go, keeps cross-compilation working, real queries	large generated package, slower than cgo
mattn/go-sqlite3	fastest	cgo — breaks simple cross-compilation, needs a C toolchain

Recommendation: start with the plain index file. It fully delivers the incremental-rescan win at the scale this tool operates at. SQLite earns its place only if we also want the streaming GROUP BY described below, or concurrent access later. mattn/go-sqlite3 should be avoided regardless, given the go install distribution story.

Bounding memory (separate, cheaper work)

Worth doing regardless of the cache, and mostly without a database:

1. Process one size-group at a time and discard it. Bounds checksum memory to the largest group rather than the whole tree. Zero dependencies, small change on top of the two-pass structure from Performance: every file is fully hashed, even when its size is unique #12.
2. Spill the stat pass to disk. Path strings dominate, and pass 1 currently holds them all. This is the one place a real database helps: insert (path, size), then SELECT ... GROUP BY size HAVING COUNT(*) > 1 and stream results, making memory O(1). Only worth it if Add recursive scanning (-r), plus --version, --min-size, --exclude #14 makes million-file scans routine.

Proposed scope

• ~/.cache/dedup/index (respecting XDG_CACHE_HOME), created on first run.
• --no-cache to bypass, --clear-cache to reset.
• Report cache effectiveness in the JSON summary — files_hashed vs cache_hits — building on the counters Performance: every file is fully hashed, even when its size is unique #12 added.
• Bound the cache: evict entries whose paths no longer exist, and cap total entries.

Tests to write first

• Second scan of an unchanged directory hashes zero files and returns results identical to the first.
• Touching a file's contents invalidates only that entry.
• Renaming a file keeps its entry (identity is device+inode, not path).
• A file whose size changes is re-hashed.
• Two hard links to one inode share a single entry.
• --no-cache hashes everything and leaves the cache untouched.
• A corrupt or truncated cache file is discarded and rebuilt, never fatal.

Order

Depends on #12 (PR #20) for the two-pass structure and the hash counters. Complements #19 rather than replacing it: #19 stops the first download, this stops every subsequent one.