Overview #

If you are building a Terminal UI, an image processor in Rust, or some other program where you are going to need a 2D data structure to represent the screen or grid, this tutorial will walk you through using a 2D array vs a 1D flat version of the same structure using SIMD and leveraging the CPU’s L1 cache. We will explore the performance implications of how you structure this 2D data in memory by comparing these approaches.

Here are some useful links for context:

  1. Rust standard library: Vec
  2. Data-Oriented Design
  3. SIMD in Rust

Quick Summary for Developers #

  1. Goal:
    • Build a high-performance 2D array data structure in Rust suitable for tasks like UI compositing.
  2. Key Challenge:
    • The immediate approach of using Vec<Vec<T>> introduces multiple heap allocations scattered randomly in memory. This leads to terrible CPU cache locality and massive pipeline stalls during iteration.
    • While using a flat 1D array (Box<[T]>) solves the cache locality problem, simple mathematical coordinate transformations (modulo and division) can still stall the CPU pipeline when iterating over the grid.
  3. Solution:
    • Use a flat 1D array to guarantee contiguous memory layout and perfect L1 cache utilization.
    • Unlock SIMD auto-vectorization and raw pointer operations using .fill() for clearing, .copy_within() for scrolling, and .chunks_exact(cols) for rendering, completely avoiding slow division operations.
  4. What You’ll Get:
    • A highly performant 2D array implementation with flatline consistent frame times, offering significant speedups (e.g., 2.3x for reading/rendering, and up to 39.0x for memory size calculations).

Project Setup #

In this tutorial, we are going to build a high-performance 2D array in Rust. Before we dive into the code, let’s scaffold our project and enable the nightly toolchain so we can run micro-benchmarks later to prove all our hypotheses and theory. It is important to measure performance impact rather than rely on intuition.

As Amdahl’s Law teaches us, the overall speedup of our program is strictly limited by the fraction of time spent in the code we are optimizing. We use micro-benchmarks to ensure that iterating our 2D array is actually the bottleneck worth attacking, rather than “optimizing” based on intuition.

# Create a temp folder for this, or choose where you would like to create your project.
cd (mktemp -d)
cargo new --lib flat2darray
cd flat2darray
rustup override set nightly
cargo add r3bl_tui

We don’t need any external dependencies, so Cargo.toml is good to go. We just need to configure our lib.rs to enable the benchmarking features and expose our modules.

pub mod vec_2d_array;

The Simple Approach #

The immediate, simple approach almost everyone takes is a “Vec of Vecs”, creating a Vec2DArray struct.

use r3bl_tui::{ColWidth, RowHeight};

pub struct Vec2DArray<T: Clone> {
    pub data: Vec<Vec<T>>,
    pub rows: RowHeight,
    pub cols: ColWidth,
}

To manipulate this grid, we need a few standard methods. Let’s ground them in a real-world Terminal UI use case:

  1. Iterate: We need to traverse the grid cell-by-cell to render it to the terminal.
  2. Diffing: We need to compare the old frame buffer with the new frame buffer to only redraw pixels that changed.
  3. Clearing: We need to wipe all cells in the grid to handle a “clear screen” command.
  4. Scrolling: We need to shift terminal history up by moving rows when a new line is printed at the bottom.

Here’s how we might implement these scalar methods, along with a .get_mem_size() method to calculate heap allocation size, and some unit tests:

impl<T: Copy + PartialEq + std::fmt::Debug> Vec2DArray<T> {
    pub fn new(rows: RowHeight, cols: ColWidth, default_val: T) -> Self {
        Self {
            data: vec![vec![default_val; cols.as_usize()]; rows.as_usize()],
            rows,
            cols,
        }
    }

    pub fn get(&self, row: usize, col: usize) -> &T {
        &self.data[row][col]
    }

    pub fn clear(&mut self, default_val: T) {
        let rows_usize = self.rows.as_usize();
        let cols_usize = self.cols.as_usize();
        for row in 0..rows_usize {
            for col in 0..cols_usize {
                self.data[row][col] = default_val.clone();
            }
        }
    }

