面对处理器缓存,一些旧有的性能优化技巧已然失效.doc

请注意，本文不是讲解处理器缓存，如果你对cpu cache这个概念不清楚，请先Google一下。另外，本文主要针对像 C，C+ 这种产生机器码的语言的，对于像 Java，.Net 这样的字节码语言，这里所说的可能无效，至少我没研究过。首先说说我所说的这些旧有的优化技巧从哪里来的。原因很简单，如果你像我一样，多年只用 J2ME，或者 Flash 这样的技术开发，你是不太可能会关心处理器缓存的，而是用一些其它的性能技巧，这些技巧遇到处理器缓存问题，就失效了。再如果你的CPU，汇编，优化知识像我一样仍停留在 80386 时代，你我掌握的优化技巧断然也是过时的。失效技巧一，使用预先计算好的变量或者查找表现在来怎么用查找表来计算一个32位整数里位为1的个数。Cpp代码1. staticconstunsignedcharBitsSetTable256256=2. 3. /预先计算好的256个8位数的1的个数4. ;5. 6. intcalculateBitsCount(unsignedintn)7. 8. unsignedchar*p=(unsignedchar*)&n;9. returnBitsSetTable256p0+10. BitsSetTable256p1+11. BitsSetTable256p2+12. BitsSetTable256p3;13. 很酷，是吧，只用了四次加法运算，我们可以想当然地认为这个算法比那些充满乘除法甚至循环的算法快。但当有了CPU的数据缓存，情况不一样了。当 calculateBitsCount 第一次取 BitsSetTable256 数据，很有可能导致数据缓存清空重新加载 BitsSetTable256 位置的内存，会导致浪费上百指令周期，而这上百指令周期，足够用普通方法计算位数了。比如下面这个算法，来自/seander/bithacks.htmlCpp代码1. unsignedintv;/countthenumberofbitssetinv2. unsignedintc;/caccumulatesthetotalbitssetinv3. for(c=0;v;c+)4. 5. v&=v-1;/cleartheleastsignificantbitset6. 这个算法看似比上面查找表算法多了很多指令，还有循环，但要记住指令成本比数据成本低非常非常多（指令数量很多超出指令缓存的除外），值票价！确实值票价，因为我用这个算法替代查找表以后，确实快了。失效技巧二，用局部变量来缓存所操作对象的成员变量请注意，这个技巧在大多数情况下是有效的，这里只是说明某些情况下会失效。比如有这样一个函数，Cpp代码1. voidfunc(SomeObject*obj)2. 3. inti,k,p;4. intcount=obj-getCount();5. 6. for(i=0;i100;+i)7. for(intk=0;k100;+k)8. for(intp=0;pcount;+p)9. /处理obj的数据10. 11. 12. 13. 假设 getCount 只是取一个数值。这看起来很好，很完美，但仔细看却有一个问题。假如所有局部变量都能被放在寄存器，没有问题。但如果 count 不能被放到寄存器里呢？那么每次循环 count 都要从堆栈内存里读取，但同时又要处理 obj 的数据，这两部分极有可能不在一个数据缓存里，这就会导致频繁的数据缓存交换，慢！如果抛弃 count，而把最内层循环改成Cpp代码1. for(intp=0;pgetCount();+p)2. /处理obj的数据3. 因为读取的数据都在 obj 范围内，如果都在数据缓存范围里，那就会相当快。失效技巧三，在一个循环里干所有事我们可能老觉得循环是慢的，因为还要跳转，所以我们宁愿在一个循环里把所有事都做了。Cpp代码1. ObjectA*objA;2. ObjectB*objB;3. for(inti=0;i100;+i)4. /对objA做点事5. /对objA做点别的事6. /对objB做点事7. 这有两个问题：1，一旦循环体里的代码长度超过指令缓存，那么每次循环都要导致指令缓存动荡，无论 CPU 有几级缓存，L1 被清空重新装载，总归比直接命中 L1 缓存慢。2，更麻烦的事，循环里在两个数据块操作，除非两个对象恰好分配的很近，否则必然导致数据缓存的动荡，慢。如果把循环切分，Cpp代码1. ObjectA*objA;2. ObjectB*objB;3. for(inti=0;i100;+i)4. /对objA做点事5. 6. for(inti=0;i100;+i)7. /对objA做点别的事8. 9. for(inti=0;i100;+i)10. /对objB做点事11. 则指令缓存和数据缓存都会觉得很高兴，自