首页 文章

如何在C中分配大型动态数组?

提问于
浏览
1

所以 I am currently trying to allocate dynamically a large array of elements in C++ (using "new") . 显然,当"large"变得太大(> 4GB)时,我的程序崩溃了"bad_alloc"异常,因为它无法找到如此大的可用内存块 .

我可以分别分配我的数组的每个元素,然后将指向这些元素的指针存储在一个单独的数组中 . 但是,时间对我的应用程序至关重要,因此我希望避免尽可能多的缓存未命中 . 我也可以将这些元素中的一些组合成块,但这个块的最佳大小是多少?

我的问题是: what is the best way (timewise) to allocate dynamically a large array of elements such that elements do not have to be stored contiguously but they must be accessible by index (using [])? 这个数组永远不会调整大小,不会插入或删除任何元素 .

我认为我可以为此目的使用 std::deque ,因为知道std :: deque的元素可能会或者可能不会连续存储在内存中但是我读到有关于此容器需要多余内存的担忧?

谢谢你对此的帮助!

4 回答

  • 1

    如果您的问题实际上是内存不足,分配相当小的块(如deque所做的那样)无济于事,跟踪分配的开销只会使情况变得更糟 . 您需要重新考虑您的实现,以便您可以在仍然适合内存的块中处理它 . 对于这样的问题,如果使用基于x86或x64的硬件,我会建议至少2兆字节(大页面大小)的块 .

  • 0

    显然,当“大”变得太大(> 4GB)时,我的程序崩溃并出现“bad_alloc”异常,因为它无法找到如此大的可用内存块 .

    此时你应该使用64位CPU和OS,分配巨大的连续内存块应该不是问题,除非你实际上内存不足 . 您可能正在构建32位程序 . 在这种情况下,您将无法分配超过4 GB . 您应该构建64位应用程序 .

    如果你想要比普通_1690662更好的东西,那么你的问题是特定于操作系统的 . 查看操作系统提供的API:在POSIX系统上,您应该在Windows上查找 mmapVirtualAlloc .

    大量分配存在多个问题:

    • 出于安全原因,OS内核永远不会为您提供填充垃圾值的页面,而是所有新内存都将初始化为零 . 这意味着只要零完全符合您的要求,您就不必初始化该内存 .

    • 操作系统在首次访问时懒洋洋地为您提供真正的内存 . 如果您正在处理大型阵列,则可能会浪费大量时间来处理页面错误 . 为避免这种情况,您可以在Linux上使用 MAP_POPULATE . 在Windows上,您可以尝试 PrefetchVirtualMemory (但我不确定它是否可以完成这项工作) . 这应该使init分配更慢,但应该减少在内核中花费的总时间 .

    • 使用大块内存浪费转换后备缓冲区(TLB)中的插槽 . 根据您的内存访问模式,这可能会导致明显的减速 . 为避免这种情况,您可以尝试使用大页面( mmapMAP_HUGETLBMAP_HUGE_2MBMAP_HUGE_1GB 在Linux上, VirtualAllocMEM_LARGE_PAGES ) . 使用大页面并不容易,因为默认情况下它们通常不可用 . 它们也无法换出(总是"locked in memory"),因此使用它们需要特权 .

    如果您不想使用特定于操作系统的功能,那么您在C中找到的最佳功能是 std::calloc . 与 std::mallocoperator new 不同,它返回零初始化内存,因此您可以避免浪费时间初始化该内存 . 除此之外,该功能没有什么特别之处 . 但这是您在使用标准C时可以获得的最接近的 .

    没有设计用于处理大量分配的标准容器,而且,所有标准容器在处理这些情况时确实非常糟糕 .

    一些操作系统(如Linux)过度使用内存,而其他操作系统(如Windows)则不会 . 如果Windows知道以后无法满足您的请求,Windows可能会拒绝为您提供内存 . 为避免这种情况,您可能希望增加页面文件 . Windows需要预先在磁盘上保留该空间,但这并不意味着它将使用它(开始交换) . 由于实际内存是懒惰地给予程序,因此可能会有大量内存保留给永远不会实际给予它们的应用程序 .

    如果增加页面文件太不方便,可以尝试创建大文件并将其映射到内存中 . 该文件将作为您的记忆"page file" . 见 CreateFileMappingMapViewOfFile .

  • 0

    这个问题的答案非常适用,并且平台,依赖 . 如果你只需要一个大于4GB的小整数因子,如果可能的话,你可以使用64位机器 . 有时也可以减小数组中元素的大小 . (例如,使用16位定点的半浮点而不是32位浮点数 . )

    除此之外,您要么关注稀疏数组还是核外技术 . 当您实际上没有在数组中的所有位置存储元素时,将使用稀疏数组 . 有许多可能的实现,并且最好取决于数据的分布和算法的访问模式 . 例如,请参见Eigen .

    Out-of-core涉及明确地从磁盘读取和写入数组的部分内容 . 这曾经相当普遍,但人们现在很难避免这样做 . 真正需要的应用程序通常 Build 在数据库或类似的数据库之上以处理数据管理 . 在科学计算中,最终需要分配计算和数据存储,因此也存在很多复杂性 . 对于重要问题,整个设计可以通过具有良好的参考局部性来驱动 .

    任何稀疏数据结构都会占用多少空间 . 这可能相当低,但这意味着如果你实际上有一个密集的数组并且只是想避免内存碎片,你必须要小心 .

    如果您的问题可以分解成只能一次访问数组的一部分而且主要问题是内存碎片使得很难分配一个大块,然后将数组分成几部分,有效地添加指针的外部向量,是个不错的选择 . 如果您可以随机访问大于4千兆字节的数组并且无法本地化访问,那么64位是可行的方法 .

  • 2

    根据您需要的内存和速度问题,如果您使用的是Linux,您可以尝试使用mmap并模拟某种交换 . 它可能会更慢,但您可以映射非常大的尺寸 . 见Mmap() an entire large file

相关问题