Contiguous Memory & Dynamic Arrays: Why CPU Cache Locality Beats Theoretical Asymptotics

In CS 101, I teach my university students that inserting into or deleting from the middle of an array is an $O(n)$ operation. In my systems architecture consulting, I tell senior engineers to use contiguous arrays anyway. Here is why modern CPU hardware rewrites the textbook rules.

---

Every fall semester, around week two of Data Structures and Algorithms, I draw a clean grid of contiguous boxes on the lecture hall whiteboard. We derive why looking up an element by index in an array is $O(1)$, while shifting elements to insert or delete at an arbitrary position costs $O(n)$ linear time.

Naturally, bright students conclude: "Professor, if arrays cost $O(n)$ to grow or shift, shouldn't we use linked structures whenever our data changes?"

On a purely mathematical Turing machine where every memory access costs the exact same unit of time, that intuition is spot-on. Put that same assumption into a modern cloud server, browser engine, or high-frequency trading system, however, and your performance can degrade by an order of magnitude.

To understand why Dynamic Arrays (std::vector in C++, ArrayList in Java, Vec<T> in Rust, and TypedArrays/dense arrays in V8 JavaScript) are the undisputed workhorses of modern software development, we have to bridge two worlds: asymptotic complexity theory and silicon hardware reality.

---

1. The Academic Foundation: Contiguous Address Arithmetic

In university computer science curricula, an Array is defined as a homogeneous collection of elements stored in contiguous memory locations.

When you allocate an array of 32-bit (4-byte) integers starting at a base memory address $B$ (which you can convert between hexadecimal, binary, and decimal representations using our Base Converter), the CPU does not scan through elements to find index $i$. Instead, it executes a single hardware multiply-add instruction:

$$\text{Address}(A[i]) = B + (i \times \text{sizeof}(\text{Element}))$$

flowchart LR
    subgraph RAM["Contiguous Virtual Memory Block (Base = 0x1000, Element Size = 4 Bytes)"]
        direction LR
        A0["Index 0<br/>Addr: 0x1000<br/>Val: 42"] --> A1["Index 1<br/>Addr: 0x1004<br/>Val: 88"]
        A1 --> A2["Index 2<br/>Addr: 0x1008<br/>Val: 15"]
        A2 --> A3["Index 3<br/>Addr: 0x100C<br/>Val: 91"]
        A3 --> A4["Index 4<br/>Addr: 0x1010<br/>Val: 63"]
    end

Because this formula takes constant time regardless of whether $i = 0$ or $i = 10,000,000$, random access is strictly $O(1)$.

The Dynamic Resizing Paradox: How $O(n)$ Becomes Amortized $O(1)$

Static arrays have a fatal flaw: their capacity is fixed at allocation time. To build a Dynamic Array that grows on demand, we allocate an underlying buffer with capacity $C$, track the current logical length $n$, and double the capacity ($C \leftarrow 2C$) whenever $n = C$.

In lecture halls, we prove why appending $n$ elements to a geometric dynamic array does not cost $O(n^2)$, using the Aggregate Method of Amortized Analysis:

• Most push() operations simply write to buffer[length] and increment length, costing $1$ unit of work.
• A resize copy only triggers when $n$ is a power of $2$ ($1, 2, 4, 8, \dots, 2^k$).
• Across $n$ insertions, the total number of element copies is bounded by a geometric series:

$$\text{Total Cost} = n + \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^j < n + 2n = 3n$$

Dividing the total work $3n$ by $n$ operations yields an amortized cost of $3 = O(1)$ per insertion.

flowchart TD
    Start["Call push(item)"] --> CheckCap{"Is length === capacity?"}
    CheckCap -- "No (Fast Path: O(1))" --> WriteDirect["Write item at buffer[length]<br/>Increment length++"]
    CheckCap -- "Yes (Resize Path: O(n))" --> AllocNew["Allocate new contiguous buffer<br/>with newCapacity = capacity * 2"]
    AllocNew --> CopyLinear["Copy existing elements [0..length-1]<br/>via contiguous block copy"]
    CopyLinear --> ReplaceRef["Point internal buffer to new allocation"]
    ReplaceRef --> WriteDirect
    WriteDirect --> Done["Return updated length"]

---

2. The Hardware Reality: CPU Cache Lines and Spatial Locality

Why do dynamic arrays crush pointer-based data structures even when shifting thousands of elements? The answer lies in the Memory Hierarchy.

Modern CPUs execute instructions at gigahertz speeds (under $0.5\text{ ns}$ per cycle), while main RAM access takes roughly $60\text{–}100\text{ ns}$—a $200\times$ speed gap known as the Von Neumann Bottleneck. To bridge this gap, CPU cores use small, ultra-fast SRAM caches (L1, L2, and L3).

Crucially, the CPU never fetches a single 4-byte or 8-byte variable from RAM. It fetches memory in fixed 64-byte chunks called Cache Lines (which you can compare across byte and kilobyte scales with the Data Size Converter).

