ビット操作とnginxのパフォーマンスの関係
- 王林転載
- 2021-01-12 09:53:292257ブラウズ
nginx がその高いパフォーマンスで有名であることは誰もが知っていますが、それは主に nginx のソース コードによるものです。この記事では、ビット操作と nginx の高性能の関係について説明します。
(学習ビデオ共有: プログラミング ビデオ)
ビット操作は、命令の種類の定義 (方法) から、Nginx のソース コードのいたるところで見ることができます。現在のリクエストに未送信のデータがあるかどうかをマークするため、および Nginx イベント モジュールのポインタの最下位ビットを使用してイベントの有効期限が切れているかどうかをマークするために、多くのパラメータを運ぶことができます。これらはビット演算の魔法と魅力を反映しています。
この記事では、Nginx ソース コードのいくつかの古典的なビット操作を紹介して分析し、さらに他のビット操作テクニックも紹介します。
アライメント
Nginx が内部でメモリを割り当てるときは、メモリ開始アドレスのアライメント、つまり、一貫性のあるメモリ アライメント (パフォーマンスの向上につながる可能性があります) に細心の注意を払います。これは、アドレス指定の特性に関連しています。たとえば、一部のプロセッサは 4 バイト幅に従ってアドレス指定します。そのようなマシンでは、0x46b1e7 は読み込まれないため、0x46b1e7 から始まる 4 バイトを読み取る必要があると想定されます。 4 バイト境界 (0x46b1e7 % 4 = 3) にあるため、読み取る場合は 2 回に分けて読み取られます。1 回目は 0x46b1e4 から始まる 4 バイトを読み取り、下位 3 バイトを取り出し、次に 4 バイトを読み取ります。 0x46b1e8セクションから始まるワードの最上位バイトを取り出します。メイン メモリの読み取りと書き込みの速度は CPU に匹敵しないことがわかっているため、2 回の読み取りでは明らかにオーバーヘッドが大きくなり、命令ストールが発生し、CPI (命令あたりのサイクル数) が増加し、アプリケーションのパフォーマンスに悪影響を及ぼします。
つまり、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 の倍数を探しています。 a は 2 の累乗であるため、a のバイナリ表現は 00...1...00 の形式になります。つまり、1 が 1 つだけあるため、a - 1 は 00...01...1 となります。 . 形式の場合、~(a - 1) は下位 n ビットをすべて 0 に設定します (n は a の下位ビットにある連続する 0 の数です)。したがって、このとき、d と ~(a - 1) のビットごとの AND 演算を実行すると、d の下位 n ビットをクリアできます。d 以上の数を見つける必要があるため、d ( a - 1) 以上です。
ビットマップ
ビットマップは通常、物事のステータスをマークするために使用されます。「ビット」は、各物事が 1 ビットだけでマークされるという事実に反映されており、これによりメモリが節約され、パフォーマンスが向上します。
Nginx には、共有メモリ アロケータ (スラブ) などのビットマップの使用例が多数あり、uri (Uniform Resource Identifier) をエスケープするときに、文字が予約文字であるかどうかを判断する必要があります。または安全でない文字）、そのような文字は %XX にエスケープする必要があります。
static uint32_t uri_component[] = {
0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
/* ?>=< ;:98 7654 3210 /.-, +*)( '&%$ #"! */
0xfc009fff, /* 1111 1100 0000 0000 1001 1111 1111 1111 */
/* _^]\ [ZYX WVUT SRQP ONML KJIH GFED CBA@ */
0x78000001, /* 0111 1000 0000 0000 0000 0000 0000 0001 */
/* ~}| {zyx wvut srqp onml kjih gfed cba` */
0xb8000001, /* 1011 1000 0000 0000 0000 0000 0000 0001 */
0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
0xffffffff /* 1111 1111 1111 1111 1111 1111 1111 1111 */
};上に示したように、単純な配列は合計 8 つの数値を含むビットマップを形成し、各数値は 32 の状態を表すため、このビットマップには 256 文字 (拡張 ASCII コードを含む) が含まれます。ビット 0 は通常の文字、つまりエスケープが必要ない文字を表し、ビット 1 はエスケープする必要がある文字を表します。
それでは、このビットマップをどのように使用するのでしょうか? Nginx が URI を走査するとき、単純なステートメントを通じて判断を行います。
uri_component[ch >> 5] & (1U << (ch & 0x1f))
上に示すように、ch は現在の文字を表し、ch >> 5 は ch を 5 ビット右にシフトし、32 で割る効果があります。このステップは ch の位置を決定します。 uri_component. ではいくつかの数値を対象とし、右側の (ch & 0x1f) は ch の下位 5 ビットの値を取り出しますが、これは 32 を法とすることと同じです。この値は、対応する数値 ch のどのビットが含まれるかを示します。 ( low から high まで計算); したがって、左右の値のビットごとの AND 演算を実行した後、ch 文字が配置されているビットマップ状態が取り出されます。たとえば、ch は '0' (つまり、数値 48) であり、これはビットマップの 2 番目の数値 (48 >> 5 = 1) に存在し、この数値の 16 番目のビット (0xfc009fff) にあります。したがって、そのステータスは 0xfc009fff & 0x10000 = 0 であるため、「0」はユニバーサル文字であり、エスケープする必要はありません。
上記の例から、別のビット演算手法もわかります。つまり、2 のべき乗の数値に対してモジュロ演算または除算演算を実行する場合、ビット演算を通じて実装することもできます。直接除算やモジュロ演算よりもパフォーマンスが向上しますが、最適化レベルが適切であれば、コンパイラがこの最適化を実行することもあります。
最下位ビット 1 の位置を見つける
それでは、その他の応用スキルを紹介しましょう。
デジタル バイナリで最も低い 1 の位置を見つけるには、直感的にビット単位のトラバーサルを思い浮かべるかもしれませんが、このアルゴリズムの時間計算量は O(n) であり、パフォーマンスは満足のいくものではありません。
如果你曾经接触过树状数组，你可能就会对此有不同的看法，树状数组的一个核心概念是 计算 lowbit，即计算一个数字二进制里最低位 1 的幂次。它之所以有着不错的时间复杂度（O(logN)），便是因为能够在 O(1) 或者说常数的时间内得到答案。
int lowbit(int x)
{
return x & ~(x - 1);
}这个技巧事实上和上述对齐的方式类似，比如 x 是 00...111000 这样的数字，则 x - 1 就成了 00...110111，对之取反，则把原本 x 低位连续的 0 所在的位又重新置为了 0（而原本最低位 1 的位置还是为 1），我们会发现除了最低位 1 的那个位置，其他位置上的值和 x 都是相反的，因此两者进行按位与操作后，结果里只可能有一个 1，便是原本 x 最低位的 1。
寻找最高位 1 的位置
换一个问题，这次不是寻找最低位，而是寻找最高位的 1。
这个问题有着它实际的意义，比如在设计一个 best-fit 的内存池的时候，我们需要找到一个比用户期望的 size 大的第一个 2 的幂次。
同样地，你可能还是会先想到遍历。
事实上 Intel CPU 指令集有这么一条指令，就是用以计算一个数二进制里最高位 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 位的，则上面函数的最后一步 input |= input >> 32 是不需要的，具体执行多少次 input |= input >> m， 是由 input 的位长决定的，比如 8 位则进行 3 次，16 位进行 4 次，而 32 位进行 5 次。
为了更简洁地进行描述，我们用 8 位的数字进行分析，设一个数 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 的个数
如何计算一个数字二进制表示里有多少个 1 呢？
直觉上可能还是会想到遍历（遍历真是个好东西），让我们计算下复杂度，一个字节就是 O(8)，4 个字节就是 O(32)，而 8 字节就是 O(64)了。
如果这个计算会频繁地出现在你的程序里，当你在用 perf 这样的性能分析工具观察你的应用程序时，它或许就会得到你的关注，而你不得不去想办法进行优化。
事实上《深入理解计算机系统》这本书里就有一个这个问题，它要求计算一个无符号长整型数字二进制里 1 的个数，而且希望你使用最优的算法，最终这个算法的复杂度是 O(8)。
long fun_c(unsigned long x)
{
long val = 0;
int i;
for (i = 0; i < 8; i++) {
val += x & 0x0101010101010101L;
x >>= 1;
}
val += val >> 32;
val += val >> 16;
val += val >> 8;
return val & 0xFF;
}这个算法在我的另外一篇文章里曾有过分析。
观察 0x0101010101010101 这个数，每 8 位只有最后一位是 1。那么 x 与之做按位与，会得到下面的结果：
设 A[i] 表示 x 二进制表示里第 i 位的值（0 或 1）。 第一次： A[0] + (A[8] << 8) + (A[16] << 16) + (A[24] << 24) + (A[32] << 32) + (A[40] << 40) + (A[48] << 48) + (A[56] << 56) 第二次： A[1] + (A[9] << 8) + (A[17] << 16) + (A[25] << 24) + (A[33] << 32) + (A[41] << 40) + (A[49] << 48) + (A[57] << 56) ...... 第八次： A[7] + (A[15] << 8) + (A[23] << 16) + (A[31] << 24) + (A[39] << 32) + (A[47] << 40) + (A[55] << 48) + (A[63] << 56) 相加后得到的值为： (A[63] + A[62] + A[61] + A[60] + A[59] + A[58] + A[57] + A[56]) << 56 + (A[55] + A[54] + A[53] + A[52] + A[51] + A[50] + A[49] + A[48]) << 48 + (A[47] + A[46] + A[45] + A[44] + A[43] + A[42] + A[41] + A[40]) << 40 + (A[39] + A[38] + A[37] + A[36] + A[35] + A[34] + A[33] + A[32]) << 32 + (A[31] + A[30] + A[29] + A[28] + A[27] + A[26] + A[25] + A[24]) << 24 + (A[23] + A[22] + A[21] + A[20] + A[19] + A[18] + A[17] + A[16]) << 16 + (A[15] + A[14] + A[13] + A[12] + A[11] + A[10] + A[9] + A[8]) << 8 + (A[7] + A[6] + A[5] + A[4] + A[3] + A[2] + A[1] + A[0])
之后的三个操作：
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]) << 24 + (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]) << 16 + (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]) << 8 + (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])
第二次折半（val += val >> 16）后，得到的 val 的低 16 位：
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]) << 8 + (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])
第三次折半（val += val >> 8）后，得到的 val 的低 8 位：
(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])
可以看到，经过三次折半，64 个位的值全部累加到低 8 位，最后取出低 8 位的值，就是 x 这个数字二进制里 1 的数目了，这个问题在数学上称为“计算汉明重量”。
位运算以它独特的优点（简洁、性能棒）吸引着程序员，比如 LuaJIT 内置了 bit 这个模块，允许程序员在 Lua 程序里使用位运算。学会使用位运算对程序员来说也是一种进步，值得我们一直去研究。
相关推荐：nginx教程
以上がビット操作とnginxのパフォーマンスの関係の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。