Radial Stride Array (RSA)

A cache-friendly 2D array with built-in directional traversal — inspired by the Ashoka Chakra 🇮🇳

O(1) access · O(D) spoke traversal · O(N) spiral scan · Heterogeneous type support

---

What is it?

Radial Stride Array is a 2D grid data structure that combines the raw performance of a flat contiguous array with a built-in spoke-based directional traversal API.

Instead of manually writing for loops with index arithmetic every time you need to walk a diagonal, scan neighbors, or spiral outward from a center point — RSA gives you one-liner methods that do it safely, efficiently, and with zero overhead compared to hand-written code.

use rsa_bench::radial_stride_array::{RadialStrideArray, Direction};

// Create an 8×8 chess board
let mut board = RadialStrideArray::<u8>::new(8, 8);
board.set(3, 3, 1); // Place a piece at center

// Walk diagonally — one line, no manual index math
let diagonal = board.walk_spoke(Direction::DOWN_RIGHT, 1);

// Get all 8 neighbors (Game of Life pattern)
let neighbors = board.neighbors(3, 3);

// Spiral outward from center
let spiral = board.spiral_from_center();

// Walk from any position in any direction
let ray = board.walk_from(0, 0, Direction::DOWN_RIGHT, 1, 8);

The Origin Story

The idea came from looking at the Ashoka Chakra — the 24-spoke wheel on the Indian national flag. The wheel's spokes radiate outward from a center in every direction, and the insight was:

"What if an array could work like this wheel — where from any center point, you can traverse in any direction at any stride?"

Standard CS courses teach array indexing, matrix traversal, and direction vectors as separate concepts. RSA unifies them into a single abstraction:

            Direction: (dr, dc)
            Stride: step size

                    UP (-1,0)
                      ↑
         UP_LEFT ↗    |    ↖ UP_RIGHT
        (-1,-1)       |       (-1,+1)
                      |
    LEFT (0,-1) ←— CENTER —→ RIGHT (0,+1)
                      |
       DOWN_LEFT ↙    |    ↘ DOWN_RIGHT
        (+1,-1)       |       (+1,+1)
                      ↓
                   DOWN (+1,0)

    Element k steps along direction (dr, dc) from center (r₀, c₀):
    index = (r₀ + k × stride × dr) × cols + (c₀ + k × stride × dc)

The formula is standard stride-based access — but no existing library packages it as a unified API.

Why RSA?

vs. Manual Flat Arrays

Flat Vec<T> with index = r * cols + c is the standard approach. RSA uses the exact same layout under the hood — so you get identical performance. But instead of writing this every time:

// Manual: walk 8 directions from center — repeated boilerplate
let dirs = [(0,1),(1,0),(0,-1),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)];
for (dr, dc) in &dirs {
    let mut r = center_r as i32;
    let mut c = center_c as i32;
    loop {
        r += dr; c += dc;
        if r < 0 || c < 0 || r as usize >= rows || c as usize >= cols { break; }
        // ... use grid[r as usize * cols + c as usize]
    }
}

You write:

// RSA: one line
let spokes = rsa.all_spokes(1);

Same performance, 90% less code, zero bugs from manual index math.

vs. Nested Arrays (Vec<Vec<T>>)

	RSA (flat)	Vec<Vec<T>>
Memory	Contiguous, cache-friendly	Scattered heap allocations
Access	data[r * cols + c] — 1 pointer	data[r] → row[c] — 2 pointers
Cache	Prefetcher-friendly sequential access	Cache misses on row transitions
Benchmark	Baseline	10-20% slower (measured)

vs. HashMaps (HashMap<(i32,i32), T>)

	RSA	HashMap<(i32,i32), T>
Access	O(1) — arithmetic	O(1) avg — hash + probe
Memory	4 bytes per i32 cell	~56 bytes per entry (hash overhead)
Sequential scan	Cache-optimal	Random bucket order
Benchmark	Baseline	4-28× slower (measured)

vs. Quadtrees / Spatial Hashes

These are different tools for different problems:

	RSA	Quadtree / Spatial Hash
Best for	Dense grids (every cell populated)	Sparse worlds (few objects in large space)
Access	O(1)	O(log N) / O(1) avg
Range query	O(area)	O(log N + k) ✅
Memory (dense)	Optimal	10-40× more (node/bucket overhead)
Use case	Chess, Go, images, cellular automata	Game worlds, physics, particle systems

