O(1) vs O(log n): La brecha del caché en Estructuras de Datos

# ¿Por qué los algoritmos O(1) pierden ante O(log n): Caché y rendimiento en el mundo real

Durante el desarrollo de un bootloader para un SoC RISC-V, nos topamos con un problema: buscar configuraciones de dispositivos en una tabla de 500 elementos consumía demasiado tiempo. Una tabla hash con complejidad amortizada O(1) resultaba en tiempos de arranque superiores a 100 ms —tres órdenes de magnitud peores—. Cambiar a búsqueda binaria en un array ordenado con O(log n) aceleró las cosas un 40%.

El perfilado con perf reveló la diferencia en el comportamiento de la caché:

# 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)

Los fallos de caché en la tabla hash alcanzaron el 71.5%, cada uno costando ~100 ciclos. La búsqueda binaria redujo los fallos al 21.1% gracias a una mejor localidad de acceso.

Array vs Lista enlazada: Un experimento

La suma de 100.000 enteros mostró una gran brecha a pesar de que ambos son O(n):

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

El código del array usa acceso secuencial:

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];
}

Lista enlazada:

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;
}

El array gana gracias a la localidad espacial: una línea de caché (64 bytes) carga 16 elementos a la vez. La lista enlazada provoca ~70% de fallos por punteros dispersos.

Jerarquía de memoria y latencias

Los sistemas reales tienen una jerarquía multinivel:

| Nivel | Tamaño | Latencia | Relativo a registros |

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

| Registros | ~256 B | 1 ciclo | 1× |

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

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

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

| DRAM | GB | 100-200 ciclos| 100× |

Un solo fallo de DRAM equivale a 100 operaciones ALU. En RISC-V embebido:

• L1: 16-32 KB (frente a 64 KB en escritorios)
• Sin L3
• DRAM a 100 MHz

Un conjunto de trabajo >16 KB implica fallos constantes.

Líneas de caché y localidad

Las CPU cargan líneas de 64 bytes. El acceso secuencial destaca:

• Array: 94% aciertos
• Acceso aleatorio: fallos frecuentes
• Nodo de lista (16 B): 75% de la línea desperdiciada

El prefetching de hardware ayuda con patrones secuenciales, pero falla con punteros.

Lecciones clave

• La caché domina: los fallos cuestan 100 veces más que las operaciones ALU
• La localidad manda: O(n) con buena caché > O(log n) con mala caché
• Embebido es más duro: cachés diminutas exigen caber en L1
• Siempre perfila: perf descubre los cuellos de botella reales
• Los algoritmos evolucionan: los libros de texto envejecen en silicio

— Editorial Team