# cartog Benchmark Suite

Compares cartog graph queries vs grep/cat approaches for common code navigation tasks.

## Benchmark surfaces

One row per entry point — if you're lost, start here:

| Surface | Question it answers | Run with |
|---------|---------------------|----------|
| **Shell suite** (this file) | Is a single cartog query smaller / more complete than grep? | `make bench` |
| **Edge resolution** | What share of edges resolve, per language? (heuristic / host LSP / strict Docker LSP) | `make bench-resolution`, `make bench-resolution-docker` |
| **Resolution scaling** | Does resolution stay near-linear as the repo grows? (catches quadratic regressions, cf. #110) | `make bench-resolution-scale` |
| **Criterion micro-benchmarks** | How fast is cartog's own CPU work (µs–ms)? | `make bench-criterion` |
| **ONNX model benches** | How fast are the real embed/rerank models? | `make bench-onnx` |
| **RAG relevancy** | Does hybrid search rank the relevant symbols on top? | `make bench-rag` |
| **Agent-task** (`agent/`) | Does giving an agent cartog cut the *end-to-end* token cost of a task? | `make bench-agent` |
| **ContextBench** (`contextbench/`) | Does cartog retrieve the *right* context for real issues (vs human gold)? | [contextbench/README.md](contextbench/README.md) |
| **Skill / agent evals** | Do the cartog skill and agents behave as designed? (LLM-as-judge) | `make eval-skill`, `make eval-agents` |

The shell suite below is **per-query** (no LLM). The
[agent-task suite](agent/README.md) drives a real agent through whole tasks with
and without cartog — the end-to-end "does it actually help" claim. See
[docs/tech.md → Benchmarks](../docs/tech.md#benchmarks) for the full
test-and-benchmark matrix.

## What it measures

| Dimension | Metric | Method |
|-----------|--------|--------|
| Token efficiency | Output bytes / approx tokens | Compare output size of cartog vs grep/cat for identical questions |
| Accuracy | Recall against ground truth | Count expected items found by each approach |
| Command count | Tool calls needed | How many commands each approach requires |
| Query latency | Microseconds per query | Criterion benchmarks on indexed fixture (Rust-native) |

## Fixtures

| Fixture | Language | Files | LOC |
|---------|----------|-------|-----|
| `fixtures/webapp_py/` | Python | 69 | ~4,000 |
| `fixtures/webapp_ts/` | TypeScript | 49 | ~2,500 |
| `fixtures/webapp_go/` | Go | 45 | ~3,300 |
| `fixtures/webapp_rs/` | Rust | 65 | ~3,200 |
| `fixtures/webapp_rb/` | Ruby | 51 | ~2,300 |
| `fixtures/webapp_java/` | Java | 41 | ~1,800 |
| `fixtures/webapp_php/` | PHP | 25 | ~1,500 |
| `fixtures/webapp_dart/` | Dart | 9 | ~200 |
| `fixtures/webapp_swift/` | Swift | 16 | ~500 |
| `fixtures/webapp_kt/` | Kotlin | 17 | ~460 |
| **Total** | | **387** | **~19,760** |

All fixtures model the same domain (auth service, tokens, routes, middleware, database, cache, events, validators) with controlled, known relationships defined in `ground_truth/`.

The criterion `indexing` bench exercises all 13 fixtures (10 code-language webapps
+ the `webapp_{vue,svelte,astro}` SFC apps). The full 13-scenario shell suite and
`ground_truth/` cover the 10 code-language fixtures (minus `webapp_dart`, which has
no scenario ground truth yet). The three SFC fixtures are component apps, not the
shared backend graph, so their `ground_truth/` covers only the scenarios that fit
an SFC app (outline, callees, deps, search) — derived from real `cartog --json`
output and hand-verified.

## Scenarios

| # | Question | Key differentiator |
|---|----------|--------------------|
| 01 | "Who calls validate_token?" | `refs --kind calls` vs grep string match |
| 02 | "What's in auth/service?" | `outline` (structure only) vs `cat` (full file) |
| 03 | "Impact of renaming AuthService?" | `impact` (transitive BFS) vs grep (flat) |
| 04 | "Class hierarchy of BaseService?" | `hierarchy` (structured pairs) vs grep for class keywords |
| 05 | "Trace login -> DB call chain" | Sequential `callees` vs multiple grep rounds |
| 06 | "File dependencies?" | `deps` (resolved targets) vs grep for import keywords |
| 07 | "Type references to X?" | `refs --kind references` vs context-unaware grep |
| 08 | "Find all token-related symbols" | `search token` (ranked, deduplicated) vs grep (raw lines) |
| 09 | "Disambiguate 'validate' (4+ defs)" | `search validate` (distinct files) vs grep (wall of matches) |
| 10 | "High-fanout: who uses get_logger?" | `refs` (precise call sites) vs grep (every mention) |
| 11 | "Deep call chain (5+ hops)" | Sequential `callees` x6 vs 6 grep rounds with noise |
| 12 | "Deep impact at depth 5" | `impact --depth 5` (transitive BFS) vs flat grep |
| 13 | "Find authentication logic" | `rag search` (FTS5 + vector KNN + reranker) vs grep keywords |

## Index isolation

The fixtures live inside the cartog repo, so a bare `cartog index .` walks up and
writes to the repo-root `.cartog`, where every fixture would clobber the next and
recall would be measured against whichever fixture indexed last. `token_savings.sh`
and the scenarios pin `CARTOG_DB` to a per-fixture file under `benchmarks/.indexes/`
(gitignored) so each fixture stays isolated. Any new `cartog` invocation in a
scenario must do the same — use `fixture_db_path "$fixture_dir"` from `lib/common.sh`.

## Known cartog gaps

Some scenarios deliberately keep ground truth at the *objectively correct* answer
read from source, so cartog scores below 100% where its resolution is incomplete.
These rows exist to track that — they should approach parity as the gaps close:

- **Rust traits / Go interfaces (excluded from scenario 04)**: Rust uses traits and
  Go uses struct embedding, not class inheritance. cartog does not model
  trait-impl or interface-satisfaction as a hierarchy, so "who implements this
  contract?" is not answerable today. Those rows are skipped rather than scored 0.
- **Dart mixins**: `hierarchy AuthResult` (sealed class) resolves, but `refs`
  on a `mixin` (e.g. `TokenCache`) does not surface the `with`-ing classes.

## Usage

```bash
# Run all scenarios (01-13) across the code-language fixtures
./benchmarks/token_savings.sh

# Run single scenario
./benchmarks/token_savings.sh --scenario 01

# Run only one language fixture
./benchmarks/token_savings.sh --fixture py
./benchmarks/token_savings.sh --fixture ts
./benchmarks/token_savings.sh --fixture go
./benchmarks/token_savings.sh --fixture rs
./benchmarks/token_savings.sh --fixture rb
./benchmarks/token_savings.sh --fixture java
./benchmarks/token_savings.sh --fixture php
```

## Edge-resolution rate

`resolution_rate.sh` measures resolved / total edges per language (a different
axis from token savings: how completely the resolver links call/import/type
edges). Re-run after extractor or resolver changes.

```bash
./benchmarks/resolution_rate.sh                 # heuristic, all langs, save snapshot
./benchmarks/resolution_rate.sh --lsp           # add LSP pass (uses installed servers)
./benchmarks/resolution_rate.sh --fixture rs    # one language
./benchmarks/resolution_rate.sh --baseline      # diff vs last snapshot (no overwrite)
```

## Resolution scaling (quadratic-regression guard)

The rate fixtures are ~50 files each, so a *time-complexity* regression hides in
them — the tier-2 quadratic fixed in #110 only diverged at transformers scale.
`resolution_scale.sh` is the time-axis complement: it generates a synthetic
Python repo with heavy cross-file imports (so most edges resolve via tier-2, the
#110 hot path) at sizes N and 2N, times `cartog index --no-lsp --force` for each,
and asserts `time(2N)/time(N)` stays under a near-linear threshold. Linear
resolution doubles (~2x); quadratic quadruples (~4x). Self-calibrating — no
committed baseline, so it is machine-independent. Exit 1 on regression.

```bash
make bench-resolution-scale                      # default N=1000
N=2000 ./benchmarks/resolution_scale.sh          # larger N → clearer signal, slower
RATIO_MAX=2.5 ./benchmarks/resolution_scale.sh   # stricter threshold
```

Opt-in (not in `make check`): the large run is seconds-to-minutes depending on N.

> **History:** on first introduction this bench *failed* (ratio ~3.6 at N=1000),
> surfacing two O(n²) terms #110 had not closed: `compute_in_degrees` used a
> correlated subquery (re-scanned the counts set per row), and the per-file
> `DELETE FROM edges WHERE file_path=?` full-scanned the edge table (no
> `idx_edges_file`). Both were fixed (`UPDATE...FROM` + the index); the bench now
> passes at ~1.3 and guards against further regression. Before: 32k→1.45s,
> 64k→5.17s, 128k→19.8s. After: index of 2000 files dropped 5.17s→0.87s.

## Reproducing the numbers

Both result files now carry provenance so a published number can be traced back
to an exact build:

- `results/resolution_rate{,_lsp}.json` — top-level `cartog_version`, `git_sha`,
  `timestamp`, plus per-language `lsp_source` (`docker:<image>`, `host:<bin>`, or
  `none`).
- `results/latest.jsonl` — first line is a `{"_meta": {...}}` header with the
  same `cartog_version` / `git_sha` / `timestamp` (the summary loop skips it).

To reproduce:

1. Build the pinned commit: `cargo build --release` (the scripts prefer
   `target/release/cartog`; override with `CARTOG=/path/to/cartog`).
2. Run the script. Provenance is captured automatically.

**Host-independent LSP via Docker.** The plain `--lsp` numbers depend on which
servers happen to be installed (Go needs a toolchain, Ruby ≥3.2, jdtls a JDK,
sourcekit-lsp the Swift toolchain). `--docker-lsp` runs each server from a
pinned image instead, so the LSP numbers reproduce across machines:

Building the images and running the benchmark are two independent steps:

```bash
make lsp-images                 # 1. build the 10 cartog-lsp-<lang>:stable images
make bench-resolution-docker    # 2. run --lsp --docker-lsp (errors if an image is missing)
```

`benchmarks/lsp-images/<lang>.Dockerfile` holds one pinned recipe per language
(rust, python, typescript, go, ruby, java, php, dart, swift, kotlin). Under
`--docker-lsp` the script generates a `[lsp.<lang>]` Docker override (`docker run
-i -v ${ROOT}:${ROOT} -w ${ROOT} <image>`) and records `lsp_source=docker:<image>`.
It is **strict**: a missing `cartog-lsp-<lang>:stable` image is an explicit error
(no host fallback), so the numbers always reflect the containerized server — a
preflight check lists any unbuilt images and tells you to run `make lsp-images`.
Build a single image with, e.g., `docker build -t cartog-lsp-go:stable -f
benchmarks/lsp-images/go.Dockerfile benchmarks/lsp-images`. See the "LSP server
overrides" section in [docs/usage.md](../docs/usage.md) for how the override
works (path mirroring is mandatory). Per-image caveats (gopls deps,
jdtls/sourcekit startup time, ruby-lsp bundle compose) are noted in each
Dockerfile header.

All 10 containerized servers resolve **identically to host** (same `lsp`-tier
edge count). `python` and `typescript` use the upstream `lspcontainers` images
(pinned by digest); the other 8 self-build on a pinned official base. cartog
sends `processId: null` to a command-override server because its host PID is
absent from a container's PID namespace — without that, pyright and
typescript-language-server honor the LSP parent-liveness check and exit at
startup (they alone enforce it strictly).

## Criterion benchmarks (in-process latency)

Rust-native criterion benchmarks measure cartog's own CPU-bound work against the
`benchmarks/fixtures/` corpora indexed into in-memory SQLite. They are split into
four `[[bench]]` targets so the ONNX boundary is expressed by target membership
(see [docs/tech.md](../docs/tech.md#benchmarks) for the full rationale). Inputs and
results are wrapped in `black_box`, so the µs-scale benches measure real work.

```bash
# Everything ONNX-free (queries + per-language indexing + hybrid search)
make bench-criterion

# Real-model embed/rerank — needs `cartog rag setup`, not run in CI
make bench-onnx
```

### `queries` — query latency (`cartog`)

Microsecond-scale latency for `search`, `refs`, `impact`, `outline`, `callees`,
`hierarchy`, `deps`, `stats` on the Python and Java fixtures. Query latency is
language-agnostic (same SQL regardless of source language), so two fixtures suffice.

```bash
cargo bench -p cartog --bench queries
cargo bench -p cartog --bench queries -- search_token   # one bench (substring match)
```

### `indexing` — per-language indexing (`cartog-indexer`)

Lives in `cartog-indexer`, which has no `cartog-rag`/ONNX dependency, so it builds
and runs without the native ONNX library. Per-language cost lives in the
tree-sitter grammar + extractor, so the full-index scenario is parameterized over
all 13 fixtures.

```bash
cargo bench -p cartog-indexer --bench indexing
cargo bench -p cartog-indexer --bench indexing -- index_full_force/rs   # one language
```

| Benchmark | What it measures |
|-----------|-----------------|
| `index_full_force/<lang>` | Full index of each fixture (force=true) — `py ts go rs rb java php dart swift kt` |
| `index_incremental_noop` | Re-index with no changes (all files skipped via hash); Python |
| `index_incremental_one_file` | One file's hash invalidated, triggers Merkle diff + scoped resolution; Python |

### `rag_search` — hybrid search (`cartog`)

`hybrid_search` (FTS5 + vector KNN + RRF merge) over the embedded Python fixture,
using a deterministic stub embedding provider — no ONNX model is loaded, so it runs
in CI.

```bash
cargo bench -p cartog --bench rag_search
```

### `rag_onnx` — real embedding + reranking (`cartog`, opt-in)

Loads the actual fastembed/ONNX models to measure `embed_query`,
`embed_documents`, and cross-encoder `rerank`. **Not run in CI**; requires the
models on disk (`cartog rag setup`) and skips gracefully if they are absent.

```bash
make bench-onnx   # or: cargo bench -p cartog --bench rag_onnx
```

## Benchmark any project

`bench-project.sh` runs cartog vs grep on **any codebase** — no ground truth needed.

It auto-discovers symbols, runs 5 comparison scenarios (outline, callers, callees, deps, impact), and reports token efficiency.

```bash
# Benchmark a project
./benchmarks/bench-project.sh /path/to/project

# Test more symbols (default: 3)
./benchmarks/bench-project.sh /path/to/project -n 5

# Benchmark current directory
./benchmarks/bench-project.sh .
```

## Fixture integrity checks

Validate that all fixture codebases compile/parse correctly:

```bash
make check-fixtures   # all fixtures (py, ts, go, rs, rb, java, php)
make check-py         # Python: py_compile
make check-ts         # TypeScript: tsc --noEmit (requires npx)
make check-go         # Go: go build ./...
make check-rs         # Rust: cargo check
make check-rb         # Ruby: ruby -c
make check-java       # Java: javac
make check-php        # PHP: php -l
```

Run `make check` to also include Rust project checks (fmt + clippy + test).

## Prerequisites

- `cartog` binary (built automatically by `token_savings.sh` if not in PATH)
- `jq` for ground truth comparison and stats (optional but recommended)
- bash 3+ (macOS/Linux compatible)

## Output

`token_savings.sh` prints a comparison table and saves results to `results/latest.jsonl`.

Each line is a JSON object:
```json
{"scenario":"01_find_callers","lang":"webapp_py","naive_tokens":420,"naive_recall":80.0,"best_tokens":280,"best_recall":80.0,"cartog_tokens":95,"cartog_recall":100.0}
```

`bench-project.sh` prints a summary table to stderr (no file output).
