缓存无关数据结构

缓存无关模型

在算法层面考虑储存器层次结构时,我们通常使用的是外部储存模型(External Memory Model)。在这样的模型中,储存器具有两级 $L_1, L_2$,且 $|L_1| = M, |L_2| = \infty$。$L_1$ 被看作 $L_2$ 的缓存,当访问的数据不在 $L_1$ 中时,我们将数据从 $L_2$ 中调入 $L_1$,并花费 $T$ 的传输时间。

事实上,由于传输延迟很大,每次从 $L_2$ 中会将连续长度为 $B$ 的数据调入 $L_1$ 中,也就是说整个储存按照 $B$ 的块大小划分为 $M/B$ 个块。外部储存模型是说,给定 $M, B$,设计算法以降低传输数据的次数。缓存无关模型(Cache Oblivious Model)则加了一个限制:算法不知道 $M, B​$ 的具体取值,换言之,其要在不同的层次结构下取得良好的性能。

值得说明的一点是,在缓存无关模型的讨论中,我们均认为页面置换算法取最优算法 OPT。这是因为常用的置换算法如 $LRU, FIFO$ 在拥有两倍空间的情况下拥有常数竞争比,因此在渐进意义下 OPT 即可代表实际开销。

举例而言,无论 $M, B$ 为多少,顺序扫描长度为 $N$ 的数组均可以在 $\Theta(N/B)$ 次内存传输内完成,而二分查找则做不到这一点。事实上,通过在内存中维护递归树前 $\lg B$ 层的所有结点,我们可以说明二分查找的内存传输次数是 $\Theta(\lg n - \lg B)$ 的,而非我们希望的 $\Theta(\lg n/\lg B)$。

BBST 的优化

BST 的操作往往是从树根出发,沿着一条链向下直到遇到某个结点为止。和二分查找一样,如果不经过特殊安排,访问一个结点的内存传输次数可能高达 $\Theta(\lg n-\lg B)$。事实上存在优秀的策略可以将单次操作的内存传输次数降低到 $O(\log_B n)$。

将 BST 如此重新标号:设线段树的高度为 $h$,将最高的 $h$ 层构成的联通块记作 $T_0$,删去 $T_1$ 后形成的联通块分别为 $T_1, T_2, \dots, T_k$。我们按照 $T_0, T_1, T_2, \dots, T_k$ 的顺序依次递归标号。这可以使用 dfs 在 $O(n)$ 的时间复杂度内完成。接下来,将标记为 $k$ 的结点放置到数组第 $k$ 位的位置,并修改所有的指针结构。这样的放置顺序称为数组的 vEB 序。

veb.png

定理:按照 vEB 序放置的平衡查找树每次操作仅需 $O(\log_B n)$ 次内存传输。

证明:设缓存参数为 $M, B​$,为了方便不妨假设 BBST 正是一棵满二叉树。注意到我们的递归划分算法每次将树高降低一半,大小变为 $\sqrt N​$。设 $N_0​$ 是递归中第一次小于等于 $B​$,那么 $N_0 \ge \sqrt B, h_0 \ge \frac{1}{2}\log B​$。由于大小为 $N_0​$ 的子树连续放置于内存中,因此位于至多两个缓存块中。那么对于一次访问,会经过至多 $\lg n/h_0​$ 个大小为 $N_0​$ 的子树,因此进行了不超过 $2\times 2\log n/\log B = O(\log_B n)​$ 次内存传输。Q.E.D.

vEB 序一个有趣的应用是改进线段树的缓存性能,我们可以利用 dfs 给结点标号,并按照标号重新放置线段树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* dfs_relabel:使用 dfs 标号
* @nd: 当前处理的子树根节点
* @h: 当前处理的子树高度,仅处理从 @nd 开始深度为 @h 的结点构成的子树
* @id: 记录已使用标号
* @que: 记录深度为 @h 结点的所有儿子结点
*/
void dfs_relabel(node *nd, int h, int &id, std::vector<node*> &que)
{
if (nd == nullptr)
return;
if (h == 1) {
pos[nd - pool] = id++;
// nd - pool 为结点在数组中的位置
if (nd->lc != nullptr) {
que.push_back(nd->lc);
}
if (nd->rc != nullptr) {
que.push_back(nd->rc);
}
} else {
std::vector<node*> q;
int up = h / 2, down = h - up;
dfs_relabel(nd, up, id, q);
// 处理高处的子树
for (auto nxt : q) {
dfs_relabel(nxt, down, id, que);
}
// 处理低处的子树
}
}