    /// Scrolls the grid up by one row.
    ///
    /// # Logic
    /// Because `self.data` is a `Vec<Vec<T>>`, we don't actually need
    /// to copy the underlying elements. We can simply rotate the `Vec`
    /// of row pointers! `rotate_left(1)` moves the first row to the
    /// end, and shifts all other row pointers up by 1. This is extremely
    /// fast because it only moves memory pointers, not the actual items
    /// in the rows.
    ///
    /// # ASCII Diagram
    /// ```text
    /// Before:         After:
    /// [ Row 0 ]       [ Row 1 ]  <-- Shifted up
    /// [ Row 1 ]  ==>  [ Row 2 ]
    /// [ Row 2 ]       [ Row 2 ]  <-- Duplicated from above
    /// ```
    pub fn scroll_up(&mut self) {
        if !self.data.is_empty() {
            self.data.rotate_left(1);
            let len = self.data.len();
            if len > 1 {
                // After rotation, the old top row is now at the bottom.
                // To mimic `copy_within` (where the last row is left
                // untouched and thus duplicated), we overwrite this new
                // bottom row with a clone of the row just above it.
                self.data[len - 1] = self.data[len - 2].clone();
            }
        }
    }

    pub fn diff(&self, other: &Self) -> Vec<(usize, usize)> {
        let mut changes = Vec::new();
        let rows_usize = self.rows.as_usize();
        let cols_usize = self.cols.as_usize();
        for row in 0..rows_usize {
            for col in 0..cols_usize {
                if self.data[row][col] != other.data[row][col] {
                    changes.push((row, col));
                }
            }
        }
        changes
    }

    pub fn get_mem_size(&self) -> usize {
        // Struct.
        let mut total = std::mem::size_of::<Self>();

        // Vec<_>.
        let num_of_rows = self.data.capacity();
        total += num_of_rows * {
            let size_of_a_row = std::mem::size_of::<Vec<T>>();
            size_of_a_row
        };

        // Vec<T> for each row (containing the columns / cells).
        for row in &self.data {
            total += row.capacity() * std::mem::size_of::<T>();
        }

        total
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_vec_2d_array() {
        let mut grid = Vec2DArray::new(
            RowHeight::from(5), ColWidth::from(10), 0);

        // 1. Test clear & get
        grid.clear(1);
        assert_eq!(*grid.get(0, 0), 1);

        // 2. Test diff
        let mut other = Vec2DArray::new(
            RowHeight::from(5), ColWidth::from(10), 1);
        other.data[0][0] = 5;
        let changes = grid.diff(&other);
        assert_eq!(changes.len(), 1);
        assert_eq!(changes[0], (0, 0));

        // 3. Test scroll_up
        grid.data[0][0] = 9; // Top row, col 0
        grid.data[1][0] = 8; // Second row, col 0
        grid.scroll_up();
        // Second row should now be shifted to the top
        assert_eq!(*grid.get(0, 0), 8);

        // 4. Test memory size calculation
        assert!(grid.get_mem_size() > 0);
    }
}

But there is a major performance catch here. A Vec<Vec<T>> is terrible for iteration because it requires multiple heap allocations scattered randomly in memory. This destroys CPU cache locality. Because the CPU’s Hardware Prefetcher can’t predict where the next row is, the pipeline suffers massive stalls—wasting up to 300 clock cycles fetching from slow RAM instead of the 1 to 4 cycles it takes to read from the L1 Cache. By the end of this post, we’ll see exactly how much performance is lost with real benchmarks.

But don’t throw away Vec<Vec<T>> entirely! I’ll also show you one surprisingly elegant trick where Vec2DArray actually wins: scrolling. Because it’s an array of pointers, we can use rotate_left(1) to scroll the screen by just shifting pointers, which is lightning fast compared to moving contiguous bytes.

For more info, read the production code on which this tutorial is based in the r3bl-open-core repo.

The 1D Solution #

First, let’s expose our new module in src/lib.rs:

pub mod flat_2d_array;

The solution is to flatten our 2D grid into a single, contiguous 1D array using Box<[T]>.

Why does this matter? Let’s look at the memory layout.

# Vec<Vec<T>> (Scattered Heap Memory):

[Ptr] -> [Ptr, Ptr, Ptr]
        |    |    |
        v    v    v
    [Row1] [Row2] [Row3]  <-- Cache Misses!

Box<[T]> (Contiguous Memory):
[Ptr] -> [Row1 | Row2 | Row3] <-- Perfect L1/L2 Cache Hits!

By guaranteeing a single contiguous memory allocation, the CPU’s Hardware Prefetcher can effortlessly pull data from RAM into the L1 Cache in perfect 64-byte chunks, known as Cache Lines. To access any coordinate, we just use simple math: (row, col) -> index = row * cols + col.

# 2D to 1D Mapping

The grid is stored row-by-row in a flat 1D slice.

To find the element at `(row, col)`, we skip `row` full rows of size `width`,
and then step forward by `col`.

