乐趣区

bitcount优化之路

问题:

使用 Go 实现 bitcount 函数,统计一个 uint64 型数值中被设置为 1 的比特位的数量。

方案一:

最容易想到的实现就是每次右移一位,检测最后一位是否是 1,这样完成挨个比特检测后,就可以得出结果。

func bitCount1(n uint64)int8{
   var count int8

   var i uint

   for i < 64 {if ( (n >> i) & 1) != 0{count += 1}

      i += 1
   }

   return count
}

var BitCount = bitCount1



实现一个测试函数和一个基准测试函数测试正确性和性能:

测试环境:

型号名称:MacBook Pro
处理器名称:Intel Core i7
处理器速度:2.5 GHz
处理器数目:1
核总数:4
L2 缓存(每个核):256 KB
L3 缓存:6 MB
超线程技术:已启用
内存:16 GB

// main_test.go

package main

import "testing"

var tests = []struct{
   input uint64
   want int8
}{{ 7118255637391829670 , 34},
   {7064722311543391783 , 25},
   {4608963400064623015 , 34},
   {14640564048961355682 , 39},
   {8527726038136987990 , 27},
   {9253052485357177493 , 29},
   {8999835155724014433 , 28},
   {14841333124033177794 , 35},
   {1220369398144154468 , 33},
   {15451339541988045209 , 33},
   {2516280747705128559 , 28},
   {4938673901915240208 , 29},
   {410238832127885933 , 29},
   {1332323607442058439 , 33},
   {15877566392368361617 , 30},
   {3880651382986322995 , 35},
   {3639402890245875445 , 30},
   {16428413304724738456 , 39},
   {14754380477986223775 , 37},
   {2517156707207435586 , 29},
   {15317696849870933326 , 30},
   {6013290537376992905 , 35},
   {17378274584566732685 , 29},
   {5420397259425817882 , 31},
   {11286722219793612146 , 35},
   {8183954261149622513 , 30},
   {17190026713975474863 , 41},
   {379948598362354167 , 34},
   {3606292518508638567 , 31},
   {10997458781072603457 , 33},
   {7601699521132896572 , 31},
   {16795555978365209258 , 34},
   {9555709025715093094 , 35},
   {2957346674371128176 , 29},
   {6297615394333342337 , 36},
   {15800332447329707343 , 31},
   {10989482291558635871 , 36},
   {10116688196032604814 , 29},
   {13017684861263524258 , 29},
   {9721224553709591475 , 35},
   {7710983100732971068 , 28},
   {11089894095639460077 , 38},
   {938751439326355368 , 34},
   {8732591979705398236 , 33},
   {5679915963518233779 , 36},
   {16532909388555451248 , 33},
   {13248011246533683006 , 31},
   {1317996811516389703 , 30},
   {4318476060009242000 , 33},
   {3082899072464871007 , 34},
}

func TestBitCount(t *testing.T){

   for _, test := range tests{if got := BitCount(test.input); got != test.want{t.Errorf("BitCount(%q) = %v", test.input, got)
      }

   }
}

func BenchmarkBitCount(b *testing.B) {
   var input uint64 = 5679915963518233779

   for i := 0; i < b.N; i ++{BitCount(input)
   }
}

命令行执行 go test -bench=.,输出如下:

平均一次执行时间 91.2ns

for 循环固定执行了 64 次,可以稍作优化,因为输入数值的第 64 个比特不一定是 1,只要检测到最高位的那个 1 就可以结束了。

func bitCount11(n uint64) int8{
   var count int8

   for n != 0 {if ( n & 1) != 0{count += 1}

      n = n >> 1
   }

   return count
}

var BitCount = bitCount11

跑一下测试,

性能并没有改观,甚至更糟糕了一点。。。不过在数值较小的情况下,执行时间的确短很多,比如输入是 1 的情况下:

上一版的实现对应是 41.5ns

方案二:

方案一里的实现受限于最高位值位 1 的比特所在的位数,有没有办法只关注值为 1 的比特的数量呢?熟悉位操作的话,很容易想到 n = n &(n-1)可以将 n 的最低一个值为 1 的比特位置为 0,比如 14 & 13 = (0b1110) & (0b1101) = 0b1100。这样数值 n 中有 M 个值为 1 的比特位,循环检测的次数就是 M 次了。

func bitCount2(n uint64)int8{
   var count int8

   for n != 0{n = n & ( n - 1)
      count += 1
   }

   return count
}

跑一下测试:

时间降到原来 1 / 3 的水平了,提升还是很给力。

如果输入 n 是 1 的话,测试结果:

和第一版里优化过的结果旗鼓相当。

方案三:

上两个版本的结果都受数值 n 中值为 1 的比特位数量 M 的影响,有不有常数时间的算法呢?空间换时间的思路很容易想到查表,将一个字节 (8 位) 的所有可能值和对应的值为 1 的比特位数 M 预先写入表中,然后将 n 分成 8 个字节去查表,将结果相加就行了。

