c - 有人可以解释以下内存分配 C 程序的性能行为吗？

Question

在我的机器上 Time A 和 Time B 交换取决于是否定义（这会改变调用两个 sA的顺序）。calloc

我最初将此归因于分页系统。奇怪的 mmap是，当使用代替时calloc，情况就更奇怪了——正如预期的那样，两个循环都花费了相同的时间。从中可以看出strace，callocs 最终导致两个 mmaps，因此没有返回已分配内存的魔法。

我在 Intel i7 上运行 Debian 测试。

#include <stdlib.h>
#include <stdio.h>
#include <sys/mman.h>

#include <time.h>

#define SIZE 500002816

#ifndef USE_MMAP
#define ALLOC calloc
#else
#define ALLOC(a, b) (mmap(NULL, a * b, PROT_READ | PROT_WRITE,  \
                          MAP_PRIVATE | MAP_ANONYMOUS, -1, 0))
#endif

int main() {
  clock_t start, finish;
#ifdef A
  int *arr1 = ALLOC(sizeof(int), SIZE);
  int *arr2 = ALLOC(sizeof(int), SIZE);
#else
  int *arr2 = ALLOC(sizeof(int), SIZE);
  int *arr1 = ALLOC(sizeof(int), SIZE);
#endif
  int i;

  start = clock();
  {
    for (i = 0; i < SIZE; i++)
      arr1[i] = (i + 13) * 5;
  }
  finish = clock();

  printf("Time A: %.2f\n", ((double)(finish - start))/CLOCKS_PER_SEC);

  start = clock();
  {
    for (i = 0; i < SIZE; i++)
      arr2[i] = (i + 13) * 5;
  }
  finish = clock();

  printf("Time B: %.2f\n", ((double)(finish - start))/CLOCKS_PER_SEC);

  return 0;
}

我得到的输出：

 ~/directory $ cc -Wall -O3 bench-loop.c -o bench-loop
 ~/directory $ ./bench-loop 
Time A: 0.94
Time B: 0.34
 ~/directory $ cc -DA -Wall -O3 bench-loop.c -o bench-loop
 ~/directory $ ./bench-loop                               
Time A: 0.34
Time B: 0.90
 ~/directory $ cc -DUSE_MMAP -DA -Wall -O3 bench-loop.c -o bench-loop
 ~/directory $ ./bench-loop                                          
Time A: 0.89
Time B: 0.90
 ~/directory $ cc -DUSE_MMAP -Wall -O3 bench-loop.c -o bench-loop 
 ~/directory $ ./bench-loop                                      
Time A: 0.91
Time B: 0.92

score 10 · Accepted Answer

您还应该测试 usingmalloc而不是calloc. 要做的一件事calloc是用零填充分配的内存。

我相信在您的情况下，当您calloc最后一个 arr1 然后分配给它时，它已经出现在高速缓存内存中，因为它是最后一个分配并填充零的内存。当您calloc首先 arr1 和其次 arr2 时， arr2 的零填充会将 arr1 推出缓存。

score 6 · Accepted Answer

猜猜我本可以写更多或更少，尤其是少即是多。

原因可能因系统而异。然而; 对于 clib：

每个操作使用的总时间是相反的；如果你计时calloc+ 迭代。

IE：

Calloc arr1 : 0.494992654
Calloc arr2 : 0.000021250
Itr arr1    : 0.430646035
Itr arr2    : 0.790992411
Sum arr1    : 0.925638689
Sum arr2    : 0.791013661

Calloc arr1 : 0.503130736
Calloc arr2 : 0.000025906
Itr arr1    : 0.427719162
Itr arr2    : 0.809686047
Sum arr1    : 0.930849898
Sum arr2    : 0.809711953

第一个calloc随后malloc具有比第二个更长的执行时间。malloc(0)在任何等之前的调用会平衡同一进程中calloc用于malloc类似调用的时间（解释如下）。但是，如果一个人排队进行几次，则可以看到这些呼叫的时间略有下降。

然而，迭代时间将会变平。

