分支历史记录表深度
现代CPU一般都有分支预测功能，以提高指令预取的效率。而分支历史记录表是获得高的分支预测准确率的有效手段，所以现代CPU一般都有分支历史记录表，这在x86体系结构上叫做BTB：Branch Target Buffer。而不同的CPU的BTB深度显然是不同的。Intel宣称Pentium可以正确地预测对奇数和偶数进行不同处理的循环，表示Pentium的BTB深度至少为2。Intel的文档还说Pentium Pro系列的BTB深度为5，P4可以正确预测16次以内的循环的执行情况（深度为16？？）。AMD这方面的资料要少一些，但是一定深度的BTB肯定是有的。对于这些情况，我们必须用测试来说话。在进行检测之前我们要说明一下，BTB其实可以认为是指令缓存的一部分，所以在这里进行检测并没有完全偏离主体。
BTB深度的检测原理其实也不复杂。我们知道，分支预测成功的开销是很小的，一般是1个周期或者0个周期。而预测失败的开销非常大，AMD的文档说至少是9，Intel也反复强调降低分支预测失败率的重要性。所以，我们主要制造一点点的分支预测失败，程序性能就会有显著的变化。
根据BTB的原理，在最佳情况下，只要循环内部的分支指令的“转移”和“不转移”发生的模式的“波长”不超过BTB的深度，预测准确率都会是100％（当然实际情况会稍差一些），而当其“波长”超过BTB深度的时候，预测准确率就会下降。所以，在测试中，我们“制造”一个指定“波长”的分支，然后调整其“波长”为1、2、3......，分别测试其性能，在性能发生突变的时候就是达到BTB深度的时候。
测试之前还有一些问题，首先是分支“转移”和“不转移”的开销是不同的。在测试中我们采取2个措施处理这个问题：（1）2个执行路径执行的指令完全相同，这其实很容易做到，只要把转移的目的地址设成分支指令的下一条指令就可以了；（2）先测试一次得到结果，然后把分支“转移”和“不转移”条件完全反转后再测试一次（反相、相移180度），把2次测试结果都输出。
第二个问题是产生什么样的分支模式，也就是在一个周期中几次转移、几次不转移。我们采用最简单的方案：一个周期仅有1次转移和一个周期仅有1次不转移（反转的情况）2种。
第三个问题是如何产生这些分支模式。我们采用一个数组来控制分支的发生与不发生。设我们想产生的“波长”为n，则我们在数组的前n-1个单元中放1，在第n个单元放0，然后用一条简单的比较指令就可以控制分支的发生与不发生。这样的控制策略可以生成任意复杂的分支模式，而不仅仅限于上面的模式。这里会衍生一个问题，就是数组元素仅有n个，而我们的循环要执行多次，所以在循环n次后要调整数组指针，这样会产生一个新的分支指令，而且这个分支指令的2个分支执行的指令是不同的（一个调整指针，一个不），该分支还与我们要测试的分支“波长”相同（叫做“共振”，//haha）！！这与我们的测试原则不同，所以必须把这个分支消除调。事实上x86指令集有2个辅助指令可以让这个分支彻底消失。这2个指令是CMOVcc和SETcc（其中的cc是条件代码）。通过这2条指令都可以实现上面的分支消除功能，不过CMOVcc可以少用很多指令，这会使要测试的分支指令在测试中占的比例高一些，有利于反映出差异。但是COMVcc指令仅在P6及以后的CPU上才有，而SETcc至少从486就有了。所以我们把2个方案都实现了，在测试前检测CPU是否支持CMOVcc，如果支持则用CMOVcc方案，否则用SETcc方案。
下面是CMOVcc方案的核心指令：
test ebx, [esi+edx]
jnz short NextPos
NextPos:
add edx, 4
mov eax, 12345678h ; dummy fill
cmovns edx, edi
其中倒数第二条指令是为了使要测试的分支指令和后面的循环附加分支指令远一些设置的，不影响执行结果。我们把控制分支的（数组首地址＋n×4）放在ESI，在进入循环前EDX清0，EDI放入－n×4，EBX设为1。根据这些初始条件，可以很容易理解上面的代码的含义。注意在这里第一次分支将使用数组的第（n+1）个单元，所以初始化时也要把第（n+1）个单元初始化成与第1个单元相同的值。另外，这个控制方案的第一个周期要长一个单位，这也不会有大的影响，我们要执行很多次，要经过成千上万个周期，一个周期的误差不会干扰测试。
下面是SETcc方案的核心指令：
test ebx, [esi+edx]
jnz short NextPosCC
NextPosCC:
xor eax, eax
add edx, 4
sets al
sub eax, 1
and eax, edi
add edx, eax
初始条件与上面相同，也很容易理解。这个方案的第一个周期是正确的，不会有上面的问题。
下面是测试结果：
最左面一列是波长。测量值表示执行一次核心指令系列需要的周期数。在测试中，我们没有进行循环展开，因为循环展开实现起来有困难。这样导致测试循环非常小，对起始地址很敏感。所以我们遍历0～15的所有起始偏移，把性能最好和最差的都列出来。表中后缀Min表示最好性能，Max表示最差性能。其中N表示一个周期中不转移的情况较多（Not taken），而Y表示发生转移的情况较多（taken）。对波长为1的来说，N表示永远不转移，Y表示永远转移。Penalty是根据缓存理论的计算公式得出的分支预测失败附加开销：
AvgTime＝HitTime＋MissRate×Penalty ===> Penalty = （AvgTime－HitTime）/MissRate
其中，HitTime取为分支永不转移时的测量值，AvgTime取相应行的N/Min的值。根据前面的分析和我们产生的分支模式，当波长n超过BTB深度时，MissRate应该正比于1/n，我们在计算中取为1/n。在波长不超过BTB深度时，MissRate无法估计，所以就不列出Penalty值。可以看出，计算出的Penalty基本稳定，说明还是符合理论的，而且14左右是比较合理的值。
为了把结果看得更明显，我们把测量值画成曲线图如下：
明显看出，在波长为6处有一个性能突变点，说明PIII的BTB深度为5，与Intel的说明一致。图中还可以看出，分支发生转移和不发生转移的开销确实有区别，一般情况下分支不发生转移性能会好一些。但在波长为2时性能很好（与永不转移相同），说明Intel对这种情况作了优化。表中数据还能说明其它一些问题，这里不想再分析了。
至于P4和Athlon的反映如何，由于我没有相应平台，就不得而知了。谁有这些机器可以自己测来看看。
