当内存池不是一个好主意时避免内存碎片
Avoid memory fragmentation when memory pools are a bad idea
我正在开发一个 C++ 应用程序，其中程序 运行 无休止地随着时间的推移分配和释放数百万个字符串 (char*)。 RAM 的使用是程序中的一个重要考虑因素。这导致 RAM 使用率随着时间的推移越来越高。我认为问题是堆碎片。我真的需要找到解决方案。
从图中可以看出，在程序中经过数百万次分配和释放后，使用量一直在增加。而我测试它的方式，我知道它存储的数据并没有增加。我猜你会问，“你怎么确定？”，“你怎么确定这不仅仅是内存泄漏？”，嗯。
这个测试运行要长得多。我运行malloc_trim(0)，只要有可能就在我的程序中。看起来，应用程序最终可以 return 未使用的内存到 OS，它几乎变为零（我的程序当前的实际数据大小）。这意味着问题不是内存泄漏。但我不能依赖这种行为，我程序的分配和释放模式是随机的，如果它永远不会释放内存怎么办？
- 我在标题中说过内存池对于这个项目来说是个坏主意。当然我没有绝对的知识。但是我分配的字符串可以是 30-4000 字节之间的任何内容。这使得许多优化和聪明的想法变得更加困难。内存池就是其中之一。
- 我正在使用
GCC 11 / G++ 11 作为编译器。如果一些旧版本有错误的分配器。我不应该有那个问题。
- 我如何获取内存使用情况？ Python
psutil 模块。 proc.memory_full_info()[0]，这给了我 RSS。
- 当然，我的程序细节你是不知道的。这仍然是一个有效的问题，如果这确实是因为堆碎片。那么我可以说的是，我保持 最新 有关发生了多少分配和释放的信息。而且我知道程序中每个容器的元素数。但如果您对问题的原因仍有一些想法，我愿意接受建议。
- 我不能只为所有字符串分配 4096 个字节，这样优化起来会更容易。这与我正在尝试做的相反。
所以我的问题是，在随着时间的推移发生数百万次分配和释放的应用程序中，程序员做什么（我应该做什么），并且它们的大小不同，因此内存池很难有效使用。我无法更改程序的功能，我只能更改实现细节。
赏金编辑： 尝试使用内存池时，是否可以创建多个内存池，以至于每个可能的字节数都有一个池？例如，我的字符串可以介于 30-4000 字节之间。所以不能有人为程序的每个可能的分配大小制作 4000 - 30 + 1, 3971 个内存池。这不适用吗？所有池都可以从小开始（不会丢失太多内存），然后在性能和内存之间取得平衡。我并不是想利用内存池的能力来预先保留大 spaces。我只是想有效地重用释放的 space，因为频繁的分配和释放。
最后编辑： 事实证明，图表中出现的内存增长实际上来自我程序中的 http 请求 queue。我没有看到我所做的数十万次测试使这个 queue（类似于 webhook）变得臃肿。而图 2 的合理解释是，我最终从服务器中禁止了 DDOS（或者由于某种原因无法再打开连接），queue 被清空，RAM 问题得到解决。因此，以后阅读此问题的任何人，请考虑每一种可能性。我永远不会想到它是这样的。不是内存泄漏，而是实现细节。我仍然认为@Hajo Kirchhoff 值得赏金，他的回答真的很有启发性。
如果一切确实is/works如您所说，并且没有您尚未发现的错误，那么试试这个：
malloc 和其他内存分配通常使用 16 字节的块，即使实际请求的大小小于 16 字节。所以你只需要4000/16 - 30/16 ~ 250个不同的内存池。
const int chunk_size = 16;
memory_pools pool[250]; // 250 memory pools, managing '(idx+1)*chunk_size' size
char* reserve_mem(size_t sz)
{
size_t pool_idx_to_use = sz/chunk_size;
char * rc=pool[pool_idx_to_use].allocate();
}
IOW，你有 250 个内存池。 pool[0] 分配和管理长度为 16 字节的 chunk。 pool[100] 管理 1600 字节等的块...
如果你事先知道字符串的长度分布，你可以根据这些知识为池预留初始内存。否则我可能会以 4096 字节为增量为池保留内存。
因为虽然 malloc C 堆通常以 16 字节的倍数分配内存，但它会（至少在 Windows 之前，但我猜，Linux 在这里是相似的）询问 OS 用于内存 - 通常适用于 4K 页面。 IOW，由操作系统管理的“外部”内存堆保留和释放 4096 字节。
因此，将您自己的内部内存池增加 4096 字节意味着 OS 应用程序堆中没有碎片。这个 4096 页大小（或......的倍数）来自处理器架构。 Intel 处理器的内置页面大小为 4K（或 4K 的倍数）。不知道其他处理器，但我怀疑那里有类似的架构。
所以，总结一下：
为每个内存池的字符串使用 16 字节的倍数的块。
使用 4K 字节的倍数的块来增加内存池。
这将使您的应用程序的内存使用与 OS 的内存管理保持一致，并尽可能避免碎片化。
从 OS 的角度来看，您的应用程序只会增加 4K 块的内存。这很容易分配和释放。而且没有碎片。
从内部 (lib) C 堆管理的角度来看，您的应用程序将使用内存池并且每个字符串最多浪费 15 个字节。所有类似的长度分配也会堆在一起，所以也没有碎片。
这里有一个解决方案，可能会有所帮助，如果您的应用程序具有以下特征：
- 在 Windows
上运行
- 有剧集，其中工作集很大，但所有数据都是在大约同一时间点完全发布的。 （如果数据以某种批处理模式处理，工作完成后释放相关数据）。
此方法使用一个（独特的？）Windows 功能，称为自定义堆。也许，您可以在其他 OS.
上为自己创建类似的东西
您需要的函数在一个名为 <heapapi.h> 的 header 中。
这是它的样子：
- 在程序的内存密集型阶段开始时，使用
HeapCreate() 有一个堆，所有数据都将放在堆中。
- 执行内存密集型任务。
- 在内存密集阶段结束时，释放您的数据并调用
HeapDestroy()。
根据您的应用程序的详细行为（例如，此内存密集型计算是否在 1 个或多个线程中运行），您可以相应地配置堆，甚至可能获得一点速度（如果只有 1 个线程使用数据，你可以给 HeapCreate() HEAP_NO_SERIALIZE 标志，这样它就不需要锁。）你也可以给出堆允许存储的上限。
一旦您的计算完成，销毁堆也可以防止长期碎片化，因为当下一个计算阶段到来时，您会从一个新的堆开始。
Here is the documentation of the heap api.
事实上，我发现这个功能非常有用，所以我在 FreeBSD 上复制了它，Linux 用于我移植的应用程序，使用虚拟内存函数和我自己的堆实现。几年前，我没有那段代码的权利，所以我不能展示或分享。
您还可以将此方法与固定元素大小的池结合使用，对一个专用块大小使用一个堆，然后在每个堆中期望 less/no 碎片（因为所有块都具有相同的大小）。
struct EcoString {
size_t heapIndex;
size_t capacity;
char* data;
char* get() { return data; }
};
struct FixedSizeHeap {
const size_t SIZE;
HANDLE m_heap;
explicit FixedSizeHeap(size_t size)
: SIZE(size)
, m_heap(HeapCreate(0,0,0)
{
}
~FixedSizeHeap() {
HeapDestroy(m_heap);
}
bool allocString(capacity, EcoString& str) {
assert(capacity <= SIZE);
str.capacity = SIZE; // we alloc SIZE bytes anyway...
str.data = (char*)HeapAlloc(m_heap, 0, SIZE);
if (nullptr != str.data)
return true;
str.capacity = 0;
return false;
}
void freeString(EcoString& str) {
HeapFree(m_heap, 0, str.data);
str.data = nullptr;
str.capacity = 0;
}
};
struct BucketHeap {
using Buckets = std::vector<FixedSizeHeap>; // or std::array
Buckets buckets;
/*
(loop for i from 0
for size = 40 then (+ size (ash size -1))
while (< size 80000)
collecting (cons i size))
((0 . 40) (1 . 60) (2 . 90) (3 . 135) (4 . 202) (5 . 303) (6 . 454) (7 . 681)
(8 . 1021) (9 . 1531) (10 . 2296) (11 . 3444) (12 . 5166) (13 . 7749)
(14 . 11623) (15 . 17434) (16 . 26151) (17 . 39226) (18 . 58839))
Init Buckets with index (first item) with SIZE (rest item)
in the above item list.
*/
// allocate(nbytes) looks for the correct bucket (linear or binary
// search) and calls allocString() on that bucket. And stores the
// buckets index in the EcoString.heapIndex field (so free has an
// easier time).
// free(EcoString& str) uses heapIndex to find the right bucket and
// then calls free on that bucket.
}
您正在尝试做的事情叫做 slab 分配器，这是一个研究得很好的问题，有很多研究论文。
您不需要所有可能的尺寸。通常平板有 2 种尺寸的幂。
不要重新发明轮子，有很多 slab 分配器的开源实现。 Linux 内核使用一个。
首先阅读有关 Slab 分配的维基百科页面。
我不知道你的程序的细节。处理记忆的模式有很多种，每种模式都会导致不同的结果和问题。但是，您可以查看 .Net 垃圾收集器。它使用几代对象（类似于内存池）。该世代中的每个对象都是可移动的（它在内存中的地址在世代压缩期间发生变化）。这种技巧允许“compress/compact”内存并减少内存碎片。您可以实现具有类似语义的内存管理器。根本不需要实现垃圾收集器。
我正在开发一个 C++ 应用程序，其中程序 运行 无休止地随着时间的推移分配和释放数百万个字符串 (char*)。 RAM 的使用是程序中的一个重要考虑因素。这导致 RAM 使用率随着时间的推移越来越高。我认为问题是堆碎片。我真的需要找到解决方案。
从图中可以看出，在程序中经过数百万次分配和释放后，使用量一直在增加。而我测试它的方式，我知道它存储的数据并没有增加。我猜你会问，“你怎么确定？”，“你怎么确定这不仅仅是内存泄漏？”，嗯。
这个测试运行要长得多。我运行malloc_trim(0)，只要有可能就在我的程序中。看起来，应用程序最终可以 return 未使用的内存到 OS，它几乎变为零（我的程序当前的实际数据大小）。这意味着问题不是内存泄漏。但我不能依赖这种行为，我程序的分配和释放模式是随机的，如果它永远不会释放内存怎么办？
- 我在标题中说过内存池对于这个项目来说是个坏主意。当然我没有绝对的知识。但是我分配的字符串可以是 30-4000 字节之间的任何内容。这使得许多优化和聪明的想法变得更加困难。内存池就是其中之一。
- 我正在使用
GCC 11 / G++ 11作为编译器。如果一些旧版本有错误的分配器。我不应该有那个问题。 - 我如何获取内存使用情况？ Python
psutil模块。proc.memory_full_info()[0]，这给了我RSS。 - 当然，我的程序细节你是不知道的。这仍然是一个有效的问题，如果这确实是因为堆碎片。那么我可以说的是，我保持 最新 有关发生了多少分配和释放的信息。而且我知道程序中每个容器的元素数。但如果您对问题的原因仍有一些想法，我愿意接受建议。
- 我不能只为所有字符串分配 4096 个字节，这样优化起来会更容易。这与我正在尝试做的相反。
所以我的问题是，在随着时间的推移发生数百万次分配和释放的应用程序中，程序员做什么（我应该做什么），并且它们的大小不同，因此内存池很难有效使用。我无法更改程序的功能，我只能更改实现细节。
赏金编辑： 尝试使用内存池时，是否可以创建多个内存池，以至于每个可能的字节数都有一个池？例如，我的字符串可以介于 30-4000 字节之间。所以不能有人为程序的每个可能的分配大小制作 4000 - 30 + 1, 3971 个内存池。这不适用吗？所有池都可以从小开始（不会丢失太多内存），然后在性能和内存之间取得平衡。我并不是想利用内存池的能力来预先保留大 spaces。我只是想有效地重用释放的 space，因为频繁的分配和释放。
最后编辑： 事实证明，图表中出现的内存增长实际上来自我程序中的 http 请求 queue。我没有看到我所做的数十万次测试使这个 queue（类似于 webhook）变得臃肿。而图 2 的合理解释是，我最终从服务器中禁止了 DDOS（或者由于某种原因无法再打开连接），queue 被清空，RAM 问题得到解决。因此，以后阅读此问题的任何人，请考虑每一种可能性。我永远不会想到它是这样的。不是内存泄漏，而是实现细节。我仍然认为@Hajo Kirchhoff 值得赏金，他的回答真的很有启发性。
如果一切确实is/works如您所说，并且没有您尚未发现的错误，那么试试这个：
malloc 和其他内存分配通常使用 16 字节的块，即使实际请求的大小小于 16 字节。所以你只需要4000/16 - 30/16 ~ 250个不同的内存池。
const int chunk_size = 16;
memory_pools pool[250]; // 250 memory pools, managing '(idx+1)*chunk_size' size
char* reserve_mem(size_t sz)
{
size_t pool_idx_to_use = sz/chunk_size;
char * rc=pool[pool_idx_to_use].allocate();
}
IOW，你有 250 个内存池。 pool[0] 分配和管理长度为 16 字节的 chunk。 pool[100] 管理 1600 字节等的块...
如果你事先知道字符串的长度分布，你可以根据这些知识为池预留初始内存。否则我可能会以 4096 字节为增量为池保留内存。
因为虽然 malloc C 堆通常以 16 字节的倍数分配内存，但它会（至少在 Windows 之前，但我猜，Linux 在这里是相似的）询问 OS 用于内存 - 通常适用于 4K 页面。 IOW，由操作系统管理的“外部”内存堆保留和释放 4096 字节。
因此，将您自己的内部内存池增加 4096 字节意味着 OS 应用程序堆中没有碎片。这个 4096 页大小（或......的倍数）来自处理器架构。 Intel 处理器的内置页面大小为 4K（或 4K 的倍数）。不知道其他处理器，但我怀疑那里有类似的架构。
所以，总结一下：
为每个内存池的字符串使用 16 字节的倍数的块。 使用 4K 字节的倍数的块来增加内存池。
这将使您的应用程序的内存使用与 OS 的内存管理保持一致，并尽可能避免碎片化。
从 OS 的角度来看，您的应用程序只会增加 4K 块的内存。这很容易分配和释放。而且没有碎片。
从内部 (lib) C 堆管理的角度来看，您的应用程序将使用内存池并且每个字符串最多浪费 15 个字节。所有类似的长度分配也会堆在一起，所以也没有碎片。
这里有一个解决方案，可能会有所帮助，如果您的应用程序具有以下特征：
- 在 Windows 上运行
- 有剧集，其中工作集很大，但所有数据都是在大约同一时间点完全发布的。 （如果数据以某种批处理模式处理，工作完成后释放相关数据）。
此方法使用一个（独特的？）Windows 功能，称为自定义堆。也许，您可以在其他 OS.
上为自己创建类似的东西您需要的函数在一个名为 <heapapi.h> 的 header 中。
这是它的样子：
- 在程序的内存密集型阶段开始时，使用
HeapCreate()有一个堆，所有数据都将放在堆中。 - 执行内存密集型任务。
- 在内存密集阶段结束时，释放您的数据并调用
HeapDestroy()。
根据您的应用程序的详细行为（例如，此内存密集型计算是否在 1 个或多个线程中运行），您可以相应地配置堆，甚至可能获得一点速度（如果只有 1 个线程使用数据，你可以给 HeapCreate() HEAP_NO_SERIALIZE 标志，这样它就不需要锁。）你也可以给出堆允许存储的上限。
一旦您的计算完成，销毁堆也可以防止长期碎片化，因为当下一个计算阶段到来时，您会从一个新的堆开始。
Here is the documentation of the heap api.
事实上，我发现这个功能非常有用，所以我在 FreeBSD 上复制了它，Linux 用于我移植的应用程序，使用虚拟内存函数和我自己的堆实现。几年前，我没有那段代码的权利，所以我不能展示或分享。
您还可以将此方法与固定元素大小的池结合使用，对一个专用块大小使用一个堆，然后在每个堆中期望 less/no 碎片（因为所有块都具有相同的大小）。
struct EcoString {
size_t heapIndex;
size_t capacity;
char* data;
char* get() { return data; }
};
struct FixedSizeHeap {
const size_t SIZE;
HANDLE m_heap;
explicit FixedSizeHeap(size_t size)
: SIZE(size)
, m_heap(HeapCreate(0,0,0)
{
}
~FixedSizeHeap() {
HeapDestroy(m_heap);
}
bool allocString(capacity, EcoString& str) {
assert(capacity <= SIZE);
str.capacity = SIZE; // we alloc SIZE bytes anyway...
str.data = (char*)HeapAlloc(m_heap, 0, SIZE);
if (nullptr != str.data)
return true;
str.capacity = 0;
return false;
}
void freeString(EcoString& str) {
HeapFree(m_heap, 0, str.data);
str.data = nullptr;
str.capacity = 0;
}
};
struct BucketHeap {
using Buckets = std::vector<FixedSizeHeap>; // or std::array
Buckets buckets;
/*
(loop for i from 0
for size = 40 then (+ size (ash size -1))
while (< size 80000)
collecting (cons i size))
((0 . 40) (1 . 60) (2 . 90) (3 . 135) (4 . 202) (5 . 303) (6 . 454) (7 . 681)
(8 . 1021) (9 . 1531) (10 . 2296) (11 . 3444) (12 . 5166) (13 . 7749)
(14 . 11623) (15 . 17434) (16 . 26151) (17 . 39226) (18 . 58839))
Init Buckets with index (first item) with SIZE (rest item)
in the above item list.
*/
// allocate(nbytes) looks for the correct bucket (linear or binary
// search) and calls allocString() on that bucket. And stores the
// buckets index in the EcoString.heapIndex field (so free has an
// easier time).
// free(EcoString& str) uses heapIndex to find the right bucket and
// then calls free on that bucket.
}
您正在尝试做的事情叫做 slab 分配器，这是一个研究得很好的问题，有很多研究论文。
您不需要所有可能的尺寸。通常平板有 2 种尺寸的幂。
不要重新发明轮子，有很多 slab 分配器的开源实现。 Linux 内核使用一个。
首先阅读有关 Slab 分配的维基百科页面。
我不知道你的程序的细节。处理记忆的模式有很多种，每种模式都会导致不同的结果和问题。但是，您可以查看 .Net 垃圾收集器。它使用几代对象（类似于内存池）。该世代中的每个对象都是可移动的（它在内存中的地址在世代压缩期间发生变化）。这种技巧允许“compress/compact”内存并减少内存碎片。您可以实现具有类似语义的内存管理器。根本不需要实现垃圾收集器。