简而言之；使用的总系统时间是最先分配的。然而，这是在进程的限制中无法逃脱的开销。

正在进行大量维护工作。快速了解一些案例：

页面短

当一个进程请求内存时，它会得到一个虚拟地址范围。此范围通过页表转换为物理内存。如果一个页面一个字节一个字节地翻译，我们很快就会得到巨大的页表。这就是为什么内存范围以块或页的形式提供服务的原因。页面大小取决于系统。该架构还可以提供各种页面大小。

如果我们查看上述代码的执行并添加一些从/proc/PID/stat读取的内容，我们会看到这一点（特别是注释 RSS）：

PID Stat {
  PID          : 4830         Process ID
  MINFLT       : 214          Minor faults, (no page memory read)
  UTIME        : 0            Time user mode
  STIME        : 0            Time kernel mode
  VSIZE        : 2039808      Virtual memory size, bytes
  RSS          : 73           Resident Set Size, Number of pages in real memory
} : Init

PID Stat {
  PID          : 4830         Process ID
  MINFLT       : 51504        Minor faults, (no page memory read)
  UTIME        : 4            Time user mode
  STIME        : 33           Time kernel mode
  VSIZE        : 212135936    Virtual memory size, bytes
  RSS          : 51420        Resident Set Size, Number of pages in real memory
} : Post calloc arr1

PID Stat {
  PID          : 4830         Process ID
  MINFLT       : 51515        Minor faults, (no page memory read)
  UTIME        : 4            Time user mode
  STIME        : 33           Time kernel mode
  VSIZE        : 422092800    Virtual memory size, bytes
  RSS          : 51428        Resident Set Size, Number of pages in real memory
} : Post calloc arr2

PID Stat {
  PID          : 4830         Process ID
  MINFLT       : 51516        Minor faults, (no page memory read)
  UTIME        : 36           Time user mode
  STIME        : 33           Time kernel mode
  VSIZE        : 422092800    Virtual memory size, bytes
  RSS          : 51431        Resident Set Size, Number of pages in real memory
} : Post iteration arr1

PID Stat {
  PID          : 4830         Process ID
  MINFLT       : 102775       Minor faults, (no page memory read)
  UTIME        : 68           Time user mode
  STIME        : 58           Time kernel mode
  VSIZE        : 422092800    Virtual memory size, bytes
  RSS          : 102646       Resident Set Size, Number of pages in real memory
} : Post iteration arr2

PID Stat {
  PID          : 4830         Process ID
  MINFLT       : 102776       Minor faults, (no page memory read)
  UTIME        : 68           Time user mode
  STIME        : 69           Time kernel mode
  VSIZE        : 2179072      Virtual memory size, bytes
  RSS          : 171          Resident Set Size, Number of pages in real memory
} : Post free()

正如我们所见，实际分配在内存中的页面被推迟arr2等待页面请求；一直持续到迭代开始。如果我们添加一个malloc(0)before calloc，arr1我们可以注册在迭代之前两个数组都没有分配到物理内存中。

由于可能不使用页面，因此根据请求进行映射会更有效。这就是为什么当进程 ie 执行calloc足够数量的页面时被保留，但不一定实际分配在实际内存中。

当引用地址时，会查询页表。如果地址位于未分配的页面中，则系统会出现页面错误，并且随后会分配该页面。分配页面的总和称为驻留集大小(RSS)。

我们可以通过迭代（触摸）即 1/4 来对我们的数组进行实验。这里我还添加malloc(0)了 any calloc。

Pre iteration 1/4:
RSS          : 171              Resident Set Size, Number of pages in real meory

for (i = 0; i < SIZE / 4; ++i)
    arr1[i] = 0;

Post iteration 1/4:
RSS          : 12967            Resident Set Size, Number of pages in real meory

Post iteration 1/1:
RSS          : 51134            Resident Set Size, Number of pages in real meory

为了进一步加快速度，大多数系统还在转换后备缓冲区(TLB) 中缓存 N 个最近的页表条目。

brk, 地图

