c++ - 使用 MMU 实现可调整大小的数组

Question

通常，列表要么被实现为链表，它的遍历速度很慢，要么是数组列表，它在插入元素时很慢。

我想知道是否可以通过在插入或删除元素时重新映射而不是复制内存来使用处理器的 MMU 更有效地实现列表。这意味着索引和插入/删除数组中任何地方的速度都是 O(1), better than any other list implementation .

我的问题是:

程序是否真的能够控制自己的虚拟内存，或者是否需要对操作系统进行更改？

每个进程的页表条目数是否有限制？随着条目的增加，内存访问会变慢吗？

更改页表条目是否如此缓慢以至于仅对非常大的列表更有效？

是否有此类列表的任何现有实现？如果是，是什么阻止人们更多地使用它们？

Answer 1

首先对您的问题进行一些具体的回答:

是的，在许多操作系统上，程序对其虚拟内存有很大的控制权，例如， mmap 在类 UNIX 操作系统和 similar APIs 上在 Windows 上。特别是 Linux 最近添加了 several methods允许在不复制的情况下从内核对用户可见的缓冲区进行高级操作——但其中一个有趣的是 no longer for this world (至少在性能方面)。

通常，每个进程的页表条目数没有具体限制。当然，您可能会遇到其他限制，例如每个进程的内存限制、物理内存限制等。随着条目的增加，对内存的访问通常不会变慢。当然，访问更多页面可能意味着访问速度变慢(例如，因为您超出了 TLB 的大小)——但这并不是更多页面的直接函数。页表条目本身只是位于 RAM 中，因此您可以毫无问题地拥有数百万个条目。

在现代操作系统上更改页表条目相当快。例如，在我的笔记本电脑上，更改页表条目似乎每页大约需要 120 ns(加上系统调用的一些固定开销)。

是的，您可以找到examples在那里，但他们通常针对相当狭窄的场景。其实可以看到mach的libc尝试使用use MMU tricks对于同样重要的例程than memcpy !

讨论

使用 MMU 技巧的核心问题是 (a) 您只能“零复制”整个页面，这几乎意味着 4K 或更大的粒度，以及类似的限制性对齐 (b) 即使 mmap -type 调用很快，高效的内存复制例程也很快!

我们先来看(a)。如果我理解正确的话，你想加速插入到诸如 std::vector 之类的东西中。通过使用 MMU 技巧来移动发生插入时需要移动的元素。问题是在典型系统上您只能移动 0、4096、8192 等字节!所以如果你插入一个 4 字节 int成 vector<int>这有什么帮助？您或许可以“破解” vector 的底层存储。在插入点分成两部分并跟踪它，希望在某个点再次合并它们(例如，如果你插入了 4096 字节的东西) - 但你最终会得到不同的数据结构，具有不同的属性，以及 MMU 技巧无论如何，这里并不是真正的基础。

这将我们带到(b)。理所当然地，在我的机器上，页面可以在 ~120 ns 内重新映射(通过 mmap )。这看起来很快(当您考虑到它涉及获取各种内核锁、弄乱页表、添加 VMA 等时，这还不错)——但复制内存也非常快。在同一个机器上，我可以以大约 12 GB/s 的速度复制内存(即，到/从任何缓存级别的 RAM)，而在 L1 或 L2 中的复制速度可能为 80-100 GB/s。因此，复制 4K 页面需要 41 ns(缓存)和 340 ns(未缓存，到 RAM)之间的某个时间。因此，即使有可能，弄乱页表也不是一个明显的胜利，尤其是在缓存的情况下(并且缓存的情况可能是主要的情况，对大多数工作负载进行平均)。

所以这些类型的技巧可能有意义，但仅限于特定场景，例如:

您有一些方法可以处理页面映射只能在页面粒度的块中移动/复制/移动事物的事实，例如，因为您的结构恰好是页面粒度的倍数，或者您使用的是倍数的批量插入页面粒度等

您有一些方法可以更快地映射页面:例如，使用 2MB 页面而不是 4K 页面，或者通过编写一些内核端代码来加速您的用例。

您想使用比简单地移动内存更有趣的技巧，例如，。使相同的数据同时出现在两个地方，实现 COW 结构或类似的东西。

重新分配

MMU 技巧最常见和最有用的例子可能是 realloc .在 Linux 和 Windows ( it seems ?) 上， realloc可以通过重新映射和扩展内存中的映射页面(又名 MMU 技巧)来实现，这既避免了物理拷贝，又避免了临时让旧分配区域和新区域同时“事件”的需要(如果它们的总和接近物理内存的大小)。

特别是，最新版本的 Linux 可能会使用 mremap 至 realloc mmap 的堆区域首先是 ed(默认情况下，这发生在大于 128K 的分配请求，但也可能发生在 sbrk 可用空间耗尽时)。