内存分配和池化，针对受限环境
5.00/5 (4投票s)
一些 C++ 魔术，有助于减少简单场景中的堆栈滥用。
引言
我正在为包括 Arduino 及其兼容平台在内的受限环境编写一个相当复杂的 JSON 库。在此过程中，我发现如果我想要内存中的 JSON 树，就需要某种方式来池化内存并进行高效分配。此外，由于受限平台内存的多样性，我还需要开发人员能够完全控制分配多少内存以及在哪里分配。
随意使用 new 和 delete 很简单，但在没有大量 RAM 可供分配或 CPU 周期可浪费在堆碎片上的情况下，这会带来危害。在这种情况下，您需要对内存的分配位置和方式进行一些控制。
为了增加一点难度，代码应该尽可能小，因为我们的程序空间也有限。
这里的目标是在不增加太多复杂性的情况下提高性能。
概念化这个混乱的局面
在小型设备上运行时，一切都很重要。没有什么可以被理所当然，包括您的内存。我们希望完全避免使用内存，这对于这些设备来说是理想情况，但显然是不可能的。下一个最好的办法是减少其使用，并在分配内存时控制其位置/类型。
与运行在分页操作系统上的垃圾回收系统相比，后者的内存问题几乎是事后才考虑的，它们是完全不同的世界。我之前在 C# 工作多年，然后才回归 C++，我当时被宠坏了。
垃圾回收系统以资源消耗大而闻名，但它们在内存分配方面比传统的 C/C++ 堆模型具有巨大的性能优势。传统的堆通常会跟踪已用和空闲空间的某种链表。分配需要遍历该列表。这看起来不多，但累积起来很快，而且堆碎片越多，遍历列表所需的时间就越长，因为块就越多。垃圾回收器不保留链表。它们只保留一个指针，在每次请求分配时递增。当该指针接近末尾时，就会发生垃圾回收，压缩堆并将指针再次移离末尾。这里的魔力在于回收过程，也就是让这一切正常工作的地方。基本上，您在初始分配时间上节省的，将在后端通过更复杂的删除/压缩来弥补。
这种分配方案的一个很好的附带好处是，如果我们能保证它是连续的，那么我们就可以在不知道需要多少空间的情况下，一边进行一边分配字符串或向量。每次分配时，指针都位于我们上次分配的末尾，因此内存是连续的。正确使用，这可以带来巨大的性能提升。
那么，如果我们能同时拥有这种出色的分配方案，以及一种不那么复杂的删除/回收方案呢？如果我们能做到，我们也许就能在受限设备上获得优势。
问题是我们能舍弃什么？我们可能负担不起垃圾回收器，但也许我们不需要它。
一个问题是垃圾回收器在分配内存方面非常激进。它们会预先保留尽可能多的堆空间。这对于性能很重要，但对于内存受限的情况并不真正适用。假设我们可以自己定义池的大小，并给它们一个硬性限制。再假设我们可以创建多个独立的池。也许这会给我们一些灵活性，并对我们的内存分配情况设定现实的限制。
所以我们有这些小型池，而垃圾回收器有一个大型池。我们无法负担垃圾回收器的另一个方面是跟踪我们所有的对象引用。这会占用大量 CPU，编码复杂，即使优化了，对于我们的小型设备来说，至少在一般情况下，它可能也不合适。
那我们如何删除我们的对象呢？
这是正确的问题吗？在编程和生活中，有时正确的问题比 100 个正确的答案更有价值。
如果问题是，我们需要删除我们的对象吗？
有什么替代方案？
为什么不直接回收池，一次性删除所有对象呢？
这真的可行吗？考虑以下场景
您想使用拉式解析器逐一解析大型 JSON 文档，一次只读取一点 JSON。
当您导航到感兴趣的部分时，您会将一小部分 JSON 加载到内存中的树中，以便将它们作为一个单元进行查询。您将其分配给您为此目的专用池。
完成该操作后，所有内存中的树对象都不再需要了，因此我们可以一次性释放它们，并为下一个片段回收整个池。
明白了吗？太好了！
您可以以这种方式处理各种场景 - 设置/分配/准备，执行，清理。这并不少见。同样，唯一的真正缺点是您无法单独释放单个分配。这意味着编辑/更新效率不高。假设您正在分配一个字符串。现在假设您想将该字符串更改为新值。您可以创建一个新字符串，但不能删除旧字符串，因此现在您可能使用了两倍甚至更多的内存，这仅仅发生了一次编辑之后。问题是，您是在构建 DOM 吗？您是在编辑对象吗？可能不是。一次加载、使用、丢弃在这里对我们来说最为重要。
我将为您详细分解
这是我们所追求的：一个可池化、顺序分配的内存缓冲区，我们可以将其放置在任何地方——堆或栈中。
为了获得它，我们放弃了什么
- 我们无法动态地即时重新分配更多内存。我们必须预先指定一个最大容量。这实际上并不算太糟，尽管它可能令人不悦。如果它看起来令人不悦，那是因为您习惯于在功能齐全的 PC 上编写代码。再次强调，我们（通常）没有大量的 RAM、多线程，或其他允许并且倾向于需要更多内存的因素。我们正在回归基础，这对性能有利。另一种选择是我们必须在每次重新分配发生时提供某种回调，以便被调用者可以用原始位置和移动位置之间的差异来偏移它存储在该内存中的任何指针。这不仅复杂，实际上重新映射这些指针几乎效率不高。这正是垃圾回收器中的压缩变慢的原因。我们需要避免这种情况。
- 我们无法单独从池中删除项目。我们只能一次性回收整个池，使池中的所有指针失效。同样，如果您设计的代码是用于设置/分配、执行、回收/清理阶段的，这也不是什么坏事，而且效率很高。具体来说，您的
List类将没有remove()方法，而是只有push_back()或add()方法，并期望在回收整个池时清理列表。回收整个池的效率与分配一样高——实际上略高。请记住，您不是在构建交互式 DOM。在大多数情况下，您是在处理数据。K.I.S.S.（保持简单）原则在这里适用。
编写这个混乱的程序
针对此进行编码非常简单，一旦您了解了它的工作原理。您可以创建一个 StaticMemoryPool<C> 类来分配一个最大工作大小在编译时已知的池，或者您可以创建一个 DynamicMemoryPool，其最大工作大小在初始化之前是未知的。对于 StaticMemoryPool<C>，如果它在局部声明，则该内存将在栈上；如果它声明为全局变量，则将在全局堆上。 DynamicMemoryPool 始终从堆中分配其内存。
分配非常简单，其工作方式类似于 malloc()。将大小传递给 alloc()，它将从池中预留一块内存，并为您提供指向该内存的 void*，如果池中没有更多空间，则返回 nullptr。
这款产品的绝妙之处在于，连续调用 alloc() 总是会返回一个连续的、顺序的指针。
例如，这可以正常工作（为简洁起见，已移除错误检查）
char* sz; // for remembering the start of the string
char* sznew; // our new pointer
// allocate 6 bytes, and prime our sz to point to the start
sz = sznew = (char*)memoryPool.alloc(6);
// copy 6 bytes
strncpy(sz,"Hello ",6);
// allocate 6 more bytes - guaranteed sequential!
sznew=(char*)memoryPool.alloc(6); // leave space for the trailing null
// copy "World" (6 bytes total)
strcpy(sznew,"World");
printf("%s",sz); // prints Hello World!
释放必须通过销毁类实例或调用 freeAll() 来完成。调用 freeAll() 是回收池的方式。
如果您想高效地执行一系列连续操作，回收池会很有用。
在任何时候，您都可以检查 capacity() 来了解池的大小，而 used() 将告诉您池中保留了多少字节。 next() 将让您预览下一个分配指针的位置，但直到调用 alloc() 之前不应使用它。此方法主要提供给需要知道池何时更改以进行优化的消费者。
代码必然很简单
// represents an interface/contract for a memory pool
struct MemoryPool {
public:
// allocates the specified number of bytes
// returns nullptr if there's not enough free
virtual void* alloc(const size_t size)=0;
// invalidates all the pointers in the pool and frees the memory
virtual void freeAll()=0;
// retrieves the next pointer that will be allocated
// (for optimization opportunities)
virtual void* next()=0;
// indicates the maximum capacity of the pool
virtual size_t capacity()=0;
// indicates how many bytes are currently used
virtual size_t used()=0;
};
// represents a memory pool whose maximum capacity is known at compile time
template<size_t C> class StaticMemoryPool : public MemoryPool {
// the actual buffer
uint8_t _heap[C];
// the next free pointer
uint8_t *_next;
public:
// allocates the specified number of bytes
// returns nullptr if there's not enough free
void* alloc(const size_t size) override {
// if we don't have enough room return null
if(used()+size>=C)
return nullptr;
// get our pointer and reserve the space
void* result = _next;
_next+=size;
// return it
return result;
}
// invalidates all the pointers in the pool and frees the memory
void freeAll() override {
// just set next to the beginning
_next = _heap;
}
// retrieves the next pointer that will be allocated
// (for optimization opportunities)
void *next() override {
if(!C)
return nullptr;
return _next;
}
// indicates the maximum capacity of the pool
size_t capacity() override { return C; }
// indicates how many bytes are currently used
size_t used() override {return _next-_heap;}
StaticMemoryPool() : _next(_heap) {}
~StaticMemoryPool() {}
};
// represents a memory pool whose maximum capacity is determined at runtime
class DynamicMemoryPool : public MemoryPool {
// the actual buffer
uint8_t *_heap;
// the capacity
size_t _capacity;
// the next free pointer
uint8_t *_next;
public:
// initializes the dynamic pool with the specified capacity
DynamicMemoryPool(const size_t capacity) {
// special case for 0 cap pool
if(0==_capacity) {
_heap=_next = nullptr;
}
// reserve space from the heap
_heap = new uint8_t[capacity];
// initialize the next pointer
_next=_heap;
if(nullptr==_heap)
_capacity=0;
}
// allocates the specified number of bytes
// returns nullptr if there's not enough free
void* alloc(const size_t size) override {
if(nullptr==_heap)
return nullptr;
// if we don't have enough room, return null
if(used()+size>=_capacity) {
return nullptr;
}
// store the result pointer, then increment next
// reserving space
void* result = _next;
_next+=size;
// return it
return result;
}
// invalidates all the pointers in the pool and frees the memory
void freeAll() override {
// just set next to the beginning
_next = _heap;
}
// retrieves the next pointer that will be allocated
// (for optimization opportunities)
void* next() override {
// just return the next pointer
return _next;
}
// indicates the maximum capacity of the pool
size_t capacity() override { if(nullptr==_heap) return 0; return _capacity; }
// indicates how many bytes are currently used
size_t used() override { return _next-_heap;}
~DynamicMemoryPool() { if(nullptr!=_heap) delete _heap;}
};
再次强调，您可以看到代码非常简单。分配是小菜一碟，其余的也很简单。这只是基本的指针数学和错误处理。
您不必再害怕这些设备上的内存分配了。有了正确的工具，我们可以完成不可思议的事情。希望这个小工具能帮助您控制堆分配，并使您的代码紧凑高效。祝您使用愉快！
历史
- 2020 年 12 月 14 日 - 初次提交