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并不那么昂贵...或者是吗？:)

欢迎任何评论！

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

我正在尝试获得我的算法的一些性能结果，因此我希望消除这个额外的成本。我的算法中使用的大多数内存都在开始时分配。 有没有办法告诉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)

- coyotemk

---

这完全取决于实现。 - Jabberwocky

在许多实现中，调用malloc函数除了修改一些元数据字节外，不会做任何事情，而与malloc分配的大小无关。也许calloc()更符合您的期望，因为它初始化内存。 - Ctx

仅计时一次malloc或free的时间并不准确。太多外部因素会影响它。在获得显著数字之前，您应该至少计时其中许多。即使如此，这些分配发生的顺序也可能会影响时间。正如其他人所说，这取决于实现。有许多不同的分配算法，有些在某些方面比其他算法更快，而其他算法在其他方面更快等。 - Rudy Velthuis

Answer 1

在大多数情况下，这非常依赖于具体实现。但是让我们尝试看一下典型的malloc实现如何工作。

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

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

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

页面分配级别是以页面粒度完成的。这意味着需要进行的更新将是页面数量的顺序（再次强调，这非常取决于操作系统，在某些系统上，分配一个页面可能与分配10000个页面的成本相等）。

正如@Ctx所提到的，大多数现代操作系统甚至不会在sbrk或mmap的时候更新页面表，而是在实际读取/写入页面数据时才这样做。因此，提交可能只涉及内核中的一些内部数据结构更新。

对于小型分配，释放通常非常便宜，因为它只涉及将分配返回给空闲列表和1或2个合并。在这种情况下，堆不一定会返回页面。

对于大型分配，情况与分配类似。系统调用用于取消提交页面。操作可能与页面数成比例，也可能不成比例。

另一个可能影响您时间的因素是分配器的默认行为。malloc不需要在返回之前清除内存，但是一些分配器会这样做（基本上它们的行为类似于calloc）。在这种情况下，malloc的成本可能会线性增加。在您的情况下，还可以使用不同大小的calloc进行类似比较。

- Ajay Brahmakshatriya

---

最近的操作系统中，页面分配是在写入页面时（在页面错误句柄中）完成的，而不是在调用mmap()/sbrk()进行malloc()时。 - Ctx

@Ctx 我同意。尽管所有新页面都已提交，但它们可能仅在第一次访问时才被添加到页面表中。我会将这一点添加到答案中。 - Ajay Brahmakshatriya