哪种算法适用于小内存块的连续重新分配? [英] What algorithm to apply for continuious reallocation of small memory chunks?

问题描述

在C程序中，我遇到需要大量内存块的事务，我需要知道是否存在用于处理所有这些malloc/free的算法或最佳实践方法，我已经使用数组来存储这些内存块但是在某个时候数组本身变满了，重新分配数组只会浪费更多，解决这个问题的优雅方法是什么?

In C program I face transactions that require to have alot of memory chunks, I need to know if there is an algorithm or best practice teqnique used to handle all these malloc/free, I've used arrays to store these memory chunks but at some point the array itself gets full and reallocating the array is just more waste, what is the elegant way to handle this issue?

推荐答案

在这种情况下，最好的算法是免费列表分配器+二进制搜索树.

The best algorithm in this case would be free list allocator + binary search tree.

您要从系统中请求一个大内存块，然后从该块中分配固定大小的内存块.当块已满时，您正在分配另一个，并将它们链接到红黑色或AVL二叉搜索间隔树(否则，在free期间通过遍历块列表来搜索块会成为瓶颈)

You are asking one big memory chunk from system, and then allocating memory blocks of fixed size from this chunk. When chunk is full you are allocating another one, and link them into red-black or AVL binary search interval tree (otherwise searching for a chunk during free by iterating over the chunks list becomes a bottleneck)

同时，多线程和线程同步也变得很重要.如果仅使用互斥锁或琐碎的自旋锁，则会发现libc malloc的运行速度比自定义内存分配器快得多.可以在危险指针中找到解决方案，即每个线程都有其自己的内存分配器(或一个分配器)每个CPU核心).这将增加另一个问题-当一个线程分配内存而另一个线程释放内存时，这将需要在释放函数期间搜索确切的分配器，并执行严格锁定或无锁定数据结构.

And in the same time, multi-threading and thread synchronization becomes important. If you will simply use mutexes or trivial spin-locks, you will found you libc malloc works much faster than your custom memory allocator. Solution can be found in Hazard pointer, i.e. each thread have it's own memory allocator (or one allocator per CPU core). This will add another problem - when one thread allocates memory and another releasing it, this will require searching for the exact allocator during free function, and strick locking or lock-free data structures.

最佳选择-您可以使用 jemalloc ，

The best option - you can use jemalloc, tcmalloc or any another generic propose fast memory allocator to replace your libc (i.e. pdmalloc) default allocator completely or partially.

这篇关于哪种算法适用于小内存块的连续重新分配?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！