        col 0   col 1   col 2
      ┌───────┬───────┬───────┐
row 0 │ idx 0 │ idx 1 │ idx 2 │  ← row_offset = 0 * 3 = 0
      ├───────┼───────┼───────┤
row 1 │ idx 3 │ idx 4 │ idx 5 │  ← row_offset = 1 * 3 = 3
      ├───────┼───────┼───────┤
row 2 │ idx 6 │ idx 7 │ idx 8 │  ← row_offset = 2 * 3 = 6
      └───────┴───────┴───────┘

Example: `(row 1, col 2)`
- `row_offset = 1 * 3 = 3`
- `final_index = 3 + 2 = 5`

Conversely, we also need to be able to map a flat 1D index back to its 2D coordinates. Here is a diagram illustrating the math behind that reverse mapping:

# 1D to 2D Mapping

This is the exact inverse of the above. It is primarily used
during SIMD fast-path diffing, where the algorithm iterates linearly over the
1D slice, finds a difference at a specific 1D `index`, and needs to know the
corresponding `(row, col)` coordinate to issue a terminal cursor movement
command.

```text
        col 0   col 1   col 2
      ┌───────┬───────┬───────┐
row 0 │ idx 0 │ idx 1 │ idx 2 │
      ├───────┼───────┼───────┤
row 1 │ idx 3 │ idx 4 │ idx 5 │  ← index_to_pos(5)
      ├───────┼───────┼───────┤    = Pos { row: 1, col: 2 }
row 2 │ idx 6 │ idx 7 │ idx 8 │
      └───────┴───────┴───────┘
```

Example: `index 5` with `width 3`
- `row = index / width = 5 / 3 = 1`
- `col = index % width = 5 % 3 = 2`

Here’s the implementation for the Flat2DArray struct, along with scalar methods and tests:

use r3bl_tui::{ColWidth, RowHeight};

pub struct Flat2DArray<T: Clone> {
    pub data: Box<[T]>,
    pub rows: RowHeight,
    pub cols: ColWidth,
}

impl<T: Copy + PartialEq + std::fmt::Debug> Flat2DArray<T> {
    pub fn new(rows: RowHeight, cols: ColWidth, default_val: T) -> Self {
        let size = rows.as_usize() * cols.as_usize();
        Self {
            data: vec![default_val; size].into_boxed_slice(),
            rows,
            cols,
        }
    }

    pub fn get(&self, row: usize, col: usize) -> &T {
        &self.data[row * self.cols.as_usize() + col]
    }

    pub fn clear(&mut self, default_val: T) {
        let cols_usize = self.cols.as_usize();
        let rows_usize = self.rows.as_usize();
        for row in 0..rows_usize {
            for col in 0..cols_usize {
                self.data[row * cols_usize + col] = default_val.clone();
            }
        }
    }

    pub fn scroll_up(&mut self) {
        let cols_usize = self.cols.as_usize();
        let rows_usize = self.rows.as_usize();
        for row in 0..rows_usize - 1 {
            for col in 0..cols_usize {
                let src_idx = (row + 1) * cols_usize + col;
                let dest_idx = row * cols_usize + col;
                self.data[dest_idx] = self.data[src_idx].clone();
            }
        }
    }

    pub fn diff(&self, other: &Self) -> Vec<(usize, usize)> {
        let mut changes = Vec::new();
        let cols_usize = self.cols.as_usize();
        let rows_usize = self.rows.as_usize();
        for row in 0..rows_usize {
            for col in 0..cols_usize {
                let idx = row * cols_usize + col;
                if self.data[idx] != other.data[idx] {
                    changes.push((row, col));
                }
            }
        }
        changes
    }

    pub fn print_screen(&self) {
        let cols_usize = self.cols.as_usize();
        for (index, item) in self.data.iter().enumerate() {
            let row = index / cols_usize;
            let col = index % cols_usize;
            print!("[{}][{}]-{:?} ", row, col, item);
        }
        println!();
    }

