链表：缓存未命中和基准测试

链表与缓存未命中：为什么在实际任务中不如数组

链表看似非常适合动态操作：O(1) 插入和删除，无需重新分配内存。但在实践中，由于缓存未命中，它们往往败给数组。通过 next 指针的每次跳转都会给内存子系统带来负担，将理论优势转化为瓶颈。

在 10 万个元素上的测试显示了差距：

| 操作 | 数组 | 链表 | 落后倍数 |

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

| 顺序遍历 | 70 μs | 179 μs | ×2.5 |

| 随机访问 | 95 μs | 2847 μs | ×30 |

| 追加 | 42 μs | 1234 μs | ×29 |

即使是插入操作，链表本应占优，但由于重新分配和缓存未命中，最终反而更慢。

缓存未命中机制

CPU 缓存行一次获取 64 字节。在数组中，元素顺序布局——一次未命中即可访问 16 个 int。在链表中，节点散布在堆中：

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

遍历链表时，每个节点都会产生一次未命中（~100 个时钟周期延迟）。对于 10 万个节点——这是 1000 万个周期，而数组只需 62.5 万个。数组占用 400 KB，链表占用 1.6 MB（4 倍开销）。

内存分配开销

创建链表需要 10 万次 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;
}

数组——一次调用。基准测试差异：42 μs 与 1234 μs。

链表适用的罕见场景

链表在特定场景下才有意义：

• 侵入式链表在内核中（Linux list_head）：节点嵌入结构，局部性更好。
• 无锁结构：指针上的原子 CAS 比数组简单。
• 小型静态数据集，插入罕见。

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

必须使用链表时的优化

对象池

预分配节点数组：

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

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

速度：287 μs（比 malloc 快 4.3 倍，但比数组慢 6.8 倍）。

展开链表

每个节点存储多个元素：

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

遍历：45 μs（优于标准链表，对于顺序访问与数组相当）。

XOR 链表

通过 prev^next 的 XOR 节省内存：

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;

缺点：调试复杂，无法双向遍历。不推荐。

RTOS 案例：为什么链表在那里有效

在 FreeRTOS 中，调度器使用按优先级（32 级）的链表数组：

list_head ready_tasks[MAX_PRIORITIES];

成功原因：

• 链表很小（1–5 个任务）。
• 节点嵌入在 task_struct 中。
• 按优先级的 O(1) 操作。

在 Cortex-M4 上的基准测试：插入 0.8 μs，删除 0.6 μs。

关键要点

• 缓存主导：指针未命中即使在 O(1) 操作中也会严重影响性能。
• 内存开销：指针 + 碎片导致 4 倍增长。
• 优先动态数组：均摊 O(1) 插入，无缓存惩罚。
• 优化有所帮助：池和展开链表缩小差距但无法超越。
• RTOS 例外：嵌入节点 + 小尺寸证明选择合理。

— Editorial Team