# best-path Optimization Notes

Analysis of [konrads/best-path](https://github.com/konrads/best-path) — a Floyd-Warshall based optimal trade route finder targeting Substrate pallets.

The algorithm is correct. The implementation has several performance issues that compound at larger graph sizes.

---

## Issue 1: BTreeMap as the distance matrix (critical)

**Current:**
```rust
let mut matrix: BTreeMap<Pair, Path> = BTreeMap::new();

for k in vertices.iter() {
    for i in vertices.iter() {
        for j in vertices.iter() {
            let ij = matrix.get(&Pair { source: *i, target: *j });
            let ik = matrix.get(&Pair { source: *i, target: *k });
            let kj = matrix.get(&Pair { source: *k, target: *j });
```

The inner loop runs n³ times. Each `matrix.get()` is O(log n) — pointer-chasing through a tree scattered across the heap. Three lookups per iteration means 3n³ tree traversals total, all with poor cache locality.

**Fix:** flat `Vec<f64>` indexed by `i * n + j` — O(1) access, contiguous in memory, fits in L1/L2 cache for typical exchange graph sizes.

```rust
let n = vertex_count;
let mut cost = vec![f64::INFINITY; n * n];

// access
let val = cost[i * n + j];
cost[i * n + j] = new_val;
```

**Expected gain:** 5–15× on matrix access cost from O(log n) → O(1), plus significant cache benefit.

---

## Issue 2: Vec::clone() inside the O(n³) loop (dominant issue)

**Current:**
```rust
let (ik_cost, ik_edges) = match matrix.get(&Pair { source: *i, target: *k }) {
    Some(ik) => (ik.total_cost, ik.edges.clone()),  // ← clone on every iteration
    None => (f64::MAX, vec![])
};
let (kj_cost, kj_edges) = match matrix.get(&Pair { source: *k, target: *j }) {
    Some(kj) => (kj.total_cost, kj.edges.clone()),  // ← clone on every iteration
    None => (f64::MAX, vec![])
};
```

Two Vec allocations per inner iteration regardless of whether the path is updated. As Floyd-Warshall progresses, paths grow — later iterations clone paths of length 2, 3, ... up to n-1 edges. Total copy work across the full run is O(n⁴), not O(n³).

**Fix:** store a predecessor/next-hop index per cell (`usize`), reconstruct the full path only on demand after the algorithm completes.

```rust
let mut cost = vec![f64::INFINITY; n * n];
let mut next = vec![usize::MAX; n * n];  // one hop index per cell

// in the triple loop — no allocation, no clone
if new_cost < cost[i * n + j] {
    cost[i * n + j] = new_cost;
    next[i * n + j] = next[i * n + k];  // copy one usize
}

// path reconstruction after the loop, only for queried pairs
fn reconstruct(next: &[usize], from: usize, to: usize, n: usize) -> Vec<usize> {
    let mut path = vec![from];
    let mut cur = from;
    while cur != to {
        cur = next[cur * n + to];
        if cur == usize::MAX { return vec![]; }  // no path
        path.push(cur);
    }
    path
}
```

**Complexity change:** O(n⁴) → O(n²) for storage and in-loop work.

**Expected gain:** dominant factor. Rough order-of-magnitude estimates:

| n  | Current    | Fixed    | Speedup |
|----|------------|----------|---------|
| 20 | ~1ms       | ~20μs    | ~50×    |
| 50 | ~50ms      | ~200μs   | ~250×   |
| 100| ~500ms     | ~1ms     | ~500×   |

*These are estimates, not benchmarks. Validate with `criterion`.*

---

## Issue 3: BTreeSet for vertex iteration

**Current:**
```rust
let mut vertices: BTreeSet<usize> = BTreeSet::new();

for k in vertices.iter() {
    for i in vertices.iter() {
        for j in vertices.iter() {
```

Vertices are already `usize` IDs. Iterating a `BTreeSet` is pointer-chasing through a tree. The compiler cannot auto-vectorize or pipeline this.

**Fix:** map currencies to a dense integer range `0..n` during setup, then use plain ranges:

```rust
for k in 0..n {
    for i in 0..n {
        for j in 0..n {
```

A tight integer range allows the compiler to generate optimal loop code and enables future SIMD vectorization of the inner loop.

**Expected gain:** minor on its own (~10–30% on loop overhead), but prerequisite for SIMD.

---

## Issue 4: Redundant allocations in `longest_paths_mult`

**Current:**
```rust
// allocation 1
let weight_map: BTreeMap<(Pair, usize), f64> = edges.iter().map(...).collect();
// allocation 2
let edges_with_log_weights: Vec<Edge> = edges.iter().map(...).collect();
// then calls shortest_paths → unique_cheapest_edges → allocation 3
```

Three heap allocations before the triple loop starts. `unique_cheapest_edges` is also called inside `longest_paths_mult` which then calls `shortest_paths`, which calls `unique_cheapest_edges` again — deduplication runs twice.

**Fix:** pass pre-deduplicated edges in, apply the log transform in-place or inline during matrix initialisation. The back-mapping (`weight_map`) can be eliminated by storing original weights separately and never transforming the stored values.

---

## Issue 5: No early termination in the inner loop

**Current:** the inner loop always runs all n³ iterations even for sparse graphs where many pairs have no path (`f64::MAX`).

**Fix:** skip unreachable pairs:

```rust
for k in 0..n {
    for i in 0..n {
        if cost[i * n + k] == f64::INFINITY { continue; }  // skip pruning
        for j in 0..n {
            let new_cost = cost[i * n + k] + cost[k * n + j];
            if new_cost < cost[i * n + j] {
                cost[i * n + j] = new_cost;
                next[i * n + j] = next[i * n + k];
            }
        }
    }
}
```

For sparse exchange graphs this can skip a significant fraction of inner iterations.

---

## Algorithm considerations

### Floyd-Warshall vs Bellman-Ford vs Dijkstra

| Goal | Algorithm | Complexity |
|---|---|---|
| All-pairs routing table | Floyd-Warshall | O(V³) |
| All-pairs, sparse graph | Johnson's algorithm | O(V² log V + VE) |
| Best route from one asset | Bellman-Ford | O(VE) |
| Best route, single pair, no negative weights | Dijkstra | O((V+E) log V) |
| Arbitrage cycle detection | Bellman-Ford (Vth relaxation) | O(VE) |

For a **specific user swap query** (one source, one target), Bellman-Ford is ~30× fewer operations than Floyd-Warshall on a typical sparse exchange graph (50 assets, 80 pairs).

For **arbitrage detection**, Bellman-Ford is required — Dijkstra cannot handle negative edge weights produced by the log2 transform of rates above 1.0.

### The fixed-weight assumption

This library assumes oracle-provided fixed rates per calculation. This is correct for its Substrate pallet target. It is not suitable for:
- AMM-based DEXes (rate is a function of trade size, requires convex optimisation)
- Order book exchanges (rate depends on available depth at each price level)

### WASM note

The Vec::clone allocations (Issue 2) are worse in WASM than native. WASM uses a bump allocator inside linear memory with no free list — repeated clone/drop cycles fragment memory faster than a system allocator. The fixed version avoids this entirely, which is particularly valuable if this library is compiled to WASM for client-side routing.
