JavaScript性能优化:(四)程序流程控制

代码数量多少并不是程序运行速度的决定性因素,代码的组织结构和解决问题的思路才是影响代码性能的主要因素。而代码结构中最重要的就是流程控制:循环、条件分支、函数调用…

循环

ES5 及之前版本中有以下四种循环类型:

  • for( ; ; ) {}
  • while() {}
  • do{} while()
  • for...in

上面列表中的所列的前三个循环,一般说来,在性能方面没有差距特别显著的高下之分,大多数人最常用的应该是 for 循环了。

更快的 for 循环

对于最常用的 for 循环了,我们唯一可做的性能优化措施就是缓存待遍历数据集的相关属性值。例如进行数组循环时,我们应该缓存数组的 length 属性值,这样就可以避免每次遍历一个元素都会重新访问其 length 属性,从而避免了不必要的性能损失。

1
2
3
4
5
6
const arr = [0, 1, 2, 3, 4, 5];
const len = arr.length;
for (let i = 0; i < len; i++) {
console.log(arr[i]);
}

反向 while 循环

对于大量数据而言最快速的迭代方式是反向 while 循环。这项技术之所以没有使用 for 循环,是因为 for 循环每遍历一项还需要进行终止条件的判断这一步骤(在上面代码中就是 i < len)。

得益于 JavaScript 的隐式类型转换,在反向 while 循环中我们不用写 index >=0 这种表达式,因为 0 值会被自动转换为 false

1
2
3
4
5
6
const arr = [0, 1, 2, 3, 4, 5];
let index = arr.length;
while (index--) {
console.log(arr[index]);
}

观察上面的代码,与之前的 for 循环相比,可以看出,反向 while 循环省去了以下步骤:

  1. 数值比较:i < len
  2. 计算数值比较结果的真假性:(i < len) == true

需要强调的是,虽然反向 while 循环是最快速的迭代方法,但对于超大型数组来说也只是快了几百毫秒而言。因此,这种技术更像是理论应用而不实际的性能优化技巧。注意,由于 JavaScript 是单线程的、事件驱动的、异步的,所以性能开销也依赖于实际执行环境具体而异。

使用 break 或 continue 缩短循环次数

如果我们遍历某个数据集的目的是找到某个符合要求的值,那么当已经找出了所要寻找的值时,就应该立马跳出当前这一轮遍历,或结束整个循环。

breakcontinue 关键字可以帮助我们进行这种操作:

  • break 使当前整个循环停止执行,然后程序会转而继续执行循环语句之后的代码
  • continue 使当前遍历的迭代停止,并开始进行下一次迭代

避免在循环中创建函数

为了更快地进行循环,我们应该永远避免在循环中创建函数。每一次创建函数时,都会为该函数分配一定的物理内存,并填充到表示该函数的对象数据。

为了避免在每一次迭代中创建一个函数,可以先在循环语句之前创建并声明一个单独的函数,然后在循环体内引用该函数。

基于函数的迭代

ES5 引入为 Array 类型引入了一个名为 forEach() 的原生方法,该方法接受一个函数做参数。执行此方法会遍历一个数组的所有成员,并对每个成员执行传入的函数。这个作为 forEach() 参数的函数接受三个指定的参数:当前数组项的值、当前值的索引、数组本身。

1
2
3
4
5
const arr = [0, 1, 2, 3, 4, 5];
arr.forEach((value, index, arr) => {
process(value); // process() 为一个已经定义的函数
});

但就性能角度考量,不建议使用 forEach() 方法遍历数组。因为现代浏览器引擎内部已经为最常用的 for 循环进行了优化,就遍历时间而言,forEach() 用时多于 for 循环。

另外,这种遍历数组的方式有个缺陷:既不能使用 break 语句中断循环,也不能使用 return 语句返回到外层函数。

减少迭代次数:Duff’s Device

如果迭代超过 1e3 数量级了,无论如何循环多会变得慢很多。对于这种情况,我们应该设法减少迭代次数以提高循环性能。

“Duff’s Device” 是一个循环体展开技术,它使得一次迭代中实际上执行了多次迭代的操作。Jeff Greenberg 被认为是将 “Duff’s Device” 代码从原始的 C 实现移植到 JavaScript 中的第一个人。 ——《高性能JavaScript》

