來源 |?https://juejin.im/post/6844903889125244936寫在前面
作為一個前端開發(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é)合小標(biāo)題的暗示，你會發(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)存別名使用 的原因，這里就不詳解了，感興趣的可以去看書。當(dāng)然針對這段代碼的優(yōu)化很簡單，通過一個臨時變量，在循環(huán)前事先計算調(diào)用一次strlen即可，然后使用那個變量當(dāng)作判斷條件。值得注意的是：僅僅這樣一個簡單的優(yōu)化，時間復(fù)雜度就從o(n^2)變成o(n)了，這是巨大的提升。有經(jīng)驗的編程者可能認(rèn)為，這段代碼的問題c語言上獨有的，因為大部分高級語言的字符串的長度，是被語言本身作為一個常量維護(hù)的，不需要遍歷就能得到。實際上，這個例子只是給你一個提醒，微小的變動，可能導(dǎo)致性能的巨大下降或提升
接下來，我們以 combine 函數(shù)為例 對一個對數(shù)組進(jìn)行求和，看看一段功能相同的代碼，經(jīng)過優(yōu)化后，其性能的差距。combine1函數(shù)在for循環(huán)判斷中調(diào)用 getLengthFromArray 得到數(shù)組長度，比起strlen，這個函數(shù)的時間復(fù)雜度是o(1)，很可能有人會問？為什么要脫了褲子放屁，為什么不直接用 .length 屬性，這里有以下幾個考量：- 即使是o(1)的調(diào)用，也會有性能上的影響
至于為什么要用 getFromArray 函數(shù)獲取數(shù)組元素，因為js的數(shù)組沒有越界檢查（越界訪問不會報錯），可能會發(fā)生程序運行了很長時間后，錯誤才顯現(xiàn)出來。所以getFromArray的目的是提供越界檢查，當(dāng)越界時拋出錯誤。版本1：
function getFromArray(arr, index) { if (index < 0 || index >= arr.length) throw new Error('OUT OF INDEX' + index); return arr[index]}
function getLengthFromArray(arr) { if (arr == null) throw new Error(arr + 'is not an Array.') return arr.length; }
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++) { sum += getFromArray(arr, i); } 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() { console.time('combine2'); let sum = 0; const len = getLengthFromArray(arr); 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)化的提升是否巨大，它都是低效率的一種來源，需要被消除，否則這有可能成為進(jìn)一步優(yōu)化時的瓶頸。減少多余的函數(shù)調(diào)用
通過分析combine2函數(shù)，我們可以發(fā)現(xiàn)，getFromArray函數(shù)的提供的越界檢查似乎是不必要的，如果我們正確的設(shè)置循環(huán)的終止條件。對于每一次訪問，getFromArray都會做判斷，這種判斷是不必要的，且每一次函數(shù)調(diào)用也是一種開銷。(function combine3() { 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)存訪問
- 1）對于一個函數(shù)，其內(nèi)部變量一般存儲在寄存器中，你可以把寄存器看成一個CPU和內(nèi)存之間的一個緩存
- 2）程序訪問寄存器的速度遠(yuǎn)快于訪問內(nèi)存
- 3）對于值為數(shù)組的變量，其在寄存器中的值是數(shù)組在內(nèi)存中的地址，所以更改或訪問其數(shù)據(jù)需要訪問內(nèi)存
在明確這幾點以后，讓我們來看一段負(fù)優(yōu)化后的代碼：(function combine4() { let sum = [0]; console.time('combine4'); const len = getLengthFromArray(arr); for (let i = 0; i < len; i++) { sum[0] += arr[i]; } console.log('sum', sum[0]); console.timeEnd('combine4');}());
combine4與combine3唯一不同點在于，sum變成一個引用類型的變量，其引用一個存儲在內(nèi)存中的，長度為1的數(shù)組，此時我們分析下對于 sum[0] += arr[i] 要訪問幾次內(nèi)存：為了得出更令人信服的結(jié)論，這里提供combine4的另一個正優(yōu)化后版本進(jìn)行對比。(function combine4_anothor() { let sum = [0]; let tmp = 0; console.time('combine4_anothor'); const len = getLengthFromArray(arr); for (let i = 0; i < len; i++) { tmp += arr[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é)果：- combine4_anothor: 17.618ms
本節(jié)核心在于：通過設(shè)置臨時變量，復(fù)用變量，減少不必要的內(nèi)存訪問這節(jié)中，你可能會疑惑：為什么內(nèi)存速度會很慢？寄存器和內(nèi)存什么關(guān)系？為什么局部變量存儲在寄存器上？怎么做到的？同樣的，這些問題在《CSAPP》都有解答。使用循環(huán)展開
(function combine5() { let sum = 0; console.time('combine5'); const len = getLengthFromArray(arr); const limit = len - 1; let i; for (i = 0; i < limit; i += 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ù)，所以性能會得到提升。然而令人意外的時：但是當(dāng)我在機器上實踐的時候，采用步長為2的展開時，combine5并沒有比combine4 ?anothor跑的快，相反還要慢一點，但當(dāng)我逐漸增高循環(huán)展開的步數(shù)后，時間才逐漸逼近combine4 anothor，最后大概一致，這是為什么呢？首先剛才提了，循環(huán)性能提升的原因在于減少for循環(huán)中判斷的次數(shù)，當(dāng)我們采用步長為1的循環(huán)時，現(xiàn)代的編譯器可以識別出這種常用的循環(huán)模式，從而直接進(jìn)行類似循環(huán)展開的優(yōu)化，因此當(dāng)我們提高循環(huán)展開的步長時，其實是在手動進(jì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的知識，大家認(rèn)為代碼(指令)按序執(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）作出改進(jìn)，考慮以下代碼提高代碼并行性
(function combine5_another() { console.time('combine5_another'); let sum = 0; let tmp1 = 0; const len = getLengthFromArray(arr); const limit = len - 1; 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)模式，進(jìn)行優(yōu)化。另一個重要的原因就是 循環(huán)展開 和 提高并行性 兩種優(yōu)化是依賴于底層硬件的，就拿后者來說，cpu之所能進(jìn)行并行計算，是因為底層設(shè)置了冗余計算功能單元，而單元的數(shù)量限制了同一時間并行計算的次數(shù)**，對于相同優(yōu)化后的代碼，在不同cpu上運行，其性能提升不一定，甚至可能會下降**。所以這兩種優(yōu)化需要針對具體機器，具體分析，但在原則上是通用的。同樣的，《CSAPP》詳細(xì)講解了這兩項優(yōu)化背后的原理以及原因，有興趣的可以去看書。最后提供下未優(yōu)化和優(yōu)化后版本的對比：利用程序的局部性
本節(jié)重點是：你寫的程序需要有良好的局部性讓我們先明確一個事實：操作系統(tǒng)會緩存經(jīng)常使用的數(shù)據(jù)，通過將數(shù)據(jù)存儲在內(nèi)存與cpu之間的 高速緩存 中，即當(dāng)一個程序請求一項數(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的矩陣進(jìn)行求和。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[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)了一種空間局部性，當(dāng)我們訪問arr[0][0](內(nèi)存地址 0)時，操作系統(tǒng)根據(jù) 空間局部性原理 假設(shè)我們很可能會接著訪問 arr[0][1]，于是就將其裝入高速緩存，當(dāng)我們真的訪問的時，就不需要經(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)以局部性為前提提供的緩存機制，當(dāng)你訪問arr[0][0]時，系統(tǒng)把arr[0][1]加入緩存，然后你直接跳到了arr[1][0]，緩存沒有命中，就需要經(jīng)歷等待取內(nèi)存的時間，當(dāng)這種操作大量的累積起來時，就會造成可觀，低下的程序性能。這里給你一個不嚴(yán)謹(jǐn)，但直觀的矩陣求和示例代碼結(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)化是可以定量分析的。
