高性能JavaScript 达夫设备

  在《高性能JavaScript》一书的第四章算法和流程控制中,提到了减少迭代次数加速程序的策略—达夫设备(Duff's device)。达夫设备本身很好理解,但是其效果是否真的像书中所说“如果迭代次数超过1000,那么达夫设备的执行效率将明显提升”?还是随着浏览器性能的逐渐增强,这种以牺牲代码阅读性而获取的性能提升已经微不足道?

达夫设备

  达夫设备真的很简单,说白了就是“循环体展开”。看如下的代码:

var a = [0, 1, 2, 3, 4]; var sum = 0; for(var i = 0; i < 5; i++) sum += a[i]; console.log(sum);

  我们将循环体展开来写:

var a = [0, 1, 2, 3, 4]; var sum = 0; sum += a[0]; sum += a[1]; sum += a[2]; sum += a[3]; sum += a[4]; console.log(sum);

  因为少作了多次的for循环,很显然这段代码比前者效率略高,而且随着数组长度的增加,少作的for循环将在时间上体现更多的优势。

  达夫设备这种思想或者说是策略,原来是运用在C语言上的,Jeff Greenberg将它从C语言移植到了JavaScript上,我们可以来看看他写的模板代码:

var iterations = Math.floor(items.length / 8), startAt = items.length % 8, i = 0; do { switch(startAt) { case 0: process(items[i++]); case 7: process(items[i++]); case 6: process(items[i++]); case 5: process(items[i++]); case 4: process(items[i++]); case 3: process(items[i++]); case 2: process(items[i++]); case 1: process(items[i++]); } startAt = 0; } while(--iterations);

  注意看switch/case语句,因为没有写break,所以除了第一次外,之后的每次迭代实际上会运行8次!Duff's Device背后的基本理念是:每次循环中最多可调用8次process()。循环的迭代次数为总数除以8。由于不是所有数字都能被8整除,变量startAt用来存放余数,便是第一次循环中应调用多少次process()。

  此算法一个稍快的版本取消了switch语句,将余数处理和主循环分开:

var 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--]); }

  尽管这种方式用两次循环代替了之前的一次循环,但它移除了循环体中的switch语句,速度比原始循环更快。

性能测试

  接着我们来进行达夫设备的性能测试。如果迭代中的操作复杂的话,会减小达夫设备优化对于时间的影响,所以循环内部我只选取了简单的操作;而且为了方便操作,选取了8的倍数作为数组长度。

var a = []; var times = 1000; // init array for(var i = 1; i <= times; i++) a[i] = i; // ordinary way console.time('1'); var sum = 0; for(var i = 1; i <= times; i++) sum += 1 / a[i]; console.log(sum); console.timeEnd('1'); // Duff's device console.time('2'); var sum = 0; while(times) { sum += 1 / a[times--]; sum += 1 / a[times--]; sum += 1 / a[times--]; sum += 1 / a[times--]; sum += 1 / a[times--]; sum += 1 / a[times--]; sum += 1 / a[times--]; sum += 1 / a[times--]; } console.log(sum); console.timeEnd('2');

  当times取值较小时,得到了这样的结果(chrome 版本 43.0.2357.134 m):

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/df6a8821d99ddf56a9fae52b7cea2337.html