下面是该算法的一个较好实现,其基本理念是:每次循环最多可调用 8 次 process()。循环的迭代次数为总数除以 8。由于不是所有数字都能被 8 整除,变量 i 用于存放余数,表示第一次循环应该调用多少次 process()。然后剩余的每次循环都调用 8次 process()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let i = items.length % 8;
while (i) {
process(items[i--]);
}
i = Math.floor(items.length / 8);
while (i) {
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
}

是否应该使用 “Duff’s Device”,很大程度上依赖于迭代次数。当循环迭代次数超过 1000时,使用了 “Duff’s Device” 技术的迭代性能提升显著。

for…of 循环(ES6+)

这四种循环类型中,for(...in...) 循环效率低下,究其原因是其本身实际是被用于遍历对象属性的“键”而非“值”,但很多人都误用其去遍历对象属性的 “值”。

考虑到 Web 世界的向下兼容,不能直接修改 fo...in 循环的内部原理以及行为表现,所以 ES6 新引入了 for...of 循环,我们可以用其专门遍历键值对中的“值”。

当执行 for..of 循环时,会首先调用对象的 [Symbol.iterator]() 方法(这是 for...of 循环必需的东西),然后返回一个新的迭代器对象。迭代器对象可以是任意具有 .next() 方法的对象;for...of 循环将重复调用这个方法,每循环一次调用一次。

1
2
3
4
5
6
7
8
9
const arr = ['a', 'b', 'c', 'd', 'e'];
for(let i in arr) {
console.log(i); // '0' '1' '2' '3' '4'
}
for(let i of arr){
console.log(i); // 'a' 'b' 'c' 'd' 'e'
}

条件分支

受 C 语言的影响,JavaScript 中的条件分支语句也有两种:if-else 和 switch。由于不同的浏览器针对流程控制进行了不同的优化,因此使用哪种技术性能开销更小没有绝对定论。

if-else VS switch

使用 if-else 还是 switch,最流行的方法是基于测试条件的数量来判断:条件数量越多,越倾向于使用 switch 而不是 if-else

事实证明,大多数情况下 switchif-else 运行得要快,但只有当条件数量很大时才快得明显。这两种分支语句主要性能区别是:当条件增加时,if-else 性能负担增加得程度比 switch 要多。因此,我们自然倾向于在条件数量较少时使用 if-else,而在条件数量较大时使用 switch,这从性能方面考虑也是合理的。

通常来说,if-else 用于判断两个离散值或几个不同的值域。当判断多于两个离散值时,switch 语句是更加选择。

注意,JavaScript 中 switch 操作符使用的是 “===” 操作符进行比较,所以不会产生类型转换的损失。

if-else 的优化

优化 if-else 的目标是,最小化到达正确分支前所需判断的条件数量。

最简单的优化方法就是将概率最大的条件放在第一个分支 if()

1
2
3
4
5
6
7
if (x < 3) {
} else if (x > 3 && x < 10) {
} else {
}

上面这段条件语句,只有当变量 x 的值大于 3时,if-else 语句的性能才是最优的。

另一种减少条件判断次数的方法是把多个并列的 if-else 分支语句组织成一系列嵌套的 if-else 语句。使用单个庞大的 if-else 通常会导致运行缓慢,因为每个条件都需要判断。例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
if (x === 0) {
return result0;
} else if (x === 1) {
return result1;
} else if (x === 2) {
return result2;
} else if (x === 3) {
return result3;
} else if (x === 4) {
return result4;
} else if (x === 5) {
return result5;
} else {
return undefined;
}
// 优化之后
if (x < 3) {
if (x < 1) {
if (x === 0) {
return result0;
} else {
return undefined;
}
} else {
if (x === 1) {
return result1;
} else {
return resul2;
}
}
} else {
if (x < 5) {
if (x === 3) {
return result3;
} else {
return result4;
}
} else {
if (x === 5) {
return result5;
} else {
return undefined;
}
}
}

查找表

在计算机科学中,查找表 是用简单的查询操作替换运行时计算的数组或者关联数组这样的数据结构。由于从内存中提取数值经常要比复杂的计算速度快的多,所以这样得到的速度提升是很显著的。——维基百科

当有大量离散值需要测试时,我们可以使用查找表,将要判断真假的条件表达式可能的值及其对应的表达式操作构建为键值对,然后将这些键值对填充到数组或者普通对象(ES6+之后可以使用 Map 结构)中。

