使用页表重新映射来避免数组重新分配期间的数据复制

Question

假设您有一个类似

std::vector

的容器类，并且该向量已用数据项填充其容量的 100%，并且调用代码调用

push_back()

添加一个数据项。

此时，向量将需要重新分配其内部数组来保存额外的数据项（可能为调用代码可能想要使用的任何其他项目提供一些额外的空间）。

特别是，它必须：

1. 分配一个新的/更大的数组
2. 将所有对象从旧数组复制/移动到新数组
3. 更新其内部状态以指向新数组
4. 释放旧数组

...所有这些都可能相当耗时，并且还需要足够的 RAM 来同时在内存中保存旧数组和新数组。

但是，大多数现代计算机都具有虚拟内存，它允许将 RAM 的物理页映射到虚拟地址。因此，至少在原则上，应该可以用这个过程代替上述过程：

1. 分配足够大的连续范围的虚拟地址来表示新的/更大的数组。
2. 将与现有数组关联的前

   N

   物理页映射到新虚拟地址范围的前

   N

   虚拟页地址块。
3. 从物理页取消旧阵列虚拟地址的映射。
4. 为新数组中的附加空间分配新的物理页（或者可能只是进行设置，以便新数组中的附加虚拟地址在访问时会出现页错误以按需分配物理页）

这样做的优点是根本不需要任何数据复制，因此扩展向量的容量可能非常有效。缺点（除了有限的可移植性之外）是数据中存储的任何指针都不会更新到新的虚拟地址集，因此该技术仅适用于不包含向量旧数组中任何指针的数据。

我的问题是，这种技术在用户空间程序中可行吗？如果是这样，人们将如何实施它？或者如果没有，是什么阻止了它的完成？ （即是否有任何根本原因导致它无法工作，或者只是目前不存在合适的 API 来做到这一点？）

Answer 1

是的，这是可以做到的，而且效果相当好。 Windows 在用户模式下提供了足够的访问页面错误的权限来执行此操作。

Jeffrey Richter 关于 Windows NT 4 时期的 Win32 的书籍给出了以这种方式实现动态数组的示例。它并没有试图成为

std::vector

的准确实现，但充分展示了如何进行动态调整大小，使其余的一致实现变得非常简单。

不幸的是，至少在我测试它时，我确实看到了很大的速度提升。如果足够小心，也许会产生更大的变化，但我并不是特别鼓励。