Phase 9 measurements

This report covers phase 9 of the version 1 plan in architecture.md: tracing overhead and cache-check time on real projects, discovery time on large trees, cache cleanup on a large cache, and the decision on a tracer fast path. It ends with the defect the measurements found and fixed, and the follow-up work.

Summary

Environment

Measured projects

ProjectSource repositoryCommitCopies
tree-sitter-cddl/repo/tree-sitter-cddl, branch main3c19b3fdf95f6582ab6c01d9881394f1b04ea427$ROOT/measure/ts-*
dntls-tunnel (Go)/repo/DNTLS/dntls-tunnel, branch main3a50e2e8aa84d9d57460545959c4c6a57055c5d0$ROOT/measure/go-*
cosmos-sdk (discovery only)/repo/DNTLS/cosmos-sdk2086680ff8b08fd269ee653e087ea577bab79534$ROOT/discovery/cosmos-sdk

Every copy is the committed tree of the repository's HEAD, written into a new temporary directory with git archive, so the original repositories were only read. git status --porcelain=v1 was empty in each of them before and after the measurements. The Go module dntls-tunnel has 256 Go files and external dependencies such as quic-go, and go build ./... compiles all of them. The tree-sitter-cddl repository has two builds: make compiles the C parser into a library, and cargo build --offline builds the Rust binding, which compiles the same parser through the cc crate.

Task files

The kizz.md files exist only in the copies. The tree-sitter-cddl copies used this one:

# tree-sitter-cddl

## Build the C library

```starlark build
env.inherit("PATH")
run("make", expect = [0])
```

## Build the Rust binding

```starlark rust
env.inherit("PATH", "HOME")
run("cargo", "build", "--offline", expect = [0])
```

## Build the C library, timed inside the trace

```starlark build-timed
env.inherit("PATH")
run("bash", "-c", "TIMEFORMAT='inner %R %U %S'; time make", expect = [0], stream = True)
```

## Build the Rust binding, timed inside the trace

```starlark rust-timed
env.inherit("PATH", "HOME")
run("bash", "-c", "TIMEFORMAT='inner %R %U %S'; time cargo build --offline", expect = [0], stream = True)
```

The dntls-tunnel copies used this one, with MEASURE_GOCACHE naming a fresh Go build cache under $ROOT:

# dntls-tunnel

## Build every package

```starlark build
env.inherit("PATH", "HOME")
env.set("GOCACHE", env.caller("MEASURE_GOCACHE"))
env.set("GOPROXY", "off")
env.set("GOTOOLCHAIN", "local")
run("go", "build", "./...", expect = [0])
```

## Build every package, timed inside the trace

```starlark build-timed
env.inherit("PATH", "HOME")
env.set("GOCACHE", env.caller("MEASURE_GOCACHE"))
env.set("GOPROXY", "off")
env.set("GOTOOLCHAIN", "local")
run("bash", "-c", "TIMEFORMAT='inner %R %U %S'; time go build ./...", expect = [0], stream = True)
```

The fixed cost of kizz was measured with a task that runs only true:

# No-op

## Run `true`

```starlark noop
env.inherit("PATH")
run("true", expect = [0])
```

Commands

The scripts under $ROOT ran every measurement; these are their commands, with $PATH and $HOME the caller's values. $KIZZ is /repo/worktrees/kizz/core-builder-v1/target/release/kizz.

A copy of a repository:

mkdir -p "$COPY" && git -C "$REPO" archive --format=tar HEAD | tar -x -C "$COPY"

Every timed command ran as { time COMMAND >LOG 2>&1; } 2>TIMES with TIMEFORMAT='%R %U %S'. Every traced run started kizz in the copy with only these variables:

cd "$COPY" && env -i PATH="$PATH" HOME="$HOME" KIZZ_CACHE_DIR="$CACHE" MEASURE_GOCACHE="$GOCACHE" \
    "$KIZZ" --no-banner build TARGET

Cold traced runs used a fresh copy and a fresh $CACHE each; the cache checks ran the same command again. For a check after a change of metadata only, every committed file of the copy was touched, three seconds passed, and the check ran twice:

