Binary search trees: O(log n) and cache performance

Binary Search Trees in Practice: Why O(log n) Isn't Always Fast

In the realm of theoretical computer science, Binary Search Trees (BSTs) and their self-balancing variants, such as Red-Black Trees, are considered the gold standard for efficiency in dynamic data structures. Their asymptotic complexity of O(log n) for insertion, search, and deletion operations appears ideal. However, in practice, under the conditions of modern processor architectures with multi-level cache memory, BST performance can significantly underperform simpler structures, even if they possess similar theoretical complexity. This article explores the reasons behind this discrepancy and offers practical recommendations for choosing data structures.

An Unexpected Compiler Performance Drop

Imagine a scenario: a compiler spends 60% of its time not on parsing or code generation, but on symbol lookup in a table. For embedded systems with thousands of symbols, this is unacceptable. The symbol table, storing variable names, functions, and types, was implemented using a Red-Black Tree — a classic self-balancing BST. Theoretically, O(log n) should have ensured high speed.

However, the perf profiler revealed a concerning picture:

$ perf stat -e cache-misses,instructions ./compiler test.c
  Performance counter stats:
    2,847,234 cache-misses
    8,500,000 instructions

Nearly 2.8 million cache misses for 8.5 million instructions — that's one cache miss for every three instructions. Such a metric points to serious memory access issues. As an experiment, the Red-Black Tree was replaced with a sorted array using binary search, which also has a theoretical complexity of O(log n). The result was astonishing: the compiler sped up by 3 times.

How can two data structures with identical asymptotic complexity exhibit such vastly different performance? The answer lies in the specifics of cache memory operation.

Investigating the Causes: Cache Memory and Misses

Detailed analysis using perf confirmed the suspicions. Comparing the Red-Black Tree and the sorted array revealed a critical difference in cache behavior:

# Red-Black Tree Version
$ perf stat -e cache-references,cache-misses,cycles ./compiler_rbtree test.c
  Performance counter stats:
    3,247,832  cache-references
    2,847,234  cache-misses  (87.7% miss rate)
   24,000,000  cycles

# Sorted Array Version
$ perf stat -e cache-references,cache-misses,cycles ./compiler_array test.c
  Performance counter stats:
    1,123,456  cache-references
      234,567  cache-misses  (20.9% miss rate)
    8,000,000  cycles

The Red-Black Tree exhibited an 87.7% cache miss rate, while the sorted array showed only 20.9%. On RISC-V systems, each cache miss can cost up to 100 CPU cycles. This means the Red-Black Tree spent most of its time idle, waiting for data from main memory, rather than performing computations.

Theory vs. Practice: The Pointer Chasing Problem

Data structure textbooks often highlight BSTs for their balanced performance across various operations. They guarantee O(log n) for insertion, search, and deletion, and maintain elements in sorted order. Balanced variants, such as AVL trees or Red-Black Trees, prevent performance degradation to O(n) in the worst case, ensuring logarithmic height.

However, these theoretical advantages do not account for the memory hierarchy of modern computers. The core problem with BSTs lies in pointer chasing. Each traversal from a node to its child (left or right) involves following a pointer to an arbitrary memory address. This drastically reduces cache utilization efficiency.

Sorted Array: Data Locality

When using a sorted array, elements are stored contiguously in memory. For example:

Memory: [10][20][30][40][50][60][70][80]
          ↑   ↑   ↑   ↑   ↑   ↑   ↑   ↑
       0x1000 ...contiguously, cache-friendly...

When the processor accesses array[4], it loads a memory block, for example, 64 bytes, into a cache line. This block includes array[4] and several adjacent elements (e.g., array[5], array[6]). Subsequent accesses to these adjacent elements will be cache hits, taking only 1 CPU cycle.

Binary Search Tree: Data Dispersion

In a BST, each node is typically allocated dynamically (e.g., using malloc()) and can be located at an arbitrary position in the heap. This leads to memory fragmentation:

       40 (@ 0x5000)
      /  \
    20    60 (@ 0x2000, @ 0x8000)
   /  \   /  \
  10  30 50  70 (@ 0x1000, @ 0x3000, @ 0x6000, @ 0x9000)

When searching in a BST, each pointer traversal will likely require accessing a completely new memory region that is not within the current cache line. This results in cache misses, incurring a latency of hundreds of CPU cycles until the data is loaded from main memory.

Consider searching for the value 70:

Sorted Array (Binary Search):

* Step 1: Access middle element [40] @ 0x1020. CACHE MISS (100 cycles). A cache line containing [30][40][50][60] is loaded.

* Step 2: Access [60] @ 0x1030. CACHE HIT (1 cycle).

* Step 3: Access [70] @ 0x1038. CACHE HIT (1 cycle).

* Total: ~102 cycles, 1 cache miss.

Binary Search Tree:

* Step 1: Access root [40] @ 0x5000. CACHE MISS (100 cycles). A cache line at 0x5000 is loaded.

* Step 2: Traverse right, access [60] @ 0x8000. CACHE MISS (100 cycles). Address in a different cache line.

* Step 3: Traverse right, access [70] @ 0x9000. CACHE MISS (100 cycles). Yet another new address.

