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

问题描述

我听说过这个词之前，我想知道如何设计和code之一。结果
我应该使用STL分配器（如果可用）？结果
如何能在它没有操作系统的设备来完成？结果
什么是使用它，并使用常规的编译器实现的malloc之间的权衡/新？

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。
为了减少碎片，你需要创建一个内存池特定于对象的，你在它被分配的类型。从本质上讲，你再限制每个分配的大小设置为您感兴趣的对象的大小，你可以实现一个模板类，它具有动态分配的内存块的列表（该列表是，你可以成长的空间量的原因可用）。每一个动态分配的内存块将基本上是T的数组

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.

然后，您将有一个免费的名单，这是一个单向链表，这里头指向下一个可用块。分配，然后简单地返回头。你可以覆盖在块本身，即每个块链接列表（重新presents T的对齐大小），将基本上是T的联盟和链表，节点分配时，氏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)

静态我相信，意味着T类型的所有对象的缺点是，对于各t，你必须有一个独立的内存池一个单独的内存池。你可能是聪明，并具有管理不同大小的池（使用指针池中对象的一个​​阵列，其中该索引是例如对象的大小）的单个对象。

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).

在previous款的整点是概述究竟如何复杂，这是了，喜欢RC上面说，要确定你需要它，你这样做之前 - 因为它很可能会推出更多的痛苦比可能是必要的！

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。
如果STL分配器满足您的需求，使用它，它是由一些谁知道他们在做什么，很聪明的人设计的 - 但它是为通用的情况下，如果你知道你的对象是如何分配的，你可以把上面的执行速度更快。

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。
你需要能够以某种方式分配内存（硬件支持或某种HAL的 - 不管） - 我在别处，不知道你的程序是如何工作的。

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。
常规的malloc /新做了很多更多的东西在幕后（谷歌是你的朋友，我的回答是已经一篇文章！）简单的分配上面我形容也不为重入，当然你可以用互斥锁把它包提供一点盖的，即使这样，我敢大胆地说了简单的allocator会更快地执行数量级比普通的malloc /免费。

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.

但是，如果你在这个阶段的优化 - presumably你已经用完优化算法和数据结构使用的可能性

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

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