如何在C和Java中产生cpucaching效果?

在Ulrich Drepper的论文中,每个程序员应该知道关于内存的知识 ,第三部分:CPU Caches,他显示了一个图表,显示了“工作集”大小和每个操作(在本例中为连续读取)消耗的CPU周期之间的关系。 图中有两个跳转指示L1caching和L2caching的大小。 我写了自己的程序来重现c中的效果。 它只是从头到尾依次读取一个int []数组,并且我尝试了不同的数组大小(从1KB到1MB)。 我将数据绘制成graphics,没有跳跃,graphics是一条直线。

我的问题是:

  1. 我的方法有问题吗? 产生cpucaching效果的正确方法是什么(查看跳转)。
  2. 我在想,如果是连续读取,那么它应该像这样操作:当读取第一个元素时,它是一个caching未命中,并且在caching行大小(64K)内,会有命中。 在预取的帮助下,读取下一个caching行的延迟将被隐藏。 即使工作集大小超过L1高速caching大小,它也会连续读取数据到L1高速caching中,它将驱逐最近最less使用的数据,并继续预取。 因此,大部分caching未命中都将被隐藏,从L2获取数据所消耗的时间将被隐藏在阅读活动之后,这意味着它们同时运行。 assosiativity(在我的情况下是8)将隐藏从L2读取数据的延迟。 所以,我的程序现象应该是正确的,我错过了什么?
  3. 是否有可能在java中获得相同的效果?

顺便说一下,我在linux中这样做。


编辑1

感谢Stephen C的build议,这里有一些额外的信息:这是我的代码:

int *arrayInt; void initInt(long len) { int i; arrayInt = (int *)malloc(len * sizeof(int)); memset(arrayInt, 0, len * sizeof(int)); } long sreadInt(long len) { int sum = 0; struct timespec tsStart, tsEnd; initInt(len); clock_gettime(CLOCK_REALTIME, &tsStart); for(i = 0; i < len; i++) { sum += arrayInt[i]; } clock_gettime(CLOCK_REALTIME, &tsEnd); free(arrayInt); return (tsEnd.tv_nsec - tsStart.tv_nsec) / len; } 

在main()函数中,我已经尝试了从1KB到100MB的数组大小,仍然是相同的,每个元素的平均耗时是2纳秒。 我想时间是L1d的访问时间。

我的caching大小:

L1d == 32k

L2 == 256k

L3 == 6144k


编辑2

我已经改变了我的代码来使用链表。

 // element type struct l { struct l *n; long int pad[NPAD]; // the NPAD could be changed, in my case I set it to 1 }; struct l *array; long globalSum; // for init the array void init(long len) { long i, j; struct l *ptr; array = (struct l*)malloc(sizeof(struct l)); ptr = array; for(j = 0; j < NPAD; j++) { ptr->pad[j] = j; } ptr->n = NULL; for(i = 1; i < len; i++) { ptr->n = (struct l*)malloc(sizeof(struct l)); ptr = ptr->n; for(j = 0; j < NPAD; j++) { ptr->pad[j] = i + j; } ptr->n = NULL; } } // for free the array when operation is done void release() { struct l *ptr = array; struct l *tmp = NULL; while(ptr) { tmp = ptr; ptr = ptr->n; free(tmp); } } double sread(long len) { int i; long sum = 0; struct l *ptr; struct timespec tsStart, tsEnd; init(len); ptr = array; clock_gettime(CLOCK_REALTIME, &tsStart); while(ptr) { for(i = 0; i < NPAD; i++) { sum += ptr->pad[i]; } ptr = ptr->n; } clock_gettime(CLOCK_REALTIME, &tsEnd); release(); globalSum += sum; return (double)(tsEnd.tv_nsec - tsStart.tv_nsec) / (double)len; } 

最后,我将打印出globalSum以避免编译器优化。 正如你所看到的,它仍然是一个顺序读取,我甚至已经尝试了500MB的数组大小,每个元素的平均时间大约是4纳秒(也许是因为它必须访问数据'pad'和指针' n',两次访问),与1KB的数组大小相同。 所以,我认为这是因为像prefetch这样的caching优化很好地隐藏了延迟,对吗? 我会尝试随机访问,并把结果放在后面。


编辑3

我试着随机访问链表,这是结果: 随机访问一个链表

第一条红线是我的L1caching大小,第二条是L2。 所以我们可以在那里看到一些小跳 有些时候,延迟仍然很好。

Solutions Collecting From Web of "如何在C和Java中产生cpucaching效果?"

这个答案不是一个答案,而是更多的一套笔记。

