Open AlexiaChen opened 4 years ago
title: CPU缓存效果概要 date: 2018-02-8 17:16:53 tags:
大部分看过《CSAPP》这本经典的人，一般都能理解CPU缓存的大概机制，并能简单通过CPU的缓存机制来优化程序性能。
我这篇文章主要也是用一些代码样例来从一些不同的角度演示缓存的工作机制和实战中的代码优化。
比较以下两种不同的循环，哪种循环相对更快？(不用管是什么语言的代码)
int[] arr = new int[64 * 1024 * 1024]; // 128MB // Loop 1 for (int i = 0; i < arr.Length; i++) arr[i] *= 3; // Loop 2 for (int i = 0; i < arr.Length; i += 16) arr[i] *= 3;
如果不出意外，只要写过代码的人，直观上就可以判断出来，哪段更快，很明显，Loop 2中的循环的步长为16，每16个进行一次乘法运算，而Loop 1中是每一个元素都需要进行乘法运算。显然易见，Loop 2只做了Loop 1的工作量的6%（（64/16）/64）。
以上对代码的分析貌似是正确的，但是在现代处理器体系架构下从实际代码运行性能的分析，这两个循环花费的时间差不多（Loop 1是80ms，Loop 2是78ms）。显然Loop 2花费的时间不是Loop 1的6%。为什么？ 怎么与设想的不符呢？
原因是，两个循环都在内存访问上花费了大致相同的时间。运行时花费的代价反而是对数组的内存访问上，而不是循环体内的整型乘法运算。
来，下面我们来对以上例子代码进行一次更深入的探索，循环步长的值不再是1和16了，而把其改为一个变量，设为K：
for (int i = 0; i < arr.Length; i += K) arr[i] *= 3;
对K设不同的值，观察循环性能的变化曲线：
由上图看到了，K值在1到16之间，性能的变化不明显，耗费的时间都相差不大。
但是，在16以后，步长每增加2倍，运行耗费的时间几乎减半。为什么？
这种现象背后的原因是当今的现代CPU不会一个字节一个字节的访问内存。相反，CPU它一般会直接把内存中相邻的内存以64字节每块（chunk）组成的块状数据取到缓存中，这种就叫缓存行。（64字节算一个缓存行，缓存行可以一次取多个）。当你在读取一个特定的内存地址上的数据的时候，CPU就会把以当前内存地址开始以后的64字节读入到缓存中，所以访问在一个相同的缓存行中的任何数据，所花费的时间都差不多，而且代价小很多。
讲解到这里，你应该就能理解为什么当步长为1和16时，循环所花费的时间差不多了，因为步长1到16之间的数据都在一个相同的缓存行中，16*sizeof(int)=64字节。 正好是一个缓存行。你可以想象CPU已经把这个128MB的数组全部放到了缓存中，每64字节组成一个缓存行。所以步长为32的时候，每一次循环就访问一个新的缓存行，当步长为64的时候，循环以一次每4个缓存行来访问。
所以理解缓存行的机制，对于程序优化很重要。比如，数据对齐可能会决定一个CPU的操作会触碰到1个还是2个缓存行。如果数据没对齐，那么一次取数可能对于CPU要做2次操作。
当今计算机，一般都有二级缓存了，L1和L2，甚至还有L3缓存了。如果你想知道不同缓存和缓存行的大小，你还需要用工具和系统提供相关的API来细致分析。因为缓存行真不一定是64字节。windows上你可以通过CoreInfo这个工具来查看缓存详细信息，或者通过调用GetLogicalProcessorInformation这个Win32 API来实现查找缓存相关详情。
D:\MathxH\tools\Coreinfo>Coreinfo.exe -c -l Coreinfo v3.31 - Dump information on system CPU and memory topology Copyright (C) 2008-2014 Mark Russinovich Sysinternals - www.sysinternals.com Logical to Physical Processor Map: **-- Physical Processor 0 (Hyperthreaded) --** Physical Processor 1 (Hyperthreaded) Logical Processor to Cache Map: **-- Data Cache 0, Level 1, 32 KB, Assoc 8, LineSize 64 **-- Instruction Cache 0, Level 1, 32 KB, Assoc 8, LineSize 64 **-- Unified Cache 0, Level 2, 256 KB, Assoc 8, LineSize 64 **** Unified Cache 1, Level 3, 3 MB, Assoc 12, LineSize 64 --** Data Cache 1, Level 1, 32 KB, Assoc 8, LineSize 64 --** Instruction Cache 1, Level 1, 32 KB, Assoc 8, LineSize 64 --** Unified Cache 2, Level 2, 256 KB, Assoc 8, LineSize 64 在我这台ThinkPad破本上用windows相关命令行查看到的缓存信息是，有三级缓存，并且缓存行的大小都是64字节。32KB的L1数据缓存，32KB的L1指令缓存还有3MB的L3缓存等。 好我们再来分析一下下面的代码程序: ``` java int steps = 64 * 1024 * 1024; // 64MB int lengthMod = arr.Length - 1; for (int i = 0; i < steps; i++) { arr[(i * 16) & lengthMod]++; // (x & lengthMod) 相当于 (x % arr.Length) }
以下是以上代码片段随着数组大小增大的性能曲线图:
因为L1是32KB, L2是256KB，L3是3MB。所以你可以看到大约在数组大小超过32KB，256KB，3MB或4MB以后会有明显的性能下降，也就是耗费的时间越多。
现在，我们来看看一些不一样的地方。以下两个循环，谁会更快？
int steps = 256 * 1024 * 1024; //256MB int [] a = new int[2]; //Loop 1 for(int i = 0; i < steps; ++i) { a[0]++; // op1 a[0]++; // op2 } // Loop 2 for(int i = 0; i < steps; ++i) { a[0]++; // op1 a[1]++; // op2 }
很多人一眼看上去貌似是一样快，但是我几乎在所有的机器上测试过，几乎都是Loop 2快过Loop 1。为什么？ 这就需要认真分析两个循环体里面的操作依赖性了。
在Loop 1的循环体中op1和op2是有依赖关系的，op2的操作执行必须等到op1完成才能开始。而Loop 2的循环体中，op1和op2没有依赖关系，理论上可以同时完成，这个就为处理器提供了优化的可行性。
现代处理器对Loop 2这种情况有多种的并发处理方式，他可以在L1缓存中同时访问a[0]和a[1]，并同时执行op1和op2这两个算数运算。但是在Loop 1中，处理器就没有机会利用指令级并行了。
在缓存的设计中，有一个关键的决定就是是否要把主内存的每个chunk都存储到每个缓存中，或者只是选择多个缓存的其中几个。
在现代处理器体系中，就有如下几种方式来把多个缓存映射到主内存的块中：
直接映射缓存，每个内存块只可能被映射到其中一个特定的缓存槽中，是一对一的关系。这种算法就简单的实现方式就是，把主内存的块的index映射到缓存中(chunk index % 缓存槽数)。块下标对缓存槽数取模运算。两个内存块不可能同时都存放在一个相同的缓存槽中。
N路相联缓存（组相联缓存），每一个主内存上的块能被存储到N个特定缓存槽中的其中一个槽中。例如，在16路相联缓存中，每个内存块被存储到特定的16个不同的缓存槽中（16个槽的其中一个）。通常的实现是块的index的最低序列位来表示16个不同的槽
全相联缓存， 每个内存块可能会被存储到任何一个缓存槽中。类似于操作Hash表这样的数据结构。
直接映射缓存容易造成冲突，因为可能会有多个内存块都被映射到相同的内存槽中了，这样会造成缓存频繁的抖动（内存块不停地换入换出，命中率下降）。另一方面，对于全相联缓存比较复杂，硬件实现成本也高。所以N路相联缓存是现代处理器缓存典型的解决方案，它在实现成本和友好的命中率上做了很好的折中和取舍。
例如，在我的电脑上，3MB的L3缓存就是12路相联，32KB的L1缓存和256KB的L2缓存都是8路相联。对于L3缓存，所有的64字节的内存块都会基于自身的index被映射到L3缓存中的特定的12个不同的槽中。
因为L3缓存有4096（2^12 = 4096）个槽，那么每个集合就有12个槽相联,那么就有341个集合。2^8 约等于 341 。 所以chunk index的低8位就决定了这个块存放在那个集合中。
显然，缓存的相联方案也会影响性能，但是这里就不再深入，这方面知识也不是本篇文章的重点。还有一个原因就是我目前暂时不能给大家讲解清楚。
在多核机器上，缓存就有遭遇到另一个问题-----并发一致性。不同的核一般来说都有属于自己的缓存。我的机器上L1一般都有属于自己的核，L2是多个核共享的缓存。在现代多核架构中缓存一般有多个层级，速度越快越“接近”核的缓存约属于单个核所有。
当一个核修改了它自身缓存中的一个值的时候，那么其他处理器的核就不能再使用原来的值了，这就导致了缓存失效。
为了演示这个问题，考虑下面的代码样例：
private static int[] s_counter = new int[1024]; private void UpdateCounter(int position) { for (int j = 0; j < 100000000; j++) { s_counter[position] = s_counter[position] + 3; } }
以上这段代码如果在多核机器上，用四个不同的线程分别执行UpdateCounter(0),UpdateCounter(1),UpdateCounter(2),UpdateCounter(3)等到四个线程的结束时所花费的时间记为T1。
如果你用四个线程分别执行UpdateCounter(16),UpdateCounter(32),UpdateCounter(48),UpdateCounter(64)等到四个线程结束时所花费的时间记为T2。
这两种不同的方式比较性能，T2比T1少！
为什么？ 方法一中的0，1，2，3所取的数据几乎都在一个缓存行中，其中一个核每更新计数一次，那么整个缓存行就失效了，那么其他核取数据就cache miss了。如果这样，需要关闭缓存机制。方法二中，是因为不同线程所取的数据在不同的缓存行中，这样就提高了并发量
好吧，即使你完全了解之前所讲述的缓存机制，但是在实战中，还不一定照葫芦画瓢就能轻而易举通过优化程序提高性能，一些个别的硬件体系在有些时候还是会使你震惊，不同处理器架构的优化手段也不尽相同。
比如，在有些处理器架构中，L1缓存可以存在并行（如果从不同卡槽来访问），如果是来自相同卡槽的访问那么L1缓存就可能是顺序访问了。有时候，处理器作出的优化，也能让你吃惊，你的优化是多余的。 :)
还是不喜欢通过缓存特性来优化程序，虽然很多高性能的网络框架用到了这些缓存的原理，但是我还是喜欢算法级别的优化。原因就是Example 7，由于硬件的复杂性，很难写出跨平台的缓存利用友好的高性能程序，也很难根据硬件特性来预测程序性能。
title: CPU缓存效果概要 date: 2018-02-8 17:16:53 tags:
性能优化
前言
大部分看过《CSAPP》这本经典的人，一般都能理解CPU缓存的大概机制，并能简单通过CPU的缓存机制来优化程序性能。
我这篇文章主要也是用一些代码样例来从一些不同的角度演示缓存的工作机制和实战中的代码优化。
Example 1：内存访问和性能
比较以下两种不同的循环，哪种循环相对更快？(不用管是什么语言的代码)
如果不出意外，只要写过代码的人，直观上就可以判断出来，哪段更快，很明显，Loop 2中的循环的步长为16，每16个进行一次乘法运算，而Loop 1中是每一个元素都需要进行乘法运算。显然易见，Loop 2只做了Loop 1的工作量的6%（（64/16）/64）。
以上对代码的分析貌似是正确的，但是在现代处理器体系架构下从实际代码运行性能的分析，这两个循环花费的时间差不多（Loop 1是80ms，Loop 2是78ms）。显然Loop 2花费的时间不是Loop 1的6%。为什么？ 怎么与设想的不符呢？
原因是，两个循环都在内存访问上花费了大致相同的时间。运行时花费的代价反而是对数组的内存访问上，而不是循环体内的整型乘法运算。
Example 2: 缓存行（Cache Line）的影响
来，下面我们来对以上例子代码进行一次更深入的探索，循环步长的值不再是1和16了，而把其改为一个变量，设为K：
对K设不同的值，观察循环性能的变化曲线：
由上图看到了，K值在1到16之间，性能的变化不明显，耗费的时间都相差不大。
但是，在16以后，步长每增加2倍，运行耗费的时间几乎减半。为什么？
这种现象背后的原因是当今的现代CPU不会一个字节一个字节的访问内存。相反，CPU它一般会直接把内存中相邻的内存以64字节每块（chunk）组成的块状数据取到缓存中，这种就叫缓存行。（64字节算一个缓存行，缓存行可以一次取多个）。当你在读取一个特定的内存地址上的数据的时候，CPU就会把以当前内存地址开始以后的64字节读入到缓存中，所以访问在一个相同的缓存行中的任何数据，所花费的时间都差不多，而且代价小很多。
讲解到这里，你应该就能理解为什么当步长为1和16时，循环所花费的时间差不多了，因为步长1到16之间的数据都在一个相同的缓存行中，16*sizeof(int)=64字节。 正好是一个缓存行。你可以想象CPU已经把这个128MB的数组全部放到了缓存中，每64字节组成一个缓存行。所以步长为32的时候，每一次循环就访问一个新的缓存行，当步长为64的时候，循环以一次每4个缓存行来访问。
所以理解缓存行的机制，对于程序优化很重要。比如，数据对齐可能会决定一个CPU的操作会触碰到1个还是2个缓存行。如果数据没对齐，那么一次取数可能对于CPU要做2次操作。
Example 3: L1 和 L2缓存的大小
当今计算机，一般都有二级缓存了，L1和L2，甚至还有L3缓存了。如果你想知道不同缓存和缓存行的大小，你还需要用工具和系统提供相关的API来细致分析。因为缓存行真不一定是64字节。windows上你可以通过CoreInfo这个工具来查看缓存详细信息，或者通过调用GetLogicalProcessorInformation这个Win32 API来实现查找缓存相关详情。
以下是以上代码片段随着数组大小增大的性能曲线图:
因为L1是32KB, L2是256KB，L3是3MB。所以你可以看到大约在数组大小超过32KB，256KB，3MB或4MB以后会有明显的性能下降，也就是耗费的时间越多。
Example 4 指令级并行
现在，我们来看看一些不一样的地方。以下两个循环，谁会更快？
很多人一眼看上去貌似是一样快，但是我几乎在所有的机器上测试过，几乎都是Loop 2快过Loop 1。为什么？ 这就需要认真分析两个循环体里面的操作依赖性了。
在Loop 1的循环体中op1和op2是有依赖关系的，op2的操作执行必须等到op1完成才能开始。而Loop 2的循环体中，op1和op2没有依赖关系，理论上可以同时完成，这个就为处理器提供了优化的可行性。
现代处理器对Loop 2这种情况有多种的并发处理方式，他可以在L1缓存中同时访问a[0]和a[1]，并同时执行op1和op2这两个算数运算。但是在Loop 1中，处理器就没有机会利用指令级并行了。
Example 5 缓存相联
在缓存的设计中，有一个关键的决定就是是否要把主内存的每个chunk都存储到每个缓存中，或者只是选择多个缓存的其中几个。
在现代处理器体系中，就有如下几种方式来把多个缓存映射到主内存的块中：
直接映射缓存，每个内存块只可能被映射到其中一个特定的缓存槽中，是一对一的关系。这种算法就简单的实现方式就是，把主内存的块的index映射到缓存中(chunk index % 缓存槽数)。块下标对缓存槽数取模运算。两个内存块不可能同时都存放在一个相同的缓存槽中。
N路相联缓存（组相联缓存），每一个主内存上的块能被存储到N个特定缓存槽中的其中一个槽中。例如，在16路相联缓存中，每个内存块被存储到特定的16个不同的缓存槽中（16个槽的其中一个）。通常的实现是块的index的最低序列位来表示16个不同的槽
全相联缓存， 每个内存块可能会被存储到任何一个缓存槽中。类似于操作Hash表这样的数据结构。
直接映射缓存容易造成冲突，因为可能会有多个内存块都被映射到相同的内存槽中了，这样会造成缓存频繁的抖动（内存块不停地换入换出，命中率下降）。另一方面，对于全相联缓存比较复杂，硬件实现成本也高。所以N路相联缓存是现代处理器缓存典型的解决方案，它在实现成本和友好的命中率上做了很好的折中和取舍。
例如，在我的电脑上，3MB的L3缓存就是12路相联，32KB的L1缓存和256KB的L2缓存都是8路相联。对于L3缓存，所有的64字节的内存块都会基于自身的index被映射到L3缓存中的特定的12个不同的槽中。
因为L3缓存有4096（2^12 = 4096）个槽，那么每个集合就有12个槽相联,那么就有341个集合。2^8 约等于 341 。 所以chunk index的低8位就决定了这个块存放在那个集合中。
显然，缓存的相联方案也会影响性能，但是这里就不再深入，这方面知识也不是本篇文章的重点。还有一个原因就是我目前暂时不能给大家讲解清楚。
Example 6 缓存行伪共享
在多核机器上，缓存就有遭遇到另一个问题-----并发一致性。不同的核一般来说都有属于自己的缓存。我的机器上L1一般都有属于自己的核，L2是多个核共享的缓存。在现代多核架构中缓存一般有多个层级，速度越快越“接近”核的缓存约属于单个核所有。
当一个核修改了它自身缓存中的一个值的时候，那么其他处理器的核就不能再使用原来的值了，这就导致了缓存失效。
为了演示这个问题，考虑下面的代码样例：
以上这段代码如果在多核机器上，用四个不同的线程分别执行UpdateCounter(0),UpdateCounter(1),UpdateCounter(2),UpdateCounter(3)等到四个线程的结束时所花费的时间记为T1。
如果你用四个线程分别执行UpdateCounter(16),UpdateCounter(32),UpdateCounter(48),UpdateCounter(64)等到四个线程结束时所花费的时间记为T2。
这两种不同的方式比较性能，T2比T1少！
为什么？ 方法一中的0，1，2，3所取的数据几乎都在一个缓存行中，其中一个核每更新计数一次，那么整个缓存行就失效了，那么其他核取数据就cache miss了。如果这样，需要关闭缓存机制。方法二中，是因为不同线程所取的数据在不同的缓存行中，这样就提高了并发量
Example 7 硬件复杂性
好吧，即使你完全了解之前所讲述的缓存机制，但是在实战中，还不一定照葫芦画瓢就能轻而易举通过优化程序提高性能，一些个别的硬件体系在有些时候还是会使你震惊，不同处理器架构的优化手段也不尽相同。
比如，在有些处理器架构中，L1缓存可以存在并行（如果从不同卡槽来访问），如果是来自相同卡槽的访问那么L1缓存就可能是顺序访问了。有时候，处理器作出的优化，也能让你吃惊，你的优化是多余的。 :)
总结
还是不喜欢通过缓存特性来优化程序，虽然很多高性能的网络框架用到了这些缓存的原理，但是我还是喜欢算法级别的优化。原因就是Example 7，由于硬件的复杂性，很难写出跨平台的缓存利用友好的高性能程序，也很难根据硬件特性来预测程序性能。