Benchmark cache- and SIMD-oriented pathfinding strategies

[botoddly]

Context

IndexedPathSearch<TIndex, TCost> already addresses several common pathfinding costs:

• dense array-indexed costs, predecessors, and queue positions;
• reusable search storage and no steady-state allocations;
• method-generic graph and heuristic adapters that the JIT can specialize;
• a cache-friendlier 4-ary indexed heap instead of duplicate open-list entries.

The current benchmarks measure elapsed time, P95 latency, and allocations on synthetic open, weighted, and partitioned grids. They do not establish whether strict best-first ordering is still the best use of modern CPU memory hierarchies and SIMD units, or whether a grid-specialized strategy can perform more logical work in less wall-clock time.

The hypothesis is:

For regular grids, a relaxed or dense frontier with compact sequential state may outperform work-efficient A*/Dijkstra by trading additional cell visits for fewer dependent heap operations, fewer cache misses, predictable branches, and word/SIMD-parallel updates.

This is not a claim that the current implementation is cache-oblivious or that SIMD will necessarily help a single search. A*/Dijkstra has a serial extract-min dependency, grid nodes expose only four or eight neighbours, and irregular gather/scatter or divergent lanes can erase SIMD throughput. Cache layout, bit parallelism, and SIMD must therefore be measured separately.

Research basis

• Fringe Search avoided a fully sorted A* open list and ran approximately 10–40% faster on game grids while visiting more nodes. After further A* optimization, the reported advantage remained approximately 10% on octile maps and 20% on tile maps.
• SlimSell reformulated BFS as SIMD-friendly sparse matrix/vector work and showed that vectorization can outweigh additional work, while also documenting the locality and memory-pressure trade-offs.
• GraphIt treats graph execution as an explicit trade-off among work efficiency, locality, and parallelism rather than assuming that the fewest operations produce the shortest runtime.
• High-performance GPU graph traversal demonstrates the opposing constraint: irregular memory access, control-flow divergence, and load imbalance can underutilize SIMD hardware.
• Jump Point Search shows that grid-specific algorithmic pruning can reduce A* work by an order of magnitude. A hardware-oriented approach must therefore be compared with algorithmic pruning, not only with textbook A*.
• The MovingAI grid benchmarks provide public game-derived maps and query sets suitable for validation beyond synthetic grids.

Investigation

Establish the baseline

Extend the existing BenchmarkDotNet project with representative workloads:

• current synthetic open, weighted, and unreachable/partitioned maps;
• public MovingAI maps with recorded map and scenario provenance;
• short and long paths, reachable and unreachable destinations;
• warm reused searches and cold first-use searches;
• Dijkstra, A*, bounded and complete ExpandTree workloads;
• four-connected and eight-connected uniform-cost grids where the candidate supports them.

Record:

• elapsed time, P95 latency, and allocation as today;
• visited cells, expanded cells, edge relaxations, and frontier operations;
• instructions, branch misses, and cache misses where platform tooling supports reliable counters;
• working-set and persistent memory per map and per search;
• path reconstruction time when a full path is requested.

Keep graph construction and preprocessing visible as separate results. Do not compare a preprocessed candidate's query time with an unprocessed baseline without also reporting preprocessing time and storage.

Build benchmark-only candidates

Implement candidates inside the benchmark project first so no public API is selected before evidence exists:

1. Fringe-style thresholded search using compact contiguous frontier storage.
2. Uniform-cost grid BFS using an explicit sparse frontier.
3. A bit-packed wavefront using scalar word operations.
4. The same bit-packed representation with portable vector operations or architecture-specific intrinsics plus a scalar fallback.
5. An adaptive sparse/bitmap frontier that switches according to measured frontier density.
6. A bucketed frontier for bounded integer costs if the weighted workload demonstrates that heap maintenance is material.
7. A JPS or JPS+ comparator for static uniform-cost grids, either benchmark-local or through a reproducible reference implementation.

Compare scalar and vector bitmap variants directly to isolate SIMD benefit from layout and bit-packing benefit. Do not attribute their combined improvement to SIMD.

Cross-query batching, multithreading, GPU execution, hierarchical pathfinding, dynamic-map invalidation, and flow-field caching are separate workload and API decisions. Record them as follow-up opportunities rather than combining them into this experiment.

Preserve the abstraction boundary

IIndexedPathGraph<TIndex, TCost> represents arbitrary dense-indexed graphs and must not acquire grid layout, obstacle bitmap, bounded-cost, or SIMD requirements.

If a grid-specialized candidate is justified, design a separate consumer-facing representation around the data it actually needs. Do not hardcode grid assumptions into the general search API or expose benchmark implementation details as public contracts.

Correctness

• Cross-check every candidate against IndexedPathSearch for reachability and least cost on deterministic randomized grids and benchmark scenarios.
• Validate reconstructed paths against map connectivity and reported cost.
• Keep optimal and deliberately suboptimal variants in separate result groups.
• Test scalar and SIMD implementations for identical results, including row boundaries, widths not divisible by the word/vector width, and unsupported-intrinsics fallback.
• Preserve weighted-cost overflow behavior where a candidate supports the generic numeric contract.

Acceptance criteria

• The benchmark suite and reproduction commands cover the documented workloads without relying only on the existing 128×128 synthetic case.
• Results separate algorithmic work, cache-friendly representation, bit parallelism, and SIMD rather than presenting one combined speedup.
• Cold and warm behaviour, preprocessing, path extraction, and memory consumption are reported.
• All compared optimal implementations return equivalent path costs and valid paths.
• A written conclusion identifies the workload regions in which each candidate wins or loses.
• Production code changes are made only for a repeatable improvement with a clear supported domain and acceptable memory/preprocessing cost.
• If no candidate justifies a production implementation, close the investigation with the benchmark evidence and retain the current API unchanged.