비트 연산과 nginx 성능 간의 연결

우리 모두는 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  /.-, +*)( &#39;&%$ #"!  */
        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 중국어 웹사이트의 기타 관련 기사를 참조하세요!