比較效能:迴圈 vs. 疊代器

為了決定該使用迴圈還是疊代器,你需要知道哪個 search 函式的版本比較快:是顯式 for 迴圈的版本,還是疊代器的版本。

我們可以透過讀取整本 Sir Arthur Conan Doyle 寫的 The Adventures of Sherlock HolmesString 中並搜尋內容中的 the 來進行評測。以下為針對 search 函式使用 for 迴圈與使用疊代器的版本評測(benchmark):

test bench_search_for  ... bench:  19,620,300 ns/iter (+/- 915,700)
test bench_search_iter ... bench:  19,234,900 ns/iter (+/- 657,200)

疊代器版本竟然比較快一些!我們在此不會解釋評測的程式碼,因為這裡的重點不再於證明這兩種版本是一樣快的,而是要理解這兩種實作對效能的影響。

要做更全面的評測的話,你應該要檢查使用不同大小的不同文字來作為 contents、不同單字與不同長度來作為 query,以及所有各式各樣的可能性。這邊的重點在於:疊代器雖然是高階抽象,但其編譯出來的程式碼與你親自寫出低階的程式碼幾乎相同。疊代器是 Rust 其中一種零成本抽象(zero-cost abstractions),這指的是使用的抽象不會在執行時有額外的開銷。這是 C++ 的初始設計暨實作者 Bjarne Stroustrup 在 “Foundations of C++” (2012) 書中所定義的零開銷(zero-overhead)的概念:

大致上來說,C++ 的實作遵守著零開銷的原則:你沒有使用到的話,你就不必買單。而且你有使用到的話,你不可能在寫出更好的程式碼。

作為另一個例子,以下程式碼是音訊解碼器的其中一個段落。解碼演算碼使用線性預測數學運算,並依據之前樣本的線性函式來預估未來的數值。此程式碼使用一連串的疊代器來對作用域中的三個變數進行數學運算:資料切片 buffer、長度為 12 的 coefficients 陣列以及要偏移的數量 qlp_shift。我們在範例中宣告變數但沒有給予任何數值,雖然只看此程式碼的確沒有什麼意義,但是這仍然是個現實世界中的其中一個簡例,可以來看出 Rust 如何將高階的想法轉換成低階的程式碼。

let buffer: &mut [i32];
let coefficients: [i64; 12];
let qlp_shift: i16;

for i in 12..buffer.len() {
    let prediction = coefficients.iter()
                                 .zip(&buffer[i - 12..i])
                                 .map(|(&c, &s)| c * s as i64)
                                 .sum::<i64>() >> qlp_shift;
    let delta = buffer[i];
    buffer[i] = prediction as i32 + delta;
}

要計算 prediction 的數值的話,此程式碼會遍歷 coefficients 的 12 個數值並使用 zip 方法將係數數值與 buffer 中之前 12 個數值做配對。然後在每個配對中,我們將數值相乘,然後相加所有結果,最後對總和往右偏移 qlp_shift 位。

像音訊解碼器這種的應用程式運算通常最注重效率。我們在此建立了一個疊代器,使用兩個配接器,然後消化數值。這段 Rust 程式碼會產生什麼樣的組合語言程式碼呢?在本書撰寫時,它會編譯出與你自己手寫一樣的組合語言。遍歷 coefficients 的數值完全不需用到迴圈:Rust 知道一共有 12 次疊代,所以它會「展開(unroll)」迴圈。展開是一種優化方式,這會移除迴圈控制程式碼並改產生針對迴圈中每次疊代的重複程式碼。

所有的係數都會存在暫存器中,這意味著存取數值會非常地快。在執行時不會有對陣列的界限檢查。這些所有 Rust 能做的優化讓產生的程式碼可以十分迅速。現在既然你已經知道了,你就可以自在地使用疊代器與閉包!它們可以寫出高階的程式碼,但不會犧牲執行時的效能。

總結

閉包與疊代是是 Rust 啟發自函式程式語言的概念。它們讓 Rust 在表達高階概念的同時,仍能擁有低階程式碼的效能。閉包與疊代器的實作對執行時效能不會有影響。這是 Rust 竭力提供零成本抽象的目標之一。

現在我們改善了 I/O 專案的可讀性,讓我們看看 cargo 一些更多的功能,來幫助我們分享專案給全世界。