避免多态容器中的内存碎片问题

Question

避免多态容器中的内存碎片问题

c++memory-managementcollectionscontainers

3

这个问题需要一些解释，如果您不跳过示例，请点赞：）

最近我读了一本书，详细描述了堆内存碎片的情况，这让我开始思考我的项目。例如，在以下方式中使用ptr_container（来自Boost）时：

ptr_array<A> arr;       // 
arr.push_back(new A()); // a1.
arr.push_back(new A()); // a2.
arr.push_back(new A()); // a3.
....

当替换元素时，很快会导致一些内存碎片。为了论证，假设实际容器可以容纳我们提供给它的所有指针。堆看起来会像这样：

[arr_array][a1][a2][a3]...[aN]

当我们开始用一个子类型（大小更大）替换指针时，情况就会改变。假设我们将所有由奇数指针（a1、a3、...）引用的对象替换为较大的类型，则结果如下所示：

[arr_array][xx][a2][xx][a4]...[aN][b1][b3]...[bN]

在这里，[xx]表示未使用的空间，b1...bN是新对象。

所以我想要一个容器来存储对象（就像STL容器一样），但支持多态存储。我知道如何实现这种容器，但更喜欢使用“专家”库（Boost，STL等）。总之，我的问题是：

是否有一种容器支持在连续的内存序列中保存（动态分配的）多态对象？

例如，内存布局可以如下所示：

[arr_array] = [ptr_lookup_table][storage]
            = [p1, p2, ..., pn][b1, a2, b3, ..., aN]

感谢您的回答/评论！

- Jens Åkerblom

1

作为建议，最好不要过多地阅读关于所谓的堆碎片和更多关于干净、惯用的C++的内容。一个健康的堆存在于一个健康的程序中。 - Kerrek SB

那么你会如何实现这种容器？ - hc_

@JensÅkerblom：您的容器与向量接近，但每次插入都需要重新分配（并复制所有元素）。这真的是您想要的吗？ - Matthieu M.

如果在创建时已知容器大小并且它实现了类似于_emplace_的方法，则不需要重新分配空间。 - Jens Åkerblom

@Jens 但是你在创建时不知道容器的大小，因为你创建的是一个容器，用于存放类型A的对象，而不是B。因此，您必须告诉容器对象的最大大小（如果只有B已经很丑陋，但想象一下您还有30个其他类），然后容器将过度分配每个对象以能够用B的实例替换它，这也很丑陋，因为B可能是2兆字节，而A只有4个字节。 - Fozi

显示剩余2条评论

3个回答

0

(编辑：抱歉，我误读了您的问题；已删除先前的答案。)

你可以使用任何内存池来管理你的对象。通常情况下，你会将相同（或相似）大小的对象放在同一个池中。由于你通常需要在池上调用特殊的delete函数，我建议你使用一个带有自定义删除器的shared_ptr。然后，你可以将这个shared_ptr与任何标准容器一起使用。

编辑：看起来需要一个例子。警告：这是完全未经测试的，只是我脑海中的想法。不要指望它能编译。

#include <boost/pool.hpp>
#include <memory>

class A;
class B; // B inherits from A

int main() {
  // could be global
  boost::object_pool<A> a_pool;
  boost::object_pool<B> b_pool;

  std::vector<std::shared_ptr<A>> v;

  v.push_back(std::shared_ptr<A>(a_pool.construct(), [&](A*p) { a_pool.free(p); }));
  v.push_back(std::shared_ptr<A>(a_pool.construct(), [&](A*p) { a_pool.free(p); }));
  v.push_back(std::shared_ptr<A>(a_pool.construct(), [&](A*p) { a_pool.free(p); }));

  v[2] = std::shared_ptr<B>(b_pool.construct(), [&](B*p) { b_pool.free(p); });

  return 0;
}