当使用查找表时,我们必需抛弃条件判断语句。这个过程演变为数组项查询或者对象成员查询。查找表的一个主要优点是:不用书写任何条件判断语句,即便候选值数量增加时,也不会产生额外的性能开销。

下面是一个使用查找表改写 switch 分支结构的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
switch (value) {
case 0:
return result0;
case 1:
return result1;
case 2:
return result2;
case 3:
return result3;
case 4:
return result4;
case 5:
return result5;
default:
return result6;
}
// 使用查找表改写
const results = [result0, result1, result2, result3, result4, result5, result6];
return results[value];

单个键和单个值之间存在逻辑映射时,查找表的优势就能体现出来。switch 语句更适合于每个键都需要对应一个独特的动作或者一系列动作的场合。

递归

最大调用栈限制

JavaScript 引擎支持的递归上限于 JavaScript 调用栈大小直接相关,大多数现代浏览器都有固定数量的调用栈限制。

当在程序中使用了太多递归,或者程序递归流程本身有问题时,就有可能会超过 JavaScript 引擎的最大调用栈限制,从而导致栈溢出错误。

递归模式

有两种递归模式可能引起栈溢出错误。

第一种模式如下:

1
2
3
4
5
process();
function process() {
process();
}

另一种模式如下:

1
2
3
4
5
6
7
8
9
first();
function first() {
second();
}
function second() {
first();
}

在这种模式中,两个函数相互调用,形成一个无限循环。

大多数调用栈错误都与这两种模式有关。最常见的的导致栈溢出的原因是不正确的终止条件,因此定位模式错误的第一步是验证终止条件。如果终止条件没有问题,那么可能是算法中包含了太多层递归,为了能在浏览中安全地工作,建议改用迭代、Memoization,或者结合两者使用。

迭代

任何递归能实现的算法同样可以使用迭代来实现。迭代算法通常包含几个不同的循环,分别对应计算过程的不同方面,这也会引入它们自身的性能问题。然而,使用优化后的循环替代长时间运行的递归函数可以提升性能,因为运行一个循环比反复调用一个函数的开销要少得多。

提升函数性能

Memoization

Memoization 是一种可以缓存之前的结算结果以供后续计算使用的技术。

下面这段代码是常见的计算阶乘的递归函数:

1
2
3
4
5
6
7
function factorial(n) {
if (n === 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}

现在,我们使用 Meomization 技术改写上面这段代码,以缓存每一次的计算结果:

1
2
3
4
5
6
7
8
9
10
11
function memFactorial(n) {
if (!memFactorial.cache) {
memFactorial.cache = new Map([[0, 1], [1, 1]]);
}
if (!memFactorial.cache.has(n)) {
memFactorial.cache.set(n, n * memFactorial(n - 1));
}
return memFactorial.cache.get(n);
}

我们还可以将 Memoization 技术抽象为一个一般性函数,以将任何普通函数转换带缓存记忆功能的函数。下面是一个简单的封装了 Memoization 技术的函数实现:

1
2
3
4
5
6
7
8
9
10
11
//
function memoize(fn) {
fn.cache = fn.cache || new Map();
return function(arg) {
if (!fn.cache.has(arg)) {
fn.cache.set(arg, fn(arg));
}
return fn.cache.get(arg);
}
}

!!!注意: 上面这种通用的 Memoization 技术与手动针对某个特定函数编写的 memoization 版本相比,优化效果较差。究其本质,memoize() 函数只会缓存特定参数的函数调用结果。例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function factorial(n) {
if (n === 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
const memoizefactorial = memoize(factorial);
memoizefactorial(6);
console.log(factorial.cache); // Map { 6 => 720 }
memFactorial(6);
console.log(memFactorial.cache); // Map { 0 => 1, 1 => 1, 2 => 2, 3 => 6, 4 => 24, 5 => 120, 6 => 720 }

由此可见,上面那种对于所有函数适用的通用 Memoization 技术存在显著性能问题,所以,如果要适用 Memoization 技术,强烈建为特定函数有针对性地实现,而不是采用通用 Memoization 技术方案。


参考

  • 《高性能JavaSript》,[美]Nicbolas C.Zakas 著,丁琛 译,电子工业出版社 2015
  • 《精通JavaSript开发》,[英]Den Odell 著,邝健威 厉海洋 译,人民邮电出版社 2015