A Concurrent Duplicate Finder

Problem

Not every part of this task benefits from concurrency, and deciding which part does is the actual design work here. Listing a directory's contents is fast and sequential by nature; there is nothing to parallelize about walking a tree structure, and trying to would only add complexity. Reading every file's bytes is the opposite: independent, I/O-bound work, one unit per file, with no ordering dependency between any two reads. Grouping the results by content afterward is fast, in-memory comparison, back to sequential, because there is no I/O left to overlap.

So the shape of the solution follows directly from where the actual waiting happens: walk sequentially, read concurrently, group sequentially. Getting this division right matters more than any amount of general enthusiasm for making things concurrent: the walk and the grouping would not go any faster for being parallelized, and would be harder to reason about for the trouble.

Design as Contract

The three phases become three methods on one class, each with a focused job:

class Dup_Finder
create
  make() do end
feature
  collect_files(dir: Directory): Array[Path] do ... end
  read_all_concurrently(files: Array[Path]): Array[File_Content] do ... end
  find_duplicates(root_dir: String): Map[String, Array[String]] do ... end

A small aside on why these are methods on a class at all, rather than three loose top-level functions in a file with no class in it, the more natural shape for what is, in effect, a small pipeline. Nex's intern <Name> requires a top-level declaration literally named <Name> in the file it loads; a functions-only module cannot be interned by a name that does not also label something declared in the file. dup_finder.nex originally held a File_Content class and three loose functions, and intern Dup_Finder failed outright: nothing in the file was named Dup_Finder. Wrapping the pipeline as methods on a real Dup_Finder class fixed the mechanical problem and reads better besides — collect_files, read_all_concurrently, and find_duplicates read as one coherent object's behavior rather than three functions that happen to share a file.

File_Content is the smallest possible result type for the concurrent step — a path and the text read from it, nothing else — which matters because it is what has to travel back across the fan-in:

class File_Content
create
  make(path: String, content: String) do
    this.path := path
    this.content := content
  end
feature
  path: String
  content: String
end

Build

The walk is ordinary recursion, no concurrency involved, exactly as designed:

collect_files(dir: Directory): Array[Path] do
  result := []
  let fs: Array[Path] := dir.files()
  ... -- append this directory's files
  let subdirs: Array[Directory] := dir.directories()
  ... -- recurse into each, appending what comes back
end

The fan-out happens in read_all_concurrently: one Task spawned per file, each doing exactly one blocking read, with every task started before any of them is waited on:

read_all_concurrently(files: Array[Path]): Array[File_Content] do
  let tasks: Array[Task[File_Content]] := []
  let i: Integer := 0
  from
    i := 0
  until
    i = files.length
  do
    let f: Path := files.get(i)
    let t: Task[File_Content] := spawn do
      result := create File_Content.make(f.to_string(), f.read_text())
    end
    tasks.add(t)
    i := i + 1
  end
  result := await_all(tasks)
end

The loop that spawns tasks and the point where it waits for them are two separate moments: every task is already running by the time await_all is reached, which is the entire mechanism behind fan-out/fan-in. The concurrency comes from starting all the work before waiting on any of it, not from anything more exotic. Grouping is back to plain sequential code, a Map keyed by file content, filtered to groups with more than one member — no file is a duplicate of nothing:

if paths.length > 1 then
  result.set(k, paths)
end

One thing this project's actual code path does not do, worth being precise about rather than implying otherwise: find_duplicates's await_all waits for every read unconditionally. There is no timeout and no cancel token anywhere in the pipeline above — a real duplicate scan over a huge tree has no way, today, to give up early on in-flight reads. cancellation_demo.nex is a small, separate, self-contained illustration of the mechanism a cancel-aware version would need — Task.await(ms) returning nil on timeout, then Task.cancel() — standing in for a feature this project's scanner does not actually have, not a workaround for one it does:

let slow: Task[Integer] := spawn do
  sleep(2000)
  result := 42
end

let v: ?Integer := slow.await(200)
if v = nil then
  print("timed out waiting; cancelling")
  let cancelled: Boolean := slow.cancel()
  ...
end

Keeping that distinction explicit (here is the mechanism, and separately, here is whether this project's own code actually uses it) matters more than quietly implying find_duplicates is cancel-aware when it is not.

Test

Testing concurrent code well means asserting on the outcome, never on timing or interleaving — nothing in this check suite cares which of several spawned tasks happens to finish first, only that all of them finish and the grouping that results is correct. The check builds a small, disposable directory tree under a temp folder — three files sharing one piece of text, two more each unique — and confirms exactly one duplicate group is found, with exactly the right members:

root.child_path("a.txt").write_text("hello world")
root.child_path("b.txt").write_text("hello world")
sub.child_path("c.txt").write_text("hello world")
root.child_path("unique.txt").write_text("nothing else looks like this")
sub.child_path("d.txt").write_text("also unique")

let dups: Map[String, Array[String]] := finder.find_duplicates(base)
c.check("one duplicate group", "1", "" + dups.size())

let keys: Array[String] := dups.keys()
let members: Array[String] := dups.get(keys.get(0))
c.check("group has 3 members", "3", "" + members.length)

Four checks, and the tree is deleted immediately afterward, with the deletion itself checked. A concurrent test that leaves scratch files behind on the filesystem is a test that will eventually collide with itself on a second run.

Takeaways

Concurrency belongs exactly where the waiting happens, and nowhere else. A directory walk and an in-memory grouping step gain nothing from being parallelized — there's no I/O to overlap — while independent, I/O-bound reads gain everything from running at once; deciding which is which, before writing any concurrent code, is the actual design work. And a concurrent test should assert on the outcome alone, never on timing or interleaving, so that which spawned task happens to finish first is simply not a fact the test needs to know.

The same fan-out shape, one task per unit of concurrent work, carries into Chapter 6, except the files on a local disk become sockets to clients who can misbehave, disconnect, or simply take their time.