这将适用于B比A大得多的情况。它也不依赖于自动释放池，因为我认为这是危险的。内存布局并不紧密，因为池总是会过度分配，但如果我理解您的问题，则不会出现碎片。

- Fozi

内存池的内存布局不如问题中加粗部分后的最后一个示例好，并且只有在多态类具有相似大小时才能工作。 - Jens Åkerblom

@Jens，这是因为每种类型都有自己的内存池。如果您坚持将所有对象存储在一起，则始终会存在碎片化或容器必须移动对象的情况。这非常难以实现（通用性很差），而且从来不值得这样做，所以您找不到真正实现这一点的容器。 - Fozi

0

碎片化并不是由于使用boost容器而发生的。当您频繁地使用new和delete来分配和释放不同大小的对象时，它会发生。 ptr_array仅存储这些分配对象的指针，并且可能不会对碎片化产生显着贡献。

如果您想抵消内存碎片化，可以重载您的对象的operator new并实现自己的内存管理系统。我建议您阅读内存池和空闲列表的主题。

- Constantinius

碎片化并不是由于使用 boost 容器导致的。当然，问题是，是否有一种容器能够完全封装内存管理，而不像 ptr_array 类那样。 - Jens Åkerblom

由于容器本身与内存分配无关（这是在之前发生的），所以答案很简单：容器无法对抗内存碎片化。必须在其他地方实现。 - Constantinius

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

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

- Matthieu M. · Accepted Answer

内存碎片化需要预先了解内存分配，因此我需要先介绍一些概念。

内存分配

当您调用operator new（默认情况下通常会在背后调用malloc）时，您并没有直接从操作系统请求内存，相反，发生的情况（通常）是：

您调用malloc以获取76个字节，它会查看是否可用：
- 如果不可用，则向操作系统请求一个页面（通常为4KB），并准备好它
然后为您提供您所请求的76个字节

内存碎片化可能会发生在两个级别：

您可能会耗尽虚拟地址空间（在64位平台上不太容易）
您可能有几乎为空的页面，无法重新获取但无法满足您进行的请求

通常，由于malloc应该一次调用4KB的页面（除非您要求更大的块，在这种情况下它将选择更大的4KB倍数），因此您不应该耗尽地址空间。对于异常大的分配，32位机器（限制为4GB）上曾经发生过这种情况。

另一方面，如果您的malloc实现太幼稚，您可能会遇到内存块碎片化的问题，因此您的内存占用量比实际使用的要高得多。这通常是现在所说的内存碎片化术语所指的。

典型策略

当我说“幼稚”时，例如，我指的是您连续分配所有内容的想法。这是一个坏主意。这通常不是发生的情况。

相反，好的malloc实现今天使用池。

通常，它们将具有每个大小的池：

1字节
2字节
4字节
...
512字节
...
4KB及以上的处理方式特殊（直接）

当您发出请求时，它们将找到可以满足该请求的最小大小的池，并且该池将为您提供服务。

因为在池中，所有请求都使用相同的大小进行服务，所以池内没有碎片化，因为空闲单元格可以用于任何传入请求。

那么，碎片化呢？

现在，您不应该观察到内存碎片化本身。

然而，您仍然可以观察到内存空洞。假设一个池正在处理9到16字节的对象，并且您分配了400万个对象。这至少需要16000个4KB页面。现在假设您释放除16000个以外的所有对象，但是狡猾地让每个页面仍然存在一个对象。由于您仍在使用它们，因此操作系统无法回收这些页面，但由于您只使用了4KB中的16个字节，所以空间相当浪费（目前为止）。

某些具有垃圾回收功能的语言可能会通过紧凑方式处理这些情况，但是在C ++中，无法重新定位内存中的对象，因为用户直接控制对象地址。

神奇容器

我不知道是否有这样的东西。我也不明白它为什么有用。

TL;DR

不要担心碎片化。

注：专家可能想编写自己的池分配机制，我想提醒他们不要忘记对齐。