    pub fn get_mem_size(&self) -> usize {
        let mut total = std::mem::size_of::<Self>();
        total += self.data.len() * std::mem::size_of::<T>();
        total
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_flat_2d_array() {
        let mut grid = Flat2DArray::new(
            RowHeight::from(5), ColWidth::from(10), 0);

        // 1. Test clear & get
        grid.clear(1);
        assert_eq!(*grid.get(0, 0), 1);

        // 2. Test diff
        let mut other = Flat2DArray::new(
            RowHeight::from(5), ColWidth::from(10), 1);
        other.data[0] = 5; // index 0 is (row 0, col 0)
        let changes = grid.diff(&other);
        assert_eq!(changes.len(), 1);
        assert_eq!(changes[0], (0, 0));

        // 3. Test scroll_up
        grid.data[0] = 9;  // Top row, col 0
        grid.data[10] = 8; // Second row, col 0 (since width is 10)
        grid.scroll_up();
        // Second row should now be shifted to the top
        assert_eq!(*grid.get(0, 0), 8);

        // 4. Test memory size calculation
        assert!(grid.get_mem_size() > 0);

        // 5. Test print_screen
        grid.print_screen();
    }
}

The 2D Iteration Trap #

But wait, there is a trap here: The Math Pipeline Stall Problem. What if we need to iterate over the whole grid, but we still need to know our (row, col) coordinates to know where to draw them? This is a common scenario in a Terminal UI, where we need to render each pixel at its correct position (row and col) on the terminal emulator screen by writing an ANSI escape sequence to stdout.

The simple way to iterate our flat array looks like what we see in print_screen above.

The trap is that division (/) and modulo (%) are extremely slow for the CPU. Now, if our grid cols was a guaranteed compile-time constant and a perfect power of two—like 128—the compiler is smart. It optimizes the math into lightning-fast bitshifts:

// Compiler optimization if cols is a hardcoded 128 (2^7):
let row = index >> 7;
let col = index & 127;

But here is the catch: In a Terminal UI, the columns count is almost never a power of two, and it’s a runtime variable because the user can resize their window at any time (for example, to 113 columns). Because the compiler doesn’t know this number at compile time, it cannot use the bitshift trick. It is forced to emit actual, slow division instructions to the CPU for every single pixel, causing significant pipeline stalls.

Unlocking SIMD & Raw Memory Operations #

So how do we fix it? We follow two simple rules of thumb for 1D memory access to replace those slow scalar loops.

Rule 1: If you DON’T care about 2D coordinates. Let’s say you just need to clear the screen or scroll memory. You don’t need chunks. Just blast through the entire raw 1D slice using .fill() for instant clearing.

    pub fn simd_clear(&mut self, default_val: T) {
        self.data.fill(default_val);
    }

Because it’s an uninterrupted memory block, LLVM aggressively auto-vectorizes this into SIMD instructions. These instructions pull data from the L1 Cache into massive 32-byte or 64-byte AVX registers—perfectly matching the 64-byte Cache Lines pulled from RAM!

If your array is larger than a SIMD register, LLVM handles the magic: it creates a highly optimized loop, chunks the data, unrolls the loop to keep the CPU pipeline saturated, and generates a “scalar tail” to clean up any leftover bytes.

For scrolling, we use .copy_within(), which maps directly to highly optimized std::ptr::copy instructions for zero-allocation memmoves. However, as we’ll see in the benchmarks, this is actually one scenario where Vec2DArray beats the Flat Array, simply because shifting memory pointers is faster than copying actual contiguous bytes!

    pub fn simd_scroll_up(&mut self) {
        let row_size = self.cols.as_usize();
        self.data.copy_within(row_size.., 0);
    }

Rule 2: If you DO care about 2D coordinates. Let’s say you’re rendering or diffing rows. The silver bullet here is .chunks_exact(cols).

    pub fn simd_diff(&self, other: &Self) -> Vec<(RowHeight, ColWidth)> {
        let mut changes = Vec::new();
        let cols_usize = self.cols.as_usize();

        let zipped = self
            .data
            .chunks_exact(cols_usize)
            .zip(other.data.chunks_exact(cols_usize));

        for (row_idx, (row, other_row)) in zipped.enumerate() {
            if row != other_row {
                for (col_idx, (item, other_item)) in
                    row.iter().zip(other_row.iter()).enumerate() {
                        if item != other_item {
                            changes.push((
                                RowHeight::from(row_idx),
                                ColWidth::from(col_idx)));
                        }
                }
            }
        }
        changes
    }

