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

Question

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

c++listhardware-accelerationmmu

15

通常，列表实现为链表或数组列表。链表遍历速度较慢，而数组列表在插入元素时速度也很慢。

我在想，是否可以利用处理器的MMU更有效地实现列表，通过重新映射而不是复制内存来进行元素插入或删除。这意味着对于数组中的任何位置，索引和插入/删除都具有O（1）的速度，比任何其他列表实现更好。

我的问题是：

程序实际上能控制自己的虚拟内存吗，还需要对操作系统进行更改吗？
每个进程的页表项数量是否有限制？随着条目增加，内存访问是否变得更慢？
更改页表项是否如此缓慢，以至于这仅适用于非常大的列表？
是否存在此类型列表的任何现有实现？如果有，是什么阻止人们更多地使用它们？

- d9584

1

作为一个很好的入门点，可以查看以下链接：https://msdn.microsoft.com/zh-cn/library/windows/desktop/aa366887(v=vs.85).aspx。总之，虚拟内存管理可以由应用程序控制。但是处理的页面大小并不是任意的。因此，如果您想尝试自己的想法，请继续尝试。但是，如果您的列表项比页面大小小，那么您将浪费大量（虚拟）内存...无论如何，我怀疑您最终是否会得到有用/高效的东西。但是，对于有创造力的灵魂，还是要给予赞扬！ - BitTickler

2

大多数现代CPU使用适度但相当大的页面大小。 4kb和8kb是典型值。 MMU只能用于映射是页面大小的偶数倍的内存块。除非你的对象具有精确的对齐方式，并且它们的大小是页面大小的偶数倍，否则MMU将无用。即使您已经成功解决这些问题：祝你好运自己编写操作系统！ - Sam Varshavchik

如果你对最新的数据结构技术感兴趣，可以了解一下“持久化数据结构”。这些想法来自函数式编程，但同样适用于C++/Rust等系统代码。 - BitTickler

2

https://uic.pure.elsevier.com/en/publications/evector-an-efficient-vector-implementation-using-virtual-memory-f - user1779715

1

你不应该过于认真地看待O()符号。对于任何合理的n，$O(1)$和$O(\log n)$之间的差异可能小于乘法常数的差异。使用MMU意味着调用具有重大成本的操作系统。 - Stig Hemmer

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- BeeOnRope · Accepted Answer

首先回答您的一些具体问题：

是的，在许多操作系统中，程序对其虚拟内存有着重要的控制权，例如，在类UNIX操作系统上使用mmap，在Windows上使用类似的API。特别是Linux最近添加了几种方法，允许从内核中高级操作用户可见缓冲区而不需要复制 - 但其中一个有趣的方法已经不再适用于这个世界（至少在性能方面）。
通常，每个进程的页面表项数量没有特定的限制。当然，你可能会遇到其他限制，例如每个进程的内存限制、物理内存限制等。随着页面条目数的增加，访问内存通常不会变慢。当然，总体访问更多页面可能意味着访问变慢（例如，因为超出TLB的大小）- 但这不是直接与更多页面相关的功能。页面表项本身只是坐在RAM中，因此可以拥有数百万个页面表项而不会出现问题。
在现代操作系统上，更改页面表项是相当快的。例如，在我的笔记本电脑上，更改页面表项似乎需要大约每个页面120 ns（加上一些系统调用的固定开销）。
是的，你可以找到例子，但它们通常针对相当狭窄的情况。实际上，你可以看到mach的libc尝试使用MMU技巧来处理比memcpy更重要的例程！

讨论

使用MMU技巧的核心问题在于：(a)你只能“零拷贝”整个页面，这几乎意味着以4K粒度或更大的方式进行操作，同时需要相应的对齐 (b)即使mmap类型的调用很快，高效的内存复制例程也是如此！

首先看看(a)。如果我理解正确，您想通过使用MMU技巧来加速将元素插入到类似std::vector的数据结构中，并在插入发生时移动需要移动的元素。问题是，您只能在典型系统上按0、4096、8192等字节进行移动！因此，如果您将一个4字节的int插入到vector<int>中，那有什么帮助呢？也许您可以将vector的底层存储在插入点处“分开”，并跟踪它，希望在某个时候再次合并它们（例如，如果您插入了4096字节的内容），但最终您会得到一个具有不同属性的不同数据结构，而且MMU技巧在这里并没有真正起到根本作用。

现在我们来看(b)。假设在我的电脑上，通过 mmap 可以在约120纳秒内重新映射一个页面。这似乎很快（考虑到它涉及获取各种内核锁、处理页表、添加VMA等），但是复制内存也非常快。在同一台机器上，我可以在内存中复制（即从任何高速缓存级别的RAM中复制/复制到RAM）约12 GB/s，而在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可用空间耗尽时也可能发生）。