malloc 和 free 的计时

Question

我正在尝试了解 malloc 和 free 的时间安排。所以我写了这个简单的程序：

#include <stdlib.h>
#include <stdio.h>


int
main()
{
  long i;
  for(i = 2; i < 10000000000; i*=2) {
    struct timeval start, end;
    double timing ;
    long j;
    gettimeofday(&start, NULL);
    double *vect = malloc((size_t) i * sizeof(*vect));
    if (!vect) {
      printf("malloc failed\n");
      exit(-1);
    }
    gettimeofday(&end, NULL);
    timing =  (double) (end.tv_sec * 1e6 + end.tv_usec) - (start.tv_sec * 1e6 + start.tv_usec);
    printf("size %ld allocating (%f)\t", i * sizeof(*vect), timing);
    /* I do this to avoid lazy allocation */
    for(j = 0; j < i; j++)
      vect[i] = 2;

    gettimeofday(&start, NULL);
    free(vect);
    gettimeofday(&end, NULL);
    timing =  (double) (end.tv_sec * 1e6 + end.tv_usec) - (start.tv_sec * 1e6 + start.tv_usec);
    printf("deallocating (%f)\n", timing);
  }
  return 0;
}

这个程序的输出看起来这就是我得到的输出：

size 16 allocating (40.000000)  deallocating (0.000000)
size 32 allocating (0.000000)   deallocating (0.000000)
size 64 allocating (0.000000)   deallocating (0.000000)
size 128 allocating (0.000000)  deallocating (1.000000)
size 256 allocating (0.000000)  deallocating (0.000000)
size 512 allocating (0.000000)  deallocating (0.000000)
size 1024 allocating (1.000000) deallocating (0.000000)
size 2048 allocating (0.000000) deallocating (0.000000)
size 4096 allocating (1.000000) deallocating (0.000000)
size 8192 allocating (1.000000) deallocating (0.000000)
size 16384 allocating (1.000000)    deallocating (0.000000)
size 32768 allocating (1.000000)    deallocating (1.000000)
size 65536 allocating (1.000000)    deallocating (0.000000)
size 131072 allocating (1.000000)   deallocating (1.000000)
size 262144 allocating (2.000000)   deallocating (4.000000)
size 524288 allocating (2.000000)   deallocating (2.000000)
size 1048576 allocating (1.000000)  deallocating (2.000000)
size 2097152 allocating (3.000000)  deallocating (3.000000)
size 4194304 allocating (2.000000)  deallocating (4.000000)
size 8388608 allocating (4.000000)  deallocating (3.000000)
size 16777216 allocating (2.000000) deallocating (3.000000)
size 33554432 allocating (3.000000) deallocating (2.000000)
size 67108864 allocating (2.000000) deallocating (7.000000)
size 134217728 allocating (7.000000)    deallocating (8.000000)
size 268435456 allocating (6.000000)    deallocating (8.000000)
size 536870912 allocating (5.000000)    deallocating (10.000000)
size 1073741824 allocating (6.000000)   deallocating (12.000000)
size 2147483648 allocating (25.000000)  deallocating (13.000000)
size 4294967296 allocating (7.000000)   deallocating (11.000000)
size 8589934592 allocating (6.000000)   deallocating (11.000000)

当向量的大小不断增加时，malloc 的价格如此便宜，我真的很惊讶。它不应该随着尺寸的增加而急剧增加吗？

我的第二个问题是关于 free 函数的。我一直认为 malloc 是最贵的，而不是 free。它更贵，这对我来说没有意义。

我对系统如何处理内存（物理页面和虚拟页面）有一些了解，但这些结果对我来说很有意义。 malloc 毕竟没那么贵……是吗？ :)

欢迎任何意见！

编辑：非常感谢所有快速评论！非常感激！我考虑了评论并稍微更改了我的程序。我没有使用 malloc，而是使用了 calloc。此外，我两次遍历数组并为它们计时。一个是为了确保所有页面都已分配，第二个是为了测试访问数组的时间。显然有一个随着数组大小的增加而增加的差异！

我正试图获得我的算法的一些性能结果，所以我想摆脱这个额外的成本。我的算法中使用的大部分内存都是在开始时分配的。 有什么方法可以告诉 malloc 分配和关联内存？ 目标是获得更可重现（和更好 :) ）的结果。

size 262144 allocating (5.000000)   first pass (166.000000) second pass (190.000000)    diff between passes (24.000000) deallocating (10.000000)
size 524288 allocating (4.000000)   first pass (330.000000) second pass (328.000000)    diff between passes (2.000000)  deallocating (3.000000)
size 1048576 allocating (2.000000)  first pass (669.000000) second pass (673.000000)    diff between passes (4.000000)  deallocating (5.000000)
size 2097152 allocating (5.000000)  first pass (1326.000000)    second pass (1314.000000)   diff between passes (12.000000) deallocating (6.000000)
size 4194304 allocating (4.000000)  first pass (2655.000000)    second pass (2586.000000)   diff between passes (69.000000) deallocating (5.000000)
size 8388608 allocating (4.000000)  first pass (4858.000000)    second pass (4838.000000)   diff between passes (20.000000) deallocating (5.000000)
size 16777216 allocating (3.000000) first pass (9034.000000)    second pass (8458.000000)   diff between passes (576.000000)    deallocating (4.000000)
size 33554432 allocating (3.000000) first pass (15702.000000)   second pass (14375.000000)  diff between passes (1327.000000)   deallocating (4.000000)
size 67108864 allocating (4.000000) first pass (25785.000000)   second pass (23228.000000)  diff between passes (2557.000000)   deallocating (3.000000)

Answer 1

在大多数情况下，这非常取决于实现。但是让我们试着看看典型的 malloc 实现是如何工作的。

在您的分配大小较小的情况下，分配器会尝试避免内部碎片并进行非常紧凑的分配。这意味着一些页面已经分配，然后未来的分配从相同的页面完成。通过您的第一次分配如何比其他分配花费更多时间（它也在此处进行堆数据结构初始化），这一点有点清楚。

无论如何，这些操作（分配小块）中的每一个在成本上都是相等的，因为它只是一些指针更新。通过sbrk或mmap的分配已经完成（直到它需要分配更多）。

现在进行更大的分配。在这些情况下，许多分配器只是退回到映射新页面（在页面对齐大小之后）。这需要分配新页面，这是一个系统调用。

页面分配级别是在页面粒度上完成的。这意味着需要完成的更新将按照页数的顺序进行（同样，这非常依赖于操作系统，在某些系统上，分配一页可能与分配 10000 页的成本相同）。

如@Ctx 所述，大多数现代操作系统甚至不会在 sbrk 或 mmap 时更新页表，但它们会在数据实际为 read/written 在页面上。所以提交可能只是内核中正在更新的一些内部数据结构。

免费，对于小分配通常非常便宜，因为它只涉及 return 分配到空闲列表和 1 或 2 次合并。在这种情况下，堆不一定 return 页面。

对于大分配，情况与分配类似。进行系统调用以取消提交页面。该操作可能与页数成正比。

另一个可能影响您的计时的因素是分配器的默认行为。 malloc 不需要在 return 之前清除内存，但一些分配器会这样做（基本上它们的行为类似于 calloc）。在那种情况下，malloc 的成本可能会线性上升。在您的情况下，对不同尺寸的 calloc 也进行类似比较可能是值得的。

malloc 和 free 的计时

Timing on malloc and free

c

allocation