当一个进程(c|m|…)alloc堆的上限扩展为 brk()或时sbrk()。这些系统调用很昂贵，为了弥补这一点，malloc将多个较小的调用收集到一个更大的 brk() 中。

这也会free()产生负面影响，brk()而且资源昂贵，它们被收集并作为更大的操作执行。

对于巨大的要求；即像您的代码中的那个一样，malloc()使用mmap(). 此阈值可由配置mallopt()，是一个受过教育的值

我们可以通过修改SIZE您的代码来获得乐趣。如果我们利用 malloc.h和使用，

struct mallinfo minf = mallinfo();

（不，不是milf），我们可以展示这个（注意Arena和Hblkhd，...）：

Initial:

mallinfo {
  Arena   :         0 (Bytes of memory allocated with sbrk by malloc)
  Ordblks :         1 (Number of chunks not in use)
  Hblks   :         0 (Number of chunks allocated with mmap)
  Hblkhd  :         0 (Bytes allocated with mmap)
  Uordblks:         0 (Memory occupied by chunks handed out by malloc)
  Fordblks:         0 (Memory occupied by free chunks)
  Keepcost:         0 (Size of the top-most releasable chunk)
} : Initial

MAX = ((128 * 1024) / sizeof(int)) 

mallinfo {
  Arena   :         0 (Bytes of memory allocated with sbrk by malloc)
  Ordblks :         1 (Number of chunks not in use)
  Hblks   :         1 (Number of chunks allocated with mmap)
  Hblkhd  :    135168 (Bytes allocated with mmap)
  Uordblks:         0 (Memory occupied by chunks handed out by malloc)
  Fordblks:         0 (Memory occupied by free chunks)
  Keepcost:         0 (Size of the top-most releasable chunk)
} : After malloc arr1

mallinfo {
  Arena   :         0 (Bytes of memory allocated with sbrk by malloc)
  Ordblks :         1 (Number of chunks not in use)
  Hblks   :         2 (Number of chunks allocated with mmap)
  Hblkhd  :    270336 (Bytes allocated with mmap)
  Uordblks:         0 (Memory occupied by chunks handed out by malloc)
  Fordblks:         0 (Memory occupied by free chunks)
  Keepcost:         0 (Size of the top-most releasable chunk)
} : After malloc arr2

然后我们减去并sizeof(int)得到MAX：

mallinfo {
  Arena   :    266240 (Bytes of memory allocated with sbrk by malloc)
  Ordblks :         1 (Number of chunks not in use)
  Hblks   :         0 (Number of chunks allocated with mmap)
  Hblkhd  :         0 (Bytes allocated with mmap)
  Uordblks:    131064 (Memory occupied by chunks handed out by malloc)
  Fordblks:    135176 (Memory occupied by free chunks)
  Keepcost:    135176 (Size of the top-most releasable chunk)
} : After malloc arr1

mallinfo {
  Arena   :    266240 (Bytes of memory allocated with sbrk by malloc)
  Ordblks :         1 (Number of chunks not in use)
  Hblks   :         0 (Number of chunks allocated with mmap)
  Hblkhd  :         0 (Bytes allocated with mmap)
  Uordblks:    262128 (Memory occupied by chunks handed out by malloc)
  Fordblks:      4112 (Memory occupied by free chunks)
  Keepcost:      4112 (Size of the top-most releasable chunk)
} : After malloc arr2

我们注册该系统按照宣传的方式工作。如果分配的大小低于阈值sbrk，则使用内部处理的内存malloc，否则mmap使用。

这种结构也有助于防止内存碎片等。

重点是该malloc系列针对一般用途进行了优化。但是 mmap，可以修改限制以满足特殊需要。

当/如果修改 mmap 阈值时，请注意这一点（以及 100 多行）。.

如果我们在计时之前填充（触摸）arr1 和 arr2 的每一页，则可以进一步观察到这一点：

Touch pages … (Here with page size of 4 kB)

for (i = 0; i < SIZE; i += 4096 / sizeof(int)) {
    arr1[i] = 0;
    arr2[i] = 0;
}

Itr arr1    : 0.312462317
CPU arr1    : 0.32

