Cutting file comparison from 44s to 59ms

The problem

StudySmart AI lets students upload course material into a group. Two questions have to be answered on every upload: is this a near-duplicate of something already here, and which existing documents does it overlap with most? Both are the same underlying operation - score one document against every other document in the group and return the top matches.

Exact hashing does not answer it. Two students uploading the same lecture notes will have different bytes: different exports, different page breaks, a name typed at the top. The comparison has to be about content overlap, not byte equality, which means every candidate pair needs a real similarity score.

Why TF-IDF and cosine similarity

The engine represents each document as a TF-IDF vector over word unigrams and bigrams, then scores pairs by cosine similarity. That choice is worth justifying, because it is not the fanciest option available.

Term frequency alone rewards common words, so every pair of English documents looks similar. Inverse document frequency corrects for that: a term that appears in every file in the group carries almost no weight, while a term that appears in three files is highly discriminating. For study material this lands exactly where you want it - shared subject vocabulary gets discounted, and the specific phrasing of a specific set of notes is what drives the score.

Embeddings would capture meaning rather than wording, but they need a model, a GPU budget or an API bill, and they turn an offline library into a service dependency. Near-duplicate detection is a lexical problem. TF-IDF answers it with linear algebra and no network calls, which is the right trade for this feature.

Two details in the vectorizer configuration matter. The engine uses sublinear_tf=True, so a term repeated forty times counts as 1 + log(40) rather than 40 - one heading repeated on every page cannot dominate the vector. And ngram_range=(1, 2) keeps adjacent word pairs, so documents that share vocabulary but not phrasing score lower than documents that share actual sentences.

What was actually slow

The first implementation is the one everyone writes: loop over the base files, compare the uploaded file to each one, collect the scores.

# The obvious version. Correct, and quadratic in the wrong place.
scores = [compare_files(upload, base) for base in group_files]

The cost is hidden inside compare_files. Every call constructs a fresh TfidfVectorizer and fits it on exactly two documents. Fitting means building a vocabulary, computing document frequencies, and allocating a sparse matrix - and it is all thrown away before the next iteration. Against a thousand files that is a thousand vocabulary builds to answer one question.

There is a correctness problem too. IDF computed over two documents is meaningless, because every term appears in either one or both of them. The naive loop is not just slow, it is scoring against a degenerate corpus. Fitting across the whole group fixes the number and the speed at once.

The measurements

Synthetic study notes, roughly 900 words each with realistic vocabulary overlap, on Python 3.10 with scikit-learn 1.7.2. Each figure is the median of repeated runs. The task is always the same: one new upload scored against the whole group, top ten returned.

The prebuilt index answers in 59 milliseconds what the naive loop takes 44 seconds to answer - a factor of 744. The middle bar is worth noting on its own: simply hoisting the vectorizer fit out of the loop, with no index and no cache, is already a 9x improvement. Most of the naive version's cost was never the mathematics. It was rebuilding the same vocabulary a thousand times.

Query time against the index grows close to linearly with corpus size, which is what a single sparse matrix-vector product should do. Twenty times the files costs eight times the query. At a thousand documents the operation is still comfortably inside a request.

Where the time goes

Write n for the number of files in a group, L for the average document length in tokens, and k for the average number of distinct terms per document.

The asymptotic difference between the naive loop and the single fit is not dramatic on paper - both are O(n · L). The 9x gap is constant factors, which is a useful reminder that big-O is a screening tool, not a verdict. The real structural win is moving the O(n · L) work out of the request path entirely, which is what the index does.

Decision one: build the index once

FileIndex is immutable. It holds the fitted vectorizer and the document-term matrix, and it is built once for a group.

class FileIndex:
    """Immutable TF-IDF index. Build once, query many times.
    Each query is a single sparse matrix-vector multiply."""

    @classmethod
    def build(cls, base_files, cache=None, max_workers=8, ...):
        texts = [None] * len(paths)

        def _load(idx, path):
            _, text = _read_cached(path, cache)
            return idx, text

        with ThreadPoolExecutor(max_workers=max_workers) as pool:
            futures = {pool.submit(_load, i, p): i for i, p in enumerate(paths)}
            for future in as_completed(futures):
                idx, text = future.result()
                texts[idx] = text      # written back by index, order preserved

        vectorizer = TfidfVectorizer(**vkw)
        matrix = vectorizer.fit_transform(texts)

Reading is I/O bound, so it runs across a thread pool. The detail that keeps this correct is texts[idx] = text: as_completed yields futures in whatever order they finish, so results are written back by index rather than appended. Document order has to match paths order, because that correspondence is how a score gets mapped back to a filename later.

Querying is then almost nothing:

def _score(self, cleaned, label, top_n, threshold, sort):
    query_vec = self._vectorizer.transform([cleaned])
    scores = cosine_similarity(query_vec, self._matrix)[0]

    matches = [
        FileMatch(file=path, percentage=_pct(score))
        for path, score in zip(self.paths, scores)
        if _pct(score) >= threshold
    ]

Note transform, not fit_transform. The vocabulary and the IDF weights are already fixed, so the query document is projected into the existing vector space rather than redefining it. That is the whole trick: one sparse matrix-vector product instead of n vocabulary builds. It is also what makes scores comparable across queries, since every document is measured against the same basis.

Decision two: cache by content, not by path

