Most iai_algos benchmarks do not measure the work they run #833

Half of the iai_algos benchmarks are not measuring the work they run. On current main, 7 of 14 report on the order of a hundred instructions for searches that execute hundreds of thousands of basic blocks.

This matters beyond the benchmark output itself: .github/workflows/iai-callgrind.yml diffs these numbers between the base branch and the PR branch and posts the result as a PR comment. Which benchmarks are affected depends on inlining, so it changes with unrelated edits — meaning the workflow can report an enormous phantom regression on a PR that did nothing of the sort.

Evidence

Callgrind records how many basic blocks the process executed, alongside how many instructions were actually collected. On pristine main:

For contrast, in the same group and the same run, corner_to_corner_bfs_bidirectional collects 2,787,240 and corner_to_corner_dijkstra collects 3,077,484. So this is not a group-level configuration problem — some benchmarks are measured and some are not, within one binary.

Straight from the callgrind output file for corner_to_corner_bfs:

cmd:  .../iai_algos-423b1bb369c6672e --iai-run corner_to_corner 1 0 iai_algos::corner_to_corner::corner_to_corner_bfs
desc: Timerange: Basic block 0 - 566593
summary: 248 66 44 15 1 0 15

The search runs. Collection simply is not on while it does.

iai_edmondskarp looks healthy (22,288 and 46,001 instructions).

Why it can produce a bogus CI report

The affected set is not stable, because it depends on inlining decisions. Comparing main against a branch whose only change was swapping the hasher in the FxIndexMap/FxIndexSet aliases:

Both rows are artefacts. The underlying algorithms changed by single-digit percentages.

This is reproducible rather than flaky: I built pristine main twice and got byte-identical counts both times, so it is a stable property of a given build, and it flips when something perturbs inlining.

Reproducing

cargo bench --features iai --bench iai_algos
for f in $(find target/iai -name 'callgrind.*.out' | grep iai_algos); do
  echo "$(grep -E '^summary:' $f | awk '{print $2}') instructions, $(grep 'desc: Timerange' $f | sed 's/.*- //') basic blocks : $f"
done

For each benchmark this prints the instructions collected next to the basic blocks executed:

14 instructions, 710739 basic blocks : no_path/no_path_astar
3225106 instructions, 694221 basic blocks : no_path/no_path_dfs
14 instructions, 601770 basic blocks : no_path/no_path_fringe
3047873 instructions, 644322 basic blocks : no_path/no_path_dijkstra

A benchmark whose two numbers are wildly out of proportion ran the search without measuring it.

Notes on the cause

iai-callgrind turns collection on around the benchmark function. When that function is fully inlined into the generated harness wrapper, the symbol it toggles on is left as a stub, so the window covers the stub instead of the search. That would explain why the trivially-shaped benchmarks (fringe, astar with a constant heuristic) are the ones most often affected, and why the set moves when anything perturbs inlining.

I have not tried to fix it yet. Adding black_box around the benchmark inputs does not help — I tried that first, and the counts stayed in the same broken pattern. #[inline(never)] on the benchmark functions is the obvious next thing to try. Happy to open a PR if that sounds like the right direction, or if you would prefer a different approach.