Itr arr2    : 0.312869158
CPU arr2    : 0.31

另见：

编译时选项的概要
重要统计数据
…实际上整个文件都很好读。

子注释：

那么，CPU 知道物理地址吗？不。

在内存世界中，必须解决很多问题；）。一个核心硬件是内存管理单元（MMU）。要么作为CPU的集成部分，要么作为外部芯片。

操作系统在启动时配置 MMU 并定义各种区域的访问（只读、读写等），从而提供一定程度的安全性。

我们凡人看到的地址是 CPU 使用的逻辑地址。MMU 将其转换为物理地址。

CPU的地址由两部分组成：页地址和偏移量。[PAGE_ADDRESS.OFFSET]

获取物理地址的过程可以是这样的：

.-----.                          .--------------.
| CPU > --- Request page 2 ----> | MMU          |
+-----+                          | Pg 2 == Pg 4 |
      |                          +------v-------+
      +--Request offset 1 -+            |
                           |    (Logical page 2 EQ Physical page 4)
[ ... ]     __             |            |
[ OFFSET 0 ]  |            |            |
[ OFFSET 1 ]  |            |            |
[ OFFSET 2 ]  |            |            |     
[ OFFSET 3 ]  +--- Page 3  |            |
[ OFFSET 4 ]  |            |            |
[ OFFSET 5 ]  |            |            |
[ OFFSET 6 ]__| ___________|____________+
[ OFFSET 0 ]  |            |
[ OFFSET 1 ]  | ...........+
[ OFFSET 2 ]  |
[ OFFSET 3 ]  +--- Page 4
[ OFFSET 4 ]  |
[ OFFSET 5 ]  |
[ OFFSET 6 ]__|
[ ... ]

CPU 的逻辑地址空间与地址长度直接相关。32 位地址处理器具有 2^{个 32}字节的逻辑地址空间。物理地址空间是系统可以承受的内存量。

还有碎片内存的处理，重新对齐等。

这将我们带入了交换文件的世界。如果一个进程请求更多内存，那么它是物理可用的；其他进程的一个或多个页面被转移到磁盘/交换，并且它们的页面被请求进程“窃取”。MMU 对此进行跟踪；因此 CPU 不必担心内存的实际位置。

这进一步将我们带入脏记忆。

如果我们从 /proc/[pid]/smaps 打印一些信息，更具体地说，我们得到的数组范围如下：

Start:
b76f3000-b76f5000
Private_Dirty:         8 kB

Post calloc arr1:
aaeb8000-b76f5000
Private_Dirty:        12 kB

Post calloc arr2:
9e67c000-b76f5000
Private_Dirty:        20 kB

Post iterate 1/4 arr1
9e67b000-b76f5000
Private_Dirty:     51280 kB

Post iterate arr1:
9e67a000-b76f5000
Private_Dirty:    205060 kB

Post iterate arr2:
9e679000-b76f5000
Private_Dirty:    410096 kB

Post free:
9e679000-9e67d000
Private_Dirty:        16 kB
b76f2000-b76f5000
Private_Dirty:        12 kB

创建虚拟页面时，系统通常会清除页面中的脏位。
当 CPU 写入该页面的一部分时，脏位被设置；因此，当交换带有脏位的页面时，会跳过干净的页面。

score 3 · Accepted Answer

3

这只是进程内存映像何时扩展一页的问题。

于 2012-04-10T20:57:58.140 回答

score 3 · Accepted Answer

简答

第一次calloc调用它是显式地将内存清零。下一次调用它时，它假定从返回的内存mmap已经清零。

细节

以下是我检查过的一些事情来得出这个结论，如果你愿意，你可以自己尝试：

calloc在您的第一个呼叫之前插入ALLOC呼叫。您会看到在此之后时间 A 和时间 B 的时间相同。
使用该clock()函数检查每个ALLOC调用需要多长时间。在他们都在使用的情况下，calloc您会看到第一次通话比第二次通话花费的时间要长得多。
用于对版本和版本time的执行时间进行计时。当我这样做时，我看到的执行时间始终略短。callocUSE_MMAPUSE_MMAP
我跑了strace -tt -Twhich 显示了系统调用的时间和花费了多长时间。这是输出的一部分：

