malloc/realloc/free 容量优化

发布于 2024-12-29 11:53:35 字数 429 浏览 1 评论 0原文

当您有一个动态分配的缓冲区，在运行时以不可预测的方式（例如向量或字符串）改变其大小时，优化其分配的一种方法是仅按 2 的幂（或其他一组边界/阈值），并保留多余的空间未使用。这有助于分摊搜索新的可用内存和复制数据的成本，但会消耗一点额外的内存。例如，许多 C++ stl 容器的接口规范（保留、调整大小、修剪）都考虑了这样的方案。

我的问题是 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 ？

原文

When you have a dynamically allocated buffer that varies its size at runtime in unpredictable ways (for example a vector or a string) one way to optimize its allocation is to only resize its backing store on powers of 2 (or some other set of boundaries/thresholds), and leave the extra space unused. This helps to amortize the cost of searching for new free memory and copying the data across, at the expense of a little extra memory use. For example the interface specification (reserve vs resize vs trim) of many C++ stl containers have such a scheme in mind.

My question is does the default implementation of the malloc/realloc/free memory manager on Linux 3.0 x86_64, GLIBC 2.13, GCC 4.6 (Ubuntu 11.10) have such an optimization?

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

Put another way, for what values of N and M (or in what other circumstances) will p == q?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

两个我 2025-01-05 11:53:36

来自 glibc trunk 中的 realloc 实现

首先，如果内存是通过mmap()而不是通过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 那样进行常数因子优化增加，而是精确分配用户请求的数量（四舍五入到下一个块边界+对齐内容等）。

我想这个想法是，如果用户想要 2 倍大小增加（或任何其他常数因子增加，以保证多次调整大小时的对数效率），那么用户可以在由C 库。

From the realloc implementation in glibc trunk at http://sources.redhat.com/git/gitweb.cgi?p=glibc.git;a=blob;f=malloc/malloc.c;h=12d2211b0d6603ac27840d6f629071d1c78586fe;hb=HEAD

First, if the memory has been obtained via mmap() instead of sbrk(), which glibc malloc does for large requests, >= 128 kB by default 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 has mremap(), so in practice this is what is done).

For smaller requests, a few lines below we have

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

where _int_realloc is a bit big to copy-paste here, but you'll find it starting at line 4221 in the link above. AFAICS, it does NOT do the constant factor optimization increase that e.g. the C++ std::vector does, but rather allocates exactly the amount requested by the user (rounded up to the next chunk boundaries + alignment stuff and so on).

I suppose the idea is that if the user wants this factor of 2 size increase (or any other constant factor increase in order to guarantee logarithmic efficiency when resizing multiple times), then the user can implement it himself on top of the facility provided by the C library.

回复收藏 0 原文