비트 연산과 nginx 성능 간의 연결
- 王林앞으로
- 2021-01-12 09:53:292269검색
우리 모두는 nginx가 고성능으로 유명하다는 것을 알고 있는데, 이는 주로 nginx의 소스 코드 때문입니다. 이 기사에서는 비트 연산과 nginx 고성능 간의 연결에 대해 설명합니다.
(학습 동영상 공유: 프로그래밍 동영상)
비트 작업은 Nginx 소스 코드의 모든 곳에서 볼 수 있으며, 명령어 유형 정의(수행할 수 있는 매개변수 수, 구성 블록이 나타날 수 있음), 현재 요청이 아직 전송되지 않은 데이터가 있고 포인터의 가장 낮은 비트는 Nginx 이벤트 모듈에서 이벤트가 만료되었는지 여부를 표시하는 데 사용됩니다. 이는 모두 비트 작업의 마법과 매력을 반영합니다.
이 기사에서는 Nginx 소스 코드의 일부 고전적인 비트 연산을 소개 및 분석하고 다른 비트 연산 기술을 소개하도록 확장합니다.
Alignment
Nginx는 내부적으로 메모리를 할당할 때 메모리 시작 주소의 정렬, 즉 메모리 정렬(일부 성능 향상으로 이어질 수 있음)에 큰 주의를 기울입니다. 이는 프로세서의 주소 지정 특성과 관련이 있습니다. 특정 처리와 같은 프로세서는 4바이트 너비에 따라 주소를 지정합니다. 이러한 머신에서는 0x46b1e7이 4바이트 경계(0x46b1e7 % 4 = 3)에 있지 않기 때문에 0x46b1e7부터 시작하는 4바이트를 읽어야 한다고 가정합니다. )이므로 읽을 때 두 단계로 읽습니다. 처음에는 0x46b1e4부터 4바이트를 읽고 하위 3바이트를 꺼낸 다음 0x46b1e8부터 4바이트를 읽고 가장 높은 바이트를 꺼냅니다. 우리는 주 메모리 읽기 및 쓰기 속도가 CPU와 일치할 수 없다는 것을 알고 있으므로 두 번의 읽기는 분명히 더 큰 오버헤드를 가져와 명령 지연을 일으키고 CPI(명령당 사이클)를 증가시키며 애플리케이션 성능을 저하시킵니다.
그래서 Nginx는 정렬 작업을 위해 특별히 매크로를 캡슐화합니다.
#define ngx_align(d, a) (((d) + (a - 1)) & ~(a - 1))
위 코드에 표시된 것처럼 이 매크로는 d를 a로 정렬합니다. 여기서 a는 2의 거듭제곱이어야 합니다.
예를 들어, d가 17이고 a가 2이면 d가 15이고 a가 4이면 16이 되고, d가 16이고 a가 4이면 16이 됩니다.
이 매크로는 실제로 d보다 크거나 같은 첫 번째 a의 배수를 찾고 있습니다. a는 2의 거듭제곱이므로 a의 이진수 표현은 00...1...00 형식입니다. 즉, 1이 하나만 있으므로 a - 1은 00...01...1입니다. 형식을 사용하면 ~(a - 1)은 모든 하위 n 비트를 0으로 설정합니다. 여기서 n은 a의 하위 비트에 있는 연속 0의 수입니다. 그래서 이때 d와 ~(a - 1)을 비트별 AND 연산을 수행하게 하면 d의 하위 n 비트를 지울 수 있습니다. d보다 크거나 같은 수를 찾아야 하므로 d +를 사용합니다. (a-1).
Bitmap
비트맵은 일반적으로 사물의 상태를 표시하는 데 사용됩니다. "비트"는 각 사물이 단 하나의 비트로 표시된다는 사실에 반영되어 메모리를 절약하고 성능을 향상시킵니다.
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로 나누는 효과가 있습니다. 이 단계에서는 uri_comComponent에 있는 ch의 개수를 결정합니다. 오른쪽에서 (ch & 0x1f)는 ch의 하위 5비트를 가져옵니다. 이는 모듈로 32를 사용하는 것과 같습니다. 이 값은 ch의 어느 숫자가 해당 숫자(낮은 숫자에서 높은 숫자로 계산)에 있는지를 나타냅니다. 양쪽 값에 대해 비트별 AND 연산을 수행한 후 ch 문자가 위치한 비트맵 상태를 꺼냅니다. 예를 들어, ch는 '0'(즉, 숫자 48)이며, 이는 비트맵의 두 번째 숫자(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 중국어 웹사이트의 기타 관련 기사를 참조하세요!