在C++中使用realloc

Question

std::realloc在C++中存在风险，如果malloc的内存包含非pod类型。唯一的问题似乎是，如果无法原地扩展内存，std::realloc将不会调用类型解构函数。

一个微不足道的解决方法是一个try_realloc函数。如果无法在原地增长，则它不会malloc新内存，只需返回false。在这种情况下，可以分配新内存，将对象复制（或移动）到新内存，最后释放旧内存。

这似乎非常有用。std::vector可能会大量使用它，可能避免所有复制/重新分配。
预先防护性灭火器：技术上而言，这与Big-O性能相同，但如果向量增长是应用程序的瓶颈，则即使Big-O保持不变，x2加速也很好。

但是，我找不到任何类似于try_realloc的c api。

我错过了什么吗？try_realloc不像我想象的那么有用吗？是否存在某些隐藏的bug使try_realloc无法使用？

更好的是，是否存在一些不太记录的API可以像try_realloc一样执行？

注意：很明显，我在特定于库/平台的代码中。我不担心try_realloc本质上是一种优化。

---

更新：根据Steve Jessops对于vector是否更高效地使用realloc的评论，我编写了一个概念验证来测试。 realloc-vector模拟了向量的增长模式，但具有realloc选项。 我将程序运行到向量的一百万个元素。

为了比较，vector在增长到一百万个元素时必须分配19次。

如果 realloc-vector 是唯一使用堆的东西，结果非常棒，只需3-4次分配就能将大小增长到百万字节。

如果 realloc-vector 与一个以66%的速度增长的 vector 同时使用，则结果不那么可靠，在增长过程中需要进行8-10次分配。

最后，如果 realloc-vector 与以相同速度增长的 vector 同时使用，则 realloc-vector 需要进行17-18次分配。与标准向量行为相比，仅节省一个分配的效果微乎其微。

我不怀疑黑客可以通过游戏化分配大小来提高节省效果，但我同意 Steve 的看法，编写和维护这样的分配器所需的巨大努力并不值得回报。

- deft_code

---

如果不知道你想要针对哪个平台，很难提供特定于平台的建议。 - Jerry Coffin

我不禁想到：如果你想要最佳性能，使用vector.reserve()，这样你就不必再扩展向量了。 - Johan Kotlinski

但是你并不能总是这样做，否则向量类的动态增长特性将变得无用。 - Konrad Rudolph

如果你的vector所持有的对象的复制性能很差，而且由于某种原因你不能使用deque，那么也许你应该将你的vector改为持有指向对象的shared_ptr实例。这样复制操作就会变得更加便宜。我不确定unique_ptr对象是否可以用于标准容器，但这样做甚至可以进一步减少复制开销。 - Praetorian

要在C++中使用realloc（或类似函数）处理非POD（普通旧数据）类型，不仅需要在失败的情况下调用析构函数，还需要在缩小数组的情况下调用它。如果数组正在增长，则还必须对新成员调用默认构造函数。另一个需要考虑的问题是移动对象可能会导致一些问题；类可能需要实现一个移动方法，这个方法类似于析构函数-重建函数，它具有对旧数据和新数据的引用，但移动的顺序可能很重要。 - nategoose

Answer 1

vector通常以大的增量增长。如果没有仔细安排，使得向量内部缓冲区上方有足够多的空闲地址(这实际上需要分配整个页面，因为显然不能在同一页上进行其他分配)，就无法重复执行此操作而不进行重新定位。

因此，我认为为了获得真正好的优化，你需要更多的“简单解决方法”，如果可能的话，会进行廉价的重新分配，但你必须在某种程度上进行一些准备工作，以使其成为可能，并且这项准备工作将占用你的地址空间。如果只对一些指示它们将变得很大的向量执行此操作，那么这项操作就是相当无意义的，因为它们可以使用reserve()指示它们将变得很大。如果您希望自动为所有向量执行此操作，则只能拥有巨大的地址空间，从而可以在每个向量上“浪费”一大块空间。

据我所知，Allocator概念没有重新分配功能是为了保持其简单性。如果std::allocator具有try_realloc函数，则每个Allocator都必须有一个(在大多数情况下无法实现，并且只能始终返回false)，或者每个标准容器都必须为std::allocator特化以利用它。没有一种伟大的分配器接口，尽管我认为对于几乎所有Allocator类的实现者来说，只需添加一个无操作的try_realloc函数不会是一个巨大的努力。