func bitCount31(n uint64)int8{table := [256]int8{
      0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
      4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
   };

   var count int8

   for n != 0 {count += table[n & 0xff]
      n = n >> 8
   }

   return count
}

测试结果如下:

11.6ns ! 只有方案二里的 1 / 3 了!

不过在 n 为 1 的时候,表现稍差,达到了 9.9ns。

将表的大小改为 16 个(即对 4 bit 建表),可以得到另一个有趣的结果:

func bitCount32(n uint64)int8{table := [16]int8{0, 1, 1, 2, 1, 2, 2, 3,  1, 2, 2, 3, 2, 3, 3, 4}

   var count int8 = 0

   for n != 0 {count += table[n & 0xf]
      n = n >> 4
   }

   return count
}


当输入 n 为 1 的时候,只需要 3.06ns,表现要好很多:

实际上,当输入从 0x0 增长到 0xffffffffffffffff 的过程中(每次左移 4 位,并将最低 4 位置为 0xf),前者耗时由 8.86ns 线性增长到 11.6ns,后者耗时由 2.41ns 线性增长到 11.5ns,因此用 4bit 建表效果更好。

方案四:

用分治的思路,同样可以常数时间内得出结果。将 n 的比特位依次按 2 一组,4 一组,8 一组,16 一组,32 个一组,64 个一组,计算出 1 的位数即可。以 0b1111 为例,两个一组得到:1 1,1 1,将组内的每个位的值相加,得到这个组 1 的个数:10,10,然后按 4 个一组,将组内的值相加,得到 0b10+0b10 = 0b100,对应的十进制值是 4,就是 0b1111 的 1 的个数。(这个算法叫 variable-precision SWAR 算法,更详细的介绍可以看文末的参考链接)

func bitCount41(n uint64)int8 {n = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
   n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333)
   n = (n & 0x0f0f0f0f0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f0f0f0f0f)
   n = (n & 0x00ff00ff00ff00ff) + ((n >> 8) & 0x00ff00ff00ff00ff)
   n = (n & 0x0000ffff0000ffff) + ((n >> 16) & 0x0000ffff0000ffff)
   n = (n & 0x00000000ffffffff) + ((n >> 32) & 0x00000000ffffffff)

   return int8(n & 0x7f)
}

只要 5.23ns,比查表的实现降低了一半。而且当 n 为 0 或者 0xffffffffffffffff,结果稳定在 5.23ns 左右。

uint64 最多 64 个 1,64 对应的二进制值不会超出一个字节,针对不必要的计算,我们再做一下优化:

func bitCount42(n uint64)int8 {n = n - ((n >> 1) & 0x5555555555555555)
   n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333)
   n = (n & 0x0f0f0f0f0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f0f0f0f0f)
   n = n + (n >> 8)
   n = n + (n >> 16)
   n = n + (n >> 32)
   return int8(n & 0x7f)
}

耗时降到了 3.91ns ! 降到接近查表法的 1/ 3 了,降到了第一版实现的 3.91/91.2 = 4.3%

附:

查表法的实现,可以把 table 放在函数外(作为全局变量),这样基准测试数据更好看。table 放在函数内的话,每次调用会在栈里面分配空间放 table 数组的值,这个过程会比较耗时。table 作为全局变量的话,按 4bit 建表和按 8bit 建表的测试结果正好反过来,当 n 为 0 时,二者耗时都是 2ns,当 n = 0xffffffffffffffff,前者耗时还是约 11.5ns,后者耗时约 7ns。当 n = 0xffffff(24 位全 1)时,后者耗时约 4ns,和方案 4 的耗时相当。因此当输入大部分分布在 0xffffff 以内时,选择 8bit 建表的查表法,时间性能更优。

可以借助 pprof 分析一下两者在代码层面的耗时。

命令行里依次执行:

$ go test -c main_test.go main.go

$ ./main.test -test.bench=. -test.cpuprofile=cpu-profile.prof

$ go tool pprof main.test cpu-profile.prof


接着在 pprof 的输入:weblist bitCount

table 作为函数的局部变量:

table 作为全局变量:

当 n 为 0 时,耗时:

当 n 为 0xffffffffffffffff 时,耗时:

总结:

在上述实现的迭代优化过程中,主要思路是降低循环内代码块的执行次数,从固定的 64 降到取决于最高一个 1 的位置,再降到比特值为 1 的比特位的数量,最后通过查表或者分治降低到常数次数操作(按 8bit 建表时最多查 8 次,分治固定 6 次),查表需要执行一次函数栈内分配数组空间和赋值的过程,会耗时较多;而分治耗时低且表现稳定,是生产环境实现中最常采用的算法。

参考:

variable-precision SWAR 算法:

https://ivanzz1001.github.io/…
https://segmentfault.com/a/11…

golang 的 pprof 使用:

https://blog.golang.org/profi…

CPU 分支预测模型:

https://zhuanlan.zhihu.com/p/…

退出移动版