realloc调用会引入多少开销？

Question

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

这是一个好的做法吗？如果多次调用realloc，它会引起错误吗？

- saber

---

什么异常？你是指C++吗？使用C++中的相关内容。如果你是指C语言，那么在C语言中是没有异常处理的。 - pmg

请不要同时标记C和C++问题。答案通常取决于您实际使用的语言。在C++中，我会问您为什么要手动管理内存？ - Björn Pollex

C函数中没有异常，但如果realloc失败，您会冒着返回空指针的风险。为什么不分配一个合理大小的缓冲区并保留它，直到您需要更大的东西？或者使用一个标准容器来管理内存？ - Bo Persson

使用一个容器代替？ - jk.

Answer 1

只有当你的内存耗尽时，它才会失败（使用其他分配器也会出现这种情况） - 但是如果您成功预估所需存储空间，您的代码通常会运行得更快。

通常最好再多做一次循环仅仅为了确定存储要求。

我不会说realloc不能用，但这也不是一个好的实践。

- Alexander Gessler

---

如果您可以运行额外的循环来确定存储，那么最好这样做。但在许多情况下，这并不是真正可能的，因为您需要一次性处理每个到达的项目。 - David Heffernan

即使不增加额外的循环，你也可以通过经验法则来减少realloc调用的次数，比如将分配内存的量增加为总大小的一个因子，而不仅仅是每次增加一个对象的大小（例如，你可以一开始为100个对象分配空间，当满了之后再增加50%（使得总数达到150），然后再增加50%（使得总数达到225），以此类推...）。 - GrahamS

是的，如果您需要使用realloc（即在David描述的情况下省略明显的C++替代方案），请确保小心使用它。为每个循环迭代重新分配是一个坏主意。但我认为寻找数组最佳增长因子是一个不同的话题，在SO上已经进行了很多讨论。 - Alexander Gessler

"[R]un out of memory" 可能过于简化了。当内存碎片化时，即使有足够的空间，分配也可能失败，因为它不是连续的。由于问题强烈暗示了许多增量重新分配，所以碎片化似乎是一个真正的问题。 - Adrian McCarthy

额外的循环肯定会引入比多次调用realloc更昂贵的开销。alloc函数族非常高效，比用户维护自己的堆池做得更好、更有效率。 - ffhaddad

Answer 2

我最近发现了这个问题，虽然它很久远了，但我觉得其中的信息不完全准确。

关于预先确定需要多少字节的内存而使用额外的循环，

并不总是或甚至不经常更好。预先确定需要多少内存涉及什么？这可能会产生昂贵和不必要的额外I/O。

关于一般使用realloc，

分配函数组（malloc、calloc、realloc和free）非常高效。底层分配系统从操作系统中分配一个大块，然后按请求将部分传递给用户。连续调用realloc几乎肯定只会向当前内存位置添加附加空间。

如果系统能够更高效、更正确地从一开始就为您维护堆池，则不需要自己维护堆池。

- ffhaddad

Answer 3

除了之前提到的内容外，还有一些需要考虑的事情： realloc(<X-sized-buf>, X + inc) 的性能取决于两个因素：

1. malloc(N + inc) 的速度通常随着分配块的大小而降低，趋向于O(N)； 2. 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()（即复制）。考虑实现（或使用现有实现）类似于此的东西。

- FrankH.

---

说到内存峰值，我见过的最愚蠢的realloc用法之一就是调整缓冲区大小，而不是释放它并分配一个新的缓冲区，尤其是当你不打算使用其内容时。 - R.. GitHub STOP HELPING ICE

在 realloc(buf, size++) 魔法之后，有无尽的糟糕想法。 - FrankH.

您是如何得出realloc的时间复杂度为O(N^2)的？每个具有O(N)复杂度的独立操作总体上仍被看作是O(N)。要获得O(N^2)，您需要对于N中的每个项n，执行另一个具有O(N)复杂度的操作。 - Jason

@Jason：你说得对，我错了。话虽如此......如果你说它是 (i + k)*O(N)，其中 i 是 malloc() 的份额，k 是 memcpy() 的份额，那么对于大内存块，你仍然会得到 k >> i 的代价-这可能是你不想承担的。我的关于 C++ 的 vector<> 的陈述也不再正确；行为在 C++11 之前的确被允许，但是 C++11 要求向量内容连续的内存，因此不能在调整大小时避免复制。 - FrankH.

Answer 4

如果您这样做，可能会使内存碎片化。这会导致性能降低，并且对于32位系统来说，由于缺乏大块连续内存的可用性，可能导致内存短缺问题。

我猜您是每次都将数组长度增加1。如果是这样，最好跟踪容量和长度，并仅在需要超过当前容量的长度时才增加容量。当增加容量时，应增加比1更大的数量。

当然，标准的容器可以为您执行此类操作，因此如果可以使用它们，则最好这样做。

