我們都知道nginx是以高性能出名的，這主要是歸功于nginx的源碼。本文我們就來講講位運算與nginx高性能的聯(lián)系。
（學習視頻分享：編程視頻）
位運算在 Nginx 的源碼是處處可見，從定義指令的類型（可以攜帶多少參數(shù)，可以出現(xiàn)在哪些配置塊下），到標記當前請求是否還有未發(fā)送完的數(shù)據(jù)，再到 Nginx 事件模塊里用指針的最低位來標記一個事件是否過期，無不體現(xiàn)著位運算的神奇和魅力。
本文會介紹和分析 Nginx 源碼里的一些經(jīng)典的位運算使用，并擴展介紹一些位其他的位運算技巧。
對齊
Nginx 內(nèi)部在進行內(nèi)存分配時，非常注意內(nèi)存起始地址的對齊，即內(nèi)存對齊（可以換來一些性能上的提升），這與處理器的尋址特性有關，比如某些處理器會按 4 字節(jié)寬度尋址，在這樣的機器上，假設需要讀取從 0x46b1e7 開始的 4 個字節(jié)，由于 0x46b1e7 并不處在 4 字節(jié)邊界上（0x46b1e7 % 4 = 3），所以在進行讀的時候，會分兩次進行讀取，第一次讀取 0x46b1e4 開始的 4 個字節(jié)，并取出低 3 字節(jié)；再讀取 0x46b1e8 開始的 4 個字節(jié)，取出最高的字節(jié)。我們知道讀寫主存的速度并不能匹配 CPU，那么兩次的讀取顯然帶來了更大的開銷，這會引起指令停滯，增大 CPI（每指令周期數(shù)），損害應用程序的性能。
因此 Nginx 封裝了一個宏，專門用以進行對齊操作。
#define?ngx_align(d,?a)?????(((d)?+?(a?-?1))?&?~(a?-?1))
如上代碼所示，該宏使得 d 按 a 對齊，其中 a 必須是 2 的冪次。
比如 d 是 17，a 是 2 時，得到 18；d 是 15，a 是 4 時，得到 16；d 是 16，a 是 4 時，得到 16。
這個宏其實就是在尋找大于等于 d 的，第一個 a 的倍數(shù)。由于 a 是 2 的冪次， 因此 a 的二進制表示為 00…1…00 這樣的形式，即它只有一個 1，所以 a – 1 便是 00…01…1 這樣的格式，那么 ~(a – 1) 就會把低 n 位全部置為 0，其中 n 是 a 低位連續(xù) 0 的個數(shù)。所以此時如果我們讓 d 和 ~(a – 1) 進行一次按位與操作，就能夠把 d 的低 n 位清零，由于我們需要尋找大于等于 d 的數(shù)，所以用 d + (a – 1) 即可。
位圖
位圖，通常用以標記事物的狀態(tài)，“位” 體現(xiàn)在每個事物只使用一個比特位進行標記，這即節(jié)約內(nèi)存，又能提升性能。
Nginx 里有多處使用位圖的例子，比如它的共享內(nèi)存分配器（slab），再比如在對 uri（Uniform Resource Identifier）進行轉義時需要判斷一個字符是否是一個保留字符（或者不安全字符），這樣的字符需要被轉義成 %XX 。
static?uint32_t???uri_component[]?=?{ ????????0xffffffff,?/*?1111?1111?1111?1111??1111?1111?1111?1111?*/ /*??>=<p>如上所示，一個簡單的數(shù)組組成了一個位圖，共包含 8 個數(shù)字，每個數(shù)字表示 32 個狀態(tài)，因此這個位圖把 256 個字符（包括了擴展 ASCII 碼）。為 0 的位表示一個通常的字符，即不需要轉義，為 1 的位代表的就需要進行轉義。</p><p>那么這個位圖該如何使用？Nginx 在遍歷 uri 的時候，通過一條簡單的語句來進行判斷。</p><pre class="brush:html;toolbar:false">uri_component[ch?>>?5]?&?(1U?<p>如上所示，ch 表示當前字符，ch >> 5 是對 ch 右移 5 位，這起到一個除以 32 的效果，這一步操作確定了 ch 在 uri_component 的第幾個數(shù)字上；而右邊的，(ch & 0x1f) 則是取出了 ch 低 5 位的值，相當于取模 32，這個值即表示 ch 在對應數(shù)字的第幾個位（從低到高計算）；因此左右兩邊的值進行一次按位與操作后，就把 ch 字符所在的位圖狀態(tài)取出來了。比如 ch 是 '0'（即數(shù)字 48），它存在于位圖的第 2 個數(shù)字上（48 >> 5 = 1），又在這個數(shù)字（0xfc009fff）的第 16 位上，所以它的狀態(tài)就是 0xfc009fff & 0x10000 = 0，所以 '0'是一個通用的字符，不用對它轉義。</p><p>從上面這個例子中我們還可以看到另外一個位運算的技巧，就是在對一個 2 的冪次的數(shù)進行取模或者除操作的時候，也可以通過位運算來實現(xiàn)，這比直接的除法和取模運算有著更好的性能，雖然在合適的優(yōu)化級別下，編譯器也可能替我們完成這樣的優(yōu)化。</p><p>尋找最低位 1 的位置</p><p>接著我們來介紹下一些其他的應用技巧。</p><p>找到一個數(shù)字二進制里最低位的 1 的位置，直覺上你也許會想到按位遍歷，這種算法的時間復雜是 O(n)，性能上不盡如人意。</p><p>如果你曾經(jīng)接觸過樹狀數(shù)組，你可能就會對此有不同的看法，樹狀數(shù)組的一個核心概念是 計算 lowbit，即計算一個數(shù)字二進制里最低位 1 的冪次。它之所以有著不錯的時間復雜度（O(logN)），便是因為能夠在 O(1) 或者說常數(shù)的時間內(nèi)得到答案。</p><pre class="brush:html;toolbar:false">int?lowbit(int?x) { ????return?x?&?~(x?-?1); }
這個技巧事實上和上述對齊的方式類似，比如 x 是 00…111000 這樣的數(shù)字，則 x – 1 就成了 00…110111，對之取反，則把原本 x 低位連續(xù)的 0 所在的位又重新置為了 0（而原本最低位 1 的位置還是為 1），我們會發(fā)現(xiàn)除了最低位 1 的那個位置，其他位置上的值和 x 都是相反的，因此兩者進行按位與操作后，結果里只可能有一個 1，便是原本 x 最低位的 1。
尋找最高位 1 的位置
換一個問題，這次不是尋找最低位，而是尋找最高位的 1。
這個問題有著它實際的意義，比如在設計一個 best-fit 的內(nèi)存池的時候，我們需要找到一個比用戶期望的 size 大的第一個 2 的冪次。
同樣地，你可能還是會先想到遍歷。
事實上 Intel CPU 指令集有這么一條指令，就是用以計算一個數(shù)二進制里最高位 1 的位置。
size_t?bsf(size_t?input) { ????size_t?pos; ????__asm__("bsfq?%1,?%0"?:?"=r"?(pos)?:?"rm"?(input)); ????return?pos; }
這很好，但是這里我們還是期望用位運算找到這個 1 的位置。
size_t?bsf(size_t?input) { ????input?|=?input?>>?1; ????input?|=?input?>>?2; ????input?|=?input?>>?4; ????input?|=?input?>>?8; ????input?|=?input?>>?16; ????input?|=?input?>>?32; ????return?input?-?(input?>>?1); }
這便是我們所期望的計算方式了。我們來分析下這個計算的原理。
需要說明的是，如果你需要計算的值是 32 位的，則上面函數(shù)的最后一步 input |= input >> 32 是不需要的，具體執(zhí)行多少次 input |= input >> m， 是由 input 的位長決定的，比如 8 位則進行 3 次，16 位進行 4 次，而 32 位進行 5 次。
為了更簡潔地進行描述，我們用 8 位的數(shù)字進行分析，設一個數(shù) A，它的二進制如下所示。
A[7]?A[6]?A[5]?A[4]?A[3]?A[2]?A[1]?A[0]
上面的計算過程如下。
A[7]?A[6]?A[5]?A[4]?A[3]?A[2]?A[1]?A[0] 0????A[7]?A[6]?A[5]?A[4]?A[3]?A[2]?A[1] --------------------------------------- A[7]?A[7]|A[6]?A[6]|A[5]?A[5]|A[4]?A[4]|A[3]?A[3]|A[2]?A[2]|A[1]?A[1]|A[0] 0????0?????????A[7]??????A[7]|A[6]?A[6]|A[5]?A[5]|A[4]?A[4]|A[3]?A[3]|A[2] -------------------------------------------------------------------------- A[7]?A[7]|A[6]?A[7]|A[6]|A[5]?A[7]|A[6]|A[5]|A[4]?A[6]|A[5]|A[4]|A[3]?A[5]|A[4]|A[3]|A[2]?A[4]|A[3]|A[2]|A[1]?A[3]|A[2]|A[1]|A[0] 0????0?????????0??????????????0???????????????????A[7]????????????????A[7]|A[6]???????????A[7]|A[6]|A[5]??????A[7]|A[6]|A[5]|A[4] --------------------------------------------------------------------------------------------------------------------------------- A[7]?A[7]|A[6]?A[7]|A[6]|A[5]??A[7]|A[6]|A[5]|A[4]?A[7]|A[6]|A[5]|A[4]|A[3]?A[7]|A[6]|A[5]|A[4]|A[3]|A[2]?A[7]|A[6]|A[5]|A[4]|A[3]|A[2]|A[1]?A[7]|A[6]|A[5]|A[4]|A[3]|A[2]|A[1]|A[0]
我們可以看到，最終 A 的最高位是 A[7]，次高位是 A[7]|A[6]，第三位是 A[7]|A[6]|A[5]，最低位 A[7]|A[6]|A[5]|A[4]|A[3]|A[2]|A[1]|A[0]
假設最高位的 1 是在第 m 位（從右向左算，最低位稱為第 0 位），那么此時的低 m 位都是 1，其他的高位都是 0。也就是說，A 將會是 2 的某冪再減一，于是最后一步（input – (input >> 1)）的用意也就非常明顯了，即將除最高位以外的 1 全部置為 0，最后返回的便是原來的 input 里最高位 1 的對應冪了。
計算 1 的個數(shù)
如何計算一個數(shù)字二進制表示里有多少個 1 呢？
直覺上可能還是會想到遍歷（遍歷真是個好東西），讓我們計算下復雜度，一個字節(jié)就是 O(8)，4 個字節(jié)就是 O(32)，而 8 字節(jié)就是 O(64)了。
如果這個計算會頻繁地出現(xiàn)在你的程序里，當你在用 perf 這樣的性能分析工具觀察你的應用程序時，它或許就會得到你的關注，而你不得不去想辦法進行優(yōu)化。
事實上《深入理解計算機系統(tǒng)》這本書里就有一個這個問題，它要求計算一個無符號長整型數(shù)字二進制里 1 的個數(shù)，而且希望你使用最優(yōu)的算法，最終這個算法的復雜度是 O(8)。
long?fun_c(unsigned?long?x) { ????long?val?=?0; ????int?i; ????for?(i?=?0;?i?>=?1; ????} ????val?+=?val?>>?32; ????val?+=?val?>>?16; ????val?+=?val?>>?8; ????return?val?&?0xFF; }
這個算法在我的另外一篇文章里曾有過分析。
觀察 0x0101010101010101 這個數(shù)，每 8 位只有最后一位是 1。那么 x 與之做按位與，會得到下面的結果：
設?A[i]?表示?x?二進制表示里第?i?位的值（0?或?1）。 第一次： A[0]?+?(A[8]?<p>之后的三個操作：</p><pre class="brush:html;toolbar:false">val?+=?val?>>?32; val?+=?val?>>?16; val?+=?val?>>?8;
每次將 val 折半然后相加。
第一次折半（val += val >> 32）后，得到的 val 的低 32 位：
(A[31]?+?A[30]?+?A[29]?+?A[28]?+?A[27]?+?A[26]?+?A[25]?+?A[24]?+?A[63]?+?A[62]?+?A[61]?+?A[60]?+?A[59]?+?A[58]?+?A[57]?+?A[56])?<p>第二次折半（val += val >> 16）后，得到的 val 的低 16 位：</p><pre class="brush:html;toolbar:false">15]?+?A[14]?+?A[13]?+?A[12]?+?A[11]?+?A[10]?+?A[9]??+?A[8]?+?A[47]?+?A[46]?+?A[45]?+?A[44]?+?A[43]?+?A[42]?+?A[41]?+?A[40]?+?A[31]?+?A[30]?+?A[29]?+?A[28]?+?A[27]?+?A[26]?+?A[25]?+?A[24]?+?A[63]?+?A[62]?+?A[61]?+?A[60]?+?A[59]?+?A[58]?+?A[57]?+?A[56])??<p>第三次折半（val += val >> 8）后，得到的 val 的低 8 位：</p><pre class="brush:html;toolbar:false">(A[7]??+?A[6]??+?A[5]??+?A[4]??+?A[3]??+?A[2]??+?A[1]??+?A[0]?+?A[39]?+?A[38]?+?A[37]?+?A[36]?+?A[35]?+?A[34]?+?A[33]?+?A[32]?+?A[23]?+?A[22]?+?A[21]?+?A[20]?+?A[19]?+?A[18]?+?A[17]?+?A[16]?+?A[55]?+?A[54]?+?A[53]?+?A[52]?+?A[51]?+?A[50]?+?A[49]?+?A[48]?+?A[15]?+?A[14]?+?A[13]?+?A[12]?+?A[11]?+?A[10]?+?A[9]??+?A[8]?+?A[47]?+?A[46]?+?A[45]?+?A[44]?+?A[43]?+?A[42]?+?A[41]?+?A[40]?+?A[31]?+?A[30]?+?A[29]?+?A[28]?+?A[27]?+?A[26]?+?A[25]?+?A[24]?+?A[63]?+?A[62]?+?A[61]?+?A[60]?+?A[59]?+?A[58]?+?A[57]?+?A[56])
可以看到，經(jīng)過三次折半，64 個位的值全部累加到低 8 位，最后取出低 8 位的值，就是 x 這個數(shù)字二進制里 1 的數(shù)目了，這個問題在數(shù)學上稱為“計算漢明重量”。
位運算以它獨特的優(yōu)點（簡潔、性能棒）吸引著程序員，比如 LuaJIT 內(nèi)置了 bit 這個模塊，允許程序員在 Lua 程序里使用位運算。學會使用位運算對程序員來說也是一種進步，值得我們一直去研究。
相關推薦：編程視頻