Reading and normalising a file is pure waste when the file has not changed. The cache is keyed on the SHA-256 of the file's bytes rather than its path or mtime.

def _read_cached(path, cache):
    file_hash = VectorCache.hash_file(path)
    if cache:
        hit = cache.get(file_hash)
        if hit is not None:
            return file_hash, hit
    cleaned = _clean(path.read_text(encoding="utf-8", errors="ignore"))
    if cache:
        cache.set(file_hash, cleaned)
    return file_hash, cleaned

Content addressing buys two properties that a path-keyed cache cannot. The same document uploaded by thirty students under thirty filenames is processed once, because all thirty hash identically. And a file whose contents change gets a different hash, so it misses and reprocesses - no invalidation logic to get wrong, no stale entry surviving a mtime that did not move.

In the benchmark a warm cache cut index rebuild time from 6.57 s to 4.33 s at a thousand files, about a third. The remaining time is the vectorizer fit, which cannot be cached because it depends on the whole corpus.

The storage is SQLite with WAL enabled, one connection guarded by a lock. That last part came from a bug worth recording, and the comment in the source says so plainly:

# One connection guarded by a lock, NOT one per thread. FileIndex.build reads
# through a ThreadPoolExecutor, and a thread-local connection cannot be closed
# from the thread calling close() - that leaked handles and made the index
# directory undeletable on Windows (WinError 32).

The obvious fix for SQLite's threading rules is a connection per thread. It is also the one that breaks cleanup, because pool threads are gone by the time anyone calls close(). A single locked connection is the boring choice and the correct one here: these are sub-millisecond primary-key lookups, so lock contention never becomes the bottleneck.

Decision three: two tiers, so uploads stay cheap

A prebuilt index solves reads and creates a write problem. Adding one file to a TF-IDF index means refitting it, because the new document changes document frequencies for every term it contains. Rebuilding a thousand-document index on every upload puts the O(n · L) cost straight back into the request.

DynamicFileIndex splits the difference. New files land in a pending buffer, and the expensive rebuild happens once every m additions.

def add_files(self, paths, force_merge=False):
    self._pending.extend(str(p) for p in paths)
    merged = False
    if force_merge or len(self._pending) >= self.merge_threshold:
        self._merge()
        merged = True
    return merged

An upload is an append: O(1). With the default threshold of 50, the rebuild cost is amortized across fifty uploads. Queries stay correct in between because they run against both tiers and merge the results:

if self._index is not None:
    result = self._index.query(main_file, cache=self.cache,
                               threshold=threshold, sort=False)
    all_matches.extend(result.compare)

if self._pending:
    buf_result = compare_one_to_many(main_file, self._pending,
                                     cache=self.cache,
                                     threshold=threshold, sort=False)
    all_matches.extend(buf_result.compare)

if sort:
    all_matches.sort(key=lambda m: m.percentage, reverse=True)

Both tiers are queried with sort=False and sorted once at the end. Sorting each tier separately then merging would be wasted work, and applying top_n per tier would silently drop a strong match that happened to live in the smaller buffer.

The buffer is scored with the one-shot function, not the index, and that is the deliberate cost of this design: those files are scored against a vocabulary built from the buffer alone, not the full group. Scores for recent uploads are slightly less well calibrated than scores for merged ones. The threshold is the dial - lower it for score consistency, raise it for cheaper uploads.

Groups on top

StudySmart organises material into groups, so the engine does too. IndexRegistry keeps one DynamicFileIndex per named group, a JSON manifest of what exists, and - importantly - one shared cache across all of them.

# One cache for all groups - files in multiple groups only processed once
self._cache = VectorCache(self.base_dir / self.CACHE_FILE)

# In-memory loaded indexes (lazy-loaded on first access)
self._loaded: Dict[str, DynamicFileIndex] = {}

Groups load lazily on first access, so a process serving one group does not pay to deserialise the others. The shared cache is what makes the same syllabus uploaded into five different course groups cost one parse instead of five. In StudySmart the call site ends up small:

reg = IndexRegistry("/data/indexes")

result = reg.query(group, str(filepath), top_n=10)   # score before storing
reg.add_file(group, str(filepath))                   # then stage the upload

Query first, then add. Reversing those two lines makes every upload a guaranteed 100% match against itself.

What this does not do

Three limits are worth stating, because a library that only advertises its strengths is harder to use well.

It is lexical, not semantic. Two documents that teach the same concept in different words score low. That is correct for duplicate detection and wrong for topic discovery, which is a different feature needing different machinery.

A merge refits the vocabulary, so scores can shift slightly after a rebuild as document frequencies change. Similarity here is a property of a document against a corpus at a point in time, not an absolute constant, and any stored score should be treated accordingly.

Indexes persist through pickle, which is fast and convenient and means index files must be treated as trusted data. Loading a pickle from an untrusted source executes code. For a server writing and reading its own indexes this is fine; for anything user-supplied it is not.

Where it landed

The comparison work started as feature code inside StudySmart, and once the index, cache, and buffer had settled it was clearly a general library wearing application clothing. It became filemetric-engine: MIT licensed, dependency-light, 66 passing tests, no service to run.

The lesson that transfers is smaller than the numbers suggest. Nothing here is a clever algorithm. The naive version recomputed a fixed thing on every request, so the fix was to compute it once, key the cache on what actually determines the answer, and batch the writes that would otherwise force a recompute. Measure first, and the expensive line is usually the one nobody looked at.