自定义的malloc为许多小的，固定大小的块？ [英] Custom malloc for lots of small, fixed size blocks?
问题描述
我需要分配和免费的大量固定大小，小（16字节）的内存块，在没有固定的顺序。我可以要求每个malloc和free，但是这可能会是非常低效的。一个更好的解决方案可能会调用malloc和free较大的块，这些块本身的处理分配。
现在的问题是，如何更好地做到这一点？
看来，这不应该是一个非常不寻常的问题或问题十分罕见，而且它应该被解决，但我似乎无法找到任何东西。任何指针？
要澄清一下，我知道，内存池库，什么-不存在的，但这些还采取了尺寸参数。如果尺寸是更有效的算法恒定的，则不同的选项可用，是否有这些的任何实施
您说得对，这是一个常见的问题，当然的开始。如果出现这种情况，和自由列表也是空的，你需要一个新的较大块。免费不会改变 - 只是节点添加到空闲列表
您有一个选项是否处理了块的第一，并检查空闲列表，如果这是精疲力尽，或者先检查空闲列表，并处理掉块，如果这是空的。我不知道这往往是快 - 关于后进先出空闲链表的好处是，它的缓存友好的，因为你使用的是最近使用的内存，所以我可能会尝试第一位。
请注意，并不需要在列表节点，而该单元被分配的，所以实质上有每个细胞零开销。从速度相当不谈，这很可能是在的malloc 的优势，或其他通用分配器。
请注意，放弃了整个分配器pretty多来释放内存回系统，所以谁正计划投入大量的细胞，使用它们的用户，并释放他们所有的唯一途径，应该创建自己的分配，使用它，然后摧毁它。无论是对于性能（你没有释放所有的细胞），并以prevent碎片式的效果，即如果任何细胞都在使用一整块必须保持。如果你不能做到这一点，你的内存使用将是你的程序已经运行时的高水位标记。对于一些程序，这是一个问题（例如在内存使用偶尔大尖峰一个长期运行的程序，在内存受限的系统上）。对于其他人（如果使用的增加细胞直至非常接近的程序到底有多少，或者一个范围内波动，你真的不在乎你使用的不是你能严格的更多的内存，例如）是绝对的罚款。对于它的一些积极可取的（如果你知道你要多少内存来使用，你可以分配所有的前期，而不必担心失败）。对于这个问题，的malloc 的一些实现有困难释放内存从进程返回到操作系统。
[*]其中的块的开始可能是指的块的开始，加上用于保持所有块的列表的一些节点的大小，因此它们可以在细胞分配器被破坏所有被释放
I need to allocate, and free lots of fixed size, small (16 byte) blocks of memory, in no fixed order. I could just call malloc and free for each, but that will probably be very inefficient. A better solution probably would be to call malloc and free for larger blocks, and handle the allocation within those blocks itself.
The question is, how best to do this?
It seems that this should not be a very unusual problem or rare problem, and that it should have been "solved", but I can't seem to find anything. Any pointers?
To clarify, I am aware that memory pool libraries, and what-not exist, but these also take a size parameter. If the size is constant, then different options for more efficient algorithms are available, are there any implementations of these?
You're right, it's a common problem [Edit: how to do fixed-size allocation, I mean. "malloc is slowing down my application" is less common than you might think].
If your code is too slow and malloc a plausible culprit, then a simple cell allocator (or "memory pool") might improve things. You can almost certainly find one somewhere, or it's easy to write:
Allocate a large block, and put a singly-linked list node at the start of each 16-byte cell. Link them all together. To allocate, take the head off the list and return it. To free, add the cell to the head of the list. Of course if you try to allocate and the list is empty, then you have to allocate a new large block, divide it into cells, and add them all to the free list.
You can avoid that big up-front work if you want. When you allocate a big block, just store a pointer to the end of it. To allocate, move your pointer back 16 bytes through the block and return the new value. Unless it was already at the start of the block[*], of course. If that happens, and the free list is also empty, you need a new large block. Free doesn't change - just add the node to the free list.
You have an option whether to deal out of the block first, and check the free list if that's exhausted, or to check the free list first, and deal off the block if that's empty. I don't know which tends to be faster - the good thing about a last-in-first-out free list is that it's cache-friendly, since you're using memory that was used recently, so I'd probably try that first.
Note that the list node is not needed while the cell is allocated, so there's essentially zero overhead per cell. Quite aside from speed, this is likely to be an advantage over malloc, or other general-purpose allocators.
Do be aware that dropping the whole allocator is pretty much the only way to release memory back to the system, so users who are planning to allocate a lot of cells, use them, and free them all, should create their own allocator, use it, and then destroy it. Both for performance (you don't have to free all the cells) and to prevent the fragmentation-style effect where a whole block must be kept if any of its cells are in use. If you can't do this, your memory use will be the high-water-mark of the time your program has been running. For some programs that's a problem (for instance a long-running program with occasional big spikes in memory use, on a system where memory is constrained). For others it's absolutely fine (for instance if the number of cells in use increases until very near the end of the program, or fluctuates within a range where you really don't care that you're using more memory than you strictly could). For some its actively desirable (if you know how much memory you're going to use, you can allocate it all up-front and not have to worry about failures). For that matter, some implementations of malloc have difficulty releasing memory back from the process to the OS.
[*] Where "start of the the block" probably means "the start of the block, plus the size of some node used to maintain a list of all blocks, so they can all be freed when the cell allocator is destroyed".
这篇关于自定义的malloc为许多小的，固定大小的块？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
