linux - malloc/realloc/空闲容量优化

Question

当你有一个动态分配的缓冲区，它在运行时以不可预知的方式改变其大小(例如一个向量或一个字符串)时，优化其分配的一种方法是仅根据 2 的幂(或其他一些集合)调整其后备存储的大小边界/阈值)，并保留未使用的额外空间。这有助于分摊搜索新的空闲内存和复制数据的成本，但会消耗一些额外的内存。例如，许多 C++ STL 容器的接口(interface)规范(reserve vs resize vs trim)都考虑了这样的方案。

我的问题是 Linux 3.0 x86_64、GLIBC 2.13、GCC 4.6 (Ubuntu 11.10) 上的 malloc/realloc/free 内存管理器的默认实现是否有这样的优化？

void* p = malloc(N);
... // time passes, stuff happens
void* q = realloc(p,M);

换句话说，对于什么 N 和 M 的值(或在其他情况下)，p == q？

Answer 1

来自 glibc trunk 中的 realloc 实现 http://sources.redhat.com/git/gitweb.cgi?p=glibc.git;a=blob;f=malloc/malloc.c;h=12d2211b0d6603ac27840d6f629071d1c78586fe;hb=HEAD

首先，如果内存是通过 mmap() 而不是 sbrk() 获取的，glibc malloc 为大型请求所做的，默认情况下 >= 128 kB IIRC:

   if (chunk_is_mmapped(oldp))
   {
     void* newmem;

 #if HAVE_MREMAP
     newp = mremap_chunk(oldp, nb);
     if(newp) return chunk2mem(newp);
 #endif
     /* Note the extra SIZE_SZ overhead. */
     if(oldsize - SIZE_SZ >= nb) return oldmem; /* do nothing */
     /* Must alloc, copy, free. */
     newmem = public_mALLOc(bytes);
     if (newmem == 0) return 0; /* propagate failure */
     MALLOC_COPY(newmem, oldmem, oldsize - 2*SIZE_SZ);
     munmap_chunk(oldp);
     return newmem;
   }

(Linux 有 mremap()，所以实际上就是这样做的)。

对于较小的请求，我们在下面的几行

newp = _int_realloc(ar_ptr, oldp, oldsize, nb);

其中 _int_realloc 有点大，无法复制粘贴到此处，但您会在上面的链接中从第 4221 行开始找到它。 AFAICS，它不会增加常数因子优化，例如C++ std::vector 确实如此，而是准确分配用户请求的数量(四舍五入到下一个 block 边界 + 对齐内容等等)。

我想这个想法是，如果用户想要增加 2 倍大小(或任何其他常数增加以保证多次调整大小时的对数效率)，那么用户可以自己在设施之上实现它由 C 库提供。