在我的机器上,根据A
是否是否定义(这改变了调用两个calloc
的顺序)。
我最初将此归因于寻呼系统。奇怪的是,当使用mmap
而不是calloc
,情况更为奇怪——正如预期的那样,两个循环所花费的时间相同。像从strace
可以看出,calloc
最终会产生两个mmap
s,所以没有返回已经分配的内存魔法正在进行。
我正在英特尔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: %.2fn", ((double)(finish - start))/CLOCKS_PER_SEC);
start = clock();
{
for (i = 0; i < SIZE; i++)
arr2[i] = (i + 13) * 5;
}
finish = clock();
printf("Time B: %.2fn", ((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
您还应该使用malloc
而不是calloc
进行测试。calloc
所做的一件事是用零填充分配的内存。
我相信在您的情况下,当您最后一次calloc
arr1并将其分配给它时,它已经故障到缓存中,因为它是最后一个分配的并且为零填充的。当您首先calloc
arr1,然后第二次CCD_12时,arr2的零填充会将arr1从缓存中推出。
我想我本可以写更多或更少,尤其是在少即是多的情况下
原因可能因系统而异。然而对于clib:
每次操作所用的总时间正好相反;如果你有时间13+迭代。
即:
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
第一个CCD_ 14随后的CCD_第二在任何calloc
等之前的调用(即malloc(0)
)使时间相等用于同一进程中类似CCD_ 18的调用(下面解释)。一个可以然而,如果一个人连续打了几个电话,那么这些电话的时间会略有下降。
然而,迭代时间会变平。
简而言之;使用的总系统时间是有史以来第一次分配的最高时间。然而,这是一个过程限制中无法逃脱的开销。
有很多维护工作正在进行。快速了解一些案例:
页面上的缩写
当进程请求内存时,将为其提供虚拟地址范围。此范围通过页表转换为物理内存。如果页面将字节转换为字节,我们会很快得到巨大的页表。这就是为什么内存范围以块或页的形式提供。页面大小为系统依靠的该体系结构还可以提供各种页面大小。
如果我们查看上面代码的执行情况,并添加一些来自/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)
arr1
的calloc
我们可以注册两个阵列都没有在物理中分配迭代前的内存。
由于可能不使用页面,因此根据请求进行映射更有效。这就是为什么当处理,即做一个calloc
足够的页数是保留的,但不一定在实际内存中实际分配。
当一个地址被引用时,页面表被查阅。如果地址是在未分配的页面中,系统提供页面故障,并且页面随后被分配。分配的页面总数称为Resident设置大小(RSS)。
我们可以通过迭代(触摸)来对我们的阵列进行实验,即1/4。在这里,我还在任何calloc
之前添加了malloc(0)
。
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
为了进一步加快速度,大多数系统都会额外缓存最近的N个翻译后备缓冲区(TLB)中的页表条目。
brk,mmap
当进程(c|m|…)alloc
时,堆的上限由27或CCD_ 28。这些系统调用成本高昂,而且需要补偿此CCD_ 29将多个较小的调用收集到一个较大的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
然后我们从MAX
中减去sizeof(int)
,得到:
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
我们注册该系统如宣传的那样工作。如果分配大小为低于阈值的CCD_ 41被使用并且存储器由CCD_,否则使用CCD_ 43。
这种结构也有助于防止内存碎片等。
要点是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的逻辑地址空间直接链接到地址长度。A.32位地址处理器具有232字节的逻辑地址空间。物理地址空间是系统所能提供的内存量。
还有碎片内存的处理、重新排列等。
这将我们带入交换文件的世界。如果进程请求更多内存则在物理上是可用的;其他进程的一页或几页转移到磁盘/swap,请求进程将其页面">被盗"。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写入该页面的某个部分时,会设置脏位;因此当交换了写有脏位的页面,跳过干净的页面。
简短回答
第一次调用calloc
时,它明确地将内存清零。当下一次调用它时,它假设从mmap
返回的存储器已经被清零。
详细信息
以下是我检查得出的一些结论,如果你愿意,你可以自己尝试:
-
在第一个
ALLOC
呼叫之前插入一个calloc
呼叫。你会看到,在这之后,时间A和时间B的时间是相同的。 -
使用
clock()
函数检查每个ALLOC
调用所用的时间。在它们都使用calloc
的情况下,您将看到第一个调用比第二个调用花费更长的时间。 -
使用
time
对calloc
版本和USE_MMAP
版本的执行时间进行计时。当我这样做的时候,我发现USE_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>
您可以看到,第一次mmap
调用花费了0.000014
秒,但在下一次系统调用之前大约经过了1.5
秒。然后,第二个mmap
调用用了0.000021
秒,几百微秒后又是times
调用。
我还使用gdb
逐步执行了部分应用程序,发现对calloc
的第一次调用导致了对memset
的多次调用,而对calloc
的第二次调用没有对memset
进行任何调用。如果您感兴趣,可以在此处查看calloc
的源代码(查找__libc_calloc
)。至于为什么calloc
在第一次调用时执行memset
,而在随后的调用中不执行CCD_71,我不知道。但我很有信心,这可以解释你所询问的行为。
至于为什么memset
为零的数组提高了性能,我猜测这是因为它是一个非常大的数组,所以值被加载到TLB而不是缓存中。不管您询问的性能差异的具体原因是,两个calloc
调用在执行时表现不同。
这只是进程内存映像何时扩展一页的问题。
摘要 :分析分配数组所需的时间时会解释时差。最后一个分配的calloc只需要多一点时间,而另一个(或在使用mmap时全部)几乎不需要时间。内存中的实际分配可能在首次访问时延迟。
我对Linux内部内存分配的了解还不够。但我运行的脚本略有修改:我添加了第三个数组和每个数组的一些额外迭代操作。我已经考虑了Old Pro的评论,即没有考虑分配数组的时间。
结论:使用calloc比使用mmap进行分配花费更长的时间(mmap在分配内存时实际上不使用时间,在首次访问时可能会推迟),并且使用我的程序,最终使用mmap或calloc执行整个程序几乎没有区别。
无论如何,首先要注意的是,两个内存分配都发生在内存映射区域中,而不是堆中。为了验证这一点,我添加了一个快速的n’dirty暂停,这样你就可以检查进程的内存映射(/proc//maps)
现在,对于您的问题,最后分配的带有calloc的数组似乎真的在内存中分配了(没有延迟)。由于arr1和arr2现在的行为完全相同(第一次迭代较慢,后续迭代较快)。Arr3对于第一次迭代更快,因为内存分配得更早。当使用A宏时,从中受益的是arr1。我的猜测是内核已经为最后一个calloc预先分配了内存中的数组。为什么?我不知道。。。我也只用一个数组测试过它(所以我删除了所有出现的arr2和arr3),然后我对arr1的所有10次迭代都有相同的时间(大致)。
malloc和mmap的行为相同(下面没有显示结果),第一次迭代很慢,随后的迭代对所有3个数组都更快。
注意:所有结果在各种gcc优化标志(-O0到-O3)上都是一致的,所以看起来行为的根源并不是从某种gcc优化中得出的。
注2:使用GCC 4.6.3 在Ubuntu Precise Pangolin(内核3.2)上测试运行
#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: %.2fn", intermed);
printf("arr1 addr: %pnarr2 addr: %pnarr3 addr: %pn", 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: %.2fn", intermed);
}
printf("Time A (average): %.2fn", 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: %.2fn", intermed);
}
printf("Time B (average): %.2fn", 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: %.2fn", intermed);
}
printf("Time C (average): %.2fn", finalres/ITERATION);
gfinish = clock();
intermed = ((double)(gfinish - gstart))/CLOCKS_PER_SEC;
printf("Global Time: %.2fn", 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和
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