首先,CPU倾向于在高速缓存行上操作,而不是在单个字节/字/双字上操作。 这意味着,如果顺序读取/写入整数数组,则第一次访问缓存行可能会导致缓存未命中,但后续访问同一缓存行中的不同整数将不会。 对于64字节的高速缓存行和4字节的整数,这意味着每16次访问只会发生一次高速缓存未命中; 这将稀释结果。

其次,CPU有一个“硬件预取器”。 如果它检测到高速缓存行正在顺序读取,则硬件预取器将自动预取预期将要使用的高速缓存行(试图在需要之前将它们提取到高速缓存中)。

第三,CPU做其他事情(“乱序执行”)来隐藏获取成本。 您可以测量的时间差(在缓存命中和缓存未命中之间)是CPU无法隐藏的时间,而不是提取的总成本。

这三件事合起来意味着; 为了顺序读取一个整数数组,当你从前一个缓存行读取16个数据时,CPU可能会预取下一个缓存行; 任何缓存遗漏成本都不会显着,可能完全隐藏。 为了防止这个; 你想要“随机”访问每个缓存行一次,以最大化“工作集适配在缓存/秒”和“工作集不适合缓存/秒”之间测量的性能差异。

最后,还有其他一些可能影响测量的因素。 例如,对于使用分页的操作系统(例如Linux和几乎所有其他现代操作系统),首先有一整层的缓存(TLB / Translation Look-aside Buffers),一旦工作集超出一定的大小,TLB就会丢失; 这应该作为图中的第四个“步骤”可见。 还有内核的干扰(IRQ,页面错误,任务切换,多个CPU等)。 这在图中可能是随机的静态/错误可见的(除非经常重复测试并丢弃异常值)。 高速缓存设计(高速缓存关联性)还有一些人为因素可能会以取决于内核分配的物理地址的方式降低高速缓存的有效性; 这可能被视为图中“步骤”转移到不同的地方。

我的方法有问题吗?

可能,但没有看到你的实际代码,无法回答。

  • 你对你的代码所做的描述并不是说你是否正在读取数组一次或多次。

  • 阵列可能不够大,取决于您的硬件。 (不要一些现代的芯片有一个几兆字节的三级缓存?)

  • 特别是在Java的情况下,你必须做很多事情才能实现一个有意义的微基准。


在C情况下:

  • 您可以尝试调整C编译器的优化开关。

  • 由于您的代码是串行访问数组,因此编译器可能会对指令进行排序,以使CPU保持运行状态,或者CPU可能乐观地预取或执行大量读取。 你可以尝试以一种难以预测的顺序读取数组元素。

  • 甚至有可能编译器已经完全优化了循环,因为循环计算的结果不用于任何事情。

(根据这个问答 – 从内存中取一个字需要多少时间 ,从L2缓存中取回的时间约为7纳秒,而从主内存中取回的时间约为100纳秒,但是你得到了约2纳秒。必须继续下去,使其运行速度与您观察的一样快)。

用gcc-4.7编译gcc -std=c99 -O2 -S -D_GNU_SOURCE -fverbose-asm tcache.c你可以看到编译器已经足够优化去除for循环(因为sum没有被使用)。

我必须改善你的源代码; 一些#include -s缺少, i没有在第二个函数中声明,所以你的例子甚至不会像现在这样编译。

sum作为一个全局变量,或者以某种方式将它传递给调用者(也许使用全局int globalsum;并且在循环之后放置globalsum=sum; )。

我不确定你是否正确使用memset清除数组。 我可以想象一个足够聪明的编译器理解你正在总结所有的零。

最后,您的代码具有非常规则的行为,并具有良好的局部性:曾经有一段时间,缓存未命中,整个缓存行被加载,数据足够用于多次迭代。 一些聪明的优化(如-O3或更好)可能会产生良好的prefetch指令。 这对于高速缓存来说是最佳的,因为对于32字的L1高速缓存行,高速缓存未命中每32个循环发生一次,所以分配很好。

制作链接的数据列表会使缓存行为变得更糟。 相反,在一些真正的程序中,在几个精心挑选的地方仔细添加__builtin_prefetch可能会使性能提高10%以上(但增加太多会降低性能)。

在现实生活中,处理器花费大部分时间来等待某个缓存(这很难测量;这个等待是CPU时间,而不是空闲时间)。 请记住,在L3缓存未命中期间,从RAM模块加载数据所需的时间是执行数百条机器指令所需的时间!

我不能肯定地说1和2,但用Java成功运行这样的测试会更具挑战性。 特别是,我可能会担心托管语言功能(如自动垃圾回收)可能会在您的测试过程中发生并抛弃您的结果。

从图3.26可以看出,Intel Core 2在读取时几乎没有跳跃(图上方的红线)。 正在写入/复制跳转清晰可见的地方。 最好做一个写测试。