代码之家 › 专栏 › 技术社区 › Muhammad Alkarouri

缓存遗忘数据结构背后的直觉是什么?

cache-oblivious language-agnostic

4

Muhammad Alkarouri · 技术社区 · 15 年前

我理解这个表达 cache oblivious 意思是。但我想知道,对于如何设计数据结构,在不知道缓存大小的情况下,可以优化地使用缓存,是否有任何简单的解释。

你能提供这样的解释吗?最好用一个简单的例子。

2 回复 | 直到 15 年前

1

7

Steve Jessop 15 年前

即使是像Quicksort这样熟悉的算法,也有点缓存被遗忘(但不是最佳的)。回想一下,它的工作方式是对数组进行分区,然后在分区的每一侧递归。最后,它在一个适合缓存的子数组上运行,因此在完成该子数组并移动到另一个子数组之前,不会再有缓存未命中。那是我们要找的财产。

与插入排序相比,插入排序(使用一个技术术语)一直在各地跳跃。因此,除了插入排序需要四处移动O(n^2)项之外,在大型数组上使用时,它也会错过很多缓存。

不过,快速排序在某种程度上是最佳的。每个单独的分区阶段都不会划分和重复——它会在内存中进行长时间的连续运行,从而搅动缓存。这可能会在子数组大小足够小以至于我们开始取胜之前发生几次,因此我们不会最小化缓存未命中的数量。

2

3

Jerry Coffin 15 年前

主要的直觉是,如果您递归地拆分所处理的数据集,在某个时刻(通常非常快),您将达到1)适合缓存的大小,2)至少填充一半缓存(假设每个数据集拆分(至少大约)为一半)。