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

Question

通常,列表既可以作为链接列表实现,也可以作为数组列表实现,这些列表在插入元素时很慢.

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

我的问题是:

• 程序是否实际上能够控制自己的虚拟内存,还是需要对操作系统进行更改？
• 每个进程的页表条目数是否有限制？更多条目的内存访问速度会变慢吗？
• 更改页表条目是否太慢以至于仅对非常大的列表更有效？
• 这种类型的列表是否存在任何实现？如果是,是什么阻止人们更多地使用它们？

Answer 1

首先是您的问题的一些具体答案:

• 是的,在许多操作系统上,程序可以对其虚拟内存进行重要控制,例如,mmap在类似 UNIX的操作系统和Windows上的类似API上.特别是Linux最近添加了几种 方法,允许从内核高级操作用户可见的缓冲区而无需复制 - 但其中一个有趣的方法已不再适用于这个世界(至少在性能方面).
• 通常,每个进程的页表条目数没有特定限制.当然,您可能会遇到其他限制,例如每进程内存限制,物理内存限制等.对于更多条目,访问内存通常不会变慢.当然,总共访问更多页面可能意味着访问速度较慢(例如,因为您超出了TLB的大小) - 但这并不直接是更多页面的功能.页表条目本身只是位于RAM中,因此您可以拥有数百万条而没有问题.
• 在现代操作系统上更改页表条目的速度相当快.例如,在我的笔记本电脑上,更改页表条目似乎需要每页大约120 ns(加上系统调用的一些固定开销).
• 是的,您可以找到示例,但它们通常针对相当狭窄的场景.事实上,你可以看到马赫的libc尝试使用MMU技巧,而不是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结构,或类似的东西.

的realloc

最常见和最有用的MMU技巧的例子可能是realloc.在Linux和Windows上(似乎？),realloc可以通过重新映射和扩展内存中的映射页面(也称为MMU技巧)来实现,这既避免了物理复制,又需要暂时同时拥有旧的分配区域和新区域" "立即生活"(如果他们的金额接近物理记忆的大小,可能很难).

特别是,最新版本的Linux可能会使用mremap到realloc了这堆地区mmap位居第一编(默认情况下,发生这种情况的分配请求大于128K,但是当提供给空间也可能会出现它sbrk耗尽).