如果由于重新分配而使vector变慢，那么deque可能是一个很好的替代品。

- Steve Jessop

---

我假设 try_realloc 是非常便宜的。当一个 vector 的容量超过了默认的指数增长时，它会使用 try_realloc 来增加容量。当 try_realloc 无法再进行增长而需要重新分配内存时，就会分配两倍所需的内存，执行标准的复制/移动操作，将容量加倍。 - deft_code

通常情况下，我不明白为什么 try_realloc 操作应该比 malloc 快多少。 - Johan Kotlinski

@caspin：但是，你的方法究竟比vector本身更有效率在哪呢？因为就算假设每次重新定位时它仍然会将其容量加倍，也不见得有什么区别。我认为，你唯一获得的好处就是，在你的版本中，这些额外的内存还没真正被分配，所以可以用于分配给其他用途。如果没有用到，那么就没有任何区别；如果用到了，那么你实际上还会拖慢向量运行速度，因为你的try_realloc失败的可能性要比我的"额外容量"耗尽的可能性更高。即使使用过度提交（overcommit），在我的版本中，也可以避免"真正使用"物理内存。 - Steve Jessop

@caspin：我认为你的方法在以下情况下更好，即仅出于运气，在向量要扩展到缓冲区上方时，存在大量的可用内存。这很好，但正如我所说，我认为这种情况太少了，不值得将其构建到接口中，因为 deque 存在以支持增长不可预测且复制性能糟糕的情况。也许标准的作者们也这样认为，或者可能有其他原因 - 我不知道。 - Steve Jessop

@caspin：说得对。如果vector愿意做出特定于平台的假设/猜测，那么它理论上可以确保其增加容量的序列恰好适应内存分配器实际提供的块大小，从而避免发生这种糟糕的向量性能情况。这个序列可能是32、64、128，也可能是24、56、120。如果你想将这部分作为可移植的分配器接口的一部分，我认为你需要付出很大努力，只是为了避免使用deque；-) - Steve Jessop

Answer 2

您可以实现类似于您提出的try_realloc的东西，使用mmap和mremap，其中将mmap与MAP_ANONYMOUS和MAP_FIXED一起使用，而将mremap与MREMAP_FIXED一起使用。 编辑：刚刚注意到mremap的man页甚至说：

mremap()使用Linux页表方案。mremap()更改虚拟地址和内存页面之间的映射关系。这可用于实现非常高效的realloc(3)。

- Flexo

---

问题在于使用mmap进行最小分配的大小是一页，对于大多数向量来说这是巨大的浪费。 - Donal Fellows

同意，但我认为没有任何子页面大小的分配器可以提供这种功能，如果它比一页或者更小，则性能优势可能会微不足道。 - Flexo

Answer 3

realloc在C语言中只是一个方便函数，对于提高性能/减少拷贝的好处非常有限。我能想到的主要例外是代码分配了一个大数组，然后一旦所需大小已知就减小大小 - 但即使这样也可能需要在某些malloc实现（严格按大小分离块的实现）上移动数据，因此我认为这种使用realloc是真正糟糕的做法。

只要你不是每次添加元素时都不断重新分配数组，而是在空间不足时指数级增长数组（例如增加25％、50％或100％），手动分配新内存，复制并释放旧内存将产生大致相同的（在内存碎片化的情况下完全相同的）性能与使用realloc相当。这肯定是C++ STL实现使用的方法，所以我认为你的整个关注点是没有根据的。

编辑：唯一（罕见但并非闻所未闻）realloc实际上有用的情况是在具有虚拟内存的系统中用于巨大块，在该系统中C库与内核交互以将整个页面重定位到新地址。我之所以说这很少见是因为你需要处理非常大的块（至少几百KB）才能进入大多数实现将进入处理页面粒度分配的领域，并且可能更大（几MB也许）才能进入并退出内核空间以重新排列虚拟内存比仅进行复制更便宜。当然，try_realloc在这里是无用的，因为整个好处来自于以低廉的代价实际上进行移动。

- R.. GitHub STOP HELPING ICE

---

我认为一旦分配的内存增长到兆字节，指数分配策略的绝对开销可能开始成为问题，因此仅在该大小范围内进行优化仍然是好的。另一个realloc好用的情况是当有一个循环，只重新分配一个内存块，最终应该结束在堆位置，可以在不复制的情况下进行扩展。而且复制的绝对成本随着块大小的增加而增加，因此仅应用于大块的优化仍然是好的。 - hyde