如何管理大型数组

Question

我有一个使用多个非常大的double数组的c++程序，我想减少程序的内存占用。目前，我正在分配100个数组，每个数组可能需要100Mb。

现在，我有一个优势，即这些数组的某些部分在程序执行的后期变得过时了，因此没有必要一次性将它们全部保留在内存中。

我的问题是：

是否有一种方法可以在我使用new或malloc创建数组之后告诉操作系统不再需要其中的一部分？

我得出的结论是，唯一的实现方法可能是声明一个指针数组，每个指针可能指向所需数组的1Mb块，以便不需要的旧块可以重用于新的数组部分。这似乎是编写自定义内存管理器，会对性能造成影响。

我无法移动数组中的数据，因为这将导致太多的线程争用问题。这些数组可由任意数量的线程访问，但只有一个线程会写入到任何一个给定的数组中。

- camelccc

---

通常解决大型数组问题的方法是使用稀疏数组——一种看起来像数组的数据结构，但实际上只存储相关元素。如果数组中有很多空白空间，这种方法就可以奏效。在这里是否也是如此呢？或者在某个时刻，您实际上需要给定数组中的所有元素吗？ - Ernest Friedman-Hill

一个特定于平台的解决方案是否可行？Posix允许您mmap一个大区域，然后在您完成使用它们后munmap其中的一部分。 - Mike Seymour

Answer 1

这取决于操作系统。POSIX（包括Linux）具有系统调用madvise来提高内存性能。从man页面中可以看到：

“madvise()系统调用建议内核如何处理在地址addr和大小为length字节的范围内的页面输入/输出。它允许应用程序告诉内核它希望如何使用一些映射或共享内存区域，以便内核可以选择适当的预读和缓存技术。这个调用不影响应用程序的语义（除了MADV_DONTNEED的情况），但可能影响其性能。内核可以忽略这个建议。”

有关更多信息，请参见madvise的man页面。

编辑：显然，上述描述并不清楚。因此，以下是一些更多详细信息，其中一些是特定于Linux的。

您可以使用mmap来分配一个内存块（直接从操作系统而不是libc），该内存块不由任何文件支持。对于大块内存，malloc正在执行完全相同的操作。无论使用madvise与否，您都必须使用munmap来释放内存。

void* data = ::mmap(nullptr, size, PROT_READ | PROT_WRITE,
    MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
// ...
::munmap(data, size);

如果你想要移除这个块的一些部分，你可以使用madvise命令告诉内核去做：

madvise(static_cast<unsigned char*>(data) + 7 * page_size,
    3 * page_size, MADV_DONTNEED);

地址范围仍然有效，但它不再受物理RAM或存储支持。如果您稍后访问页面，则内核将在运行时分配一些新页面并重新初始化为零。请注意，dontneed页面也是进程虚拟内存大小的一部分。可能需要对虚拟内存管理进行一些配置更改，例如激活超额提交。

- nosid

---

但是您不应该在之后使用free或delete释放内存；这可能会尝试重用进程无法访问的内存。 - Mike Seymour

只是浏览mmap的man页面。使用MAP_NORESERVE和MAP_ANONYMOUS或两者一起调用有什么好处？ - camelccc

MAP_NORESERVE 是关于内存超额承诺的，即使可能会出现后续无法提供的情况，初始内存分配是否成功。如果您计划立即使用内存，则不应使用 MAP_NORESERVE。 - nosid

Answer 2

如果我们有更多详细信息，回答会更容易。

1°）针对问题“在使用new或malloc创建数组后，是否有任何方法告诉操作系统某部分不再需要？” 的答案是“实际上没有”。这就是C和C ++的重点以及任何让您手动处理内存的语言。

2°）如果您正在使用C++而不是C，则不应使用malloc。

3°）除非出于非常特定的原因，否则不要使用数组。使用std::vector。

4°）最好使用链表（std::list），如果需要经常更改数组内容并减少内存占用量，尽管这将更昂贵地逐个“访问”列表内容（但如果只迭代通过它，速度几乎相同）。

- Raveline

Answer 3

一个带有指向 std::array<double,LARGE_NUMBER> 的指针的 std::deque 可以完成工作，但最好使用专用容器与 deque 一起使用，这样您可以重新映射索引，最重要的是定义何时不再使用条目。

专用容器还可以包含读/写锁，因此可以以线程安全的方式使用它。

- stefaanv

Answer 4

你可以尝试使用列表而不是数组。当然，列表比数组更“重”，但另一方面，很容易重构列表，以便在它变得过时时可以丢弃其中的一部分。你也可以使用一个包装器，它只包含索引，指示列表的哪个部分是最新的，哪个部分可以被重用。 这将有助于提高性能，但需要更多（可重用的）内存。

- superM

---

不过，列表必须按顺序访问。迭代访问列表以访问1000000+元素将会很慢。 - camelccc

如果每次只使用列表的一部分，那么它不会变得非常缓慢。实际上，这取决于列表的实现方式。std中的列表实现非常优化，性能不应该变得更慢。 - superM

Answer 5

通过分块分配并在过程中使用delete[]和new[]似乎是一个好的解决方案。尽可能少地进行内存管理可能是可行的。不要自己重复使用块，只需在需要时释放旧块并分配新块即可。

- log0