# Optimized2 Benchmarks — Floyd-Warshall

Date: 2026-06-09  
Criterion sample size: 10  
Graph topology: ring (sparse), all-pairs (dense)  
Edge rates: all < 1.0 (range 0.5–0.6), scaled by 10^12

## Additional optimizations applied (on top of optimized)

1. **O(E) graph construction** (was O(currencies × E)): replaced the nested
   `for c in currencies { for pp in pairs { if c == pp.source` loop in `calculator.rs`
   with a direct iterator over `pairs_and_prices`.
2. **No vertex remapping**: dropped the `BTreeSet` + `BTreeMap` setup in
   `floyd_warshall_core`; vertex IDs from `PositionIndexer` are already dense `0..n`
   and used directly as matrix indices. A `Vec<bool>` tracks which IDs actually exist.
3. **Branchless inner loop with hoisted row constants**: `cost_ik` and `next_hop_ik`
   loaded once per `(i,k)` pair; the conditional update rewritten as branchless
   `if improved { … } else { … }` to allow `cmov` / auto-vectorisation.

## size_scaling — sparse graph, 1 provider

| Nodes | Original  | Optimized | Optimized2 | vs Original | vs Optimized |
|------:|-----------|-----------|------------|:-----------:|:------------:|
|    10 |  134 µs   |   71 µs   |   73 µs    |   1.8×      |   ~same      |
|    20 | 1.17 ms   |  529 µs   |  530 µs    |   2.2×      |   ~same      |
|    30 | 3.76 ms   | 1.73 ms   | 1.81 ms    |   2.1×      |   ~same      |
|    40 | 8.99 ms   | 4.27 ms   | 4.30 ms    |   2.1×      |   ~same      |
|    50 | 18.11 ms  | 7.84 ms   | 7.93 ms    |   2.3×      |   ~same      |

For sparse graphs the O(n³) triple loop dominates; setup savings from opts 1–2 are
below measurement noise, and the branchless loop (opt 3) yields little gain because
most inner-loop cells are skipped by the `is_infinite` early-exit.

## provider_scaling — sparse graph, 30 nodes

| Providers | Original | Optimized | Optimized2 | vs Original | vs Optimized |
|----------:|----------|-----------|------------|:-----------:|:------------:|
|         1 | 3.84 ms  | 1.75 ms   | 1.71 ms    |   2.2×      |   ~same      |
|         3 | 3.91 ms  | 1.71 ms   | 1.70 ms    |   2.3×      |   ~same      |
|         5 | 3.87 ms  | 1.73 ms   | 1.69 ms    |   2.3×      |   ~same      |

## edge_density — 1 provider, 30 nodes

| Topology          | Edges | Original | Optimized | Optimized2 | vs Original | vs Optimized |
|:------------------|------:|----------|-----------|------------|:-----------:|:------------:|
| Sparse (ring)     |    30 | 3.84 ms  | 1.68 ms   | 1.69 ms    |   2.3×      |   ~same      |
| Dense (all-pairs) |   870 | 4.68 ms  | 616 µs    | 547 µs     |   8.6×      |   1.13×      |

The branchless inner loop delivers a clear additional **~11%** on the dense graph,
where nearly every `(i,j)` cell is updated on each `k` pass and the branch predictor
was under pressure. On the sparse ring the update rate is low enough that the
branch-predicted path was already fast, so the change is noise.

## Summary across all rounds

The large gains came from the first optimisation round (flat Vec matrices + next-hop
table eliminating O(n⁴) Vec::clone). The second round yields a further ~11% on dense
graphs from the branchless loop; sparse graphs are at the O(n³) floor. Further
improvement at these graph sizes (≤50 nodes) would require SIMD intrinsics or an
algorithmic change (e.g. Johnson's algorithm for sparse graphs).