实验表明,在其他实现相同的情况下,使用 vEB 序的线段树可以提高 20% 到 50% 的性能。当然这和机器的储存器体系结构有着很大的关系。完整的测试代码在 segtree-cache.zip

有序文件

为了实现缓存无关的 B 树我们需要一个称为有序文件(Ordered Files)的有趣数据结构,它是说我们要在 $O(n)$ 的数组中维护 $n$ 个元素,保证他们的顺序,并支持在对应位置插入、删除。有序文件可以做到平摊每次插入 $O(\log^2 n)$ 次元素移动。

考虑构建一个满二叉树,其每个叶子结点对应 $O(\log n)$ 个空闲数组位置,我们称这是有序文件的一个。整个结构共有 $O(n/\log n)$ 组。

files.png

设树高为 $h$,根节点深度为 $1$,我们维护整个结构使得第 $d$ 层每个节点的装载率 $load(d)$,即装入元素的个数除以该节点对应子树所对应的的空间大小满足:

注意到 $load(d)$ 可取的范围是 $load(d+ 1)$ 可取范围的真子集。在一次操作结束后,我们访问操作组所有的祖先, 找到最低的满足装载率的祖先 $g$,并利用线性扫描将 $g$ 子树中所有组均匀放置。在放置均匀后,所有组的装载率均相同,由于 $g$ 仍然满足装载率限制,那么 $g$ 子树中每一个孩子(包括 $p$)也满足装载率限制。

让我们来分析这样操作的时间复杂度。设 $g$ 的高度为 $l$,那么这次重构花费了 $O(2^{l}\log n)$ 的时间。在这次操作后 $g$ 的左右孩子都满足

那么 $g$ 下一次被重构,至少是其左右孩子中某一者违反装载率限制,这至少需要将装载率变化 $1/4h$,而每次操作仅会使装载率变化 $1/2^l\log n$,因此这至少在

次操作之后,那么 $g$ 贡献的每一次操作的平摊开销就是 $O(\log n)$。注意到每一次操作后将被其所有祖先贡献一个 $O(\log n)$ 的平摊开销,那么每一次操作总的平摊开销就是 $O(\log^2 n)$。由于我们仅仅使用了线性扫描,所需的内存传输次数不会超过 $O(\log^2 n/B)$。

缓存无关的 BBST

接下来我们试图构建缓存无关的查找树,核心思路是用有序文件保证元素的有序性。为了平摊掉有序文件所带来的 $O(\log^2 n)$ 的时间开销,我们将 $O(\log n)​$ 个相邻的递增元素分成一组放入有序文件中。接下来在有序文件数组上建立线段树,每个结点维护区间中的最大值。考察各种 BST 操作:

  • 查找元素:相当于在线段树上二分,考察当前元素和左边最大值的关系,然后递归查找。查询操作的最坏复杂度为 $O(\log n)$。
  • 插入元素:首先找到应当插入的组。取 $S = O(\log n)$,我们希望保证该组的大小在 $[S, 2S)$ 之间,如果元素过多,就将其分解成两个组,而这需要在有序文件中做插入操作。由于每 $O(S)$ 次操作会带来一次有序文件操作,因此平摊时间复杂度为 $O(\log n)$。
  • 删除元素:和插入一样,不过这次需要在元素过少时合并,平摊复杂度为 $O(\log n)$。

其余的操作均和线段树无异。如果将 BBST 按照 vEB 序存储,所有操作都可以在均摊 $O(\log_B n)$ 的时间复杂度内完成。

参考文献

1. MIT 6.851, Memory hierarchy: models, cache-oblivious B-trees
2. Memory hierarchy: ordered-file maintenance, list labeling, order queries, cache-oblivious priority queues

本文标题:缓存无关数据结构

文章作者:Jiatu Li

原始链接:http://ljt12138.github.io/2019/08/08/cache-oblivious-ds/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。