(cd "$COPY" && git -C "$REPO" ls-files -z | xargs -0 touch) && sleep 3

kizz cache clean ran once after the checks, in the copy, to count the recorded paths.

The scripts, all under $ROOT, are:

Their raw results are in measure.tsv, discovery.tsv, cleanup.tsv, and diag.tsv, with one log per run under logs.

Untraced baselines

The user allowed the project's own build commands to run directly, only inside the temporary copies, and only for the untraced baseline. These are all the commands run under that permission, each in its own copy:

LabelCopyCommand
trial-ts-baseline$ROOT/trial/ts-baseenv -i PATH="$PATH" make
trial-go-baseline-cold$ROOT/trial/go-baseenv -i PATH="$PATH" HOME="$HOME" GOCACHE=$ROOT/trial/gocache-base GOPROXY=off GOTOOLCHAIN=local go build ./...
trial-rust-baseline$ROOT/trial2/ts-baseenv -i PATH="$PATH" HOME="$HOME" cargo build --offline
ts-make-baseline-N, N = 1 to 5$ROOT/measure/ts-make-base-Nenv -i PATH="$PATH" make
ts-cargo-baseline-N, N = 1 to 5$ROOT/measure/ts-cargo-base-Nenv -i PATH="$PATH" HOME="$HOME" cargo build --offline
go-cold-baseline-N, N = 1 to 3$ROOT/measure/go-base-Nenv -i PATH="$PATH" HOME="$HOME" GOCACHE=$ROOT/measure/gocache-base-N GOPROXY=off GOTOOLCHAIN=local go build ./...
go-warm-baseline-N, N = 1 to 5$ROOT/measure/go-base-3env -i PATH="$PATH" HOME="$HOME" GOCACHE=$ROOT/measure/gocache-base-3 GOPROXY=off GOTOOLCHAIN=local go build ./...

The three trial runs checked that each build completes before the measured runs; their times are not used. $ROOT/q2-commands.log lists the same 21 runs with their start times and full commands. No other command ran a build tool by hand; the traced builds ran through kizz build.

Tracing overhead

The inner time is the build command's own time inside the trace, from the -timed tasks, so the difference from the baseline is what tracing costs the command, and the difference from the kizz build total is what kizz adds around it: starting, evaluating the task, recording the state of every touched path, and the confirming pass.

BuildUntracedTraced, insideCommand slowdownkizz build totalTotal slowdown
true---0.017-
make, tree-sitter-cddl0.0570.071+25% (+0.014)0.104+82% (+0.047)
cargo build --offline, tree-sitter-cddl0.5800.666+15% (+0.086)0.734+27% (+0.154)
go build ./..., cold Go build cache, 3 runs5.0865.872+15% (+0.786)6.018+18% (+0.932)
go build ./..., warm Go build cache0.0810.162+100% (+0.081)0.239+195% (+0.158)

Cache checks

A check is a kizz build of the same target again, every step a cache hit.

BuildRecorded pathsDatabaseCheckCheck after a change of metadata only
true--0.013-
make, tree-sitter-cddl16338 KiB0.0140.106, the command runs; then 0.014
cargo build --offline, tree-sitter-cddl1,069279 KiB0.0170.273, the command runs; then 0.019
go build ./...8,4851,515 KiB0.0430.265, the command runs; then 0.045
50,000 steps of cat, one input each50,10374 MiB9.010.6, every input hashed again, all cached; then 9.0

Discovery

kizz list ran in the root of each tree, and find ROOT -name kizz.md ran as a reference for a plain walk. The generated trees come from $ROOT/gen-tree.sh, which creates four empty files in every leaf directory and one kizz.md with one task in every second-level directory.

TreeDirectoriesFileskizz.md fileskizz listfind
generated, gen-tree.sh ROOT 10 10 10010,11140,1001000.0180.088
generated, gen-tree.sh ROOT 50 50 40102,551402,5002,5000.1450.864
cosmos-sdk copy9174,26310.0060.009

