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的比特所在的位数，即时0x8000000000000000里只有一个比特位为1，也要循环64次，有没有办法只关注值为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/records/post/data-structure/2018/09/04/ds-variable-precision-SWAR
https://segmentfault.com/a/1190000015481454

golang的 pprof 使用：
https://blog.golang.org/profiling-go-programs

CPU分支预测模型：
https://zhuanlan.zhihu.com/p/22469702