可遍历内存池的数据结构 [英] Data structures for traversable memory pool

问题描述

我正在C ++中实现一个内存池，具有以下限制：

• 分配的元素应该以线性方式遍历时间按照它们的内存地址顺序，以促进缓存重用。


• 需要重新分配元素（内存块）并将其返回到内存池。 li>
  

在实时程序的运行期间，分配和释放会频繁发生，所以需要尽可能快地发生。

我迄今为止已经使用两个链接列表作为存根实现了这个内存池，一个是空闲的，一个用于分配的元素。这是有效的，但是当然是非常慢的，因为每次元素被释放或分配时，元素都需要从一个列表中删除，并添加到另一个列表中，这是线性的。我想要这样更快。

我可以使用哪些数据结构使（de）分配尽可能高效？我在想关于使用红黑树（或类似的平衡BST）来存储分配的元素，以及免费元素的优先级队列。这将分配和释放O（log n）。

有关如何改进此设计的任何建议？我可以使用的其他数据结构？是否有可能使用不断的时间操作来创建一个内存池（具有上述限制）？

编辑：我应该澄清一下数据结构仅用于存储和访问存储器地址，存储块本身已经被分配和连续。

解决方案

由于我们处理具有固定大小的存储器块的存储器池，可以如下实现恒定时间操作。 ：将每个内存块的索引记录到池中（内存块的地址可以很容易地被

• 通过 block_address = base_address + index * block_size 从此索引派生，反之亦然）。


• 具有元数据（跟踪分配的和空闲的块）。一个符合要求的是一个固定大小的数组，其中一个项目对应于每个内存块（由相同的索引标识）。嵌入在该阵列中是两个（双重）链表（一个用于分配的，一个用于空闲块）。由于这些链接列表不重叠，因此可以使用相同的 prev 和 next 指针。

如何满足要求：

• 线性时间遍历：内存块可以通过它们的索引遍历（一个空闲/分配的标志作为元数据的一部分在这种情况下可能是有用的），或者由两个链表中的任一个依赖于要求。迭代数组和链表在线性时间内完成。


• 定时分配：分配内存块意味着从空闲列表中获取第一个项目，并移动它进入分配的列表（在结束例如。）。删除链接列表的第一个项目，并将一个项目附加到链接列表的末尾都是常数时间操作（假设指向链表的开始和/或结束的指针，使得列表循环可以帮助） 。然后返回块的索引/地址。


• 常量时间解除分配：释放内存块意味着通过索引识别对应的元数据项，并将其移动从分配的列表到免费列表（在最后的例子）。通过数组的索引获取项目，从（双重）链接列表中删除给定项目，并将项目附加到链接列表的末尾，都是常量时间操作。

I am implementing a memory pool in C++, with the following constraints:

• The allocated elements should be traversable in linear time in order of their memory address, to promote cache reuse.
• It needs to be possible to deallocate elements (memory blocks) and return them to the memory pool.

Allocation and deallocation would happen frequently during the runtime of a real-time program, so needs to happen as fast as possible.

I have so far implemented this memory pool using two linked lists as stubs, one for the free and one for the allocated elements. This works, but is of course terribly slow, since every time an element is either freed or allocated, the element needs to be removed from one list and added to the other, which is linear. I would like this to be faster.

What data structures could I use to make (de)allocation as efficient as possible? I was thinking about using a red-black tree (or similar balancing BST) to store the allocated elements, and a priority queue for the free elements. This would make allocation and deallocation both O(log n).

Any advice on how I could improve this design? Other data structures I could use? Is it even possible to make a memory pool (with the above constraints) with constant time operations?

Edit: I should probably clarify that these data structures are meant only for storing and accessing the memory addresses, the memory blocks themselves are already allocated and contiguous.

解决方案

Since we're dealing with a memory pool with fixed size memory blocks, constant time operations can be achieved as follows eg. :

• identify each memory block by its index into the pool (the address of the memory block can be easily derived from this index by block_address = base_address + index * block_size, and vice versa).
• have a data structure for the metadata (to keep track of allocated and free blocks). One that works with the requirements, is a fixed size array with an item corresponding to each memory block (identified by the same index). Embedded in that array are two (doubly) linked lists (one for the allocated and one for the free blocks). Since these linked lists don't overlap, they can use the same prev and next pointers.

How does this fit the requirements :

• linear time traversal : the memory blocks can be traversed either by their index (a free/allocated flag as part of the metadata is probably useful in that case), or by either of the two linked lists, depending on the requirements. Iterating over arrays and linked lists is done in linear time.
• constant time allocation : allocating a memory block means getting the first item from the free list, and moving it into the allocated list (at the end eg.). Removing the first item of a linked list, and appending an item to the end of a linked list are both constant time operations (assuming a pointer to the start and/or end of the linked list is kept - making the lists circular can help). The index/address of the block is then returned.
• constant time deallocation : deallocating a memory block means identifying the corresponding metadata item by its index, and moving it from the allocated list into the free list (at the end eg.). Getting an item by its index from an array, removing a given item from a (doubly) linked list, and appending an item to the end of a linked list, are all constant time operations.

这篇关于可遍历内存池的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！