* Total: ~300 cycles, 3 cache misses.

Both algorithms perform the same number of logical comparisons, but due to cache misses, the BST is significantly slower.

Performance and Code Comparison

For illustration, let's provide code examples for searching and benchmark results.

BST Search:

// Binary Search Tree Node
typedef struct bst_node {
    int key;
    void *value;
    struct bst_node *left;
    struct bst_node *right;
} bst_node_t;

void* bst_search(bst_node_t *root, int key) {
    while (root) {
        if (key == root->key) return root->value;
        root = (key < root->key) ? root->left : root->right;
    }
    return NULL;
}

Sorted Array Search:

typedef struct {
    int key;
    void *value;
} array_entry_t;

void* array_search(array_entry_t *arr, int n, int key) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid].key == key) return arr[mid].value;
        if (key < arr[mid].key) right = mid - 1;
        else left = mid + 1;
    }
    return NULL;
}

Testing 10,000 random search operations on datasets of varying sizes showed:

Dataset: 1000 elements

* BST: 2400 cycles per search operation

* Sorted Array: 800 cycles per search operation

* Speedup: 3×

Dataset: 10000 elements

* BST: 3200 cycles per search operation

* Sorted Array: 1100 cycles per search operation

* Speedup: 2.9×

perf cache miss statistics:

BST: 8.5 misses per search operation
Sorted Array: 2.1 misses per search operation

The sorted array consistently demonstrates 3 times better performance. Reasons for this:

Contiguous Memory Layout: Array elements are stored in a contiguous block, which is ideal for the cache.
Efficient Cache Line Utilization: With each miss, an entire cache line (e.g., 64 bytes) is loaded, containing several array elements at once, which minimizes future misses.
Hardware Prefetching: Modern processors have hardware prefetchers that recognize sequential access patterns and proactively load data into the cache, further reducing latencies.

BSTs lack these advantages. Each pointer dereference during a search can lead to a new cache miss.

Memory Overhead and Balanced Trees

Beyond cache issues, BSTs often have greater memory overhead due to storing pointers.

BST Node (64-bit system, with alignment):

```c

struct bst_node {

int key; // 4 bytes

void *value; // 8 bytes

struct bst_node *left; // 8 bytes

struct bst_node *right; // 8 bytes

// Padding: 4 bytes

};

// Total: 32 bytes per element

```

Sorted Array Element (with alignment):

```c

struct array_entry {

int key; // 4 bytes

void *value; // 8 bytes

// Padding: 4 bytes (for alignment)

};

// Total: 16 bytes per element

```

For 1000 elements, a BST requires 32 KB, whereas an array requires 16 KB. The increased memory footprint for BSTs means fewer nodes can fit into the cache, exacerbating the cache miss problem.

Many developers believe that balanced trees (e.g., Red-Black or AVL) solve all BST problems. They indeed guarantee logarithmic tree height, preventing degradation to a linked list with unfavorable input data. Node rotations, used to maintain balance, are low-cost pointer update operations. However, these mechanisms do not solve the fundamental cache problem: nodes still remain scattered across memory.

Cache misses for the Red-Black Tree in the compiler occurred almost at every step:

$ perf stat -e cache-misses,L1-dcache-load-misses ./compiler_rbtree test.c
  Performance counter stats:
    2,847,234 cache-misses
    2,654,123 L1-dcache-load-misses

Balanced trees solve algorithmic worst-case problems, but not hardware limitations related to memory hierarchy.

When to Use Binary Search Trees?

Despite the described drawbacks, BSTs are not useless. There are scenarios where their use is justified and even preferable.

The primary advantage of BSTs manifests in situations with frequent insertion and deletion operations. In a sorted array, these operations require shifting a large number of elements, leading to O(n) complexity:

Insertion into a sorted array: O(n)
Deletion from a sorted array: O(n)

For BSTs, insertion and deletion remain O(log n) operations, as they only require updating a few pointers and possibly a few rotations to maintain balance. A benchmark of 1000 random insert/delete operations shows:

Sorted array: 12000 cycles/operation (due to shifting)
Red-Black Tree: 3500 cycles/operation
BST Speedup: 3.4×

Thus, if your data structure is constantly changing (many insertions and deletions) and search operations do not dominate in frequency, BSTs (especially balanced ones) can be a better choice, despite potential cache issues. Otherwise, for static or rarely modified datasets where search operations prevail, sorted arrays or other cache-optimized structures (e.g., B-trees) often demonstrate superior performance.

Key Takeaways

O(log n) doesn't guarantee fast practical performance: Asymptotic complexity doesn't account for the impact of memory hierarchy and cache.
The Pointer Chasing Problem: BSTs suffer from poor data locality, leading to numerous cache misses and high latencies.
Advantages of Sorted Arrays: Contiguous element placement ensures high data locality, efficient cache line utilization, and effective hardware prefetching.
Memory Overhead: BSTs require more memory due to pointer storage, further reducing cache efficiency.
Balanced Trees Don't Solve the Cache Problem: They prevent height degradation but do not improve data locality.
Use BSTs for Frequent Insertions/Deletions: If data modification operations outweigh searches, BSTs can be more efficient than sorted arrays.

— Editorial Team