草庐IT

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

coder 2023-06-02 原文

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

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

我的问题是:

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

    • 最佳答案

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

  • 是的，在许多操作系统上，程序对其虚拟内存有很大的控制权，例如， 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 可用空间耗尽时)。

    关于c++ - 使用 MMU 实现可调整大小的数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41498413/

    可调ampcodenoreferrer条目c++listhardware-accelerationmmu

    有关c++ - 使用 MMU 实现可调整大小的数组的更多相关文章

    1. ruby - 如何使用 Nokogiri 的 xpath 和 at_xpath 方法 - 2

      我正在学习如何使用Nokogiri，根据这段代码我遇到了一些问题:require'rubygems'require'mechanize'post_agent=WWW::Mechanize.newpost_page=post_agent.get('http://www.vbulletin.org/forum/showthread.php?t=230708')puts"\nabsolutepathwithtbodygivesnil"putspost_page.parser.xpath('/html/body/div/div/div/div/div/table/tbody/tr/td/div

    2. ruby - 使用 RubyZip 生成 ZIP 文件时设置压缩级别 - 2

      我有一个Ruby程序，它使用rubyzip压缩XML文件的目录树。gem。我的问题是文件开始变得很重，我想提高压缩级别，因为压缩时间不是问题。我在rubyzipdocumentation中找不到一种为创建的ZIP文件指定压缩级别的方法。有人知道如何更改此设置吗？是否有另一个允许指定压缩级别的Ruby库？ 最佳答案 这是我通过查看ruby​​zip内部创建的代码。level=Zlib::BEST_COMPRESSIONZip::ZipOutputStream.open(zip_file)do|zip|Dir.glob("**/*")d

    3. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

      类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

    4. ruby-on-rails - 使用 Ruby on Rails 进行自动化测试 - 最佳实践 - 2

      很好奇，就使用ruby​​onrails自动化单元测试而言，你们正在做什么？您是否创建了一个脚本来在cron中运行rake作业并将结果邮寄给您？git中的预提交Hook？只是手动调用？我完全理解测试，但想知道在错误发生之前捕获错误的最佳实践是什么。让我们理所当然地认为测试本身是完美无缺的，并且可以正常工作。下一步是什么以确保他们在正确的时间将可能有害的结果传达给您？ 最佳答案 不确定您到底想听什么，但是有几个级别的自动代码库控制:在处理某项功能时，您可以使用类似autotest的内容获得关于哪些有效，哪些无效的即时反馈。要确保您的提

    5. ruby - 在 Ruby 中使用匿名模块 - 2

      假设我做了一个模块如下:m=Module.newdoclassCendend三个问题:除了对m的引用之外，还有什么方法可以访问C和m中的其他内容？我可以在创建匿名模块后为其命名吗(就像我输入“module...”一样)？如何在使用完匿名模块后将其删除，使其定义的常量不再存在？ 最佳答案 三个答案:是的，使用ObjectSpace.此代码使c引用你的类(class)C不引用m:c=nilObjectSpace.each_object{|obj|c=objif(Class===objandobj.name=~/::C$/)}当然这取决于

    6. ruby-on-rails - 在 Rails 中将文件大小字符串转换为等效千字节 - 2

      我的目标是转换表单输入，例如“100兆字节”或“1GB”，并将其转换为我可以存储在数据库中的文件大小(以千字节为单位)。目前，我有这个:defquota_convert@regex=/([0-9]+)(.*)s/@sizes=%w{kilobytemegabytegigabyte}m=self.quota.match(@regex)if@sizes.include?m[2]eval("self.quota=#{m[1]}.#{m[2]}")endend这有效，但前提是输入是倍数(“gigabytes”，而不是“gigabyte”)并且由于使用了eval看起来疯狂不安全。所以，功能正常，

    7. ruby - 使用 ruby​​ 和 savon 的 SOAP 服务 - 2

      我正在尝试使用ruby​​和Savon来使用网络服务。测试服务为http://www.webservicex.net/WS/WSDetails.aspx?WSID=9&CATID=2require'rubygems'require'savon'client=Savon::Client.new"http://www.webservicex.net/stockquote.asmx?WSDL"client.get_quotedo|soap|soap.body={:symbol=>"AAPL"}end返回SOAP异常。检查soap信封，在我看来soap请求没有正确的命名空间。任何人都可以建议我

    8. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

      关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

    9. ruby-on-rails - 'compass watch' 是如何工作的/它是如何与 rails 一起使用的 - 2

      我在我的项目目录中完成了compasscreate.和compassinitrails。几个问题:我已将我的.sass文件放在public/stylesheets中。这是放置它们的正确位置吗？当我运行compasswatch时，它不会自动编译这些.sass文件。我必须手动指定文件:compasswatchpublic/stylesheets/myfile.sass等。如何让它自动运行？文件ie.css、print.css和screen.css已放在stylesheets/compiled。如何在编译后不让它们重新出现的情况下删除它们？我自己编译的.sass文件编译成compiled/t

    10. ruby - 使用 ruby​​ 将 HTML 转换为纯文本并维护结构/格式 - 2

      我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h

    随机推荐