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

Question

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

san*_*oyd 14 c unix linux compiler-construction performance

在我的机器上,时间A和时间B交换取决于是否A定义(这改变了calloc调用两个s 的顺序).

我最初将此归因于寻呼系统.奇怪的是,当 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;
}

Run Code Online (Sandbox Code Playgroud)

我得到的输出:

 ~/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

Run Code Online (Sandbox Code Playgroud)

Answer 1

Zan*_*ynx 10

您还应该使用malloc而不是calloc.有一件事calloc是用零填充分配的内存.

我相信你的情况,当你callocarr1最后然后分配给它时,它已经出现故障,因为它是最后一个分配和零填充.当你calloc先arr1而arr2秒,然后arr2的零填充将arr1推出缓存.

Answer 2

Mor*_*pfh 6

猜猜我可以写更多或更少,尤其是越少越好.

原因可能因系统而异.然而; 对于clib:

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

即:

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

Run Code Online (Sandbox Code Playgroud)

第一个calloc随后malloc执行时间更长,然后是第二个.malloc(0)在任何calloc等之前调用ie ,malloc在相同的过程中平均用于类似调用的时间(下面的说明).一个可以但看到及时为这些电话的小幅下滑,如果一个做几次排队.

然而,迭代时间将变平.

所以总之; 使用的总系统时间是最先获得分配的最高系统时间.然而,这是在进程的限制中无法转义的开销.

有很多维护正在进行中.快速了解一些案例:

简短的页面

当进程请求内存时,它被提供虚拟地址范围.此范围通过页表转换为物理内存.如果页面逐字节翻译,我们将很快获得巨大的页表.作为一个,这就是为什么内存范围以块或页面提供的原因.页面大小取决于系统.该体系结构还可以提供各种页面大小.

如果我们查看上面代码的执行并从/ proc/PID/stat添加一些读取, 我们会看到这个在行动中(Esp.note 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()

Run Code Online (Sandbox Code Playgroud)

我们可以看到实际分配在内存中的arr2页面被推迟等待页面请求; 持续到迭代开始.如果我们添加了malloc(0)之前 calloc的arr1我们可以注册,无论是数组迭代之前在物理内存中分配.

由于可能未使用页面,因此根据请求进行映射效率更高.这就是为什么当进程即calloc保留足够数量的页面时,但不一定实际分配在实际内存中的原因.

引用地址时,将查询页表.如果地址位于未分配的页面中,则系统会发生页面错误,随后会分配页面.分配的页面总和称为驻留集大小(RSS).

我们可以通过迭代(触摸)即1/4来对我们的数组进行实验.在此malloc(0)之前我还添加了任何内容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

Run Code Online (Sandbox Code Playgroud)

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

brk,mmap

当进程(c|m|…)alloc堆的上限由brk()或扩展时 sbrk().这些系统调用是昂贵的,并且为了补偿这个系统调用malloc收集到一个更大的brk()的多个较小的调用.

这也会影响free()作为负面因素brk()也是资源昂贵,它们被收集并作为更大的操作执行.

对于巨大的要求; 就像代码中的那个一样,malloc()使用mmap(). 可以配置的阈值mallopt()是受过教育的值

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

struct mallinfo minf = mallinfo();

Run Code Online (Sandbox Code Playgroud)

(不,不是摩洛伊斯兰解放阵线),我们可以证明这一点(注意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

Run Code Online (Sandbox Code Playgroud)

然后我们减去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

Run Code Online (Sandbox Code Playgroud)

我们注册该系统的工作方式与宣传的一样.如果分配的大小低于阈值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

Run Code Online (Sandbox Code Playgroud)

另见:

编译时选项的概要
重要统计数据
......实际上整个文件读起来都不错.

子说明:

那么,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 ]__|
[ ... ]

Run Code Online (Sandbox Code Playgroud)

CPU的逻辑地址空间直接链接到地址长度.32位地址处理器的逻辑地址空间为2 ³²字节.该物理地址空间是系统能有多少内存负担.

还有碎片存储器的处理,重新对齐等.

这将我们带入交换文件的世界.如果进程请求更多内存,那么物理上可用; 其他进程的一个或几个页面被转移到磁盘/交换,并且它们的页面被请求进程" 窃取 ".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

Run Code Online (Sandbox Code Playgroud)

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

Answer 3

Gab*_*ern 3

简答

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

细节

以下是我检查后得出的一些结论，如果您愿意，您可以自己尝试：

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

跟踪输出：

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>

Run Code Online (Sandbox Code Playgroud)

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

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

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

归档时间：	13 年，8 月前
查看次数：	1365 次
最近记录：	13 年，8 月前