Maison > Article > Opération et maintenance > Le lien entre les opérations sur les bits et les performances de nginx
Le lien entre les opérations sur les bits et les performances de nginx
- 王林avant
- 2021-01-12 09:53:292257parcourir
Nous savons tous que nginx est célèbre pour ses hautes performances, qui sont principalement dues au code source de nginx. Dans cet article, nous parlerons du lien entre les opérations sur bits et les hautes performances de nginx.
(Partage de vidéos d'apprentissage : Vidéo de programmation)
Les opérations sur les bits peuvent être vues partout dans le code source de Nginx, depuis la définition du type d'instruction (comment de nombreux paramètres peuvent être transportés, il peut apparaître sous quels blocs de configuration), pour marquer s'il y a des données non envoyées dans la requête en cours, et pour utiliser le bit le plus bas du pointeur dans le module d'événement Nginx pour marquer si un événement a expiré, tout dont reflètent la magie et le charme des opérations sur bits.
Cet article présentera et analysera certaines opérations classiques sur les bits dans le code source de Nginx, et se développera pour présenter d'autres techniques d'opération sur les bits.
Alignement
Lorsque Nginx alloue de la mémoire en interne, il accorde une grande attention à l'alignement de l'adresse de départ de la mémoire, c'est-à-dire l'alignement de la mémoire (qui peut conduire à certaines améliorations de performances), ce qui est cohérent avec la recherche du processeur. Cela est lié aux caractéristiques d'adressage. Par exemple, certains processeurs adresseront selon une largeur de 4 octets. Sur une telle machine, on suppose qu'il faut lire 4 octets à partir de 0x46b1e7, car 0x46b1e7. n'est pas sur une limite de 4 octets (0x46b1e7 % 4 = 3), donc lors de la lecture, il sera lu en deux fois. La première fois consiste à lire les 4 octets à partir de 0x46b1e4, puis à supprimer les 3 octets inférieurs ; lisez les 4 mots à partir de la section 0x46b1e8, supprimez l'octet le plus élevé. Nous savons que la vitesse de lecture et d'écriture de la mémoire principale ne peut pas correspondre à celle du processeur, donc deux lectures entraînent évidemment une surcharge plus importante, ce qui entraînera des blocages d'instructions, augmentera le CPI (cycles par instruction) et nuira aux performances de l'application.
Nginx encapsule donc une macro spécifiquement pour les opérations d'alignement.
#define ngx_align(d, a) (((d) + (a - 1)) & ~(a - 1))
Comme le montre le code ci-dessus, cette macro rend d aligné par a, où a doit être une puissance de 2.
Par exemple, lorsque d vaut 17 et a vaut 2, vous obtenez 18 ; lorsque d vaut 15 et a vaut 4, vous obtenez 16 ; lorsque d vaut 16 et a vaut 4, vous obtenez 16.
Cette macro recherche en fait le premier multiple de a supérieur ou égal à d. Puisque a est une puissance de 2, la représentation binaire de a est sous la forme 00...1...00, c'est-à-dire qu'elle n'a qu'un seul 1, donc a - 1 est 00...01...1 . format, alors ~(a - 1) définira tous les n bits faibles à 0, où n est le nombre de 0 consécutifs dans les bits faibles de a. Donc à ce stade, si nous laissons d et ~(a - 1) effectuer une opération ET au niveau du bit, nous pouvons effacer les n bits inférieurs de d Puisque nous devons trouver un nombre supérieur ou égal à d, nous utilisons d +. (une - 1 ).
Bitmap
Bitmap est généralement utilisé pour marquer l'état des choses. Le "bit" se reflète dans le fait que chaque chose est marquée avec un seul bit, ce qui économise de la mémoire et améliore les performances. .
Il existe de nombreux exemples d'utilisation de bitmaps dans Nginx, tels que son allocateur de mémoire partagée (slab), et lors de l'échappement de l'uri (Uniform Resource Identifier), vous devez déterminer si un caractère est un caractère réservé (. ou caractères dangereux), ces caractères doivent être échappés dans %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 */
};Comme indiqué ci-dessus, un tableau simple forme un bitmap, contenant un total de 8 nombres. Chaque nombre représente 32 états, ce bitmap contient donc 256 caractères (y compris le code ASCII étendu). Un bit 0 représente un caractère normal, c'est-à-dire qu'aucun échappement n'est requis, tandis qu'un bit 1 représente un caractère qui doit être échappé.
Alors comment utiliser ce bitmap ? Lorsque Nginx parcourt l'uri, il émet un jugement via une simple instruction.
uri_component[ch >> 5] & (1U << (ch & 0x1f))
Comme indiqué ci-dessus, ch représente le caractère actuel, ch >> 5 consiste à décaler ch 5 bits vers la droite, ce qui a pour effet de diviser par 32. Cette étape détermine le ch dans le uri_component . sur plusieurs nombres ; et à droite, (ch & 0x1f) sort la valeur des 5 bits inférieurs de ch, ce qui équivaut à prendre modulo 32. Cette valeur indique dans quel bit du nombre correspondant ch se trouve (calculé à partir de de bas en haut ); Par conséquent, après avoir effectué une opération ET au niveau du bit sur les valeurs gauche et droite, l'état bitmap où se trouve le caractère ch est supprimé. Par exemple, ch vaut '0' (c'est-à-dire le nombre 48), qui existe sur le 2ème numéro du bitmap (48 >> 5 = 1), et se trouve sur le 16ème bit de ce numéro (0xfc009fff), donc son statut est 0xfc009fff & 0x10000 = 0, donc « 0 » est un caractère universel et n'a pas besoin d'être échappé.
À partir de l'exemple ci-dessus, nous pouvons également voir une autre technique d'opération sur bits, c'est-à-dire que lors de l'exécution d'opérations modulo ou de division sur un nombre qui est une puissance de 2, elle peut également être implémentée via des opérations sur bits. de meilleures performances que les opérations de division directe et modulo, bien qu'avec le bon niveau d'optimisation, le compilateur puisse également effectuer cette optimisation pour nous.
Trouvez la position du bit le plus bas 1
Puis introduisons quelques autres techniques d'application.
Pour trouver la position du 1 le plus bas dans un nombre binaire, vous pouvez intuitivement penser au parcours bit à bit. La complexité temporelle de cet algorithme est O(n), et les performances ne sont pas satisfaisantes.
如果你曾经接触过树状数组，你可能就会对此有不同的看法，树状数组的一个核心概念是 计算 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教程
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!