KStepPointer<T> and StridedIter<T>

A typed strided pointer that encodes the iteration stride as log2 (k_step: u8) instead of a runtime usize. The byte stride between consecutive elements is size_of::<T>() << k_step. Because the multiplier is a const shift amount rather than a multiplicand, the compiler can emit SHL with an immediate operand instead of IMUL per step.

The “stride is a shift, not a multiply” primitive. Same architectural shape as BLAS row/column strides and NumPy strided arrays - but with the stride encoded as k_step: u8 (log2-of-stride-multiplier) so it survives as a const through the codegen pipeline. The advantage is small but measurable on loops where the stride arithmetic is a meaningful fraction of the body.

Constraints (read first):

• In-process only. base: *const T is a real machine pointer, not portable across processes.
• new and tight and cache_line are all unsafe. The caller asserts base is valid and that every strided position base + i * stride stays in bounds for the indices the caller will visit.
• get(i) is unsafe and is unchecked. There is no bounds-test on i; out-of-range indices silently produce pointers past the array.
• Stride is fixed at construction. A single KStepPointer cannot adapt its stride mid-iteration. For variable-stride workloads (e.g. CSR sparse matrices with per-row strides) use a different abstraction.
• k_step: u8 limits stride to sizeof(T) << 255. In practice the cap is the address space; usable values are 0..=12 (covers tight packing through page-aligned strides).
• No iteration over mutable elements. KStepPointer<T> exposes &T only; for mutable strided iteration use the unsafe raw-pointer math via at(i) and the caller’s own unsafe mutable deref. The crate does not ship KStepMutPointer<T> today.
• Size is 16 bytes due to alignment. The struct contains a pointer (8 bytes, 8-byte alignment) + u8 + PhantomData. Rust rounds up to 16 bytes for the next 8-byte boundary, so KStepPointer<u64> is twice the size of a bare pointer.
• Modern x86 IMUL is 3-cycle pipelined. The bench wins are modest (~4% on the shipped scan); on older or simpler architectures the gap is larger.

Table of contents

• What it is
• Why k_step (log2 stride)
• Layout
• k_step values
• API at a glance
• Worked example
• Benchmark results
• Use case patterns
• Known limitations (verified)
• Common pitfalls

What it is

KStepPointer<T> is a (base, k_step) pair:

pub struct KStepPointer<T> {
    base: *const T,
    k_step: u8,
    _phantom: PhantomData<*const T>,
}

The address of element i is computed as:

addr_i = base + i * (size_of::<T>() << k_step)

The << k_step is the load-bearing piece: it’s a single SHL-with-immediate when k_step is propagated as a compile-time constant.

StridedIter<'a, T> is the iterator companion:

pub struct StridedIter<'a, T> {
    ptr: KStepPointer<T>,
    i: usize,
    count: usize,
    _life: PhantomData<&'a T>,
}

Implements Iterator<Item = &'a T> and ExactSizeIterator.

Why k_step (log2 stride)

The standard approach to strided iteration uses a runtime stride: usize:

for i in 0..n {
    let p = unsafe { base.cast::<u8>().add(i * stride).cast::<T>() };
    consume(unsafe { &*p });
}

This compiles to an IMUL per step (multiply i * stride). On modern x86, IMUL is 3-cycle latency on a dedicated unit, pipelined to one result per cycle. On older / simpler chips (early Atom, in-order ARM, RISC-V without M extension) IMUL costs more.

With KStepPointer, the stride is encoded as k_step: u8 where the actual byte stride is size_of::<T>() << k_step. The codegen pattern becomes:

load addr_offset = i << k_step_constant
load base + addr_offset

SHL with immediate is 1-cycle latency, every cycle, on every modern architecture. The compiler emits the immediate when the caller constructs the pointer with a compile-time-known k_step.

Layout

    flowchart LR
    subgraph KP["KStepPointer (16 bytes due to alignment)"]
      direction LR
      B["bytes 0..8<br/>base (*const T)"]
      K["byte 8<br/>k_step (u8)"]
      P["bytes 9..16<br/>padding (alignment)"]
    end

    classDef ptr fill:#1e3a8a,stroke:#1e40af,color:#ffffff
    classDef k fill:#7c3aed,stroke:#5b21b6,color:#ffffff
    classDef pad fill:#6b7280,stroke:#374151,color:#ffffff
    class B ptr
    class K k
    class P pad
  

The 7 bytes of padding are Rust’s natural alignment requirement for the *const T field. The struct could be made smaller via #[repr(packed)] but at the cost of misaligned pointer access which is undefined behaviour on some targets.

k_step values

KStepPointer::cache_line(base) picks the smallest k_step such that the stride is at least 64 bytes (one cache line), selecting based on size_of::<T>().

API at a glance

