WEB前端開發(fā)社區(qū) 昨天

寫在前面

作為一個前端開發(fā)人員，我一直難以理解學(xué)習(xí)計算基礎(chǔ)知識的重要性，這是因為我難以想象這些知識會以何種方式應(yīng)用到前端開發(fā)的工作上。

然而在csapp 優(yōu)化程序性能 這一節(jié)，徹底的改變了我的想法，作者講述了對于一個正確，良好編寫的c語言程序，如何優(yōu)化它的性能。

對一段相同功能的代碼，優(yōu)化后與優(yōu)化前產(chǎn)生了巨大的差別，速度得到了幾十倍的提升。然而，令我困惑的是，js與c這兩種在語言層次上相差如此之大的語言，這樣的優(yōu)化是否有同樣的效果？經(jīng)過實踐，答案是yes。

因此計算機基礎(chǔ)知識并不是空中樓閣，它確實有用，讓你寫出更好的程序。為什么大廠喜歡考察基礎(chǔ)，因為這些基礎(chǔ)確實在某些方面體現(xiàn)了一個人編程的水平的高低，對于計算機科班人員來說，這也恰恰是可以和別人拉開差距的地方。

引子

先舉個c語言的例子，以下這段代碼的功能是 將字符串中的大寫字母轉(zhuǎn)換成小寫

void lower(char *s) {size_t i;for (i = 0; i < strlen(s); i++) {if (s[i] >= 'A' && s[i] <= 'Z')            s[i] -= ('A' - 'a');    }}

你能看出這段代碼的問題在哪里嗎？

如果你足夠敏感，結(jié)合小標題的暗示，你會發(fā)現(xiàn)問題出現(xiàn)在for循環(huán)的判斷條件中 strlen()函數(shù)，首先指出一點，本段代碼在功能的正確性上毋庸置疑，但是性能上就堪憂了。

這里給不了解strlen函數(shù)的人一個提示：strlen函數(shù)是通過遍歷字符串來得到其長度的，所以每一次for循環(huán)，都會遍歷一次字符串s，因此這段代碼的時間復(fù)雜度是o(n^2)，但實際上我們只是在修改s的每個值，但不會移除或增加某個值，我們并不需要每次都計算s的長度。

你可能會疑問編譯器難道識別不出這種模式，然后針對優(yōu)化嗎？答案是否定的，簡單的講是因為編譯器無法確定是否存在 副作用 導(dǎo)致判斷條件發(fā)生變化，這其中還有 內(nèi)存別名使用 的原因，這里就不詳解了，感興趣的可以去看書。

當然針對這段代碼的優(yōu)化很簡單，通過一個臨時變量，在循環(huán)前事先計算調(diào)用一次strlen即可，然后使用那個變量當作判斷條件。值得注意的是：僅僅這樣一個簡單的優(yōu)化，時間復(fù)雜度就從o(n^2)變成o(n)了，這是巨大的提升。

有經(jīng)驗的編程者可能認為，這段代碼的問題c語言上獨有的，因為大部分高級語言的字符串的長度，是被語言本身作為一個常量維護的，不需要遍歷就能得到。實際上，這個例子只是給你一個提醒，微小的變動，可能導(dǎo)致性能的巨大下降或提升

接下來，我們以 combine 函數(shù)為例 對一個對數(shù)組進行求和，看看一段功能相同的代碼，經(jīng)過優(yōu)化后，其性能的差距。

combine1函數(shù)在for循環(huán)判斷中調(diào)用 getLengthFromArray 得到數(shù)組長度，比起strlen，這個函數(shù)的時間復(fù)雜度是o(1)，很可能有人會問？為什么要脫了褲子放屁，為什么不直接用 .length 屬性，這里有以下幾個考量：

• 模擬其他語言的行為

• 可以動態(tài)的計算數(shù)組的長度

• 提供錯誤檢查

• 即使是o(1)的調(diào)用，也會有性能上的影響

至于為什么要用 getFromArray 函數(shù)獲取數(shù)組元素，因為js的數(shù)組沒有越界檢查（越界訪問不會報錯），可能會發(fā)生程序運行了很長時間后，錯誤才顯現(xiàn)出來。所以getFromArray的目的是提供越界檢查，當越界時拋出錯誤。

版本1：