flowchart LR
    CPU["CPU Core Registers<br/>(~0.3 ns)"] <-->|"64-Byte Cache Line"| L1["L1 Data Cache<br/>32 KB (~1 ns)"]
    L1 <-->|"64-Byte Cache Line"| L2["L2 Cache<br/>512 KB (~4 ns)"]
    L2 <-->|"64-Byte Cache Line"| L3["L3 Shared Cache<br/>32 MB (~12 ns)"]
    L3 <-->|"DRAM Bus Transfer"| RAM["Main System RAM<br/>(~80 ns - Cache Miss Penalty)"]

When you iterate over a contiguous array of 32-bit integers:

1. Accessing array[0] triggers a cache miss and pulls a 64-byte cache line into L1 cache—which automatically contains array[0] through array[15]!
2. The next 15 reads (array[1] to array[15]) hit L1 cache at $\sim 1\text{ ns}$ with zero RAM latency.
3. Furthermore, the CPU's Hardware Stride Prefetcher detects your sequential memory access pattern and pre-fetches the next cache lines before your loop even asks for them.

Theoretical vs. Hardware Complexity Table

Operation	Asymptotic Time Complexity	Cache Line Behavior	Real-World CPU Execution Profile
Index Access (get(i))	$O(1)$	Single cache line load	Instant base + offset arithmetic
Push Back (push(v))	$O(1)$ amortized, $O(n)$ worst	Sequential write; SIMD memcpy on resize	Hardware prefetcher friendly
Pop Back (pop())	$O(1)$	Already hot in L1 cache	Decrements length counter only
Insert / Delete at Index $i$	$O(n)$	Contiguous memmove across cache lines	Fast for $n < 10,000$ due to vectorized CPU instructions
Sequential Scan	$O(n)$	$100%$ spatial locality utilization	Up to $20\times\text{–}50\times$ faster than pointer chasing

---

3. Under the Hood: Testable Dynamic Array & Ring Buffer Implementation

Let us write a complete, self-contained TypeScript implementation of a generic Dynamic Array that explicitly tracks its raw capacity, growth factor, reallocation telemetry, and automatic shrink-on-quarter-full threshold (preventing memory leaks after bulk deletions).

You can copy and run this entire script directly in our JS/TS Playground or any TypeScript/Node.js editor:

/**
 * Production-Style Generic Dynamic Array with Capacity Telemetry
 * Demonstrates geometric resizing (2x growth) and quarter-load shrinking.
 */
class DynamicArray<T> {
  private buffer: Array<T | undefined>;
  private _length: number = 0;
  private _capacity: number;
  private _resizeCount: number = 0;
  private _totalCopiedElements: number = 0;

  constructor(initialCapacity: number = 4) {
    if (initialCapacity < 1 || !Number.isInteger(initialCapacity)) {
      throw new RangeError("Initial capacity must be a positive integer.");
    }
    this._capacity = initialCapacity;
    this.buffer = new Array<T | undefined>(this._capacity);
  }

  public get length(): number {
    return this._length;
  }

  public get capacity(): number {
    return this._capacity;
  }

  public get telemetry() {
    return {
      length: this._length,
      capacity: this._capacity,
      loadFactor: Number((this._length / this._capacity).toFixed(3)),
      resizeCount: this._resizeCount,
      totalCopiedElements: this._totalCopiedElements,
    };
  }

  /**
   * O(1) Random Access with strict bounds checking
   */
  public get(index: number): T {
    this.checkBounds(index);
    return this.buffer[index] as T;
  }

  /**
   * O(1) Random Mutation
   */
  public set(index: number, value: T): void {
    this.checkBounds(index);
    this.buffer[index] = value;
  }

  /**
   * Amortized O(1) Append
   */
  public push(value: T): number {
    if (this._length === this._capacity) {
      this.resize(this._capacity * 2);
    }
    this.buffer[this._length] = value;
    this._length++;
    return this._length;
  }

  /**
   * Amortized O(1) Remove from end with hysteresis shrinking.
   * Note: We shrink at 25% capacity (not 50%) to prevent "thrashing"
   * when alternating push() and pop() at the capacity boundary!
   */
  public pop(): T | undefined {
    if (this._length === 0) {
      return undefined;
    }
    const lastIndex = this._length - 1;
    const value = this.buffer[lastIndex];
    this.buffer[lastIndex] = undefined; // Allow garbage collection
    this._length--;

    if (this._length > 0 && this._length <= Math.floor(this._capacity / 4) && this._capacity > 4) {
      this.resize(Math.max(4, Math.floor(this._capacity / 2)));
    }

    return value;
  }

  /**
   * O(n) Arbitrary Insertion — shifts elements [index..length-1] right by 1
   */
  public insertAt(index: number, value: T): void {
    if (index < 0 || index > this._length) {
      throw new RangeError(`Index ${index} out of bounds for insert (length: ${this._length}).`);
    }
    if (this._length === this._capacity) {
      this.resize(this._capacity * 2);
    }
    for (let i = this._length; i > index; i--) {
      this.buffer[i] = this.buffer[i - 1];
      this._totalCopiedElements++;
    }
    this.buffer[index] = value;
    this._length++;
  }

