Rendimiento y layout: por qué Vec es cache-friendly y el coste real de cada operación

Llevas todo el nivel viendo notaciones O grande: O(1) para Vec, O(log n) para BTreeMap, O(1) medio para HashMap. Es hora de la verdad incómoda: el asintótico no cuenta toda la historia. Dos operaciones “O(n)” pueden diferir en un factor de cien según cómo estén dispuestos los datos en memoria, porque el cuello de botella de un procesador moderno no es calcular, es esperar a la memoria. Esta lección cierra el nivel bajando al metal: qué es una línea de caché, por qué la contigüidad de Vec lo hace volar, y cuál es el coste real —no solo el asintótico— de cada operación de cada colección.

La jerarquía de memoria y la línea de caché

El modelo mental de “la RAM es rápida” es falso desde hace décadas. Un núcleo actual ejecuta una instrucción en una fracción de nanosegundo, pero traer un dato de la RAM principal tarda del orden de cien nanosegundos: cientos de ciclos de reloj parado. Para tapar ese abismo hay una jerarquía de cachés cada vez más pequeñas y rápidas entre el núcleo y la RAM.

La pieza clave es la línea de caché: la memoria no se trae byte a byte, sino en bloques de 64 bytes. Cuando lees un i32, el procesador arrastra a la caché los 64 bytes que lo rodean —dieciséis enteros de golpe—. Si tu siguiente acceso cae en esos mismos 64 bytes, es prácticamente gratis: ya está en L1. Si cae lejos, en una línea que no está cargada, pagas un fallo de caché y esperas la RAM. Encima, el prefetcher del hardware detecta patrones de acceso secuenciales y trae las líneas siguientes antes de que las pidas. Toda la partida del rendimiento se juega aquí: mantener los datos que usas juntos en pocas líneas, y recorrerlos en orden previsible.

Los arquitectos llaman a esto localidad, y tiene dos caras que conviene nombrar. La localidad espacial dice que si tocas una dirección, pronto tocarás las vecinas —y la caché, al traer líneas enteras y el prefetcher al adelantarse, apuestan por ello—. La localidad temporal dice que si tocas una dirección, pronto volverás a tocarla —y por eso la caché retiene lo reciente y descarta lo viejo—. Casi todo lo que vuelve rápida a una colección se reduce a explotar una de las dos: Vec es un monumento a la localidad espacial, y una caché de resultados lo es a la temporal. Escribir código veloz es, en buena medida, escribir código con buena localidad.

Vec frente a la lista enlazada

Aquí es donde la contigüidad de Vec deja de ser un detalle y se vuelve la diferencia entre volar y arrastrarse. Recorrer un Vec es el caso ideal para la máquina: los elementos están pegados, cada línea de caché trae los dieciséis siguientes, el prefetcher acierta todas sus predicciones y el bucle avanza casi sin esperar a la memoria. Una lista enlazada hace justo lo contrario: cada nodo se reservó por separado y puede vivir en cualquier rincón del heap, así que seguir cada puntero next es un salto a una dirección impredecible —pointer chasing— y, con alta probabilidad, un fallo de caché. Misma O(n) en la pizarra; en la máquina, un abismo.

flowchart TB
subgraph Vec contiguo una linea de cache trae varios
  v0[10] --- v1[20] --- v2[30] --- v3[40] --- v4[50]
end
subgraph Lista enlazada nodos dispersos por el heap
  n0[10] -.salto.-> n1[40]
  n1 -.salto.-> n2[20]
  n2 -.salto.-> n3[50]
end
style v0 fill:#a6e3a1,color:#11111b
style v1 fill:#a6e3a1,color:#11111b
style v2 fill:#a6e3a1,color:#11111b
style n0 fill:#f38ba8,color:#11111b
style n1 fill:#f38ba8,color:#11111b
style n2 fill:#f38ba8,color:#11111b

El resultado desafía la intuición de los libros de texto. El experimento célebre de Bjarne Stroustrup mide insertar en orden en mitad de una secuencia: la lista enlazada tiene la inserción “barata” O(1) una vez que sabes dónde, pero encontrar el sitio exige recorrerla saltando de nodo en nodo, y ese recorrido, plagado de fallos de caché, es tan lento que el Vec —que para insertar debe desplazar todo con memmove, en teoría más trabajo— gana por goleada para cualquier tamaño realista. La razón es que memmove sobre memoria contigua es justo lo que el hardware hace a máxima velocidad, mientras que el paseo por punteros de la lista es justo lo que peor se le da. La moraleja: la contigüidad casi siempre vence a la complejidad asintótica favorable cuando n no es astronómico.

El coste real de cada operación

Con la caché en mente, esta es la tabla de referencia del nivel. La columna asintótica es la verdad matemática; el comentario es la verdad práctica que el asintótico esconde.

Fíjate en las columnas “nota práctica”: cuentan lo que la O grande calla. Un HashMap es O(1) medio, sí, pero cada operación paga el coste fijo de calcular un hash SipHash y un salto a una dirección dispersa —dos cosas que un Vec no hace—. Un BTreeMap es O(log n), peor en papel que el hash, pero sus nodos anchos y contiguos aprovechan la caché mucho mejor que la dispersión del hash. Los números asintóticos ordenan el comportamiento cuando n crece; para el tamaño que de verdad tiene tu colección, las notas de la derecha suelen pesar más.

Cuando el asintótico engaña: n pequeño

La consecuencia más contraintuitiva y más útil: para n pequeño, un escaneo lineal sobre un Vec bate a la búsqueda O(1) de un HashMap. Buscar una clave en un Vec de veinte pares es un recorrido O(n) de veinte comparaciones sobre memoria contigua —una sola línea de caché, prefetch perfecto, sin hashear nada—. La misma búsqueda en un HashMap es O(1), pero paga calcular la huella y saltar a un bucket disperso, y ese coste fijo, para veinte elementos, es mayor que las veinte comparaciones baratísimas del vector.

// Para pocos elementos, un Vec de pares suele batir a un HashMap.
struct MapaMini<K, V> {
    pares: Vec<(K, V)>,   // contiguo: cache-friendly
}

impl<K: PartialEq, V> MapaMini<K, V> {
    fn get(&self, clave: &K) -> Option<&V> {
        // Escaneo lineal O(n): rapidisimo para n pequeno, sin hashear.
        self.pares.iter().find(|(k, _)| k == clave).map(|(_, v)| v)
    }
}

El punto de cruce depende del hardware y del tipo, pero suele estar entre unas pocas decenas y un centenar de elementos: por debajo, el Vec lineal gana; por encima, el hash despega y la escala asintótica se impone. Por eso muchas bibliotecas de alto rendimiento ofrecen un SmallMap o VecMap que es un Vec por dentro. La lección no es “el hash es malo”, sino que la elección de colección depende del tamaño real, y ese tamaño solo lo conoces midiendo.