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

Question

通常，列表可以实现为链表（遍历速度较慢），也可以实现为数组列表（插入元素时速度较慢）。

我想知道是否有可能使用处理器的MMU来更有效地实现列表，只要插入或删除一个元素，就可以重新映射而不是复制内存。这意味着数组中任何地方的索引和插入/删除速度都要达到O（1），比任何其他列表实现都要好。

我的问题是：

• 程序是否真的能够控制自己的虚拟内存，或者是否需要对操作系统进行更改
• 每个进程的页表条目数是否有限制？输入越多，内存访问速度会变慢吗
• 更改页表条目的速度是否太慢，以至于只有在非常大的列表中才能更有效
• 有没有这种列表的现有实现？如果是，是什么阻止人们更多地使用它们

Answer 1

首先是对你的问题的一些具体回答：

• 是的，在许多操作系统上，程序对其虚拟内存有很大的控制，例如，类似UNIX的操作系统和视窗上类似的应用编程接口上的mmap。Linux最近特别添加了几种方法，允许在不复制的情况下从内核高级操作用户可见的缓冲区——但是其中一个有趣的方法不再适用于这个世界（至少在性能方面）。
• 通常，每个进程的页表条目数量没有特定的限制。当然，您可能会遇到其他限制，例如每个进程的内存限制、物理内存限制等。对内存的访问通常不会因为条目越多而变慢。当然，对更多页面的访问总数可能意味着访问速度变慢（例如，因为您超过了TLB的大小）——但这并不是页面越多的直接函数。页表条目本身只是放在内存中，所以您可以拥有数百万个条目而不会有问题。
• 在现代操作系统上，更改页表条目相当快。例如，在我的笔记本电脑上，更改页表条目似乎每页需要大约120 ns（加上系统调用的一些固定开销）。
• 是的，你可以在那里找到例子，但是它们通常针对相当狭窄的场景。事实上，你可以看到mach的libc试图使用MMU技巧来完成一个不亚于memcpy的重要例程！

使用MMU技巧的核心问题是（a）你只能零拷贝整个页面，这几乎意味着4K粒度或更大，以及类似的限制性对齐（b）即使mmap类型的调用很快，高效的内存拷贝例程也是如此！

让我们先来看（a）。如果我理解正确的话，您希望通过使用MMU技巧来移动插入时需要移动的元素，从而加速插入到类似于std:：vector的内容中。问题是，在典型的系统上，只能移位0、4096、8192等字节！所以如果你在向量中插入一个4字节的int

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

因此，这些技巧可能有意义，但只适用于特定场景，例如：

• 你有办法处理这样一个事实：页面映射只能在页面粒度的块中移动/复制/移动，例如，因为你的结构恰好是页面粒度的倍数，或者你使用的批插入是页面粒度的倍数，等等。

MMU技巧最常见和最有用的例子可能是realloc。在Linux和Windows（似乎？）上，realloc可以通过重新映射和扩展内存中映射的页面来实现（也称为MMU技巧），这既避免了物理复制，也避免了临时同时让旧的分配区域和新的区域“活”的需要（如果它们的总和接近物理内存的大小，这可能很难）。

特别是，最新版本的Linux可能会使用mremap来realloc堆区域，这些区域最初是mmaped（默认情况下，对于大于128K的分配请求会发生这种情况，但当sbrk可用空间耗尽时也可能发生这种情况）。