Unrolled Linked Lists & Gap Buffers: Defeating Pointer Chasing

Defeating the Pointer Tax: Unrolled Linked Lists

Consider storing 4-byte int32_t integers in a 64-bit doubly linked list (std::list<int32_t>). Each node contains 8B prev + 8B next + 4B val + 4B alignment padding + 8B–16B malloc chunk header = 32 to 40 bytes per 4-byte integer ($800\% - 1000\%$ memory bloat!), and traversing $N$ elements incurs $N$ dependent pointer-chasing cache misses.

An Unrolled Linked List replaces the single element in each node with a small inline array T elements[B] and an occupancy counter uint16_t count. When we size the node to match a single 64-byte CPU cache line (e.g., 8B prev + 8B next + 4B count + eleven 4-byte integers = 64 bytes):

• Cache Miss Reduction: Fetching a single node into L1d brings in up to $B$ consecutive elements simultaneously, reducing cache misses during sequential traversal from $N$ to $\approx N / B$.
• B-Tree Split/Merge Occupancy Invariant: Every interior node maintains occupancy $count \in [\lceil B / 2 \rceil, B]$. Inserting into a full node ($count == B$) allocates a new sibling node and moves the upper $B / 2$ elements into it in a single cache-line register write ($O(B) = O(1)$ time), guaranteeing at least $50\%$ space utilization across all nodes!

Sequence Data Structure Trade-Off Matrix

Visualizing Cache-Line-Sized Unrolled Nodes & The Gap Buffer Split

Unrolled Node Overflow & Half-Split Lifecycle

Production Implementation: Generic Gap Buffer Engine

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstring>
#include <vector>

class GapBuffer {
  std::vector<char> buf_;
  std::size_t gap_start_ = 0;
  std::size_t gap_end_;

  std::size_t gap_size() const noexcept { return gap_end_ - gap_start_; }

  void expand_gap(std::size_t min_gap) {
    const std::size_t old_size = size();
    const std::size_t new_cap = std::max(buf_.size() * 2, old_size + min_gap + 64);
    std::vector<char> next_buf(new_cap);

    // Copy prefix [0 .. gap_start_) to start of next_buf
    std::memcpy(next_buf.data(), buf_.data(), gap_start_);
    // Copy suffix [gap_end_ .. buf_.size()) to end of next_buf
    const std::size_t suffix_len = buf_.size() - gap_end_;
    const std::size_t new_gap_end = new_cap - suffix_len;
    std::memcpy(next_buf.data() + new_gap_end, buf_.data() + gap_end_, suffix_len);

    buf_ = std::move(next_buf);
    gap_end_ = new_gap_end;
  }

public:
  explicit GapBuffer(std::size_t initial_cap = 64)
      : buf_(initial_cap), gap_start_(0), gap_end_(initial_cap) {}

  std::size_t size() const noexcept { return buf_.size() - gap_size(); }

  // Move cursor (gap_start_) to logical position pos via overlapping-safe memmove
  void move_cursor(std::size_t pos) noexcept {
    assert(pos <= size());
    if (pos < gap_start_) {
      const std::size_t delta = gap_start_ - pos;
      std::memmove(buf_.data() + gap_end_ - delta, buf_.data() + pos, delta);
      gap_start_ -= delta;
      gap_end_ -= delta;
    } else if (pos > gap_start_) {
      const std::size_t delta = pos - gap_start_;
      std::memmove(buf_.data() + gap_start_, buf_.data() + gap_end_, delta);
      gap_start_ += delta;
      gap_end_ += delta;
    }
  }

  // O(1) amortized insertion at cursor
  void insert_char(char c) {
    if (gap_start_ == gap_end_) expand_gap(1);
    buf_[gap_start_++] = c;
  }

  // O(1) backspace deletion before cursor
  void backspace() noexcept {
    if (gap_start_ > 0) --gap_start_;
  }

  // O(1) branchless random access to logical index i
  char operator[](std::size_t i) const noexcept {
    const std::size_t offset = (i >= gap_start_) ? gap_size() : 0;
    return buf_[i + offset];
  }
};