- David Heffernan

Answer 5

在C中：

如果使用得当，realloc没有什么问题。但是，使用不当会导致问题。请参考《编写可靠代码》，深入讨论了调用realloc时出现问题的各种方式以及在调试过程中可能引起的额外复杂性。

如果您发现自己一遍又一遍地重新分配相同的缓冲区，并且只增加了很少的空间，请注意通常更有效的方法是分配比您需要的更多的空间，然后跟踪实际使用的空间。如果超出了分配的空间，请分配一个新的较大尺寸的缓冲区，复制内容并释放旧的缓冲区。

在C ++中：

您应该避免使用realloc（以及malloc和free）。尽可能使用标准库中的容器类（例如std :: vector）。它们经过充分测试和优化，并减轻了管理内存正确性的许多繁琐细节（如处理异常）。

C ++没有重新分配现有缓冲区的概念。相反，在新大小处分配新缓冲区，复制内容，然后删除旧缓冲区。当realloc无法满足现有位置的新大小时，这就是realloc所做的，这使得C ++的方法似乎不太有效。但是，realloc实际上很少能够利用原地重新分配。标准C ++容器非常聪明地分配以最小化碎片，并在许多更新中分摊成本，因此如果您的目标是提高性能，则通常不值得追求realloc。

- Adrian McCarthy

Answer 6

我想为这个讨论添加一些实证数据。

一个简单的测试程序：

#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来处理不跨页边界的调整大小而无需复制缓冲区。

在我看来，除非你能找到一种避免完全复制的数据结构，否则在应用程序中跳过轨道容量并进行2的幂次方调整大小的方法，并让libc为您完成繁重的工作。

- wkz

Answer 7

你应该将realloc分配的大小设置为2的幂次方。这是stl使用的策略，因为内存管理的方式很好。 除非内存用尽(此时会返回NULL)，否则realloc不会失败但会将你现有的(旧)数据复制到新位置，这可能会影响性能。

- cprogrammer

---

STL的实现可能具有优势，因为它知道默认的内存分配器是什么。我曾经在一些系统上工作过，其中2的幂次方在有效使用内存方面是最糟糕的尺寸，因为分配器必须添加一个小的头部，然后将所需的大小舍入到偶数块。在这种情况下，2的幂次方几乎最大化了未使用的空间。 - Steve Jessop

关于二的幂次方，没有什么神奇的。你应该使用指数级增长的大小进行realloc以避免O(n^2)循环性能问题，但基数可以是大于1的任何值，不一定是2。许多人喜欢1.5（每次空间不足时将缓冲区增加50%）。 - R.. GitHub STOP HELPING ICE

@David：我该如何在 malloc 下设置分配器？它只是 HeapAlloc 的包装器。但是 new 运算符可以被重写，但正如我所说的：这是一个特殊情况，你必须意识到并加以处理。 - cprogrammer

@cprogrammer 您没有设置分配程序。您的C或C++库自带一个分配器。它将从系统获取内存，但是然后会进行子分配。因此，虽然您可能认为使用2次幂和值等于页面大小的倍数调用malloc（或任何分配函数）很聪明，但这些都被分配更大块的库所占用，并且从内部进行了子分配。迄今为止最好的策略是使用标准容器。 - David Heffernan

根据c：\Program Files（x86）\Microsoft Visual Studio 9.0 \ VC \ crt \ src \ malloc.c，malloc调用（间接）HeapAlloc并使用相同的大小（更确切地说是“size？size：1”）。在某些特殊情况下，您所说的是正确的，但正如我上面所写的那样，这不是普遍情况... - cprogrammer

Answer 8

如果您在循环中重新分配相同的缓冲区，只要您有足够的内存来处理额外的内存请求，我就看不到任何问题 :)

通常realloc()会扩展/缩小您正在操作的已分配空间，并将相同的指针还给您；如果它无法原地执行，则会涉及复制和释放操作，因此在这种情况下，realloc()会变得昂贵；并且您也会得到一个新指针 :)

- user237419

---

我认为将“horror”（恐惧）误写成“honor”（荣誉）是一种弗洛伊德式的口误。:-) 调用realloc()函数10000次看起来像是极端优柔寡断的情况。为什么不确定一个合理的大小并保持它呢？ - Bo Persson

那肯定是个小错误，因为我认为自己还是个新手 :) “极端”这个词有点过了，那么对于一个聪明但复杂的算法来说，怎么样用一些简单的工具呢？关于“设置合理大小”，这正是realloc的作用所在，当我们无法准确计算数字时。例如，我在考虑getline(3)的实现；此外，软件测试人员也需要养家糊口，对吧？如果不做出这些决策，他会怎么样呢？如果使用不当，realloc可能会解决饥饿问题；另一方面，每个未释放的指针都会杀死一只小猫！拯救小猫！ - user237419