O(1) vs O(log n) Gap: Cache in Data Structures

# Why O(1) Algorithms Lose to O(log n): Cache and Real-World Performance

During the development of a bootloader for a RISC-V SoC, we ran into an issue: searching for device configurations in a table of 500 elements was taking too much time. A hash table with amortized O(1) complexity resulted in boot times over 100 ms—three orders of magnitude worse. Switching to binary search on a sorted array with O(log n) sped things up by 40%.

Profiling with perf revealed the difference in cache behavior:

# Hash table
$ perf stat -e cache-references,cache-misses ./bootloader_hash
  1,247,832 cache-references
    892,441 cache-misses (71.5% miss rate)

# Binary search
$ perf stat -e cache-references,cache-misses ./bootloader_binsearch
    423,156 cache-references
     89,234 cache-misses (21.1% miss rate)

Cache misses in the hash table hit 71.5%, each costing ~100 cycles. Binary search cut misses down to 21.1% thanks to better access locality.

Array vs Linked List: An Experiment

Summing 100,000 integers showed a huge gap despite both being O(n):

Array: 70,147 ns (17,557,410 cycles)
Linked list: 179,169 ns (44,740,656 cycles)
Array is 2.55x faster

The array code uses sequential access:

int array[100000];
for (int i = 0; i < 100000; i++) {
    array[i] = i;
}
long long sum = 0;
for (int i = 0; i < 100000; i++) {
    sum += array[i];
}

Linked list:

typedef struct node {
    int value;
    struct node *next;
} node_t;

node_t *head = NULL;
for (int i = 0; i < 100000; i++) {
    node_t *node = malloc(sizeof(node_t));
    node->value = i;
    node->next = head;
    head = node;
}

long long sum = 0;
node_t *curr = head;
while (curr) {
    sum += curr->value;
    curr = curr->next;
}

The array wins thanks to spatial locality: a cache line (64 bytes) loads 16 elements at once. The linked list triggers ~70% misses from scattered pointers.

Memory Hierarchy and Latencies

Real systems have a multi-level hierarchy:

| Level | Size | Latency | Relative to Registers |

|-------------|------------|-------------|-----------------------|

| Registers | ~256 B | 1 cycle | 1× |

| L1 | 32-64 KB | 3-4 cycles | 3× |

| L2 | 256 KB-1 MB| 12-15 cycles| 12× |

| L3 | 4-32 MB | 40-50 cycles| 40× |

| DRAM | GB | 100-200 cycles| 100× |

A single DRAM miss equals 100 ALU operations. In embedded RISC-V:

• L1: 16-32 KB (vs 64 KB on desktops)
• No L3
• DRAM at 100 MHz

A working set >16 KB means constant misses.

Cache Lines and Locality

CPUs load 64-byte lines. Sequential access shines:

• Array: 94% hits
• Random access: frequent misses
• List node (16 B): 75% of line wasted

Hardware prefetching helps sequential patterns but flops on pointers.

Key Takeaways

• Cache dominates: misses cost 100x more than ALU ops
• Locality rules: O(n) with good cache > O(log n) with poor cache
• Embedded is tougher: tiny caches demand fitting in L1
• Always profile: perf uncovers real bottlenecks
• Algorithms evolve: textbooks age on silicon

— Editorial Team