跟踪输出：

21:29:06.127536 mmap(NULL, 2000015360, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fff806fd000 <0.000014>
21:29:07.778442 mmap(NULL, 2000015360, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fff093a0000 <0.000021>
21:29:07.778563 times({tms_utime=63, tms_stime=102, tms_cutime=0, tms_cstime=0}) = 4324241005 <0.000011>

您可以看到第一次mmap调用花费了0.000014几秒钟，但1.5在下一次系统调用之前大约过了几秒钟。然后第二次mmap调用花了0.000021几秒钟，然后在times几百微秒后调用。

我还逐步完成了应用程序执行的一部分，gdb发现第一次调用calloc导致了多次调用，memset而第二次调用calloc没有对memset. 如果您有兴趣，可以calloc 在这里查看源代码（查找）。__libc_calloc至于为什么在第一次通话时calloc不做memset后续电话，我不知道。但我相当有信心这可以解释您所询问的行为。

至于为什么清零的数组memset提高了性能，我的猜测是这是因为值被加载到 TLB 而不是缓存中，因为它是一个非常大的数组。无论您询问的性能差异的具体原因是两个calloc调用在执行时的行为不同。

score 2 · Accepted Answer

摘要：在分析分配数组所花费的时间时，解释了时间差异。最后分配的 calloc 只需要更多时间，而另一个（或使用 mmap 时全部）几乎没有时间。首次访问时，内存中的实际分配可能会延迟。

我对Linux上内存分配的内部了解不够。但是我运行了您的脚本，稍作修改：我添加了第三个数组和每个数组操作的一些额外迭代。而且我已经考虑到了 Old Pro 的评论，即没有考虑分配数组的时间。

结论：使用 calloc 比使用 mmap 进行分配花费的时间更长（mmap virtualy 分配内存时不使用时间，它可能会在第一次访问时推迟），并且使用我的程序最终使用 mmap 或 calloc 几乎没有区别用于整个程序的执行。

无论如何，首先要说明的是，内存分配都发生在内存映射区域而不是堆中。为了验证这一点，我添加了一个快速的 n'dirty pause 以便您可以检查进程的内存映射 (/proc//maps)

现在对于您的问题，最后分配的带有 calloc 的数组似乎确实是在内存中分配的（未推迟）。由于 arr1 和 arr2 现在的行为完全相同（第一次迭代很慢，后续迭代更快）。Arr3 对于第一次迭代更快，因为内存分配得更早。使用 A 宏时，arr1 会从中受益。我的猜测是内核已经为最后一个 calloc 预先分配了内存中的数组。为什么？我不知道...我也只用一个数组对其进行了测试（所以我删除了所有出现的 arr2 和 arr3），然后我对 arr1 的所有 10 次迭代都有相同的时间（大致）。

malloc 和 mmap 的行为相同（结果未在下面显示），第一次迭代很慢，后续迭代对所有 3 个数组都更快。

注意：所有结果在各种 gcc 优化标志（-O0 到 -O3）上都是一致的，因此看起来行为的根源并非源自某种 gcc 优化。

注2：在 Ubuntu Precise Pangolin（内核 3.2）上测试运行，使用 GCC 4.6.3

#include <stdlib.h>
#include <stdio.h>
#include <sys/mman.h>

#include <time.h>

#define SIZE 500002816
#define ITERATION 10

#if defined(USE_MMAP)
#  define ALLOC(a, b) (mmap(NULL, a * b, PROT_READ | PROT_WRITE,  \
                          MAP_PRIVATE | MAP_ANONYMOUS, -1, 0))
#elif defined(USE_MALLOC)
#  define ALLOC(a, b) (malloc(b * a))
#elif defined(USE_CALLOC)
#  define ALLOC calloc
#else
#  error "No alloc routine specified"
#endif