  /**
   * O(n) Arbitrary Removal — shifts elements [index+1..length-1] left by 1
   */
  public removeAt(index: number): T {
    this.checkBounds(index);
    const removed = this.buffer[index] as T;

    for (let i = index; i < this._length - 1; i++) {
      this.buffer[i] = this.buffer[i + 1];
      this._totalCopiedElements++;
    }

    this.buffer[this._length - 1] = undefined;
    this._length--;

    if (this._length > 0 && this._length <= Math.floor(this._capacity / 4) && this._capacity > 4) {
      this.resize(Math.max(4, Math.floor(this._capacity / 2)));
    }

    return removed;
  }

  public toArray(): T[] {
    const result: T[] = [];
    for (let i = 0; i < this._length; i++) {
      result.push(this.buffer[i] as T);
    }
    return result;
  }

  private resize(newCapacity: number): void {
    const newBuffer = new Array<T | undefined>(newCapacity);
    for (let i = 0; i < this._length; i++) {
      newBuffer[i] = this.buffer[i];
      this._totalCopiedElements++;
    }
    this.buffer = newBuffer;
    this._capacity = newCapacity;
    this._resizeCount++;
  }

  private checkBounds(index: number): void {
    if (index < 0 || index >= this._length) {
      throw new RangeError(`Index ${index} is out of bounds for length ${this._length}.`);
    }
  }
}

// ============================================================================
// Verification & Amortized Complexity Proof in Action
// ============================================================================
const dynArr = new DynamicArray<number>(4);

// Push 64 elements into an array starting with capacity 4
for (let i = 1; i <= 64; i++) {
  dynArr.push(i * 10);
}

console.log("After 64 pushes:", dynArr.telemetry);
// Expected: length=64, capacity=64, resizeCount=4 (4->8->16->32->64), totalCopiedElements=60
// Notice: 60 total copies across 64 insertions is < 1 copy per push!

// Insert 999 at index 2
dynArr.insertAt(2, 999);
console.log("Element at index 2:", dynArr.get(2));
console.log("After insertAt(2, 999):", dynArr.telemetry);

// Pop 50 elements to trigger quarter-load shrinking
for (let i = 0; i < 50; i++) {
  dynArr.pop();
}
console.log("After 50 pops (shrunk cleanly):", dynArr.telemetry);

---

4. Where Contiguous Arrays Live in Modern Production Systems

When students graduate and enter industry, they often assume arrays are merely "beginner syntax" while "real systems" use complex pointer graphs. In reality, high-performance engineering moves in the exact opposite direction: flattening pointer trees into contiguous arrays.

1. V8 JavaScript Engine: PACKED_SMI_ELEMENTS vs. DICTIONARY_ELEMENTS

In Chrome's V8 engine and Node.js, a standard JavaScript Array is not always a hash map. V8 tracks an internal Elements Kind for every array:

• When you store dense small integers ([10, 20, 30]), V8 assigns the PACKED_SMI_ELEMENTS layout—a raw, contiguous C++ array in memory that executes at near-native speed.
• If you create a "holey" sparse array (const a = []; a[0] = 1; a[100000] = 2;), V8 downgrades the array to DICTIONARY_ELEMENTS (a hash table), sacrificing spatial locality and slowing iteration significantly.

2. Data-Oriented Design & Entity Component Systems (ECS)

Modern game engines (Unity DOTS, Bevy in Rust) and financial simulation engines reject traditional Object-Oriented Programming (where every object is allocated separately on the heap) in favor of Structure of Arrays (SoA). By storing all positions in one contiguous Float32Array and all velocities in another contiguous Float32Array, a physics loop can update 100,000 entities per frame using single-instruction multiple-data (SIMD) vector registers.

3. React Fiber & Hook State Arrays

When you call useState or useMemo in React, why does React forbid calling hooks inside if statements or loops? Because under the hood, each component instance tracks its hooks sequentially in a fixed-order structure indexed by call position during render traversal—avoiding expensive string-key dictionary lookups on every single UI re-render.

---

5. The Professor's Architecture Cheat Sheet

When to Choose Contiguous / Dynamic Arrays:

• Your default collection choice ($95%$ of use cases): Unless profiling proves otherwise, start with a contiguous array.
• Read-heavy & iteration-heavy workloads: Analytics pipelines, vector math, rendering buffers, and tabular datasets.
• Batch appends & stack operations: Pushing and popping at the tail is $O(1)$ amortized with near-zero allocation overhead once capacity stabilizes.

When NOT to Choose Contiguous Arrays:

• Massive, latency-sensitive buffers where a single $O(n)$ resize spike violates SLA: If an array holds 50 million items, the single push() that triggers a $2\times$ reallocation will pause that thread to copy 50 million items. Use chunked arrays (like C++ std::deque) or pre-allocate capacity upfront.
• Stable pointers/references to elements are required: Resizing a dynamic array invalidates memory addresses/references to its internal elements.
• High-frequency insertions/deletions at the very front (unshift/shift): Use a Ring Buffer (Circular Queue) instead—which we will explore in depth in Article 4 of this series!