Heim > Artikel > Betrieb und Instandhaltung > Der Zusammenhang zwischen Bitoperationen und Nginx-Leistung
Der Zusammenhang zwischen Bitoperationen und Nginx-Leistung
- 王林nach vorne
- 2021-01-12 09:53:292213Durchsuche
Wir alle wissen, dass Nginx für seine hohe Leistung bekannt ist, was hauptsächlich auf den Quellcode von Nginx zurückzuführen ist. In diesem Artikel werden wir über den Zusammenhang zwischen Bitoperationen und der hohen Leistung von Nginx sprechen.
(Teilen von Lernvideos: Programmiervideo)
Bitoperationen sind überall im Quellcode von Nginx zu sehen, von der Definition der Art der Anweisungen (wie viele Parameter können übertragen werden, unter welchen Konfigurationsblöcken können angezeigt werden), um zu markieren, ob die aktuelle Anfrage noch nicht gesendete Daten enthält, und das niedrigste Bit des Zeigers wird im Nginx-Ereignismodul verwendet, um zu markieren, ob ein Ereignis abgelaufen ist, was alles die Magie und den Charme von Bitoperationen widerspiegelt.
In diesem Artikel werden einige klassische Bitoperationen im Nginx-Quellcode vorgestellt und analysiert und um einige andere Bitoperationstechniken erweitert.
Ausrichtung
Wenn Nginx intern Speicher zuweist, legt es großen Wert auf die Ausrichtung der Speicherstartadresse, also auf die Speicherausrichtung (was zu einigen Leistungsverbesserungen führen kann). Dies hängt mit den Adressierungseigenschaften des Prozessors zusammen. Beispielsweise wird der Prozessor entsprechend der 4-Byte-Breite adressieren. Auf einer solchen Maschine wird davon ausgegangen, dass 4 Bytes ab 0x46b1e7 gelesen werden müssen, da 0x46b1e7 nicht an einer 4-Byte-Grenze liegt (0x46b1e7 % 4 = 3). ), also beim Lesen wird es in zwei Schritten gelesen: Das erste Mal werden die 4 Bytes ab 0x46b1e4 gelesen und die unteren 3 Bytes herausgenommen. Dann werden die 4 Bytes ab 0x46b1e8 gelesen und das höchste Byte herausgenommen. Wir wissen, dass die Lese- und Schreibgeschwindigkeit des Hauptspeichers nicht mit der der CPU mithalten kann, sodass zwei Lesevorgänge offensichtlich einen größeren Overhead mit sich bringen, was zu Befehlsblockaden führt, den CPI (Zyklen pro Befehl) erhöht und die Leistung der Anwendung beeinträchtigt.
Also kapselt Nginx ein Makro speziell für Ausrichtungsvorgänge.
#define ngx_align(d, a) (((d) + (a - 1)) & ~(a - 1))
Wie im obigen Code gezeigt, bewirkt dieses Makro, dass d durch a ausgerichtet wird, wobei a eine Potenz von 2 sein muss.
Wenn d beispielsweise 17 und a 2 ist, erhalten Sie 18; wenn d 15 und a 4 ist, erhalten Sie 16; wenn d 16 und a 4 ist, erhalten Sie 16.
Dieses Makro sucht tatsächlich nach dem Vielfachen des ersten a, das größer oder gleich d ist. Da a eine Potenz von 2 ist, hat die binäre Darstellung von a die Form 00...1...00, das heißt, sie hat nur eine 1, also ist a - 1 00...01...1 . Format, dann setzt ~(a - 1) alle niedrigen n Bits auf 0, wobei n die Anzahl der aufeinanderfolgenden Nullen in den niedrigen Bits von a ist. Wenn wir also zu diesem Zeitpunkt eine bitweise UND-Verknüpfung zwischen d und ~(a - 1) durchführen, können wir die unteren n Bits von d löschen. Da wir eine Zahl finden müssen, die größer oder gleich d ist, verwenden wir d + (a - 1 ).
Bitmap
Bitmap wird normalerweise verwendet, um den Status von Dingen zu markieren. Das „Bit“ spiegelt sich in der Tatsache wider, dass jedes Ding nur mit einem Bit markiert ist, was Speicherplatz spart und die Leistung verbessert.
Es gibt viele Beispiele für die Verwendung von Bitmaps in Nginx, z. B. den Shared-Memory-Allocator (Slab), und beim Escapen von uri (Uniform Resource Identifier) müssen Sie feststellen, ob ein Zeichen ein reserviertes sicheres Zeichen ist (oder nicht). ), müssen solche Zeichen in %XX maskiert werden.
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 */
};Wie oben gezeigt, bildet ein einfaches Array eine Bitmap, die insgesamt 8 Zahlen enthält. Jede Zahl repräsentiert 32 Zustände, sodass diese Bitmap 256 Zeichen enthält (einschließlich erweitertem ASCII-Code). Ein Bit von 0 stellt ein normales Zeichen dar, das heißt, es ist kein Escape erforderlich, während ein Bit von 1 ein Zeichen darstellt, das maskiert werden muss.
Wie verwendet man diese Bitmap? Wenn Nginx die URI durchquert, fällt es eine Beurteilung durch eine einfache Anweisung.
uri_component[ch >> 5] & (1U << (ch & 0x1f))
Wie oben gezeigt, stellt ch das aktuelle Zeichen dar. ch >> 5 dient dazu, ch um 5 Bits nach rechts zu verschieben, was eine Division durch 32 zur Folge hat. Dieser Schritt bestimmt, welche Anzahl von ch in uri_component enthalten ist. Auf der rechten Seite entfernt (ch & 0x1f) die unteren 5 Bits von ch, was der Verwendung von Modulo 32 entspricht. Dieser Wert gibt an, welche Ziffer von ch in der entsprechenden Zahl enthalten ist (berechnet von niedrig nach hoch); Nach dem Ausführen einer bitweisen UND-Operation für die Werte auf beiden Seiten wird der Bitmap-Status herausgenommen, in dem sich das CH-Zeichen befindet. Beispielsweise ist ch „0“ (d. h. die Zahl 48), die auf der zweiten Zahl der Bitmap (48 >> 5 = 1) vorhanden ist und sich auf dem 16. Bit dieser Zahl (0xfc009fff) befindet. Der Status ist also 0xfc009fff und 0x10000 = 0, daher ist „0“ ein universelles Zeichen und muss nicht maskiert werden.
Aus dem obigen Beispiel können wir auch eine andere Bitoperationstechnik erkennen, das heißt, wenn eine Modulo- oder Divisionsoperation an einer Zahl durchgeführt wird, die eine Potenz von 2 ist, kann diese auch durch Bitoperationen implementiert werden, was besser als direkt ist Divisions- und Modulo-Operationen bieten eine bessere Leistung, obwohl der Compiler mit der richtigen Optimierungsstufe solche Optimierungen möglicherweise auch für uns durchführen kann.
Finden Sie die Position des niedrigsten Bits 1
Dann stellen wir einige andere Anwendungsfähigkeiten vor.
Um die Position der niedrigsten 1 in einer digitalen Binärdatei zu finden, können Sie intuitiv an eine bitweise Durchquerung denken. Die zeitliche Komplexität dieses Algorithmus ist O(n) und die Leistung ist nicht zufriedenstellend.
如果你曾经接触过树状数组，你可能就会对此有不同的看法，树状数组的一个核心概念是 计算 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教程
Das obige ist der detaillierte Inhalt vonDer Zusammenhang zwischen Bitoperationen und Nginx-Leistung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!