1. 首页
  2. Nginx私房菜

我眼中的 Nginx(一):Nginx 和位运算

作者张超:又拍云系统开发高级工程师,负责又拍云 CDN 平台相关组件的更新及维护。Github ID: tokers,活跃于 OpenResty 社区和 Nginx 邮件列表等开源社区,专注于服务端技术的研究;曾为 ngx_lua 贡献源码,在 Nginx、ngx_lua、CDN 性能优化、日志优化方面有较为深入的研究。

众所周知 Nginx 以性能而出名,这和它优秀的代码实现有着密切的关系,而本文所要讲述的——位运算,也是促成 Nginx 优秀性能的原因之一。

位运算在 Nginx 的源码是处处可见,从定义指令的类型(可以携带多少参数,可以出现在哪些配置块下),到标记当前请求是否还有未发送完的数据,再到 Nginx 事件模块里用指针的最低位来标记一个事件是否过期,无不体现着位运算的神奇和魅力。

本文会介绍和分析 Nginx 源码里的一些经典的位运算使用,并扩展介绍一些位其他的位运算技巧。

对齐

Nginx 内部在进行内存分配时,非常注意内存起始地址的对齐,即内存对齐(可以换来一些性能上的提升),这与处理器的寻址特性有关,比如某些处理器会按 4 字节宽度寻址,在这样的机器上,假设需要读取从 0x46b1e7 开始的 4 个字节,由于 0x46b1e7 并不处在 4 字节边界上(0x46b1e7 % 4 = 3),所以在进行读的时候,会分两次进行读取,第一次读取 0x46b1e4 开始的 4 个字节,并取出低 3 字节;再读取 0x46b1e8 开始的 4 个字节,取出最高的字节。我们知道读写主存的速度并不能匹配 CPU,那么两次的读取显然带来了更大的开销,这会引起指令停滞,增大 CPI(每指令周期数),损害应用程序的性能。

因此 Nginx 封装了一个宏,专门用以进行对齐操作。


\#define ngx_align(d, a) (((d) + (a - 1)) & ~(a - 1)) //JS中文网 – 前端进阶资源分享 https://www.javascriptc.com/ 趣聊CSS系列

如上代码所示,该宏使得 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,所以 a – 1 便是 00…01…1 这样的格式,那么 ~(a – 1) 就会把低 n 位全部置为 0,其中 n 是 a 低位连续 0 的个数。所以此时如果我们让 d 和 ~(a – 1) 进行一次按位与操作,就能够把 d 的低 n 位清零,由于我们需要寻找大于等于 d 的数,所以用 d + (a – 1) 即可。

位图

位图,通常用以标记事物的状态,“位” 体现在每个事物只使用一个比特位进行标记,这即节约内存,又能提升性能。

Nginx 里有多处使用位图的例子,比如它的共享内存分配器(slab),再比如在对 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 在对应数字的第几个位(从低到高计算);因此左右两边的值进行一次按位与操作后,就把 ch 字符所在的位图状态取出来了。比如 ch 是 ‘0’(即数字 48),它存在于位图的第 2 个数字上(48 >> 5 = 1),又在这个数字(0xfc009fff)的第 16 位上,所以它的状态就是 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 程序里使用位运算。学会使用位运算对程序员来说也是一种进步,值得我们一直去研究。

作者:又拍云
链接:https://juejin.im/post/6844903785274277902

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「IT平头哥联盟」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:我眼中的 Nginx(一):Nginx 和位运算

链接:https://www.javascriptc.com/4199.html

« Vue3 模板编译原理
用uniapp开发微信小程序的心得 – 总结与思考»
Flutter 中文教程资源

相关推荐

QR code