这几天一直在收集一些关于JavaScript函数式编程的性能测试用例，以及内存使用分析。一年前（2017年1月）写过一篇文章《JavaScript 函数式编程存在性能问题么？》，里面对数组高阶函数和for-loop进行了benchmark，结果是map`reduce`这些函数比nativefor-loop有大约20倍的性能差距。不过一年半之后，V8引擎也有了很大的提升，包括对数组高阶函数的性能提升，取得了很好的效果。可以看出，两者相当接近。但是我在jsperf中发现了一个很有意思的测试用例：https://jsperf.com/sorted-loop/2//对整型数组数据进行累加求和functionperf(data){varsum=0;for(vari=0;i=128){sum+=data[i];}}returnsum;}两个测试用例都使用这个函数，唯一的区别是Arrays（参数）：一个是有序的，一个是无序的。结果是两者之间有4倍的性能差异。我们都知道，如果我们搜索有序数组，我们可以使用二分查找算法获得更好的性能。但是二分查找和普通查找是两种完全不同的算法，性能上有差距也是正常的。但是这个测试用例不一样，两者的算法是完全一样的，因为都是同一个函数。两者生成的二进制机器码也是一样的。为什么会有这么大的性能差距？于是我用关键字fastarraysorted在google上搜索，找到了stackoverflow的结果。问题和答案都获得了20000多个点赞，应该值得一看。虽然原文是用C++和Java写的，但应该有共性。结果发现虽然两者的代码一模一样，但是CPU执行的时候是不一样的。原因在于CPU的一个优化特性：BranchPrediction（分支预测）。为了更容易理解，回答者打了个比方：考虑铁轨上的叉子：（图片来自Mecanismo，来源维基媒体，许可CC-By-SA3.0）假设我们在19世纪，你负责选择火车叉方向。那时候连电话、手机都没有普及。当火车来的时候，你不知道火车开往哪个方向。所以你的方法（算法）是：让火车停下来，当火车停下来的时候，你问司机，然后你确定火车是往哪个方向走，把铁轨拉到对应的轨道上。另外需要注意的是，火车的惯性很大，所以司机一定要在很远的地方开始减速。当您将铁轨转向正确的方向时，火车需要很长时间才能启动和加速。那么有没有更好的方法来减少火车等候时间呢？有一个很简单的方法，你提前把轨道往某个方向移动。那么你想转向哪个方向呢？你用的方法是“盲法”：对了，火车直接过去，花费的时间为0。如果错了，火车停下来，然后倒车，你把铁轨往反方向转，火车重新启动，加速，然后开走。如果你很幸运，每次都做对了，火车将永远不会停下来，继续前行！（可以买彩票。）如果不幸错了，会浪费很多时间。所以现在我们考虑一个if语句。if语句会产生一个“分支”，类似于之前的铁轨：很多人会想，CPU怎么会像火车一样呢？CPU是否也需要减速和后退？不是遇到中断就直接跳转吗？现代CPU芯片非常复杂。为了提高性能，大多数芯片都采用了指令流水线技术。通常有几个主要步骤：读取指令（IF）->解码（ID）->执行（EX）->内存访问（MEM）->回写寄存器（WB）这大大提高了指令的传递速度（数量每单位时间执行的指令数）。当第一条指令执行时，第二条指令已经解码，可以立即执行。那么CPU是如何进行分支预测的呢？最简单的方法之一是基于历史。如果过去99%的次数都在某个分支上执行，那么CPU会猜测下一次可能会执行这个分支，所以可以提前将这个分支的代码加载到流水线中。如果预测失败，则需要刷新并重新加载流水线，可能需要20个左右的时钟周期。如果数组是按照一定的顺序排列的，那么CPU的预测就会很准确，就像我们之前的代码，data[i]>=128，不管数组是升序还是降序，分界点前后128，CPU分支预测可以得到正确的结果。如果数组乱序，CPU流水线将不断预测失败并重新加载指令。那么如果我们已经知道我们的数组乱序了，分支预测很有可能会失败，我们是否可以通过优化代码来避免CPU的分支预测呢？答案是肯定的。我们可以去掉分支语句，这样CPU就可以直接在指令流水线上加载指令，而不需要依赖分支预测。在这里使用按位技巧。我们观察前面的代码：if(data[i]>=128){sum+=data[i];}累加所有大于128的数。因为位运算只对32位整数有效，所以我们可以使用右移判断一个数。对于有符号数：非负数右移31位一定是0，负数右移31位一定是-1，即0xffff，因为-1的二进制表示是所有位都是1，即是：0b1111_1111_1111_........_1111_1111_1111//32个。因此，如果-1与任何数字进行AND运算，其值将保持不变。-1&x===x0正好和-1相反，所有32位都是0:0b0000_0000_0000_..._0000_0000_0000//32可以看出，对应数字0和-1，每一位都是相反的，所以我们可以一点一点取反：~-1===0~0===-1这样，我们可以分析前面的代码，“如果大于128，累加”，我们反汇编一下：我们把这个从数字中减去128，则只有2个结果：正数（0）和负数右移31位得到0或-1。我们需要将所有结果为0（大于128）的值相加：按位取反，将大于128的数变为-1，将小于128的数变为0，与原数进行AND运算。代码是：constt=(data[i]-128)>>31sum+=~t&data[i];这避免了分支预测失败。性能测试：可以看出两者的性能几乎相同，并且性能明显高于之前使用if分支的随机数组。但是我们也看到两者的性能比有序数组的if分支代码差很多。是不是因为位运算没有使用分支预测，所以有序数组的分支预测代码性能更差？羊毛布？并不真地。即使排序后的数组的分支预测成功率很高，但是当经过128的分支临界点时，CPU仍然会预测失败，损失大量的时钟周期时间。除非数组中的所有数组都大于128或小于128。使用按位运算根本不需要CPU停顿。位运算比if分支要慢，这也与很多开发者的心理预期相悖。很多人认为位运算应该是最快的。其实我很早之前写过一篇文章：JavaScript位运算，可能没那么快Long，所以需要更长的指令周期来执行，所以比if分支的代码慢。最后，我们做一个总结。按位运算更稳定，因为它们消除了分支，但可读性也较差。甚至有人说：“所有在业务代码中使用位运算的行为都是矫揉造作”，“代码是写给人看的，位运算是写给机器看的”。