Worked example

use subetha_pointers::kstep_pointer::KStepPointer;

// 4x4 row-major matrix stored as a flat Vec<u64>. Each row is
// 4 elements * 8 bytes = 32 bytes. Walking column 0 means
// stride 32 bytes = sizeof(u64) << 2, so k_step = 2.
let matrix: Vec<u64> = (0..16u64).collect();
let col_0 = unsafe { KStepPointer::new(matrix.as_ptr(), 2) };
assert_eq!(col_0.stride(), 32);

// SAFETY: 4 strided positions at stride 32 = 96 bytes from
// matrix.as_ptr() = within the 128-byte allocation.
let column: Vec<u64> = unsafe { col_0.iter(4) }.copied().collect();
assert_eq!(column, vec![0, 4, 8, 12]);

// Cache-line stride: for u64, stride 64 = k_step 3. Walks every
// 8th element.
let cl = unsafe { KStepPointer::<u64>::cache_line(matrix.as_ptr()) };
assert_eq!(cl.k_step(), 3);
assert_eq!(cl.stride(), 64);

// Tight packing for default Vec iteration.
let tight = unsafe { KStepPointer::tight(matrix.as_ptr()) };
assert_eq!(tight.stride(), 8);  // sizeof(u64)
let all: Vec<u64> = unsafe { tight.iter(16) }.copied().collect();
assert_eq!(all, (0..16u64).collect::<Vec<_>>());

Benchmark results

256 strided loads (1024-element matrix walked at stride 32). Measured on Windows 11 / Zen+ R7 2700, criterion at --measurement-time 2 --warm-up-time 1 --sample-size 30 (middle estimate of each [low, mid, high] triple).

Bench fairness

The runtime-stride contender sources its stride from a Vec<usize> indexed by a black_box’d value, so the compiler cannot constant-fold it. A local let stride: usize = 32; would fold into SHL-with-immediate, identical to the typed k_step path - parity that measures the fold, not the pointer. A third contender, compile_const_stride_baseline, keeps that compile-time-foldable case visible for reference.

Results

The two compile-time-stride paths (typed_k_step and compile_const_stride_baseline) are within measurement noise of each other (74.7 ns vs 74.0 ns) and both are ~1.03x faster than the truly-runtime path (77.2 ns). Communicating the stride at compile time - whether via the typed k_step field or a const - lands at the same speed; the runtime path pays ~3 ns more for the IMUL.

Why each result lands where it does

Use case patterns

Known limitations (verified)

1. In-process only. base is a raw machine pointer.

2. All accessors are unsafe. No bounds-check on get(i) or at(i); out-of-range i silently produces invalid addresses.

3. Stride is fixed at construction. No mid-iteration stride changes. Variable-stride workloads (CSR sparse matrices, per-row strides) need a different abstraction.

4. k_step encodes log2 strides only. Non-power-of-2 strides (e.g. 12 bytes for Vec3) cannot be represented; use runtime stride: usize for those.

5. Size is 16 bytes due to alignment. Twice the size of a bare pointer. For collections of strided pointers this doubles the storage cost vs raw *const T.

6. No KStepMutPointer<T> shipped. Strided mutable access requires hand-rolled unsafe pointer math via at(i) as *mut T.

7. Codegen win is ~4% on modern x86. The architectural claim “SHL vs IMUL” is real but small because modern IMUL is pipelined. The win grows on older / simpler architectures.

8. cache_line cap is k_step = 6. For T smaller than 1 byte (which is not expressible in Rust), the cap would still be 6 (giving stride 64 = one cache line).

9. Bench fairness caveat (see above). The runtime-stride contender uses a truly-runtime stride (not a compile-foldable constant), against which the typed path is ~1.03x faster (and within noise of the compile-const baseline).

10. StridedIter is double-ended in shape but not in trait. The iterator goes forward only; reverse iteration requires constructing a separate KStepPointer from the end of the array.

Common pitfalls

let data: Vec<u64> = (0..10u64).collect();
let p = unsafe { KStepPointer::new(data.as_ptr(), 0) };
// SAFETY violation: i = 20 is past the array.
let v = unsafe { *p.get(20) };  // reads arbitrary memory

struct Vec3 { x: f32, y: f32, z: f32 }  // 12 bytes
let data: Vec<Vec3> = ...;
// SoA gather over .x with stride 12 bytes:
// `12 / sizeof(f32) = 3`, which is NOT a power of 2.
// You cannot pick a k_step that gives stride = 12 for T = f32.

let p = {
    let data: Vec<u64> = (0..10u64).collect();
    unsafe { KStepPointer::new(data.as_ptr(), 0) }
};  // data dropped here
// p.base is dangling.
unsafe { *p.get(0); }  // UB

back to subetha-pointers docs