在《高性能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):
此時心中一萬頭草泥馬奔騰而過,默默問自己為什麼會出現這樣有悖常理的結果。直到times取值越來越大:
而在firefox(39.0)下則出現了更詭異的一幕,似乎達夫設備對其不起任何效果:
那麼達夫設備真的達不到想象當中的優化程度了嗎?為了驗證自己的猜想,同時在網上找到了一個外國朋友寫的測試代碼JavaScript Loop Optimization,大多數的測試結果還是和預料一致,但是也能捕獲到這樣的截圖:
經過測試,我覺得在迭代次數少的情況下,完全沒有必要用達夫設備進行優化,且不說代碼可讀性差,有時甚至會適得其反,而多大的迭代次數算多,多大算少,也不好說,特定的浏覽器特定的版本都有其一定的取值。老版本的浏覽器運用達夫設備優化性能能得到大幅度的提升,而新版的浏覽器引擎肯定對循環迭代語句進行了更強的優化,所以達夫設備能實現的優化效果日趨減弱甚至於沒有。而在查閱資料的過程中,有人提出while循環的效果和達夫設備不相上下,接下去也會針對不同的循環方式作進一步的探索。
高性能JavaScript編程(高清PDF原版)及中英文對照版 PDF http://www.linuxidc.com/Linux/2015-08/121418.htm