使用 MMU 实现可调整大小的数组
Using MMU to implement resizable arrays
通常，列表实现为链表，遍历速度慢，或者数组列表，插入元素时速度慢。
我想知道是否可以使用处理器的 MMU 更有效地实现列表，方法是在插入或删除元素时重新映射而不是复制内存。这意味着数组中任何位置的索引和 insertion/deletion 都具有 O(1)，better than any other list implementation 的速度。
我的问题是：
- 程序是否真的能够控制自己的虚拟内存，或者是否需要对 OS 进行更改？
- 每个进程的页面 table 条目数是否有限制？条目越多，内存访问越慢吗？
- 更改页面 table 条目的速度是否如此之慢以至于仅对非常大的列表更有效？
- 是否存在此类列表的现有实现？如果是，是什么阻止人们更多地使用它们？
首先对您的问题进行一些具体的回答：
- 是的，在许多操作系统上，程序对其虚拟内存有很大的控制权，例如
mmap on UNIX-like OSes and similar APIs on Windows. Linux in particular has recently added several methods to allow advanced manipulation of user-visible buffers from the kernel without copying — but one of the interesting ones is no longer for this world（至少在性能方面）。
- 通常，每个进程的页面 table 条目数没有具体限制。当然，你可能 运行 变成 其他 限制，比如每个进程的内存限制，物理内存限制等等。对内存的访问通常不会随着条目的增加而变慢。当然，总共访问更多 页 可能意味着访问速度较慢（例如，因为您超过了 TLB 的大小）——但这并不是更多页的直接函数。页面 table 条目本身就位于 RAM 中，因此您可以毫无问题地拥有数百万个条目。
- 更改页面 table 条目在现代操作系统上 相当快 。例如，在我的笔记本电脑上，更改页面 table 条目似乎每页大约需要 120 ns（加上系统调用的一些固定开销）。
- 是的，你可以找到 examples out there, but they generally target fairly narrow scenarios. In fact, you can see that the mach's libc tries to use use MMU tricks for no less an important routine than memcpy!
讨论
使用 MMU 技巧的核心问题是 (a) 您只能 "zero copy" 整个页面，这几乎意味着 4K 粒度或更大，以及类似的限制性对齐 (b) 即使 mmap 类型的调用速度很快，内存复制例程也很高效！
我们先来看(a)。如果我理解正确的话，您想通过使用 MMU 技巧来移动插入发生时需要移动的元素来加速插入 std::vector 之类的东西。问题是您只能在典型系统上移动 0、4096、8192 等字节！因此，如果您将一个 4 字节 int 插入到 vector<int> 中，这有什么帮助？您也许可以 "crack apart" vector 的底层存储在插入点分为两部分并跟踪它，希望在某个点再次合并它们（例如，如果您插入 4096 字节的东西）-但是你最终会得到一个不同的数据结构，具有不同的属性，而且 MMU 技巧在这里并不是真正的基础。
这将我们带到 (b)。想当然地认为在我的机器上可以在 ~120 ns 内重新映射一个页面（通过 mmap）。这看起来很快（当你考虑到它涉及获取各种内核锁、弄乱页面 tables、添加 VMA 等时，这还不错）——但复制内存也是 also非常快。在同一个盒子上，我可以在大约 12 GB/s 处复制内存（即 to/from 任何缓存级别的 RAM），而 L1 或 L2 中的副本可能在 80-100 GB/s 处进行].因此，复制一个 4K 页面需要 41 ns（缓存）和 340 ns（未缓存，到 RAM）之间的某个时间。因此，即使 可能 ，弄乱页面 tables 也不是一个明显的胜利，尤其是在缓存的情况下（并且缓存的情况可能是主要的，平均大多数工作负载）。
所以这些类型的技巧可能有意义，但仅在特定场景下，例如：
- 你有一些方法来处理页面映射只能 move/copy/shift 页面粒度块中的事情，例如，因为你的结构恰好是页面粒度的倍数，或者你使用批处理插入页面粒度的倍数等
- 您有一些方法可以更快地映射页面：例如，使用 2MB 页面而不是 4K 页面，或者通过编写一些内核端代码来加速您的用例。
- 您想使用比简单移动内存更高级的技巧，例如。让相同的数据同时出现在两个地方，实现 COW 结构，或类似的东西。
重新分配
MMU 技巧 最常见和有用的例子可能是 realloc。在 Linux 和 Windows (it seems?) 上，realloc 可以通过在内存中重新映射和扩展映射页面（又名 MMU 技巧）来实现，这都避免了物理复制并且需要同时临时拥有旧分配区域和新区域 "live"（如果它们的总和接近物理内存的大小，这可能很难）。
特别是，Linux 的最新版本可能会使用 mremap 到 realloc 堆区域，这些区域首先被 mmaped（默认情况下，这会发生对于大于 128K 的分配请求，但也可能在 sbrk 可用的 space 耗尽时发生。
通常，列表实现为链表，遍历速度慢，或者数组列表，插入元素时速度慢。
我想知道是否可以使用处理器的 MMU 更有效地实现列表，方法是在插入或删除元素时重新映射而不是复制内存。这意味着数组中任何位置的索引和 insertion/deletion 都具有 O(1)，better than any other list implementation 的速度。
我的问题是：
- 程序是否真的能够控制自己的虚拟内存，或者是否需要对 OS 进行更改？
- 每个进程的页面 table 条目数是否有限制？条目越多，内存访问越慢吗？
- 更改页面 table 条目的速度是否如此之慢以至于仅对非常大的列表更有效？
- 是否存在此类列表的现有实现？如果是，是什么阻止人们更多地使用它们？
首先对您的问题进行一些具体的回答：
- 是的，在许多操作系统上，程序对其虚拟内存有很大的控制权，例如
mmapon UNIX-like OSes and similar APIs on Windows. Linux in particular has recently added several methods to allow advanced manipulation of user-visible buffers from the kernel without copying — but one of the interesting ones is no longer for this world（至少在性能方面）。 - 通常，每个进程的页面 table 条目数没有具体限制。当然，你可能 运行 变成 其他 限制，比如每个进程的内存限制，物理内存限制等等。对内存的访问通常不会随着条目的增加而变慢。当然，总共访问更多 页 可能意味着访问速度较慢（例如，因为您超过了 TLB 的大小）——但这并不是更多页的直接函数。页面 table 条目本身就位于 RAM 中，因此您可以毫无问题地拥有数百万个条目。
- 更改页面 table 条目在现代操作系统上 相当快 。例如，在我的笔记本电脑上，更改页面 table 条目似乎每页大约需要 120 ns（加上系统调用的一些固定开销）。
- 是的，你可以找到 examples out there, but they generally target fairly narrow scenarios. In fact, you can see that the mach's libc tries to use use MMU tricks for no less an important routine than memcpy!
讨论
使用 MMU 技巧的核心问题是 (a) 您只能 "zero copy" 整个页面，这几乎意味着 4K 粒度或更大，以及类似的限制性对齐 (b) 即使 mmap 类型的调用速度很快，内存复制例程也很高效！
我们先来看(a)。如果我理解正确的话，您想通过使用 MMU 技巧来移动插入发生时需要移动的元素来加速插入 std::vector 之类的东西。问题是您只能在典型系统上移动 0、4096、8192 等字节！因此，如果您将一个 4 字节 int 插入到 vector<int> 中，这有什么帮助？您也许可以 "crack apart" vector 的底层存储在插入点分为两部分并跟踪它，希望在某个点再次合并它们（例如，如果您插入 4096 字节的东西）-但是你最终会得到一个不同的数据结构，具有不同的属性，而且 MMU 技巧在这里并不是真正的基础。
这将我们带到 (b)。想当然地认为在我的机器上可以在 ~120 ns 内重新映射一个页面（通过 mmap）。这看起来很快（当你考虑到它涉及获取各种内核锁、弄乱页面 tables、添加 VMA 等时，这还不错）——但复制内存也是 also非常快。在同一个盒子上，我可以在大约 12 GB/s 处复制内存（即 to/from 任何缓存级别的 RAM），而 L1 或 L2 中的副本可能在 80-100 GB/s 处进行].因此，复制一个 4K 页面需要 41 ns（缓存）和 340 ns（未缓存，到 RAM）之间的某个时间。因此，即使 可能 ，弄乱页面 tables 也不是一个明显的胜利，尤其是在缓存的情况下（并且缓存的情况可能是主要的，平均大多数工作负载）。
所以这些类型的技巧可能有意义，但仅在特定场景下，例如：
- 你有一些方法来处理页面映射只能 move/copy/shift 页面粒度块中的事情，例如，因为你的结构恰好是页面粒度的倍数，或者你使用批处理插入页面粒度的倍数等
- 您有一些方法可以更快地映射页面：例如，使用 2MB 页面而不是 4K 页面，或者通过编写一些内核端代码来加速您的用例。
- 您想使用比简单移动内存更高级的技巧，例如。让相同的数据同时出现在两个地方，实现 COW 结构，或类似的东西。
重新分配
MMU 技巧 最常见和有用的例子可能是 realloc。在 Linux 和 Windows (it seems?) 上，realloc 可以通过在内存中重新映射和扩展映射页面（又名 MMU 技巧）来实现，这都避免了物理复制并且需要同时临时拥有旧分配区域和新区域 "live"（如果它们的总和接近物理内存的大小，这可能很难）。
特别是，Linux 的最新版本可能会使用 mremap 到 realloc 堆区域，这些区域首先被 mmaped（默认情况下，这会发生对于大于 128K 的分配请求，但也可能在 sbrk 可用的 space 耗尽时发生。