malloc/free 的开销,如何去掉这种开销?
一般的malloc实现,对一块已分配的内存,都有两个机器字的簿记,甚至更多。如果不需要排错,理论上讲,只需要一个字长的额外开销,用来记录这块内存的尺寸(放在intptr[-1]处是个好主意)。
为什么需要这个开销呢?因为free传入的只是个指针,它不知道要释放多大的内存,因此free内部必须通过某种方式来获得这块内存的尺寸。
可以想象,如果用 malloc/free 来作为一个关联数组(map)的分配器,要浪费不少内存。不过好在实际数据的尺寸往往比额外消耗要大很多,相比起来,浪费的比例不算很大,况且现在内存还很便宜。
其实,打造一个高效的分配器并不难,难的是它的适用范围(多线程?cell尺寸,chunk尺寸,对齐,排错…),如果可以忍受这些缺陷,或者说是限制,还是比较值得的。下一步就是它的灵活性——让它可以更加容易集成进其它系统。
对于C标准库,如果能增加一个/一族这样的分配器,还是很有价值的。从理论上讲,只要free时多传一个size参数,就可以完全去掉额外的开销。这样两个函数就可以做到:
1 2 |
void* salloc(size_t size); void sfree(void* ptr, size_t size); |
这样做还有一个额外的好处,就是可以更好地对齐,假定程序需要按32字节对齐,malloc/free 就至少需要32字节做簿记,如果再加上内存越界检测,就需要64字节。salloc/sfree则只需要将分配的内存对齐到32字节边界即可。
但是这对程序的正确性要求很高,malloc/free中,内存越界检测可以很容易实现,而salloc/sfree就完全做不到(除非增加额外簿记)。一个好主意是可以在debug版中加入这些差错功能,而在release版中去掉。
更好(确切地讲应该是更灵活)的方案是,实现一个
1 2 3 4 5 6 7 8 9 |
struct mpool{ // ..... }; // return success or fail int mpool_init(struct mpool* pool); void mpool_destroy(struct mpool* pool); void* mpalloc(struct mpool* pool, size_t size); void mpfree(struct mpool* pool, void* ptr, size_t size); |
而让 salloc/sfree简单地作为 mpool 的包装。
gcc的std::allocator基本上是按这样的方式实现的,只不过,它的size参数,大多数时刻是自动传递的(知道具体的class/struct,也就知道它的尺寸)。实现方式上,使用 size_aligned/align 作为索引去访问特定尺寸的mempool,一个 mempool 是多个链表串起来的大chunk,每个chunk内部是链表穿起来的cell。这也许是最好的实现方式了,除了节省的额外空间开销,时间开销上,如果不考虑加锁,一次alloc平均可以在10时钟周期内完成,dealloc用的时间更短。相比之下malloc/free耗的时间也要多得多。