    pub fn simd_print_screen(&self) {
        let cols_usize = self.cols.as_usize();
        for (row_idx, row_chunk) in
            self.data.chunks_exact(cols_usize).enumerate() {
                for (col_idx, item) in row_chunk.iter().enumerate() {
                    print!("[{}][{}]-{:?} ", row_idx, col_idx, item);
                }
        }
        println!();
    }

Under the hood, this doesn’t use division. It uses pure pointer addition. It just adds cols to the memory pointer for each row, completely bypassing the Math Pipeline Stall. Fast diffing becomes incredibly simple and fast by zipping the chunks together.

Proving it with Benchmarks #

We’ve implemented both Vec2DArray and Flat2DArray. Let’s look at the benchmarks. To run cargo bench, we first need to configure lib.rs:

// We need this for cargo bench to work.
#![cfg_attr(test, feature(test))]

#[cfg(test)]
mod benches;

And then we setup src/benches.rs:

extern crate test;

use test::{black_box, Bencher};
use crate::vec_2d_array::Vec2DArray;
use crate::flat_2d_array::Flat2DArray;
use r3bl_tui::PixelChar;

const WIDTH: usize = 200;
const HEIGHT: usize = 100;

Crucial Point: First, before we even look at average speed, look at the Margin of Error. Vec2DArray suffers from massive variance—sometimes swinging by ±98%—because its performance relies entirely on lucky CPU cache placement for scattered heap allocations. Flat2DArray guarantees perfectly consistent, flatline frame times. In a UI, eliminating those micro-stutters is just as important as raw speed!

Let’s validate our theories across 5 groups of operations.

1. Clear Screen # 

#[bench]
fn group_1_clear_screen_legacy(b: &mut Bencher) {
    let mut grid = Vec2DArray::new(
        RowHeight::from(HEIGHT), ColWidth::from(WIDTH), PixelChar::Spacer);
    b.iter(|| {
        grid.clear(black_box(PixelChar::Void));
    });
}

#[bench]
fn group_1_clear_screen_flat_simd(b: &mut Bencher) {
    let mut grid = Flat2DArray::new(
        RowHeight::from(HEIGHT), ColWidth::from(WIDTH), PixelChar::Spacer);
    b.iter(|| {
        grid.simd_clear(black_box(PixelChar::Void));
    });
}

A pure 1D .fill() is consistently faster than a scalar row-by-row clear loop, giving us a 1.4x speedup.

2. Scroll Screen # 

#[bench]
fn group_2_scroll_screen_legacy(b: &mut Bencher) {
    let mut grid = Vec2DArray::new(
        RowHeight::from(HEIGHT), ColWidth::from(WIDTH), PixelChar::Spacer);
    b.iter(|| {
        grid.scroll_up();
    });
}

#[bench]
fn group_2_scroll_screen_flat_simd(b: &mut Bencher) {
    let mut grid = Flat2DArray::new(
        RowHeight::from(HEIGHT), ColWidth::from(WIDTH), PixelChar::Spacer);
    b.iter(|| {
        grid.simd_scroll_up();
    });
}

This is the one rare case where the simple Vec2DArray might actually win! Because the simple approach uses rotate_left(1) to just shift pointer addresses instead of copying actual contiguous bytes, it is extremely fast. That’s a very neat tradeoff: the simple 2D Vec is great for row-swapping pointer operations, but it suffers cache misses on traversal. The Flat 1D Array (.copy_within()) has to move the actual memory bytes, but it rules at rendering and cache-locality!

3. Read Screen / Compositing # 

#[bench]
fn group_3_read_screen_legacy(b: &mut Bencher) {
    let grid = Vec2DArray::new(
        RowHeight::from(HEIGHT), ColWidth::from(WIDTH), PixelChar::Spacer);
    b.iter(|| {
        for row in 0..HEIGHT {
            for col in 0..WIDTH {
                let _ = black_box(grid.get(row, col));
            }
        }
    });
}

#[bench]
fn group_3_read_screen_flat_simd(b: &mut Bencher) {
    let grid = Flat2DArray::new(
        RowHeight::from(HEIGHT), ColWidth::from(WIDTH), PixelChar::Spacer);
    b.iter(|| {
        for item in grid.data.iter() {
            let _ = black_box(item);
        }
    });
}

Here is The Rendering Problem. The first two tests were for writing memory. But when the compositor tries to read the screen, linearly streaming flat memory into the L1 cache completely destroys nested vector heap-chasing, which constantly causes cache misses. We see a massive 2.3x speedup.

4. Memory Overhead # 

#[bench]
fn group_4_memory_size_legacy(b: &mut Bencher) {
    let grid = Vec2DArray::new(
        RowHeight::from(HEIGHT), ColWidth::from(WIDTH), PixelChar::Spacer);
    b.iter(|| {
        black_box(grid.get_mem_size());
    });
}

#[bench]
fn group_4_memory_size_flat(b: &mut Bencher) {
    let grid = Flat2DArray::new(
        RowHeight::from(HEIGHT), ColWidth::from(WIDTH), PixelChar::Spacer);
    b.iter(|| {
        black_box(grid.get_mem_size());
    });
}

Calculating the size of Vec<Vec<T>> has massive pointer-chasing overhead, while Box<[T]> is near-instantaneous. A whopping 39.0x speedup!

5. The 3-Step Performance Staircase # 

#[bench]
fn group_5_2d_traversal_modulo(b: &mut Bencher) {
    let grid = Flat2DArray::new(
        RowHeight::from(HEIGHT), ColWidth::from(WIDTH), PixelChar::Spacer);
    b.iter(|| {
        for (idx, item) in grid.data.iter().enumerate() {
            let row = idx / WIDTH;
            let col = idx % WIDTH;
            let _ = black_box((row, col, item));
        }
    });
}

#[bench]
fn group_5_2d_traversal_chunks_exact(b: &mut Bencher) {
    let grid = Flat2DArray::new(
        RowHeight::from(HEIGHT), ColWidth::from(WIDTH), PixelChar::Spacer);
    b.iter(|| {
        for (row_idx, chunk) in grid.data.chunks_exact(WIDTH).enumerate() {
            for (col_idx, item) in chunk.iter().enumerate() {
                let _ = black_box((row_idx, col_idx, item));
            }
        }
    });
}

This proves the Math Pipeline Stall theory. We benchmarked 3 traversal methods head-to-head to prove the 1.8x speedup.

1. Vec2DArray  (Scalar) - Slowest (Cache Misses & Modulo Math)
2. Flat2DArray (Scalar) - Fast (Cache Hits! But Modulo Math stalls)
3. Flat2DArray (SIMD)   - Fastest (Cache Hits & pure pointer addition!)

Note on primitive types #

The benchmarks above were executed using a multi-byte struct representing a colored terminal pixel. When the grid relies on simple primitive integers (such as a usize), LLVM can optimize the SIMD operations more aggressively. In our tests, clearing the screen with primitive types resulted in up to a 60,000x speedup.

By flattening the 2D array, leveraging SIMD, and ensuring contiguous memory allocation, we can significantly reduce CPU pipeline stalls and improve overall traversal performance.

The CPU Cache & Hardware Prefetching #

To understand why Flat2DArray is so fast, you must understand how data travels from your RAM to the CPU. Data does not travel 1 byte at a time; it is transferred in exact 64-byte blocks (on modern x86 CPUs) called Cache Lines (you can verify this on x86 CPUs by running getconf LEVEL1_DCACHE_LINESIZE on Linux).

When your code asks for a memory address, the memory controller fetches a 64-byte Cache Line from RAM and places it into the CPU’s L1 Cache. The CPU Registers (where the actual math happens) are fed exclusively from this L1 Cache.

The Hardware Prefetcher (The Conveyor Belt): Modern CPUs have a dedicated circuit called the Hardware Prefetcher. When you iterate over a contiguous slice of memory (like Flat2DArray), the Hardware Prefetcher detects that you are moving forward in a straight line. Before your code even asks for the next block of memory, the Hardware Prefetcher secretly reaches out to RAM, grabs the next 64-byte Cache Line, and places it into the L1 Cache. This turns the L1 Cache into a high-speed conveyor belt, ensuring the CPU never has to wait for data (zero Cache Misses).

The Fragmentation Penalty: If we had used nested vectors (Vec<Vec<T>>) we would incur a hardware penalty. Because vectors are allocated randomly on the heap, Row 0 and Row 1 were not physically next to each other in RAM. The Hardware Prefetcher could not predict where the next row would be, causing it to guess wrong. The CPU would suffer a massive Cache Miss for every single row.

To quantify this penalty (using an Intel i7-14700 as an example):

