realloc调用引入了多少开销?

我在for循环的每次迭代中使用realloc ,迭代次数超过10000次。

这是一个好习惯吗? 如果多次调用realloc会导致错误吗?

除非你的内存不足(任何其他分配器也会发生这种情况),它不会失败 – 但如果你设法预先估算所需的存储空间,你的代码通常运行得更快。

通常最好只执行额外的循环运行以确定存储要求。

我不会说realloc是不行的,但它也不是好的做法。

我最近偶然发现了这个问题,虽然它已经很老了,但我觉得这些信息并不完全准确。

关于预先确定需要多少字节内存的额外循环,

使用额外的循环并不总是或甚至更好。 预先确定需要多少内存需要什么? 这可能会产生昂贵且不需要的额外I / O.

关于一般使用realloc,

alloc函数系列(malloc,calloc,realloc和free)非常有效。 底层alloc系统从OS分配一个大块,然后根据请求将部分传递给用户。 对realloc的连续调用几乎肯定只会增加当前内存位置的额外空间。

如果系统从一开始就为您提供更有效和正确的帮助,您就不希望自己维护堆池。

如果执行此操作,则存在碎片内存的风险。 这会导致性能下降,对于32位系统,由于缺少大量连续内存块,可能会导致内存不足。

我猜你每次都会将数组的长度增加1。 如果是这样,那么您可以更好地跟踪容量和长度,并且只在需要超过当前容量的长度时才增加容量。 增加容量时,请大于1。

当然,标准容器会为您做这类事情,所以如果您可以使用它们,最好这样做。

除了之前所说的内容之外,还有一些事情需要考虑:

realloc(, X + inc)取决于两件事:

  1. malloc(N + inc)的速度,它通常随着分配块的大小而向O(N)降级
  2. memcpy(newbuf, oldbuf, N)的速度,它也是O(N)的块大小

这意味着对于增量但是大的现有块, realloc()性能相对于现有数据块的大小是O(N^2) 。 想想bubblesort与quicksort ……

如果你从一个小块开始它会比较便宜,但如果要重新分配的块很大,会显着惩罚你。 为了缓解,您应确保inc相对于现有大小不小 ; 以恒定量重新分配是性能问题的一个方法。

另外,即使你以较大的增量增长(比如,将新大小扩展为旧的大小的150%),重新分配大缓冲区的内存使用量也会增加; 在复制现有内容期间,您使用两倍的内存量。 一系列:

 addr = malloc(N); addr = realloc(addr, N + inc); 

因此很快(很多)早于:

 addr[0] = malloc(N); addr[1] = malloc(inc); 

有数据结构,不需要realloc()来增长; 链表,跳过列表,间隔树都可以附加数据,而无需复制现有数据。 C ++ vector<>以这种方式增长,它以一个初始大小的数组开始,并且如果你增长超过它,则继续追加 ,但它不会realloc() (即复制)。 考虑实现(或使用预先存在的实现)类似的东西。

在C:

如果使用得当,realloc没有任何问题。 也就是说,它很容易错误地使用它。 请参阅编写实体代码 ,深入讨论调用realloc的所有方法以及调试时可能导致的其他复杂情况。

如果您发现自己一次又一次地重新分配相同的缓冲区只有一个小的增量大小的凹凸,请注意分配比您需要的空间更多的空间通常更有效,然后跟踪实际使用的空间。 如果超出分配的空间,请分配较大的新缓冲区,复制内容并释放旧缓冲区。

在C ++中:

你可能应该避免realloc(以及malloc和free)。 尽可能使用标准库中的容器类(例如,std :: vector)。 它们经过了充分测试和优化,可以减轻您正确管理内存(如处理exception)的许多内务管理细节的负担。

C ++没有重新分配现有缓冲区的概念。 而是以新大小分配新缓冲区,复制内容,并删除旧缓冲区。 这就是当realloc无法满足现有位置的新大小时所做的事情,这使得C ++的方法看起来效率较低。 但realloc很少能够实际利用就地重新分配。 标准C ++容器非常聪明,可以最大限度地减少碎片分配,并在许多更新中分摊成本,因此如果您的目标是提高性能,那么追求重新分配通常是不值得的。

你应该重新分配2的幂的大小。这是stl使用的策略,并且由于管理内存的方式很好。 realloc dones不会失败,除非你的内存不足(并将返回NULL),但会复制新位置的现有(旧)数据,这可能是性能问题。

如果你是realloc() – 在循环中使用相同的缓冲区我看到没有问题,只要你有足够的内存来恐吓额外的内存请求:)

通常realloc()将扩展/收缩你正在使用的现有分配空间,并将返回相同的指针; 如果它没有在原地进行,那么就会涉及到一个副本和免费,所以在这种情况下,realloc()会变得昂贵; 你也得到一个新的指针:)