Listas enlazadas: fallos de caché y benchmarks

Listas enlazadas y fallos de caché: Por qué quedan cortas frente a los arrays en tareas del mundo real

Las listas enlazadas parecen ideales para operaciones dinámicas: inserciones y eliminaciones en O(1), sin realocaciones. Pero en la práctica, a menudo pierden frente a los arrays debido a los fallos de caché. Cada salto a través del puntero next sobrecarga el subsistema de memoria, convirtiendo ventajas teóricas en cuellos de botella.

Las pruebas con 100.000 elementos muestran la diferencia:

| Operación | Array | Lista enlazada | Retraso |

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

| Recorrido secuencial | 70 μs | 179 μs | ×2.5 |

| Acceso aleatorio | 95 μs | 2847 μs | ×30 |

| Inserciones al final | 42 μs | 1234 μs | ×29 |

Incluso las inserciones, donde las listas deberían destacar, terminan siendo más lentas debido a las realocaciones y fallos de caché.

Mecanismo de fallos de caché

Las líneas de caché de la CPU cargan 64 bytes a la vez. En un array, los elementos están dispuestos de forma secuencial: un fallo da acceso a 16 enteros. En una lista enlazada, los nodos están dispersos por el montón:

// Typical node
struct node {
    int value;     // 4 bytes
    node *next;    // 8 bytes
}; // 16 bytes with padding

Recorrer la lista genera un fallo por cada nodo (~100 ciclos de retraso). Para 100.000 nodos, eso son 10 millones de ciclos frente a 625 mil para el array. El array usa 400 KB, la lista: 1.6 MB (sobrecarga 4×).

Costes de asignación de memoria

Crear la lista requiere 100.000 llamadas a malloc():

for (int i = 0; i < 100000; i++) {
    node *n = malloc(sizeof(node)); // Heap search, metadata, fragmentation
    n->value = i;
    n->next = head;
    head = n;
}

Array: una llamada. Diferencia en benchmark: 42 μs vs. 1234 μs.

Escenarios raros donde las listas están justificadas

Las listas enlazadas tienen sentido en casos nicho:

• Listas intrusivas en kernels (Linux list_head): nodos embebidos en estructuras, mejor localidad.
• Estructuras sin bloqueos: CAS atómico en punteros más simple que en arrays.
• Conjuntos de datos estáticos pequeños con inserciones raras.

Ejemplo de la pila sin bloqueos de Treiber:

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

void push(node_t **head, node_t *node) {
    do {
        node->next = *head;
    } while (!atomic_compare_exchange(head, &node->next, node));
}

Optimizaciones para cuando tengas que usarlas

Pools de objetos

Preasignar un array de nodos:

#define POOL_SIZE 10000
node_t pool[POOL_SIZE];
int idx = 0;

node_t *alloc() {
    return idx < POOL_SIZE ? &pool[idx++] : NULL;
}

Velocidad: 287 μs (×4.3 vs. malloc, pero ×6.8 vs. array).

Listas desenrolladas

Almacenar múltiples elementos por nodo:

#define N 16
typedef struct {
    int values[N];
    int count;
    struct node *next;
} unrolled_t;

Recorrido: 45 μs (mejor que lista estándar, comparable a array para acceso secuencial).

Listas enlazadas XOR

Ahorrar memoria vía XOR de prev^next:

typedef struct {
    int value;
    node *xor_ptr; // prev ^ next
} xor_node;

// Traversal requires tracking prev
node *next = (uintptr_t)prev ^ (uintptr_t)curr->xor_ptr;

Desventajas: complejidad en depuración, no recorrido bidireccional. No recomendado.

Caso RTOS: Por qué funcionan allí

En FreeRTOS, el planificador usa un array de listas por prioridad (32 niveles):

list_head ready_tasks[MAX_PRIORITIES];

Éxito debido a:

• Listas pequeñas (1–5 tareas).
• Nodos embebidos en task_struct.
• Operaciones O(1) por prioridad.

Benchmark en Cortex-M4: inserción 0.8 μs, eliminación 0.6 μs.

Puntos clave

• El caché domina: fallos de punteros matan el rendimiento incluso en operaciones O(1).
• Sobrecarga de memoria: crecimiento 4× por punteros + fragmentación.
• Arrays dinámicos preferidos: inserciones amortizadas O(1) sin penalizaciones de caché.
• Optimizaciones ayudan algo: pools y listas desenrolladas cierran la brecha pero no superan.
• Excepción RTOS: nodos embebidos + tamaño pequeño justifican la elección.

— Editorial Team