  • L1 Cache Hit (~32 KB size): ~1-4 clock cycles
  • L2 Cache Hit (~4 MB size): ~10-15 clock cycles
  • L3 Cache Hit (~33 MB size): ~40-70 clock cycles
  • Main RAM Fetch (Cache Miss): ~200-300+ clock cycles

The CPU pipeline would suffer a stall, wasting ~300 clock cycles per row while it waited for the memory controller to fetch data from slow RAM.

How SIMD Vectorization Works #

SIMD (Single Instruction, Multiple Data) is a CPU feature that allows the processor to perform the same mathematical operation on multiple data points simultaneously. SIMD acts as the engine that consumes the L1 Cache conveyor belt.

We do not have to write raw Assembly or use std::simd to trigger this. Instead, we rely on LLVM Auto-vectorization. Because our 2D vector is now a flat, contiguous 1D array, we can use built-in Rust slice operations. LLVM recognizes these operations and automatically injects AVX/NEON instructions. These SIMD instructions operate on specialized, ultra-wide CPU registers that are 256-bit (32 bytes) or 512-bit (64 bytes) wide. Because these registers are perfectly aligned with the 64-byte Cache Lines sitting in the L1 Cache, they can consume and process massive blocks of data in a single clock cycle.

If the array is larger than the SIMD register (which it almost always is), LLVM automatically generates a highly optimized loop. It chunks the array into 32-byte or 64-byte blocks, unrolls the loop to keep the CPU pipeline saturated, and generates a “scalar tail” to clean up any leftover bytes at the end that don’t divide perfectly into the register size.

Here are the exact triggers we use to unlock SIMD:

