# GVNS flame charts — VND vs shaking time split

Sampling-profiler (`perf`) flame charts of the `dckmst` GVNS solver on three fixed
(instance, seed) runs spanning a light, a medium, and a hard regime. Goal: see how
on-CPU time splits between **shaking** (`shake3`) and the **VND** local searches
(`vnd1`, `vnd2bi`, `vnd3bi`). No source instrumentation — `shake3`/`vnd*` live in
separate translation units, so they appear as distinct flame-graph frames.

## The three runs

All use the config that produced `results_20260519_stdgen.csv`:
`--shake3 --vnd2bi --vnd3bi --no-vnd4 --vnd-order 1234`, `iters=100000`, `--max-time 300`.

| Regime | instance | n | d | k | seed | run time | outcome |
|--------|----------|---|---|---|------|----------|---------|
| light  | R100n1 | 100 | 4 | 75 | 4  | ~3 s   | hits best-known (early exit) |
| medium | SYM500 | 50  | 2 | 50 | 25 | ~12 s  | hits best-known |
| hard   | m300n1 | 300 | 5 | 75 | 25 | 300 s  | never hits best-known (~7% gap) |

Flame charts: [`out/light.svg`](out/light.svg) · [`out/medium.svg`](out/medium.svg) · [`out/hard.svg`](out/hard.svg)
(open in a browser; click frames to zoom). Per-case tables: `out/*.summary.txt`; combined: `out/summary_combined.txt`.

## Results — % of on-CPU time

Weights are perf sample periods (∝ CPU time).

| region | light (2K smp) | medium (11K smp) | hard (298K smp) |
|--------|---------------:|-----------------:|----------------:|
| `shake3` (SHAKE)      |  1.14% |  7.22% |  3.19% |
| `vnd1`                | 24.65% | 27.71% | 40.07% |
| `vnd2bi`              | 36.81% | 12.19% | 30.61% |
| `vnd3bi`              |  0.99% |  0.09% |  3.46% |
| **sol-copy (main)**   | **35.72%** | **52.07%** | **20.88%** |
| prim (init)           |  0.00% |  0.00% |  0.00% |
| other                 |  0.70% |  0.72% |  1.80% |
| **VND total**         | **62.44%** | **39.99%** | **74.14%** |
| **SHAKE total**       |  **1.14%** |  **7.22%** |  **3.19%** |

## Findings

1. **Shaking is cheap** — 1–7% of CPU time in every regime. The perturbation step is
   not a bottleneck.

2. **VND dominates the actual search work** (40–74%), led by `vnd1` (first-improvement)
   and `vnd2bi`. `vnd3bi` is nearly free (0.1–3.5%). `vnd2bi`'s share swings a lot with
   the instance (37% → 12% → 31%).

3. **The largest single cost is not a "method" at all — it's `Solution` copy-assignment
   in the main accept/reject loop** (21–52% of CPU time). Every non-improving VND step does
   `sol = best` (`main.cpp:182`) and every improvement does `best = sol` (`main.cpp:171`),
   each copying the whole `Solution` (its hashtable + vectors). In the flame charts this
   shows up as `main → std::_Hashtable<…>` / `Solution::operator=` (the assignment is
   inlined into `main`). Its share is largest on the medium case (many accept/reject
   cycles on a small-but-hard solution) and relatively smaller on `hard` where each VND
   pass over n=300 is itself expensive.

**Actionable takeaway:** optimizing the solver's time is more about the `sol = best` /
`best = sol` bookkeeping and `vnd1`/`vnd2bi` than about shaking. Replacing full
`Solution` copies with move-undo or copy-on-write could reclaim a large fraction of
runtime, especially on the medium regime.

## Reproduce

```bash
./build_prof.sh      # g++ -O2 -g -fno-omit-frame-pointer  -> dckmst_prof
./validate.sh        # confirm cost/op-counts match results_20260519_stdgen.csv
#   (needs perf; see SETUP_perf.md for the one-time sudo setup)
./profile.sh         # perf record -> out/*.data,*.folded,*.svg,*.summary.txt
./summarize.sh       # recompute breakdowns from *.folded (no re-profiling)
```

## Notes

- **Reproduction fidelity:** light & medium early-exit on best-known and reproduce the CSV
  operation counts *exactly* (e.g. light cost 4.9390, n_shake 3424). The `hard` run is
  wall-clock-capped at 300 s and *not* op-count-identical to the CSV: the recorded run was
  `parallel --jobs 10` (10 jobs sharing the CPU → fewer iterations fit in 300 s), whereas
  this solo profiled run is faster and completes more iterations (381K vs 310K shakes). The
  per-iteration RNG sequence is identical; only the count that fits in the time budget
  differs. Final cost (2.3120) still matches. See `out/reproduction.csv`.
- **Profiler:** `perf record -F 997 --call-graph fp`; frame pointers are enabled in the
  build so unwinding is cheap and accurate. glibc-truncated stacks (e.g. bare `_int_malloc`)
  are <1% of samples, so frame-pointer unwinding is adequate here — DWARF was not needed.
- **Weighting:** `stackcollapse-perf.pl` sums perf sample periods, so bar widths and the
  percentages above are proportional to CPU time, not raw sample counts.