设计和编码非碎片化静态内存池 [英] Designing and coding a non-fragmentizing static memory pool

问题描述

我听说过这个术语，我想知道如何设计和编码一个。

如果可用，我应该使用STL分配器吗？

如何做？在没有操作系统的设备上？

使用它和使用常规编译器实现的malloc / new之间有什么折衷？

解决方案

将尝试描述什么是本质上是一个内存池 - 我只是在我的头顶部打字，已经有一段时间，因为我实现了一个，如果一些显然是愚蠢的，它只是一个建议！ ：）

1。
为了减少碎片，您需要创建一个特定于您在其中分配的对象类型的内存池。基本上，然后你将每个分配的大小限制为你感兴趣的对象的大小。你可以实现一个模板类，它有一个动态分配的块列表（列表的原因是你可以增加空间的大小可用）。每个动态分配的块基本上是一个T的数组。

然后你会有一个free列表，这是一个单链表，其中head指向下一个可用块。分配然后简单地返回头。您可以在块本身中覆盖链表，即每个块（表示T的对齐大小），本质上是T和链表中的一个节点的联合，当被分配时，它被释放时为T，列表中的节点。 !!有明显的危险！或者，您可以分配一个单独的（和受保护的块，这会增加更多的开销）来保存块中的地址数组。

分配是微不足道的，迭代通过块列表，并从第一个可用的分配，释放也是微不足道的，你必须做的附加检查是找到块这是分配然后更新头指针。 （注意，您需要使用新的展示位置或覆盖操作符new / delete in T - 有几种方法，google是您的朋友）

静态我相信隐含一个单独的内存池所有对象的类型T.缺点是，对于每个T，你必须有一个单独的内存池。你可以聪明，并有一个对象管理不同大小的池（使用指针池对象的数组，其中索引是对象的大小）。

上一段的整个要点是概述这是多么复杂，就像RC上面说的，在你做之前，确保你需要它 - 因为它可能会引入比可能需要更多的痛苦！ p>

2。
如果STL分配器满足您的需求，使用它，它由一些非常聪明的人设计，他们知道他们在做什么 - 但是它是为通用情况下，如果你知道你的对象如何分配，你可以使以上表现更快。

3。
你需要能够以某种方式分配内存（硬件支持或某种HAL - 无论如何） - 否则我不知道你的程序将如何工作。

4。
正则malloc / new在封面下做了很多东西（google是你的朋友，我的答案已经是一篇文章了！）我上面描述的简单分配器不是re-entrant，当然你可以包装用互斥体提供一点覆盖，即使这样，我会危险的是，简单的分配器将执行比正常malloc / free更快的数量级。

但如果您处于这个优化阶段，您可能已经耗尽了优化您的算法和数据结构使用的可能性。

I have heard the term before and I would like to know how to design and code one.
Should I use the STL allocator if available?
How can it be done on devices with no OS?
What are the tradeoffs between using it and using the regular compiler implemented malloc/new?

解决方案

Will try to describe what is essentially a memory pool - I'm just typing this off the top of my head, been a while since I've implemented one, if something is obviously stupid, it's just a suggestion! :)

1. To reduce fragmentation, you need to create a memory pool that is specific to the type of object you are allocating in it. Essentially, you then restrict the size of each allocation to the size of the object you are interested in. You could implement a templated class which has a list of dynamically allocated blocks (the reason for the list being that you can grow the amount of space available). Each dynamically allocated block would essentially be an array of T.

You would then have a "free" list, which is a singly linked list, where the head points to the next available block. Allocation is then simply returning the head. You could overlay the linked list in the block itself, i.e. each "block" (which represents the aligned size of T), would essentially be a union of T and a node in the linked list, when allocated, it's T, when freed, a node in the list. !!There are obvious dangers!! Alternatively, you could allocate a separate (and protected block, which adds more overhead) to hold an array of addresses in the block.

Allocating is trivial, iterate through the list of blocks and allocate from first available, freeing is also trivial, the additional check you have to do is the find the block from which this is allocated and then update the head pointer. (note, you'll need to use either placement new or override the operator new/delete in T - there are ways around this, google is your friend)

The "static" I believe implies a singleton memory pool for all objects of type T. The downside is that for each T you have to have a separate memory pool. You could be smart, and have a single object that manages pools of different size (using an array of pointers to pool objects where the index is the size of the object for example).

The whole point of the previous paragraph is to outline exactly how complex this is, and like RC says above, be sure you need it before you do it - as it is likely to introduce more pain than may be necessary!

2. If the STL allocator meets your needs, use it, it's designed by some very smart people who know what they are doing - however it is for the generic case and if you know how your objects are allocated, you could make the above perform faster.

3. You need to be able to allocate memory somehow (hardware support or some sort of HAL - whatever) - else I'm not sure how your program would work?

4. The regular malloc/new does a lot more stuff under the covers (google is your friend, my answer is already an essay!) The simple allocator I describe above isn't re-entrant, of course you could wrap it with a mutex to provide a bit of cover, and even then, I would hazard that the simple allocator would perform orders of magnitude faster than normal malloc/free.

But if you're at this stage of optimization - presumably you've exhausted the possibility of optimizing your algorithms and data structure usage?

这篇关于设计和编码非碎片化静态内存池的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！