  1. slice::fill (SIMD): Used when clearing the screen (e.g., Flat2DArray::new_empty) to instantly blast empty spacer characters across memory.
  2. slice::copy_within (SIMD): Used when scrolling by the virtual terminal tab, e.g., Flat1DSimdMut::copy_within_rows, or when shifting characters left/right during text insertion.
  3. Iterator::zip (SIMD): During the diffing phase, LLVM vectorizes the equality checks of two contiguous slices, allowing it to rapidly jump over massive blocks of identical characters.

Rule of Thumb for 1D vs 2D Memory Iteration #

  1. If you DON’T care about 2D coordinates (e.g., just clearing the whole screen, or finding the first occurrence of a character): You don’t even need chunks. Just blast through the entire raw 1D slice (.iter(), .fill(), etc.). LLVM will aggressively vectorize this into SIMD instructions because it’s just one massive, uninterrupted block of memory.

  2. If you DO care about 2D coordinates (e.g., diffing rows, tracking col_index, or knowing when a line ends): .chunks_exact(width) is the key.

    • The Math Pipeline Stall Problem (The Slow Way). The simple approach uses division (/) and modulo (%) to calculate coordinates from a 1D index (e.g., row = index / width, col = index % width). In the computer world, division and modulo are extremely slow mathematical operations. If your width was a fixed number like 8 or 16 (powers of 2), the compiler could use a lightning-fast bitshift. But because terminal widths vary at runtime (e.g., 113 columns), the compiler cannot optimize this. The CPU is forced to stop and wait for the math to finish for every single character on the screen, causing massive CPU pipeline stalls.

    • The Chunks Exact Solution (The Fast Way). By slicing the array into rows via .chunks_exact(width), you walk down the chunks and their items (e.g., for (row_idx, chunk) and for (col_idx, item)). Under the hood, .chunks_exact(width) doesn’t calculate 2D coordinates from a 1D index using division. Instead, it uses simple pointer addition. For example, if the terminal is 113 columns wide, the outer loop just adds 113 to the memory pointer for each row. The inner loop adds 1 to the pointer for each column. Because addition takes 1 clock cycle (unlike division, which takes many), 113 becomes just as fast for the CPU to process as a power of 2 like 128. You get logical 2D row boundaries to write easy-to-understand code, while the LLVM compiler sees a predictable contiguous memory layout. It will happily unroll that double loop and vectorize the inner slice comparisons into SIMD instructions—all while completely bypassing the slow CPU pipeline stalls.

#cli #cs #rust
👀 Watch Rust 🦀 live coding videos on our YouTube Channel.



📦 Install our useful Rust command line apps using cargo install r3bl-cmdr (they are from the r3bl-open-core project):
  • 🐱giti: run interactive git commands with confidence in your terminal
  • 🦜edi: edit Markdown with style in your terminal

giti in action

edi in action

Related Posts