// 本代碼可直接運行
function getFromArray(arr, index) { // 提供越界檢查的數(shù)組getterif (index < 0 || index >= arr.length) throw new Error('OUT OF INDEX' + index);return arr[index]}
function getLengthFromArray(arr) { // 得到數(shù)組長度if (arr == null) throw new Error(arr + 'is not an Array.')return arr.length; // 即使是常數(shù)級的函數(shù)調(diào)用，依舊產(chǎn)生開銷}
void function() {console.log('start');
const numberOfElement = 9999999;const arr = Array(numberOfElement).fill(2);
    (function combine1() {console.time('combine1');
let sum = 0;for (let i = 0; i < getLengthFromArray(arr); i++) { // 每次循環(huán)都要重新計算長度            sum += getFromArray(arr, i); // 使用提供越界檢查getter得到數(shù)組元素        }console.log('sum', sum);
console.timeEnd('combine1');    }());

console.log('end');}();

消除循環(huán)的低效率

函數(shù)combine1在 每一個for循環(huán)，都會調(diào)用getLengthFromArray作為循環(huán)的測試條件，根據(jù)我們函數(shù)的功能來看，我們只是訪問數(shù)組中的每一個元素，并不會修改數(shù)組的長度，因此產(chǎn)生了大量的無效計算(調(diào)用)，所以需要優(yōu)化。

(function combine2() {// 可直接執(zhí)行console.time('combine2');let sum = 0;const len = getLengthFromArray(arr); // 消除每次循環(huán)對數(shù)組長度的計算for (let i = 0; i < len; i++) {        sum += getFromArray(arr, i);    }console.log('sum', sum);console.timeEnd('combine2');}());

combine2 通過我個人電腦的測試，在消除for循環(huán)判斷條件中的無用計算后，combine2確實比combine2要快個10ms左右，可能你覺得這點時間不算什么。

但是：無論這個優(yōu)化的提升是否巨大，它都是低效率的一種來源，需要被消除，否則這有可能成為進一步優(yōu)化時的瓶頸。

減少多余的函數(shù)調(diào)用

通過分析combine2函數(shù)，我們可以發(fā)現(xiàn)，getFromArray函數(shù)的提供的越界檢查似乎是不必要的，如果我們正確的設(shè)置循環(huán)的終止條件。

對于每一次訪問，getFromArray都會做判斷，這種判斷是不必要的，且每一次函數(shù)調(diào)用也是一種開銷。

(function combine3() {/**     * 現(xiàn)在消除了每次循環(huán)對數(shù)組長度的計算     * 并且確定訪問不會越界，不需要越界檢查，直接訪問數(shù)組     */console.time('combine3');let sum = 0;const len = getLengthFromArray(arr);for (let i = 0; i < len; i++) {        sum += arr[i]; // 直接訪問    }console.log('sum', sum);console.timeEnd('combine3');}());

經(jīng)過實踐，combine3對比combine1性能幾乎提升了一倍多，所以從性能上看，這種優(yōu)化顯然是需要的。

但是值得爭論的一點在于，你如果把 arr 看作一個別人提供的數(shù)據(jù)結(jié)構(gòu)，getFromArray作為這個數(shù)據(jù)的結(jié)構(gòu)的getter，我們作為用戶，不應(yīng)該對arr的底層實現(xiàn)有任何的假設(shè)，我們不知道它的底層是數(shù)組還是鏈表，因此它違背了 黑盒原則，提高了程序的耦合性。

所以在程序優(yōu)化時，你可能需要平衡好 高性能高耦合 或 低性能低內(nèi)聚 的抉擇

消除不必要的內(nèi)存訪問

為了理解這個優(yōu)化點，你首先得明白：

• 1）對于一個函數(shù)，其內(nèi)部變量一般存儲在寄存器中，你可以把寄存器看成一個CPU和內(nèi)存之間的一個緩存

• 2）程序訪問寄存器的速度遠快于訪問內(nèi)存

• 3）對于值為數(shù)組的變量，其在寄存器中的值是數(shù)組在內(nèi)存中的地址，所以更改或訪問其數(shù)據(jù)需要訪問內(nèi)存

在明確這幾點以后，讓我們來看一段負優(yōu)化后的代碼：

(function combine4() {let sum = [0]; // 負優(yōu)化在這里，sum現(xiàn)在是個指針了console.time('combine4');const len = getLengthFromArray(arr);for (let i = 0; i < len; i++) {        sum[0] += arr[i]; // 三次內(nèi)存訪問    }console.log('sum', sum[0]);console.timeEnd('combine4');}());

combine4與combine3唯一不同點在于，sum變成一個引用類型的變量，其引用一個存儲在內(nèi)存中的，長度為1的數(shù)組，此時我們分析下對于 sum[0] += arr[i] 要訪問幾次內(nèi)存：

• 讀取sum[0]

• 讀取arr[i]

• 寫回sum[0] 兩次讀，一次寫，總共三次

為了得出更令人信服的結(jié)論，這里提供combine4的另一個正優(yōu)化后版本進行對比。

(function combine4_anothor() {let sum = [0];let tmp = 0; // 通過設(shè)計臨時變量，減少內(nèi)存訪問次數(shù)console.time('combine4_anothor');const len = getLengthFromArray(arr);for (let i = 0; i < len; i++) {        tmp += arr[i]; // 一次內(nèi)存訪問    }    sum[0] = tmp;console.log('sum', sum[0]);console.timeEnd('combine4_anothor');}());

現(xiàn)在我們分析下combine4_anothor在每一次for循環(huán)訪問內(nèi)存的次數(shù)，只有一次讀arr[i]的操作，對比原來的combine4減少了兩次的內(nèi)存訪問，比起combine4的每次循環(huán)寫入內(nèi)存，combine4 anothor選擇在最后寫入內(nèi)存。實際上這個操作性能的提升也是巨大的，這里我給出自己電腦的上結(jié)果：

• combine3: 15.298ms

• combine4: 28.701ms

• combine4_anothor: 17.618ms

本節(jié)核心在于：通過設(shè)置臨時變量，復(fù)用變量，減少不必要的內(nèi)存訪問

這節(jié)中，你可能會疑惑：為什么內(nèi)存速度會很慢？寄存器和內(nèi)存什么關(guān)系？為什么局部變量存儲在寄存器上？怎么做到的？同樣的，這些問題在《CSAPP》都有解答。

使用循環(huán)展開

(function combine5() {/**     * 利用循環(huán)展開     */let sum = 0;        console.time('combine5');const len = getLengthFromArray(arr);const limit = len - 1; //防止越界let i;for (i = 0; i < limit; i += 2) {  // 步長為2的展開        sum += arr[i]; // 直接訪問        sum += arr[i + 1];    }for (; i < len; i++) { //處理剩余未訪問的元素        sum += arr[i];    }console.log('sum', sum);console.timeEnd('combine5');}());

循環(huán)展開是怎么提升這段代碼性能的？原因在于他消除了部分調(diào)用for循環(huán)的開銷，這個特定了例子里，他減少了大概一半的for循環(huán)次數(shù)，因此也就減少一半的判斷次數(shù)，所以性能會得到提升。

然而令人意外的時：但是當我在機器上實踐的時候，采用步長為2的展開時，combine5并沒有比combine4  anothor跑的快，相反還要慢一點，但當我逐漸增高循環(huán)展開的步數(shù)后，時間才逐漸逼近combine4 anothor，最后大概一致，這是為什么呢？

首先剛才提了，循環(huán)性能提升的原因在于減少for循環(huán)中判斷的次數(shù)，當我們采用步長為1的循環(huán)時，現(xiàn)代的編譯器可以識別出這種常用的循環(huán)模式，從而直接進行類似循環(huán)展開的優(yōu)化，因此當我們提高循環(huán)展開的步長時，其實是在手動進行這種優(yōu)化。

但值得注意的是，對于這段簡單的代碼，編譯器可以識別出來，但是復(fù)雜點的，就不一定了，所以掌握這種展開的技術(shù)是必要的，并且這種通過循環(huán)展開優(yōu)化后的 性能瓶頸來源 很值得我們思考。

再次分析性能瓶頸

現(xiàn)在我們分析下combine5性能的限制，或者說這個函數(shù)的運行時間主要依賴于哪個因素？

我們可以通過循環(huán)展開減少循環(huán)次數(shù)，從而節(jié)省每次循環(huán)后比較的開銷，但是 sum += arr[i] 的開銷沒法省，無論怎么優(yōu)化 我們都至少要訪問arr數(shù)組 length次數(shù)，且計算機對于 sum += arr[i] 執(zhí)行必須是按序的，無論是否采用循環(huán)展開，因為每一次sum的計算值都依賴于上一次的sum的計算值。

所以combine5函數(shù)的主要運行時間源于 sum += arr[i]，如果arr數(shù)組長為100，計算機每次執(zhí)行 sum += arr[i] 需要花費1s，那么combine5 無論怎么優(yōu)化，每次執(zhí)行都至少要花費100s。

這里，我們要引入一點現(xiàn)代CPU的知識，大家認為代碼(指令)按序執(zhí)行，實際上展示的效果也確實是這樣的，但是在底層，cpu其實是亂序執(zhí)行代碼的。通過對指令的分析再排序，cpu可以并發(fā)、甚至并行的執(zhí)行代碼(通過利用多核)，至于這樣為什么正確？

考慮以下這段代碼

let a = 1 + 1;let b = 2 + 2;let c = a + b;let d = c + c;

a，b是可以并行計算，因為它們并不相互依賴，而c就必須等到a，b執(zhí)行完才能運行，d必須等到c后才能執(zhí)行，所以c，d無法并行，只能按序執(zhí)行。

現(xiàn)在我們再回顧下制約combine5性能的原因：

• 1）我們都至少要訪問arr數(shù)組 length次數(shù)

• 2）計算機對于 sum += arr[i] 執(zhí)行必須是按序的，無論是否采用循環(huán)展開，因為每一次計算sum都依賴于上一次sum的計算值

1）是無法避免的，但我們是否有機會對2）作出改進，考慮以下代碼

提高代碼并行性

(function combine5_another() {/**     * 提高并行性     */console.time('combine5_another');let sum = 0;        let tmp1 = 0;const len = getLengthFromArray(arr);const limit = len - 1; //防止循環(huán)展開后越界let i;for (i = 0; i < limit; i += 2) {        sum += arr[i]; // 直接訪問        tmp1 += arr[i + 1];    }for (; i < len; i++) { //處理剩余未訪問的元素        sum += arr[i];    }    sum += tmp2;console.log('sum', sum);console.timeEnd('combine5_another');}());

combine5_another通過設(shè)置一個臨時變量tmp1來計算數(shù)組arr[2n - 1]的累計和，sum計算arr[2n - 2]的累計和，這使得cpu可以并行的計算tmp1和sum，因為tmp1的計算不依賴sum，反之亦然。

最后，循環(huán)結(jié)束后再合并結(jié)果，理論上100s的執(zhí)行時間，就減少到50s了。

不過，在我實踐時，并行優(yōu)化并沒有帶來性能上的提升，甚至下降了，可能的原因有兩個，一個是干擾，而另一個原因則非常重要。

這里先談干擾，這是因為：由于并行計算使用循環(huán)展開，導(dǎo)致編譯器無法識別其循環(huán)模式，進行優(yōu)化。

另一個重要的原因就是 循環(huán)展開 和 提高并行性 兩種優(yōu)化是依賴于底層硬件的，就拿后者來說，cpu之所能進行并行計算，是因為底層設(shè)置了冗余計算功能單元，而單元的數(shù)量限制了同一時間并行計算的次數(shù)**，對于相同優(yōu)化后的代碼，在不同cpu上運行，其性能提升不一定，甚至可能會下降**。

所以這兩種優(yōu)化需要針對具體機器，具體分析，但在原則上是通用的。

同樣的，《CSAPP》詳細講解了這兩項優(yōu)化背后的原理以及原因，有興趣的可以去看書。

最后提供下未優(yōu)化和優(yōu)化后版本的對比：

• 優(yōu)化前: 47.267ms

• 優(yōu)化后: 12.731ms

大概提升了70%的性能

利用程序的局部性

本節(jié)重點是：你寫的程序需要有良好的局部性

讓我們先明確一個事實：操作系統(tǒng)會緩存經(jīng)常使用的數(shù)據(jù)，通過將數(shù)據(jù)存儲在內(nèi)存與cpu之間的 高速緩存 中，即當一個程序請求一項數(shù)據(jù)時，操作系統(tǒng)會先去高速緩存中找，再去內(nèi)存中找(雖然內(nèi)存的傳輸速度比硬盤快的多，但比起cpu的處理速度，還是很慢，因此在與cpu中間又加了一層高速緩存)，再去硬盤中找，這樣一級級的向下找。找到就直接返回，且每一級的找尋速度越來越慢。

其次，通俗的講，程序的局部性就是：剛剛 被訪問的 數(shù)據(jù) 或 執(zhí)行的 代碼 其本身或其臨近的數(shù)據(jù)(代碼) 很可能會被(再次)訪問(執(zhí)行)。

其中局部性又分為：

• 時間局部性(已經(jīng)被訪問的數(shù)據(jù)(代碼)，很可能會被再次訪問)

• 空間局部性(對于已經(jīng)訪問的數(shù)據(jù)(代碼)，其臨近的數(shù)據(jù)(代碼)很可能被訪問)

舉個例子：以下這段代碼對一個10*10的矩陣進行求和。

const matrix = getMatrix(10, 10);let sum = 0;for (let row = 0; row < matrix.length; row++) {for (let col = 0; col < matrix[0].length; col++) {        sum += matrix[row][col];    }}

對于變量sum，其很好的體現(xiàn)了時間局部性，在第一次訪問后，以后每一次循環(huán)都會再次訪問它，所以操作系統(tǒng)在第一次訪問將它加入高速緩存后，每一次都sum的訪問都會直接去高速緩存中去取，而非內(nèi)存，從而減少了每次訪問的內(nèi)存的時間消耗。

對于martix[row][col]的訪問，其體現(xiàn)了空間局部性，為了明白這點，你得先理解 二維數(shù)組在內(nèi)存的存儲方式，二維數(shù)組在內(nèi)存中是以 行優(yōu)先 存儲，舉個例子對于一個10*10的二維數(shù)組arr，假設(shè)其開始的內(nèi)存地址是0，那么其每個元素對應(yīng)的地址位：

• arr[0][0] -> 內(nèi)存地址 0

• arr[0][1] -> 內(nèi)存地址 1

• ....

• arr[0][9] -> 內(nèi)存地址 9

• arr[1][0] -> 內(nèi)存地址 10

• arr[1][1] -> 內(nèi)存地址 11

• ...

• arr[9][0] -> 內(nèi)存地址 90

• arr[9][1] -> 內(nèi)存地址 91

• ...

• arr[9][9] -> 內(nèi)存地址 99

即，如果我們以 先行再列(就是上面代碼的方式) 的方式遍歷，那么我們遍歷的內(nèi)存地址順序就是一種線性連續(xù)遞增順序的方式：內(nèi)存地址 0, 1, 2, ..., 50, 51, 52, ..., 90, 91, 92, ..., 99

這就體現(xiàn)了一種空間局部性，當我們訪問arr[0][0](內(nèi)存地址 0)時，操作系統(tǒng)根據(jù) 空間局部性原理 假設(shè)我們很可能會接著訪問 arr[0][1]，于是就將其裝入高速緩存，當我們真的訪問的時，就不需要經(jīng)歷等待取內(nèi)存的時間，而是直接從高速緩存中拿到了。

作為對比我們介紹一個壞例子。

let sum = 0;for (let col = 0; col < matrix[0].length; col++) {for (let row = 0; row < matrix.length; row++) {        sum += matrix[row][col];    }}

這段代碼與上面那段代碼的 功能完全一樣，唯一不同的是其遍歷的方式變成了先列再行，為了給你個直觀的理解，此時遍歷內(nèi)存的地址順序是: 0, 10, 20, ..., 80, 90, 1, 11, 21, ..., 81, 91, 2, 12, 22, ...。

比起剛才的連續(xù)遞增遍歷，這樣的遍歷多了些許 跳躍性。這樣問題在于，它沒法利用 系統(tǒng)以局部性為前提提供的緩存機制，當你訪問arr[0][0]時，系統(tǒng)把arr[0][1]加入緩存，然后你直接跳到了arr[1][0]，緩存沒有命中，就需要經(jīng)歷等待取內(nèi)存的時間，當這種操作大量的累積起來時，就會造成可觀，低下的程序性能。

這里給你一個不嚴謹，但直觀的矩陣求和示例代碼結(jié)果：

startsum 99980001良好的局部性:  159.879mssum 99980001壞的局部性:    3420.815msend

void function() {    console.log('start');    const size = 9999;    const matrix = Array(size);    for (let i = 0; i < matrix.length; i++) {        matrix[i] = Array(size).fill(1);    }
    (function goodVersion() {        console.time('良好的局部性');        let sum = 0;        for (let row = 0; row < matrix.length; row++) {            for (let col = 0; col < matrix[0].length; col++) {                sum += matrix[row][col];            }        }        console.log('sum', sum);        console.timeEnd('良好的局部性');    })();
    (function worseVersion() {        console.time('壞的局部性');        let sum = 0;        for (let col = 0; col < matrix[0].length; col++) {            for (let row = 0; row < matrix.length; row++) {                sum += matrix[row][col];            }        }        console.log('sum', sum);        console.timeEnd('壞的局部性');    })();    console.log('end');}();

再強調(diào)下重點是：你寫的程序在保證正確的前提下，需要有良好的局部性

小結(jié)

礙于文章篇幅限制，本文對高性能代碼背后原理的解釋對于讀者來說只能算是一種 淺嘗輒止，有很多的東西沒談，一些優(yōu)化牽扯計算機各個層次的知識，比如對于程序局部性原理的利用僅僅停留在宏觀層面上，只是定性的分析，但對于局部性原理來說，其實質(zhì)上是基于一套堅實的理論，依賴于計算機各個層次工作的良好分工，并且這種優(yōu)化是可以定量分析的。