八年前，有人发现把数组排个序能让程序快6倍。原因不是算法优化，而是CPU猜错了分支走向。这个发现至今仍在Stack Overflow挂着，但大多数人只记住了"分支预测"这个词，没搞懂真正的问题在哪。
现代CPU的流水线越来越深。Intel Skylake有14级，苹果Firestorm更宽但更浅。指令在前端解码、重命名、找操作数、执行、退休，一环扣一环。问题是：遇到条件分支时，CPU还不知道往哪走，流水线不能空等。分支预测器的工作，就是在真相出现之前，先放一个"可能正确"的答案。
猜对了，一切顺利。猜错了，前面做的全作废。Skylake的预测错误惩罚大约是15到20个周期，苹果M1约13个周期。5GHz下，15周期就是3纳秒。一次无所谓，一秒猜错十亿次就是灾难。
当前最先进的预测架构叫TAGE，由法国INRIA的André Seznec提出。它维护多张带标签的表，分别用4、8、16、64等数量的历史分支来索引。短循环用短历史表，长而不规则的模式用深历史表。在SPEC 2000整数测试集、4KB硬件预算下，基础版TAGE的误预测率是4.6%，比gshare基线提升26%。现在的量产芯片预算更大，有逆向工程论文发现苹果Firestorm和高通Oryon的预测器各有六张模式历史表。
但"95%准确率"这个数字是 workload-averaged——工作负载平均后的 headline。真正的问题是：哪5%错了？
可预测的分支不花钱。跑一万次的循环、按单字节跳转的跳转表、处理相似请求的长跑Web服务热点路径——这些几乎不会预测失败。成本堆在不可预测的地方：动态分派的间接调用（虚方法、函数指针表，每个解释器和JIT语言都躲不开）、链表遍历的指针追逐（下一个分支依赖还没完成的内存加载）、输入数据本身无规律的依赖比较。
那篇Stack Overflow神帖的6倍加速，就是因为排序后分支走向变得有规律，预测器能猜对；乱序数组让预测器持续踩空，流水线反复清空重填。
所以评价现代分支预测器，准确率数字本身意义有限。关键问题是：错误发生在哪？猜错时付出的代价多大？猜对时又泄露了什么信息？
热门跟贴