Skip to content

Chapter 3: Strided Tensors & Zero-Copy ShapeTracker Views

"It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures."
— Alan J. Perlis (Epigrams on Programming, ACM SIGPLAN, 1982)


📁 Companion Code & Reproduction Suite:
examples/ch03/ • include/rcre.h • make ch03 • make ch03_bench

3.1 The Geometry of Memory: Multi-Dimensional Spaces on Flat Silicon

Computer Vision and Machine Learning operate primarily on multi-dimensional mathematical entities: * A digital photograph is a 3-dimensional tensor \(I \in \mathbb{R}^{H \times W \times C}\) (Height, Width, Color Channels). * A video stream or batched inference request is a 4-dimensional tensor \(V \in \mathbb{R}^{N \times H \times W \times C}\). * A deep attention weight matrix or covariance tensor is an \(N\)-dimensional array.

Yet, physical computer hardware—from the L1 cache controller down to physical DRAM silicon banks—is strictly linear. Memory is a flat, 1-dimensional array of bytes indexed by a scalar 64-bit integer address \(A \in [0, 2^{64}-1]\).

Therefore, every multi-dimensional abstraction requires a bijective mapping function: $\(\phi: \mathbb{N}^D \to \mathbb{N}\)$

How this mapping is designed dictates whether an image processing engine runs at \(240\text{ FPS}\) or stutters at \(12\text{ FPS}\).


3.2 The Generalized Stride Linear Combination

Let a tensor \(\mathcal{T}\) have rank \(D \in \mathbb{N}\) with shape vector: $\(\mathbf{d} = (d_0, d_1, \dots, d_{D-1}) \in \mathbb{N}^D\)$

For any coordinate tuple \(\mathbf{i} = (i_0, i_1, \dots, i_{D-1})\) satisfying \(0 \le i_k \lt d_k\), the physical scalar element offset in linear memory is governed by the generalized stride inner product:

\[\text{FlatIndex}(\mathbf{i}) = \text{offset} + \langle \mathbf{i}, \mathbf{s} \rangle = \text{offset} + \sum_{k=0}^{D-1} i_k \cdot s_k\]

where \(\mathbf{s} = (s_0, s_1, \dots, s_{D-1}) \in \mathbb{Z}^D\) is the stride vector (expressed in elements, signed via ptrdiff_t to permit reverse traversals), and \(\text{offset} \in \mathbb{N}\) is the base pointer displacement.

1. Canonical Contiguous Layouts

A tensor is said to be canonical contiguous if its elements are laid out in memory with zero gaps or interleavings.

Row-Major (\(HWC\) / Interleaved) Format

Commonly used in camera hardware, display drivers, and OpenCV. Adjacent color channels of a single pixel reside next to each other: $\(s_2 = 1, \quad s_1 = C, \quad s_0 = W \cdot C\)$

Memory Layout: [ R0 G0 B0 | R1 G1 B1 | R2 G2 B2 ... ]
* Advantage: Optimal for pointwise pixel operations (e.g., RGB to Grayscale conversion, brightness/contrast adjustments). A single vector register load reads complete pixels. * Disadvantage: Inefficient for spatial convolutions, as filtering a single channel requires strided, non-contiguous gathers.

Planar (\(CHW\)) Format

Standard in high-performance neural network inference engines (e.g., TensorRT, ONNX Runtime) and HPC finite-difference stencils: $\(s_2 = 1, \quad s_1 = W, \quad s_0 = H \cdot W\)$

Memory Layout: [ R0 R1 R2 ... | G0 G1 G2 ... | B0 B1 B2 ... ]
* Advantage: Spatial convolutions on channel \(R\) operate on contiguous memory, enabling 8-way and 16-way SIMD vectorization without horizontal permute instructions.


3.3 The ShapeTracker Principle: \(\mathcal{O}(1)\) Zero-Copy Views

In naive computer vision libraries, geometric transformations—such as cropping a region of interest, transposing matrix rows and columns, or rearranging color planes—are implemented by allocating a new memory buffer and copying pixel bytes:

// Naive, slow approach: Allocates 6.22 MB and copies 6,220,800 bytes for 1080p RGB
uint8_t* cropped = malloc(crop_w * crop_h * 3);
for (size_t y = 0; y < crop_h; ++y) {
    memcpy(&cropped[y * crop_w * 3], &src[(y + start_y) * src_w * 3 + start_x * 3], crop_w * 3);
}

This violates the fundamental law of mechanical sympathy: copying data across the memory bus consumes power and pollutes CPU caches.

Under the ShapeTracker paradigm (pioneered in modern systems engines like tinygrad), the underlying data buffer is completely immutable during view transformations. Transposing, slicing, broadcasting, and permuting are strictly \(\mathcal{O}(1)\) operations that mutate only the metadata: shape, strides, and data pointer offset.

Mathematical Proof of \(\mathcal{O}(1)\) Transformations

1. Slicing (Sub-Tensor Windowing)

Given a bounding box with start indices \(\mathbf{p} = (p_0, \dots, p_{D-1})\) and end indices \(\mathbf{e} = (e_0, \dots, e_{D-1})\): $\(\mathbf{d}'_k = e_k - p_k, \quad \mathbf{s}' = \mathbf{s}, \quad \text{offset}' = \text{offset} + \sum_{j=0}^{D-1} p_j \cdot s_j\)$ * Data bytes copied: \(0\) bytes. * Complexity: \(\mathcal{O}(D)\) metadata updates \(\approx 6\text{--}8\text{ nanoseconds}\).

2. Transposition (Axis Swapping)

To transpose dimensions \(a\) and \(b\): $\(d'_a = d_b, \quad d'_b = d_a, \quad s'_a = s_b, \quad s'_b = s_a\)$ * Data bytes copied: \(0\) bytes. * Complexity: \(\mathcal{O}(1)\) register swaps.

(Note: In contrast to an axis swap, a spatial horizontal or vertical flip reverses dimension traversal: \(s'_k = -s_k\), with \(\text{offset}' = \text{offset} + (d_k - 1) \cdot s_k\). This is why strides are signed ptrdiff_t in production systems).

3. Channel Permutation (\(HWC \to CHW\))

Permuting axis order \(\pi = (2, 0, 1)\): $\(\mathbf{d}' = (d_{\pi(0)}, d_{\pi(1)}, d_{\pi(2)}) = (C, H, W)\)$ $\(\mathbf{s}' = (s_{\pi(0)}, s_{\pi(1)}, s_{\pi(2)}) = (1, W \cdot C, C)\)$ * Data bytes copied: \(0\) bytes.


3.4 Contiguity and Coalescing

While zero-copy views provide instantaneous transformations, certain low-level hardware accelerators (e.g., DMA video controllers, BLAS GEMM kernels) require memory to be strictly contiguous (\(s_{D-1} = 1\)).

The Contiguity Invariant

A tensor \(\mathcal{T}\) of rank \(D\) is contiguous if and only if: $\(s_{D-1} = 1 \quad \text{and} \quad \forall k \in [0, D-2] \text{ such that } d_{k+1} > 1: s_k = s_{k+1} \cdot d_{k+1}\)$

Dimensions of extent \(1\) (\(d_{k+1} = 1\)) are mathematically exempt from stride multiplication, as a degenerate unit dimension does not alter memory layout contiguity.

When an algorithm encounters a non-contiguous view (such as after a slice or transposition) and requires dense sequential streaming, it invokes coalescing (rcre_tensor_contiguous), which executes a packed memory copy:

[[nodiscard]] bool rcre_tensor_is_contiguous(const RCRE_Tensor* t) {
    if (!t) return false;
    ptrdiff_t expected_stride = 1;
    for (int d = (int)t->ndim - 1; d >= 0; --d) {
        if (t->shape[d] > 1) {
            if (t->strides[d] != expected_stride) return false;
            expected_stride *= (ptrdiff_t)t->shape[d];
        }
    }
    return true;
}

3.5 C23 Bare-Metal Implementation

The foundational data structure in RCRE is RCRE_Tensor, defined in include/rcre.h:

typedef struct RCRE_Tensor {
    void*        data;            /* Pointer to base element (0, 0, ...)               */
    float*       grad;            /* Backprop buffer (training); nullptr otherwise     */
    size_t       shape[4];        /* Dimensions (rank 1 to 4)                          */
    ptrdiff_t    strides[4];      /* Signed element stride per dimension               */
    size_t       numel;           /* Cached element count (set at construction)        */
    uint8_t      ndim;            /* Rank (1 to 4)                                     */
    RCRE_DType   dtype;           /* F32, U8, I32                                      */
    RCRE_Layout  layout;          /* Spatial layout convention (HWC, CHW, Tabular)     */
    bool         is_view;         /* true: data owned elsewhere (zero-copy view)       */
    const char*  label;           /* Optional name for visualization/telemetry         */
} RCRE_Tensor;

Zero-Copy Slicing Implementation (By-Value)

Because an RCRE_Tensor metadata struct is small (80 bytes), slicing operations can return views directly by-value in CPU registers. This eliminates memory allocation overhead entirely:

[[nodiscard]] RCRE_Tensor rcre_tensor_slice(
    const RCRE_Tensor* src, const size_t* starts, const size_t* ends
) {
    RCRE_Tensor dst = {0};
    if (!src || !src->data || !starts || !ends) return dst;

    dst = *src;
    dst.is_view = true;

    size_t byte_offset = 0;
    size_t elem_size = rcre_dtype_size(src->dtype);
    size_t total_elements = 1;

    for (uint8_t i = 0; i < src->ndim; ++i) {
        if (starts[i] > ends[i] || ends[i] > src->shape[i]) {
            memset(&dst, 0, sizeof(RCRE_Tensor));
            return dst; // Invalid slice bounds
        }
        dst.shape[i] = ends[i] - starts[i];
        dst.strides[i] = src->strides[i];
        byte_offset += starts[i] * (size_t)src->strides[i] * elem_size;
        total_elements *= dst.shape[i];
    }

    dst.numel = total_elements;
    dst.data  = (uint8_t*)src->data + byte_offset;
    return dst;
}

3.6 Micro-Architectural Verification: Slicing vs. memcpy

We evaluate the CPU cycle consumption of cropping a \(256 \times 256 \times 3\) bounding box (\(196,608\text{ bytes}\)) from an active \(1080\text{p}\) image stream (\(1920 \times 1080 \times 3\)) on an Apple Silicon M5 Max core across 10,000 iterations:

Implementation Technique Execution Latency (Steady-State) Data Transferred to L1 Allocation Overhead
Traditional Deep Copy (malloc + memcpy + free) \(2,564\text{ ns}\) (p50: \(2,459\text{ ns}\))* \(196,608\text{ bytes}\) Dynamic heap lock & scan
RCRE ShapeTracker Zero-Copy View \(6.2\text{ ns}\) (p50: \(< 1\text{ ns}\)) \(0\text{ bytes}\) \(0\text{ bytes}\) (Registers / Bump)

*Note: The traditional deep copy experiences cold-cache and first-touch page commit tail latency spikes reaching up to \(20,000\text{--}55,000\text{ ns}\) (\(20\text{--}55\ \mu\text{s}\)) under allocator contention. In contrast, the ShapeTracker view exhibits negligible jitter (\(p99 \le 42\text{ ns}\)).

The ShapeTracker zero-copy view is \(\approx 420\times\text{--}630\times\) faster in steady state, completely eliminating memory bus bandwidth saturation and cache pollution.

The complete benchmark harness is runnable directly via:

make ch03_bench


3.7 Chapter Project: The Zero-Copy Matrix Transpose & Coalescer

Project Objective

Implement a general-purpose, multi-dimensional tensor view engine in rcre_tensor_view.h.

Applied Tasks

  1. Task 1: Zero-Copy Matrix Transpose — Implement rcre_tensor_transpose(RCRE_DoubleArena* arena, const RCRE_Tensor* src, size_t dim0, size_t dim1) swapping dimensions and strides in \(\mathcal{O}(1)\) time without copying buffer bytes.
  2. Task 2: Tensor Axis Permutation — Implement rcre_tensor_permute(RCRE_DoubleArena* arena, const RCRE_Tensor* src, const size_t* order) supporting arbitrary rank-\(D\) axis reorderings (e.g., \(HWC \to CHW\)).
  3. Task 3: DType-Aware Coalescer — Implement rcre_tensor_contiguous_2d(RCRE_DoubleArena* arena, const RCRE_Tensor* src) that detects whether a tensor is already contiguous via rcre_tensor_is_contiguous(). If non-contiguous, allocate a compact buffer and copy elements according to their dynamic dtype size (F32, U8, I32) in row-major order.

Grading Test: Construct a non-contiguous \(3 \times 3\) slice from a \(100 \times 100\) matrix, transpose its axes, and verify that coalescing produces identical numerical values to an exact analytical baseline. Verify rank-3 \(HWC \to CHW\) permutations and \(U8\) buffer safety under Clang AddressSanitizer and UndefinedBehaviorSanitizer with zero memory leaks.

make ch03

3.8 Where This Carries Forward: Cache Tiling in GEMM

The zero-copy strided view abstraction developed in this chapter is not merely a convenience for image cropping—it is the direct mathematical prerequisite for high-performance linear algebra.

In Chapter 4, we will discover that multiplying two matrices naively trashes the CPU cache hierarchy because column strides force non-contiguous memory accesses across disparate cache lines:

flowchart LR
    A["Flat Linear Memory (DRAM / Arena)"] --> B["RCRE_Tensor View<br/>(shape, strides, offset)"]
    B --> C["2D Strided Slice<br/>(BM x BK and BK x BN Sub-Tiles)"]
    C --> D["L1/L2 Cache-Blocked GEMM<br/>(Chapter 4 Micro-Kernel)"]

By decomposing large matrices into sub-tensor tiles using strided views, we can fit active computational operands entirely within the CPU's L1/L2 cache lines, boosting matrix multiplication throughput from \(1.7\text{ GFLOPS}\) to over \(70\text{ GFLOPS}\).


3.9 Chapter Summary

  1. Physical Reality vs. Mathematical Illusion: Physical silicon memory is strictly a flat 1D byte array. Multi-dimensional spaces (\(HWC\), \(CHW\), \(N\)-D) exist solely through the arithmetic of the generalized stride inner product: \(\text{FlatIndex}(\mathbf{i}) = \text{offset} + \langle \mathbf{i}, \mathbf{s} \rangle\).
  2. The ShapeTracker Axiom: Data copying across the system memory bus wastes time, burns power, and evicts valuable cache lines. Transforming views (slicing, transposing, permuting) must be \(\mathcal{O}(1)\) metadata transformations.
  3. Signed Strides: Representing strides as signed integers (ptrdiff_t) enables negative indexing, instantly supporting spatial reflections and reverse scans without dedicated kernels.
  4. The Contiguity Invariant: A tensor is contiguous if and only if \(s_{D-1} = 1\) and \(s_k = s_{k+1} \cdot d_{k+1}\) for all dimensions with extent \(d_{k+1} > 1\).
  5. Selective Coalescing: Only when a hardware unit strictly requires contiguous physical memory (e.g., DMA ingestion or packed GEMM) should a strided view be materialized into a compact buffer.

3.10 Exercises

  • Exercise 3.1: Stride Derivation for Audio & Video: Compute the canonical shape and stride vectors for a 10-second stereo audio stream sampled at \(44.1\text{ kHz}\) in 32-bit floating point, both for interleaved format [Samples, Channels] and planar format [Channels, Samples].
  • Exercise 3.2: Spatial Flip Arithmetic: Derive the mathematical formula for a vertical image flip (reversing the height axis \(H\)) given an input tensor with shape \((H, W, C)\) and strides \((s_0, s_1, s_2)\). Prove that the operation requires \(0\) byte copies and consumes \(\mathcal{O}(1)\) time.
  • Exercise 3.3: 4D Batch Broadcasting: In deep learning inference, a single 1D bias vector of shape \((C,)\) is added to a 4D feature map of shape \((N, H, W, C)\). How can stride arithmetic implement broadcasting such that the bias vector appears as shape \((N, H, W, C)\) with zero memory duplication? (Hint: What happens if a dimension's stride is set to \(0\)?)
  • Exercise 3.4: Cache Penalty of Non-Contiguous Iteration: Write a micro-benchmark iterating through a \(2048 \times 2048\) matrix along column-major order (stride \(= 2048\)) versus row-major order (stride \(= 1\)). Measure the throughput difference with hardware performance counters.