Day 3: Build a Prefix Search Trie over Sorted Relics — and Track the Pointer-Chasing Memory Overhead

Day 3: Build a Prefix Search Trie over Sorted Relics — and Track the Pointer-Chasing Memory Overhead

In Day 2, we confronted the fundamental tension of memory layouts: the trade-off between the fast, predictable cache locality of contiguous byte arrays and the structural flexibility of pointer-heavy lists. We saw how packing records into contiguous blocks maximizes CPU cache-line utility, but at the cost of requiring fixed-size record layouts and expensive random insertions.

Today, we take our next architectural step. To power the autocomplete search bar of the Relic Browser, we need to query relics by their prefix (for example, typing "Aeg" to find "Aegis of the Undying").

If we use the contiguous sorted array from Day 2, finding a prefix requires a binary search followed by a linear scan. This works, but its search time scales with the number of records in our database, $O(log N)$.

To achieve $O(L)$ lookup time—where search speed depends only on the length of the query string $L$, regardless of whether we have ten thousand or ten billion records—academic courses point us directly to the Trie (Prefix Tree).

But in a production-scale system, the academic Trie has a dark secret: pointer-chasing memory amplification. Today, you will build a working prefix search Trie, measure its exact memory footprint, and calculate the hidden tax that pointer-heavy data structures levy on your hardware.

The Production Stakes: The Billion-Pointer Outage

In 2014, a major DNS resolution provider experienced a cascading outage after deploying a new zone-matching engine built on a standard, pointer-based Trie. The engine was designed to perform ultra-fast longest-prefix matching (LPM) on IP addresses and domain names.

In testing with 100,000 records, the system performed flawlessly, responding in nanoseconds. But when deployed to production and loaded with millions of active routing records, the process was abruptly terminated by the Linux Out-Of-Memory (OOM) killer.

The post-mortem revealed a stark disconnect between algorithmic theory and physical hardware:

1. 1.Pointer Overhead: On a 64-bit operating system, every pointer consumes 8 bytes of memory.

2. 2.Node Amplification: A naive English-alphabet Trie node holds an array of 26 child pointers. That is $26 times 8 text{ bytes} = 208 text{ bytes}$ of pointer memory per node, even if only a single child pointer is populated.

3. 3.Allocator Metadata: Every time you call malloc or instantiate a node on the heap, the language runtime and OS memory allocator append 8 to 16 bytes of tracking metadata (headers, alignment padding).

For a raw dataset of 50 megabytes of text, the pointer-based Trie exploded into over 1.2 gigabytes of heap allocations—a 24x memory amplification. Worse, because these nodes were scattered randomly across the heap, searching the Trie forced the CPU to chase pointers across physical RAM, causing continuous L1/L2 cache misses that stalled the CPU pipeline.

To avoid this in production, systems like Redis (using the RAX radix tree engine) and high-performance IP routers compress their trees or pack nodes into flat arrays. Today, we will build the naive version first to measure this overhead ourselves, preparing us for the optimized contiguous structures we will build in Day 4.

Component Architecture

The prefix search engine sits directly above our storage layer. It indexes the primary keys (the relic names) of our records to provide instant autocomplete suggestions.

[ Autocomplete Query ] 
         │
         ▼
 ┌────────────────────────────────────────────────────────┐
 │                 Prefix Search Engine                   │
 │                                                        │
 │  Root Node                                             │
 │    └── [R] ──► [E] ──► [L] ──► [I] ──► [C] (isWord=true)│
 │         │                                              │
 │         └── Heap-scattered memory addresses            │
 └────────────────────────────────────────────────────────┘
         │
         ▼
 [ Relic Storage Engine (Contiguous Binary File) ]

Memory Layout Comparison

When we allocate Trie nodes dynamically, they are scattered throughout the virtual memory space. Contrast this with the contiguous memory block we explored in Day 2:

Contiguous Memory Layout (Day 2):
┌───────────┬───────────┬───────────┐
│  Relic A  │  Relic B  │  Relic C  │  ◄── Single memory fetch pulls
└───────────┴───────────┴───────────┘      entire block into L1 Cache.