The parallel walk is six times faster than find on the large tree, and discovery needs no follow-up work.

Cache cleanup on a large cache

Step 14 asked for this measurement, because kizz cache clean and kizz cache reset hold every step record in memory. $ROOT/cleanup.sh 50 1000 large built 50 projects of one task each, every task running cat data/N.txt for N from 0 to 999, into one cache of 50,000 step records and 74 MiB.

CommandTime
kizz build fill, filling the cache: 50,000 traced commands164.4
kizz cache clean, nothing gone, 50,103 recorded paths, 3 runs0.612
kizz cache clean after deleting 25 projects: 25,000 step records removed0.806
kizz cache clean again, 25,053 paths, nothing gone0.292
kizz cache reset --yes in one project: 1,000 step records0.164
kizz cache reset --all --yes: 24,000 step records0.028

Holding the records in memory is not a problem at this size. Filling took 3.3 milliseconds per traced cat, against 2.1 milliseconds per step for 10,000 steps in an empty cache, which suggests that the cost of a step grows with the size of the cache (follow-up item 2).

The fast-path decision

Decision: the tracer gets no fast path in version 1.

Defect fixed in this phase

A traced cargo build --offline was never cached: every following build ran it again, because "/dev/fd/3 changed (content changed)" and "/dev/fd/5: link target changed". The command had read and written its inherited descriptors through /dev/fd, which is a link to /proc/self/fd. Kizz recorded and checked those paths in its own process, so it compared its own descriptors, which differ on every run, instead of treating them as the /proc accesses they are.

The fix, in crates/kizz-core/src/observe.rs, follows the spec's symbolic-link rule, "the link target, plus the state of what it points to", for links that lead into /proc or /sys, such as /dev/fd and /dev/stdin. Only the final object under /proc or /sys is untracked and never compared, as the spec says for /proc and /sys: /dev/fd/3 is recorded as untracked, and /dev/stdin as a link with its target and an untracked pointee. Every link on the way stays an ordinary dependency, compared by its target like any link: a directory link such as /dev/fd is recorded as a probed link with its target and an untracked pointee. Retargeting, removing, or replacing such a link runs the step again. The regression tests are:

With the fix, the second build of the Rust binding is a cache hit, and kizz why lists /dev/fd/3 and /dev/fd/5 among the step's untracked accesses. All the numbers in this report come from the first form of the fix, which recorded such paths and their links as untracked, except the evidence of the defect itself. The final form adds one link observation for /dev/fd, whose target does not change, so the hits stay hits; its cost, one more recorded path per step that uses /dev/fd, was not measured again.

Follow-up work

  1. Cache checks and recording of small steps: the per-step parallel comparison uses 30 times the CPU time of a sequential one and is slower. Compare a step's few paths sequentially, or check several steps' paths in one parallel batch, and measure again with the 50,000-step cache.
  2. Recording cost grows with the cache: 2.1 milliseconds per traced cat for 10,000 steps, 3.3 for 50,000. Profile the per-step database work, such as the last-writer and step-position updates.
  3. Last-writer entries for temporary files: one build leaves entries for paths that were gone when it ended, 30 for make, 666 for cargo, and 1,188 for go build, which only kizz cache clean removes. Consider not storing a last-writer entry for a path that is absent when the step is recorded.
  4. The spec's "/proc and /sys" section should say how paths that symbolic links lead into them, such as /dev/fd/N, are recorded, as this phase implemented: the links stay dependencies, and only the object they reach is untracked. The kizz why line "untracked /proc and /sys accesses" now also lists such objects, and its wording could say so.
  5. User documentation: Go tasks should ignore ~/.config/go/telemetry/**, since every go command on the machine changes those counters, and kizz adds no exceptions of its own.
  6. Metadata-only changes, such as a git checkout or touch that keeps the content, re-run commands that only checked the metadata of their inputs, as make and go do. That follows the spec; any change to it is a decision for the user.
  7. The tracer fast path, under the condition in The fast-path decision.