Most iai_algos benchmarks do not measure the work they run

[tachsin]

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:

benchmark	instructions collected	basic blocks executed
corner_to_corner_astar	103	92,522
corner_to_corner_bfs	248	566,593
corner_to_corner_dfs	181	756,131
corner_to_corner_fringe	103	89,305
no_path_astar	14	710,739
no_path_bfs_bidirectional	16	570,024
no_path_fringe	14	601,770

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:

benchmark	main	branch	what CI would report
corner_to_corner_bfs	248	2,716,652	+1,095,324%
no_path_bfs	2,225,049	206	-100%

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.

[tachsin]

Correcting myself: I suggested above that #[inline(never)] on the benchmark functions was the obvious thing to try. It is not, because it does not compile.

error: Invalid attribute: 'inline'
  = help: Only the `bench` and the `benches` attribute are allowed

The library_benchmark macro rejects it in either position, before or after the macro attribute. Adding black_box around the inputs alone does not help either, as I noted originally.

What does work is moving the search into an #[inline(never)] helper and returning its result from the benchmark, so the optimiser can neither see through the call nor discard the value:

shape	instructions collected	basic blocks executed
as the crate writes it today	14	713,866
work in an out-of-line helper, result returned	3,811,477	713,904

Same workload, same basic-block count, only the benchmark's shape differs.

#835 applies that to all fourteen. It also holds up when the algorithms change, which is the part that matters: applied on top of #834, which edits the inner loop of every cost-based search, 0 of 14 stopped measuring.

One concrete example of the damage, since it turned up while this was open. Measured against the current benchmarks, the overflow check in #834 looked like an 18.6% instruction regression on corner_to_corner_dijkstra. Measured against the fixed ones it is 0.7%, with five of the six no-cost benchmarks at exactly 0.0%. I had published the 18.6% figure on that PR and have corrected it.