#!/usr/bin/env python3 """Reproduce a warm-cache Linux filesystem scan comparison. Creates deterministic, generated developer-shaped trees on the filesystem hosting --workdir, then benchmarks fresh processes. This script only removes fixture directories when --regenerate is explicitly passed. The tree contains no personal files. Read README-benchmark.txt before interpreting results. """ import argparse import hashlib import json import os from pathlib import Path import platform import random import re import shutil import subprocess import sys import time import statistics SEED = 20261019 TOOLS = ("leita", "fd", "fd_stat", "find", "ncdu") EXTS = ("go", "rs", "ts", "py", "md", "json", "h", "c") DATA = (b"", b"x" * 32, b"x" * 256, b"x" * 4096) def sha256(path): h = hashlib.sha256() with open(path, "rb") as stream: for chunk in iter(lambda: stream.read(1024 * 1024), b""): h.update(chunk) return h.hexdigest() def iter_fixture_files(root, files): rng = random.Random(SEED + files) groups = (("src", files * 60 // 100), ("vendor", files * 30 // 100)) groups += (("docs", files - sum(n for _, n in groups)),) for group, count in groups: for offset in range(count): bucket, within = divmod(offset, 100) if group == "src": directory = root / "src" / f"project{bucket // 100:02d}" / f"pkg{bucket % 100:03d}" elif group == "vendor": directory = root / "vendor" / f"module{bucket:04d}" / "lib" else: directory = root / "docs" / f"section{bucket // 100:02d}" / f"part{bucket % 100:03d}" ext = EXTS[rng.randrange(len(EXTS))] name = f"f{within:03d}.{ext}" if within == 0 and bucket % 7 == 0: name = f".hidden{bucket:04d}.{ext}" yield directory / name, DATA[rng.randrange(len(DATA))] def expected_directory_count(files): src, vendor = files * 60 // 100, files * 30 // 100 docs = files - src - vendor ceil = lambda n, k: (n + k - 1) // k return 1 + 4 + ceil(src, 10000) + ceil(src, 100) + 2 * ceil(vendor, 100) + ceil(docs, 10000) + ceil(docs, 100) def verify_tree(root, files): marker = root / ".benchmark-fixture.json" if not marker.is_file() or json.loads(marker.read_text()) != {"files": files, "seed": SEED, "generator": 1}: raise RuntimeError(f"fixture marker mismatch: {root}") if (root / ".gitignore").read_text() != "vendor/\n*.log\n": raise RuntimeError(f"fixture ignore file mismatch: {root}") for path, expected in iter_fixture_files(root, files): if not path.is_file() or path.read_bytes() != expected: raise RuntimeError(f"fixture file mismatch: {path}") for i in range(400): link = root / "links" / f"link{i:03d}" if not link.is_symlink() or os.readlink(link) != f"../src/project00/pkg{i % 100:03d}": raise RuntimeError(f"fixture symlink mismatch: {link}") types = subprocess.run(["find", str(root), "-xdev", "-printf", "%y"], check=True, stdout=subprocess.PIPE).stdout expected = {ord("f"): files + 2, ord("l"): 400, ord("d"): expected_directory_count(files)} if {kind: types.count(kind) for kind in expected} != expected or len(types) != sum(expected.values()): raise RuntimeError(f"fixture entry types/count mismatch: {root}") def make_tree(root, files, regenerate): marker = root / ".benchmark-fixture.json" if root.exists(): if marker.is_file() and not regenerate: return if not regenerate: raise RuntimeError(f"{root} exists; pass --regenerate to replace this fixture") if not marker.is_file(): raise RuntimeError(f"refusing to remove unmarked directory: {root}") shutil.rmtree(root) root.mkdir(parents=True) made = 0 previous = None for path, data in iter_fixture_files(root, files): if path.parent != previous: path.parent.mkdir(parents=True, exist_ok=True) previous = path.parent with open(path, "wb") as stream: stream.write(data) made += 1 if made % 50000 == 0: print(f"created {made}/{files} files in {root.name}", flush=True) links = root / "links" links.mkdir() for i in range(400): (links / f"link{i:03d}").symlink_to(f"../src/project00/pkg{i % 100:03d}") (root / ".gitignore").write_text("vendor/\n*.log\n") marker.write_text(json.dumps({"files": files, "seed": SEED, "generator": 1}) + "\n") def count_paths(command): process = subprocess.Popen(command, stdout=subprocess.PIPE, stderr=subprocess.PIPE) total = 0 while chunk := process.stdout.read(1024 * 1024): total += chunk.count(b"\0") err = process.stderr.read().decode(errors="replace") if process.wait(): raise RuntimeError(f"count failed: {command}: {err}") return total def fingerprint_paths(command): done = subprocess.run(command, stdout=subprocess.PIPE, stderr=subprocess.PIPE, check=True) if done.stderr: raise RuntimeError(f"path listing emitted stderr: {command}: {done.stderr[:500]!r}") paths = done.stdout.split(b"\0") if paths[-1] != b"": raise RuntimeError(f"path listing is not NUL terminated: {command}") paths.pop() paths.sort() digest = hashlib.sha256(b"\0".join(paths)).hexdigest() return len(paths), digest def build_commands(tree, leita, fd, ncdu): return { "leita": [leita, "--no-history", "--whole", "--color", "never", str(tree)], "fd": [fd, "-HI", "--one-file-system", "-0", ".", str(tree)], "fd_stat": [fd, "-HI", "--one-file-system", "--changed-before", "2100-01-01", "-0", ".", str(tree)], "find": ["find", str(tree), "-xdev", "-mindepth", "1", "-print0"], "ncdu": [ncdu, "-0", "--ignore-config", "-x", "-o", "/dev/null", str(tree)], } def run_once(command, env, stderr_path, rss_path, timer): rss_path.unlink(missing_ok=True) with open(stderr_path, "wb") as err, open(os.devnull, "wb") as out: started = time.perf_counter_ns() process = subprocess.Popen([timer, "-f", "%M", "-o", str(rss_path), "--", *command], stdout=out, stderr=err, env=env) returncode = process.wait() ended = time.perf_counter_ns() if returncode: raise RuntimeError(f"command exited {returncode}: {command}; see {stderr_path}") stderr = stderr_path.read_bytes() # Allow only this exact control sequence from a command named ncdu. if stderr and not (Path(command[0]).name == "ncdu" and stderr == b"\x1b[J"): raise RuntimeError(f"command emitted stderr: {command}; see {stderr_path}") rss_kib = int(rss_path.read_text().strip()) stderr_path.unlink() rss_path.unlink() return {"elapsed_ns": ended - started, "max_rss_kib": rss_kib} def version(command): done = subprocess.run(command, text=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, check=True) return done.stdout.strip().splitlines()[0] def preflight_accounting(tree, cmd, env, reference, ncdu_export): leita = subprocess.run(cmd["leita"], text=True, stdout=subprocess.PIPE, stderr=subprocess.PIPE, env=env, check=True) used = re.search(r"tree\s+\d+ slots, (\d+) used", leita.stdout) if not used or int(used.group(1)) != reference: raise RuntimeError(f"Leita used count differs from {reference}: {leita.stdout[:500]}") subprocess.run([*cmd["ncdu"][:-2], str(ncdu_export), str(tree)], stdout=subprocess.DEVNULL, stderr=subprocess.PIPE, env=env, check=True) export = json.loads(ncdu_export.read_text()) if not isinstance(export, list) or len(export) < 4: raise RuntimeError("ncdu export has unexpected top-level structure") def count_records(node): if isinstance(node, dict): return int("name" in node) if isinstance(node, list): return sum(count_records(child) for child in node) return 0 named = count_records(export[3]) ncdu_export.unlink() if named != reference + 1: raise RuntimeError(f"ncdu exported {named} names incl root, expected {reference + 1}") return int(used.group(1)), named def main(): p = argparse.ArgumentParser(description=__doc__) p.add_argument("--workdir", type=Path, required=True, help="persistent non-tmpfs directory; fixture and isolated Leita data live here") p.add_argument("--leita", type=Path, required=True, help="optimized CLI built from recorded source") p.add_argument("--fd", default=shutil.which("fd") or "fd") p.add_argument("--ncdu", default=shutil.which("ncdu") or "ncdu") p.add_argument("--time", default=shutil.which("gtime") or shutil.which("time") or "time", help="external GNU Time executable for target-process RSS") p.add_argument("--sizes", type=int, nargs="+", default=[200000, 400000]) p.add_argument("--warmups", type=int, default=2) p.add_argument("--runs", type=int, default=7) p.add_argument("--generate-only", action="store_true") p.add_argument("--measure-only", action="store_true") p.add_argument("--regenerate", action="store_true") p.add_argument("--output", type=Path, required=True) p.add_argument("--source-revision", default="unknown") p.add_argument("--jm-revision", default="unknown") p.add_argument("--build-command", default="unknown") p.add_argument("--build-kind", default="unspecified") p.add_argument("--ncdu-package", type=Path) args = p.parse_args() if platform.system() != "Linux" or args.warmups < 1 or args.runs < 3 or any(s < 100000 for s in args.sizes): p.error("requires Linux, >=1 warmup, >=3 runs, and >=100000 files per fixture") if args.generate_only and args.measure_only: p.error("--generate-only and --measure-only conflict") work = args.workdir.resolve() work.mkdir(parents=True, exist_ok=True) for size in args.sizes: root = work / f"tree-{size}" if not args.measure_only: make_tree(root, size, args.regenerate) verify_tree(root, size) if args.generate_only: return environment = os.environ.copy() for key in list(environment): if key.startswith("LEITA_"): environment.pop(key) environment["XDG_DATA_HOME"] = str(work / "isolated-data") environment["XDG_CONFIG_HOME"] = str(work / "isolated-config") environment["XDG_CACHE_HOME"] = str(work / "isolated-cache") fd = str(Path(args.fd).resolve()) ncdu = str(Path(args.ncdu).resolve()) leita = str(args.leita.resolve()) timer = str(Path(args.time).resolve()) result = { "schema": "leita-filesystem-benchmark/1", "date_utc": time.strftime("%Y-%m-%dT%H:%M:%SZ", time.gmtime()), "platform": platform.platform(), "cpu": next((line.split(":", 1)[1].strip() for line in Path("/proc/cpuinfo").read_text().splitlines() if line.startswith("model name")), "unknown"), "tools": {"leita": {"version": version([leita, "--version"]), "sha256": sha256(leita)}, "fd": {"version": version([fd, "--version"]), "sha256": sha256(fd)}, "find": {"version": version(["find", "--version"]), "sha256": sha256(shutil.which("find"))}, "ncdu": {"version": version([ncdu, "--version"]), "sha256": sha256(ncdu), "package_sha256": sha256(args.ncdu_package) if args.ncdu_package else None}, "time": {"version": version([timer, "--version"]), "sha256": sha256(timer)}}, "source": {"leita_revision": args.source_revision, "jm_revision": args.jm_revision, "odin_version": version(["odin", "version"]), "build_command": args.build_command, "build_kind": args.build_kind}, "protocol": {"seed": SEED, "filesystem": "recorded per fixture", "cache": "warm; no global cache drops", "warmups_per_tool": args.warmups, "measured_runs_per_tool": args.runs, "schedule": "each round shuffles five modes using seed+file count", "fd_stat": "native fd modification-time filter before 2100-01-01; forces metadata reads without excluding generated entries; exact sorted path set validated against fd names-only", "elapsed": "Python perf_counter_ns before Popen through wait return; includes fresh GNU Time wrapper startup, target process, and output", "peak_memory": "GNU Time %M target-process maximum RSS, KiB; summary is maximum across measured runs, displayed as decimal MB", "op": "one enumerated filesystem entry beneath fixture root, excluding root; all tools share this denominator but perform different work"}, "fixtures": [], "runs": [], "summary": []} errpath = work / "command-stderr.txt" rsspath = work / "command-rss.txt" for size in args.sizes: tree = work / f"tree-{size}" cmd = build_commands(tree, leita, fd, ncdu) reference = count_paths(["find", str(tree), "-xdev", "-mindepth", "1", "-print0"]) fd_count, fd_paths_sha = fingerprint_paths(cmd["fd"]) fd_stat_count, fd_stat_paths_sha = fingerprint_paths(cmd["fd_stat"]) if fd_count != reference or fd_stat_count != reference or fd_paths_sha != fd_stat_paths_sha: raise RuntimeError(f"fd coverage differs from find or between modes in {tree}: {fd_count}, {fd_stat_count}, {reference}") leita_used, ncdu_named = preflight_accounting(tree, cmd, environment, reference, work / "ncdu-preflight.json") filesystem = version(["findmnt", "-no", "FSTYPE,OPTIONS", "-T", str(tree)]) result["fixtures"].append({"files": size, "entries_excluding_root": reference, "fd_entries": fd_count, "fd_stat_entries": fd_stat_count, "fd_path_set_sha256": fd_paths_sha, "fd_stat_path_set_sha256": fd_stat_paths_sha, "leita_used": leita_used, "ncdu_named_including_root": ncdu_named, "filesystem_and_options": filesystem, "root_template": f"$WORKDIR/tree-{size}"}) rng = random.Random(SEED + size) for phase, nrounds in (("warmup", args.warmups), ("measured", args.runs)): for round_number in range(nrounds): order = list(TOOLS) rng.shuffle(order) for tool in order: sample = run_once(cmd[tool], environment, errpath, rsspath, timer) if phase == "measured": result["runs"].append({"files": size, "tool": tool, "round": round_number + 1, "schedule_index": len(result["runs"]), **sample}) for tool in TOOLS: samples = [r for r in result["runs"] if r["files"] == size and r["tool"] == tool] median = statistics.median(r["elapsed_ns"] for r in samples) result["summary"].append({"files": size, "entries": reference, "tool": tool, "median_total_ms": median / 1e6, "median_ns_per_entry": median / reference, "peak_rss_mb": max(r["max_rss_kib"] for r in samples) * 1024 / 1e6}) result["protocol"]["filesystem"] = "actual host mount and options recorded per fixture" result["build_commands"] = {name: [word.replace(str(tree), "$TREE").replace(leita, "$LEITA").replace(fd, "$FD").replace(ncdu, "$NCDU") for word in words] for name, words in cmd.items()} args.output.parent.mkdir(parents=True, exist_ok=True) args.output.write_text(json.dumps(result, indent=2) + "\n") print(f"completed {size} files / {reference} entries", flush=True) if __name__ == "__main__": main()