我realloc
在循环的每次迭代中都使用了for
超过 10000 次的循环。
这是一个好习惯吗?realloc
调用很多次会报错吗?
我realloc
在循环的每次迭代中都使用了for
超过 10000 次的循环。
这是一个好习惯吗?realloc
调用很多次会报错吗?
它不会失败,除非您的内存已用完(任何其他分配器也会发生这种情况) - 但如果您设法预先估计所需的存储空间,您的代码通常会运行得更快。
通常最好只运行一个额外的循环来确定存储要求。
我不会说这realloc
是不行的,但这也不是好的做法。
我最近偶然发现了这个问题,虽然它很老,但我觉得信息并不完全准确。
关于一个额外的循环来预先确定需要多少字节的内存,
使用额外的循环并不总是或什至经常更好。预先确定需要多少内存涉及什么?这可能会导致额外的昂贵且不需要的 I/O。
关于一般使用 realloc,
alloc 系列函数(malloc、calloc、realloc 和 free)非常有效。底层分配系统从操作系统分配一个大块,然后根据请求将部分传递给用户。对 realloc 的连续调用几乎肯定只会在当前内存位置增加额外的空间。
如果系统从一开始就更有效、更正确地为您维护堆池,则您不想自己维护堆池。
除了前面所说的,还有一些事情需要考虑:
的性能realloc(<X-sized-buf>, X + inc)
取决于两件事:
malloc(N + inc)
通常会O(N)
随着分配块的大小而降低memcpy(newbuf, oldbuf, N)
也O(N)
与块的大小有关这意味着对于小增量但大的现有块,realloc()
性能O(N^2)
与现有数据块的大小有关。想想冒泡排序与快速排序......
如果你从一个小块开始,它相对便宜,但如果要重新分配的块很大,它会严重惩罚你。为了减轻影响,您应该确保inc
相对于现有大小不小;以恒定数量重新分配是导致性能问题的秘诀。
此外,即使您以较大的增量增长(例如,将新大小缩放为旧大小的 150%),重新分配大缓冲区也会导致内存使用量激增;在复制现有内容期间,您使用两倍的内存量。一个序列:
addr = malloc(N);
addr = realloc(addr, N + inc);
因此失败(远)早于:
addr[0] = malloc(N);
addr[1] = malloc(inc);
有些数据结构不需要realloc()
增长;链表、跳过列表、区间树都可以追加数据,而无需复制现有数据。C++vector<>
以这种方式增长,它从一个初始大小的数组开始,如果超过这个值,它会继续追加,但它不会realloc()
(即复制)。考虑实现(或使用预先存在的实现)类似的东西。
如果你这样做,你会冒着使你的记忆碎片化的风险。这会导致性能下降,并且对于 32 位系统,由于缺乏大的连续内存块的可用性,可能会导致内存短缺。
我猜你每次都将数组的长度增加 1。如果是这样,那么您最好跟踪容量和长度,并且仅在需要超过当前容量的长度时才增加容量。当您增加容量时,增加的量不仅仅是 1。
当然,标准容器会为您做这种事情,所以如果您可以使用它们,最好这样做。
在 C 中:
使用得当,realloc没有问题。也就是说,很容易错误地使用它。请参阅编写可靠代码以深入讨论所有搞砸调用 realloc 的方法以及它在调试时可能导致的其他复杂性。
如果您发现自己一次又一次地重新分配相同的缓冲区,只是增加了一个小的增量大小,请注意,分配比您需要的更多空间通常更有效,然后跟踪实际使用的空间。如果超出分配的空间,请分配一个更大的新缓冲区,复制内容并释放旧缓冲区。
在 C++ 中:
您可能应该避免 realloc(以及 malloc 和 free)。尽可能使用标准库中的容器类(例如,std::vector)。它们经过了良好的测试和优化,并减轻了您正确管理内存(如处理异常)的许多内务细节的负担。
C++ 没有重新分配现有缓冲区的概念。而是以新的大小分配一个新的缓冲区,复制内容,并删除旧的缓冲区。这就是 realloc 在无法满足现有位置的新大小时所做的事情,这使得 C++ 的方法看起来效率较低。但是很少有 realloc 实际上可以利用就地重新分配。标准 C++ 容器在以最小化碎片的方式进行分配和在许多更新中分摊成本方面非常聪明,因此如果您的目标是提高性能,通常不值得努力追求 realloc。
您应该重新分配到 2 的幂的大小。这是 stl 使用的策略,并且由于内存管理方式而很好。realloc 不会失败,除非内存不足(并将返回 NULL),但会将现有(旧)数据复制到新位置,这可能是一个性能问题。
我想我会在这个讨论中添加一些经验数据。
一个简单的测试程序:
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
void *buf = NULL, *new;
size_t len;
int n = 0, cpy = 0;
for (len = 64; len < 0x100000; len += 64, n++) {
new = realloc(buf, len);
if (!new) {
fprintf(stderr, "out of memory\n");
return 1;
}
if (new != buf) {
cpy++;
printf("new buffer at %#zx\n", len);
}
buf = new;
}
free(buf);
printf("%d memcpys in %d iterations\n", cpy, n);
return 0;
}
x86_64 上的 GLIBC 产生以下输出:
new buffer at 0x40
new buffer at 0x80
new buffer at 0x20940
new buffer at 0x21000
new buffer at 0x22000
new buffer at 0x23000
new buffer at 0x24000
new buffer at 0x25000
new buffer at 0x26000
new buffer at 0x4d000
new buffer at 0x9b000
11 memcpys in 16383 iterations
x86_64 上的 musl:
new buffer at 0x40
new buffer at 0xfc0
new buffer at 0x1000
new buffer at 0x2000
new buffer at 0x3000
new buffer at 0x4000
new buffer at 0xa000
new buffer at 0xb000
new buffer at 0xc000
new buffer at 0x21000
new buffer at 0x22000
new buffer at 0x23000
new buffer at 0x66000
new buffer at 0x67000
new buffer at 0xcf000
15 memcpys in 16383 iterations
因此,看起来您通常可以依靠 libc 来处理不跨越页面边界的调整大小,而无需复制缓冲区。
在我看来,除非你能找到一种方法来使用完全避免复制的数据结构,否则在你的应用程序中跳过 track-capacity-and-do-power-of-2-resized 方法,让你的 libc 来做为你举重。
如果您在循环中使用 realloc()-ing 相同的缓冲区,只要您有足够的内存来应对额外的内存请求,我认为没有问题:)
通常 realloc() 会扩展/缩小您正在处理的现有分配空间,并会给您返回相同的指针;如果它未能就地这样做,则涉及副本和免费,因此在这种情况下 realloc() 变得昂贵;你也会得到一个新的指针:)