Academic Trie Memory Layout (Today):
┌───────────┐        ┌───────────┐        ┌───────────┐
│ Node Root │ ───►   │  Node 'R' │ ───►   │  Node 'E' │  ◄── Each arrow is a pointer
└───────────┘        └───────────┘        └───────────┘      hop requiring a new
  At Heap 0x0A         At Heap 0x9F         At Heap 0x1C      DRAM fetch (Cache Miss).

Core Concepts: Pointer-Chasing and Memory Amplification

To understand why this happens, let us look at the memory footprint of a single node in Go:

type TrieNode struct {
    children [26]*TrieNode // 208 bytes (26 pointers * 8 bytes)
    isWord   bool          // 1 byte
                           // 7 bytes of compiler alignment padding
}

Even if a node only has one child (e.g., the letter 'e' pointing to 'l' in "relic"), it must allocate all 208 bytes for the children array to maintain $O(1)$ indexing of the next character.

If we store the word "relic" (5 characters), we must allocate 5 nodes:
$$text{Total Memory} = 5 text{ nodes} times 216 text{ bytes} = 1,080 text{ bytes}$$

To store 5 bytes of actual text data, we have used 1,080 bytes of RAM—a 216x memory amplification factor.

Implementation Blueprint

We will implement our Trie in Go. We will create a TrieNode structure and a Trie wrapper. To prove the cost of pointer chasing, we will build a custom tracker that measures the exact number of bytes allocated on the heap during construction.

Here is the core structure of our search node:

// TrieNode represents a single character node in our prefix tree.
type TrieNode struct {
	children [26]*TrieNode
	isWord   bool
}

// Insert adds a word to the Trie.
func (t *Trie) Insert(word string) {
	curr := t.root
	for i := 0; i < len(word); i++ {
		index := word[i] - 'a'
		if curr.children[index] == nil {
			curr.children[index] = &TrieNode{}
			t.nodeCount++
		}
		curr = curr.children[index]
	}
	curr.isWord = true
}

Notice how we calculate the index: word[i] - 'a'. This assumes lowercase English letters a through z. This is an $O(1)$ lookup, but it requires us to allocate space for all 26 pointers regardless of whether they are used.

The Failure Demo: Memory Amplification in Action

In our implementation, we will load a dictionary of 25,000 relic names. We will measure:

1. 1.The raw size of the text strings in bytes.

2. 2.The actual heap memory allocated by Go's runtime to hold the Trie.

3. 3.The average search latency.

When you run this demo, you will observe that the Trie requires over 15x to 20x more memory than the raw text file. If our raw relic names take up 500 KB, our Trie will consume nearly 10 MB of RAM. Under production scale, this ratio remains constant, turning a 10 GB dataset into a 200 GB memory liability.

Design Alternatives: When to Choose Something Else

If pointer-based Tries are so memory-intensive, what are the alternatives?

Homework Assignment

Your goal is to modify the Trie node representation to use a compressed dynamic child list instead of a fixed 26-pointer array, and measure the memory savings.

Steps:

1. 1.Open trie.go and locate the TrieNode struct definition.

2. 2.Replace children [26]*TrieNode with a slice of structures:

   goCopy

   type ChildEdge struct {
       char byte
       node *TrieNode
   }
   type TrieNode struct {
       children []ChildEdge
       isWord   bool
   }
   

3. 3.Update the Insert and Search methods. Instead of direct array indexing (curr.children[index]), you must iterate over the children slice to find the matching character.

4. 4.Run the benchmark again.

5. 5.Success Criteria: Your modified Trie must pass all tests, successfully search prefixes, and use at least 50% less heap memory than the naive implementation.

Hints:

• When inserting, if the character does not exist in the slice, append a new ChildEdge to the children slice.

• To keep lookups fast, you can keep the children slice sorted by char and use binary search (sort.Search) to find the correct edge.

Solution Hints

If you get stuck on the assignment, consider how to find a child node in a slice:

func (n *TrieNode) FindChild(char byte) *TrieNode {
	for _, edge := range n.children {
		if edge.char == char {
			return edge.node
		}
	}
	return nil
}

This changes our lookup time within a single node from $O(1)$ to $O(C)$, where $C$ is the number of active children (at most 26). Because $C$ is small, this is incredibly fast in practice and completely eliminates the unused 8-byte pointers!

In Day 4, we will take this concept to its logical conclusion: we will pack our entire dataset into a single contiguous binary file and compare its performance directly against this pointer-based implementation.