O(1) 与 O(log n) 差距：数据结构中的缓存

为什么 O(1) 算法会败给 O(log n)：缓存与实际性能

在为 RISC-V SoC 开发引导加载程序时，我们遇到了一个问题：在包含 500 个元素的表中搜索设备配置耗时过多。使用均摊 O(1) 复杂度的哈希表导致启动时间超过 100 毫秒——差了三个数量级。切换到排序数组上的二分搜索（O(log n)）将速度提升了 40%。

使用 perf 性能分析揭示了缓存行为差异：

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

# 二分搜索
$ perf stat -e cache-references,cache-misses ./bootloader_binsearch
    423,156 cache-references
     89,234 cache-misses (21.1% miss rate)

哈希表的缓存未命中率高达 71.5%，每次未命中耗费约 100 个时钟周期。二分搜索将未命中率降至 21.1%，得益于更好的访问局部性。

数组 vs 链表：一个实验

对 10 万个整数求和，尽管两者时间复杂度均为 O(n)，但性能差距巨大：

Array: 70,147 纳秒 (17,557,410 个时钟周期)
Linked list: 179,169 纳秒 (44,740,656 个时钟周期)
Array is 2.55x faster

数组代码采用顺序访问：

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

链表：

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

数组胜出得益于空间局部性：一条缓存行（64 字节）可同时加载 16 个元素。链表因指针分散导致约 70% 的未命中率。

内存层次结构与延迟

真实系统具有多级层次结构：

| 层级 | 大小 | 延迟 | 相对于寄存器 |

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

| 寄存器 | ~256 字节 | 1 个时钟周期 | 1 倍 |

| L1 | 32-64 KB | 3-4 个时钟周期 | 3 倍 |

| L2 | 256 KB-1 MB | 12-15 个时钟周期| 12 倍 |

| L3 | 4-32 MB | 40-50 个时钟周期| 40 倍 |

| DRAM | GB | 100-200 个时钟周期| 100 倍 |

一次 DRAM 未命中相当于 100 个 ALU 操作。在嵌入式 RISC-V 中：

• L1：16-32 KB（桌面版为 64 KB）
• 无 L3
• DRAM 频率 100 MHz

工作集超过 16 KB 即会导致持续未命中。

缓存行与局部性

CPU 以64 字节行加载数据。顺序访问表现出色：

• 数组：94% 命中率
• 随机访问：频繁未命中
• 链表节点（16 字节）：75% 的行空间浪费

硬件预取有助于顺序模式，但对指针访问无效。

关键要点

• 缓存主导一切：未命中成本是 ALU 操作的 100 倍
• 局部性至上：良好缓存的 O(n) > 差缓存的 O(log n)
• 嵌入式更严峻：微小缓存要求数据完全拟合 L1
• 始终性能分析：perf 揭示真实瓶颈
• 算法需演进：教科书在硅片上已过时

— Editorial Team