int main() {
  clock_t start, finish, gstart, gfinish;
  start = clock();
  gstart = start;
#ifdef A
  unsigned int *arr1 = ALLOC(sizeof(unsigned int), SIZE);
  unsigned int *arr2 = ALLOC(sizeof(unsigned int), SIZE);
  unsigned int *arr3 = ALLOC(sizeof(unsigned int), SIZE);
#else
  unsigned int *arr3 = ALLOC(sizeof(unsigned int), SIZE);
  unsigned int *arr2 = ALLOC(sizeof(unsigned int), SIZE);
  unsigned int *arr1 = ALLOC(sizeof(unsigned int), SIZE);
#endif
  finish = clock();
  unsigned int i, j;
  double intermed, finalres;

  intermed = ((double)(finish - start))/CLOCKS_PER_SEC;
  printf("Time to create: %.2f\n", intermed);

  printf("arr1 addr: %p\narr2 addr: %p\narr3 addr: %p\n", arr1, arr2, arr3);

  finalres = 0;
  for (j = 0; j < ITERATION; j++)
  {
    start = clock();
    {
      for (i = 0; i < SIZE; i++)
        arr1[i] = (i + 13) * 5;
    }
    finish = clock();

    intermed = ((double)(finish - start))/CLOCKS_PER_SEC;
    finalres += intermed;
    printf("Time A: %.2f\n", intermed);
  }

  printf("Time A (average): %.2f\n", finalres/ITERATION);


  finalres = 0;
  for (j = 0; j < ITERATION; j++)
  {
    start = clock();
    {
      for (i = 0; i < SIZE; i++)
        arr2[i] = (i + 13) * 5;
    }
    finish = clock();

    intermed = ((double)(finish - start))/CLOCKS_PER_SEC;
    finalres += intermed;
    printf("Time B: %.2f\n", intermed);
  }

  printf("Time B (average): %.2f\n", finalres/ITERATION);


  finalres = 0;
  for (j = 0; j < ITERATION; j++)
  {
    start = clock();
    {
      for (i = 0; i < SIZE; i++)
        arr3[i] = (i + 13) * 5;
    }
    finish = clock();

    intermed = ((double)(finish - start))/CLOCKS_PER_SEC;
    finalres += intermed;
    printf("Time C: %.2f\n", intermed);
  }

  printf("Time C (average): %.2f\n", finalres/ITERATION);

  gfinish = clock();

  intermed = ((double)(gfinish - gstart))/CLOCKS_PER_SEC;
  printf("Global Time: %.2f\n", intermed);

  return 0;
}

结果：

使用 USE_CALLOC

Time to create: 0.13
arr1 addr: 0x7fabcb4a6000
arr2 addr: 0x7fabe917d000
arr3 addr: 0x7fac06e54000
Time A: 0.67
Time A: 0.48
...
Time A: 0.47
Time A (average): 0.48
Time B: 0.63
Time B: 0.47
...
Time B: 0.48
Time B (average): 0.48
Time C: 0.45
...
Time C: 0.46
Time C (average): 0.46

使用 USE_CALLOC 和 A

Time to create: 0.13
arr1 addr: 0x7fc2fa206010
arr2 addr: 0xx7fc2dc52e010
arr3 addr: 0x7fc2be856010
Time A: 0.44
...
Time A: 0.43
Time A (average): 0.45
Time B: 0.65
Time B: 0.47
...
Time B: 0.46
Time B (average): 0.48
Time C: 0.65
Time C: 0.48
...
Time C: 0.45
Time C (average): 0.48

使用 USE_MMAP

Time to create: 0.0
arr1 addr: 0x7fe6332b7000
arr2 addr: 0x7fe650f8e000
arr3 addr: 0x7fe66ec65000
Time A: 0.55
Time A: 0.48
...
Time A: 0.45
Time A (average): 0.49
Time B: 0.54
Time B: 0.46
...
Time B: 0.49
Time B (average): 0.50
Time C: 0.57
...
Time C: 0.40
Time C (average): 0.43

c - 有人可以解释以下内存分配 C 程序的性能行为吗？

5 回答 5

页面短

brk, 地图

子注释：

Related

Reference