RSA wins when your grid is mostly full. Quadtrees win when your world is mostly empty.

Benchmark Results

All benchmarks run with --release on Criterion (100 samples, statistically rigorous):

Sequential Scan

Grid	RSA	FlatGrid	NestedGrid	Winner
64×64	549 ns	548 ns	664 ns	RSA ≈ Flat
256×256	9.65 µs	9.13 µs	9.88 µs	Flat ≈ RSA
512×512	36.2 µs	38.9 µs	37.2 µs	RSA 🏆

Word Search (directional traversal)

Grid	RSA	FlatGrid	NestedGrid	HashGrid	Winner
8×8	133 ns	286 ns	271 ns	416 ns	RSA 2.1× faster 🏆
19×19	135 ns	280 ns	266 ns	443 ns	RSA 2.0× faster 🏆
64×64	146 ns	283 ns	279 ns	454 ns	RSA 1.9× faster 🏆

Game of Life

Grid	RSA	FlatGrid	NestedGrid	HashGrid	Winner
19×19	15.5 µs	17.1 µs	18.7 µs	65.5 µs	RSA 🏆
64×64	179 µs	203 µs	199 µs	689 µs	RSA 🏆

RSA's built-in spoke traversal provides a consistent 2× speedup for directional algorithms while matching flat arrays on everything else.

Complexity

Operation	Time	Space
get(r, c) / set(r, c)	O(1)	O(1)
neighbors(r, c)	O(1)	O(1)
walk_spoke(dir, stride)	O(D)	O(D)
all_spokes(stride)	O(D)	O(D)
spiral_from_center()	O(N)	O(N)
iter()	O(N)	O(1)
Word Search	O(N × D)	O(1)
Game of Life	O(N)	O(N)
Sobel Edge Detection	O(N)	O(N)

Where N = rows × cols, D = max(rows, cols).

Heterogeneous Storage

Standard C/C++ arrays can only store one type. RSA + Rust enums can store mixed types in the same contiguous array:

use rsa_bench::heterogeneous::Cell;

// One grid, multiple types — impossible in C/C++ arrays
let mut grid = RadialStrideArray::<Cell>::new(8, 8);
grid.set(0, 0, Cell::Int(42));
grid.set(0, 1, Cell::Float(3.14));
grid.set(0, 2, Cell::Text("hello".into()));
grid.set(0, 3, Cell::Bool(true));

// All stored contiguously in memory — type-safe, cache-friendly

This is possible because Rust's enum is a tagged union — every variant occupies the same space (padded to the largest variant), so Vec<Cell> remains a contiguous flat array.

Project Structure

radial-stride-array/
├── rsa-bench/
│   ├── src/
│   │   ├── lib.rs                  # Module declarations
│   │   ├── radial_stride_array.rs  # Core RSA implementation
│   │   ├── comparison.rs           # FlatGrid, NestedGrid, HashGrid
│   │   ├── algorithms.rs           # Word Search, GoL, N-Queens, Sobel
│   │   ├── heterogeneous.rs        # Mixed-type Cell enum + demos
│   │   └── main.rs                 # Benchmark runner with formatted output
│   ├── benches/
│   │   └── comparison.rs           # Criterion statistical benchmarks
│   └── Cargo.toml
├── docs/
│   └── ARCHITECTURE.md             # Technical deep-dive
└── README.md

Running

# Run all 65 tests
cargo test

# Run benchmark suite with formatted tables
cargo run --release

# Run Criterion benchmarks (statistical, ~10 min)
cargo bench

Recommended For

Use Case	Why RSA Fits
♟️ Chess / Go engines	Built-in directional moves (bishop, rook, queen)
🧬 Cellular automata	O(1) neighbor access, Game of Life ready
🖼️ Image processing	Directional kernels, edge detection
🔍 Word search / pattern matching	2× faster than manual loops
🗺️ Tile-based game maps	Cache-friendly grid with center-based logic
🎯 Ray casting / line of sight	Walk any direction from any point

Not Recommended For

Use Case	Better Alternative
Sparse worlds (99% empty)	Quadtree, Spatial Hash
3D voxels	Octree
Dynamic object tracking	Spatial HashMap
Linear algebra / matrix math	ndarray crate

License

MIT

---

Conceived from the Ashoka Chakra 🇮🇳 — spokes radiating outward, each a direction through data.