Build High-Performance Flat 2D Arrays in Rust (SIMD, L1 Cache) | developerlife.com

page_cursor.exclude = nil--><br>page.exclude = nil--><br>page.title = "Build High-Performance Flat 2D Arrays in Rust (SIMD, L1 Cache)"--><br>page.category = nil--><br>page.title (json) = Build High-Performance Flat 2D Arrays in Rust (SIMD, L1 Cache)--><br>page.category (json) = -->

Overview

YouTube video for this article

Quick Summary for Developers

Project Setup

The Simple Approach

The 1D Solution

Ergonomic Array Access (Index and IndexMut)

The 2D Iteration Trap

Unlocking SIMD & Raw Memory Operations

Proving it with Benchmarks

1. Clear Screen

2. Scroll Screen

3. Read Screen / Compositing

4. Memory Overhead

5. The 3-Step Performance Staircase

Note on primitive types

The CPU Cache & Hardware Prefetching

How [SIMD] Vectorization Works

Rule of Thumb for 1D vs 2D Memory Iteration

Overview #

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

Here are some useful links for context:

Rust standard library: Vec

Data-Oriented Design

SIMD in Rust

YouTube video for this article #

If you like to learn via video, please watch the companion video on the developerlife.com<br>YouTube channel where I live code all the<br>examples from scratch. You can follow along there, step by step if you like, in addition<br>to this article and repo.

The simplified code built in the video and this tutorial is available in the rust-scratch GitHub repo.<br>The full production-ready implementation lives in the r3bl-open-core repo.

Quick Summary for Developers #

Goal:

Build a high-performance 2D array data structure in Rust suitable for tasks like UI<br>compositing.

Key Challenge:

The immediate approach of using Vec> introduces multiple heap allocations<br>scattered randomly in memory. This leads to terrible CPU cache locality and massive<br>pipeline stalls during iteration.

While using a flat 1D array (Box) solves the cache locality problem, simple<br>mathematical coordinate transformations (modulo and division) can still stall the<br>CPU pipeline when iterating over the grid.

Solution:

Use a flat 1D array to guarantee contiguous memory layout and perfect L1 cache<br>utilization.

Unlock SIMD auto-vectorization and raw pointer operations using .fill() for<br>clearing, .copy_within() for scrolling, and .chunks_exact(cols) for rendering,<br>completely avoiding slow division operations.

What You’ll Get:

A highly performant 2D array implementation with flatline consistent frame times,<br>offering significant speedups (e.g., 2.3x for reading/rendering, and up to 39.0x for<br>memory size calculations).

Project Setup #

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

As Amdahl’s Law teaches us, the overall<br>speedup of our program is strictly limited by the fraction of time spent in the code we<br>are optimizing. We use micro-benchmarks to ensure that iterating our 2D array is actually<br>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.<br>cd (mktemp -d)<br>cargo new --lib flat2darray<br>cd flat2darray<br>rustup override set nightly<br>cargo add r3bl_tui

We don’t need any external dependencies, so Cargo.toml is good to go. We just need to<br>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<br>Vec2DArray struct.

use r3bl_tui::{ColWidth, RowHeight};

pub struct Vec2DArrayT: Clone> {<br>pub data: VecVecT>>,<br>pub rows: RowHeight,<br>pub cols: ColWidth,

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

Iterate : We need to traverse the grid cell-by-cell to render it to the terminal.

Diffing : We need to compare the old frame buffer with the new frame buffer to only<br>redraw pixels that changed.

Clearing : We need to wipe all cells in the grid to handle a “clear screen” command.

Scrolling : We need to shift terminal history up by moving rows when a new line is<br>printed at the bottom.

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

implT: Copy + PartialEq + std::fmt::Debug> Vec2DArrayT> {<br>pub fn new(rows: RowHeight, cols: ColWidth, default_val: T)...