bitcount优化之路

leeright · · 552 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

**问题:** 使用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=.` , 输出如下: ![1.jpg](https://upload-images.jianshu.io/upload_images/18516712-72859eb9b124daf1.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) 平均一次执行时间 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 跑一下测试, ![2.jpg](https://upload-images.jianshu.io/upload_images/18516712-672ffb681a60f147.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) 性能并没有改观,甚至更糟糕了一点。。。 不过在数值较小的情况下,执行时间的确短很多,比如输入是 1 的情况下: ![3.jpg](https://upload-images.jianshu.io/upload_images/18516712-fef8b6373f46374c.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) 上一版的实现对应是 41.5ns ![4.jpg](https://upload-images.jianshu.io/upload_images/18516712-b81fd0a72a2d8a30.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) **方案二:** 方案一里的实现受限于最高位值为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 } 跑一下测试: ![5.jpg](https://upload-images.jianshu.io/upload_images/18516712-da2aecaaa665f781.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) 时间降到原来1/3的水平了,提升还是很给力。 如果输入n是1的话,测试结果: ![6.jpg](https://upload-images.jianshu.io/upload_images/18516712-9d169ead67a0f96c.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) 和第一版里优化过的结果旗鼓相当。 **方案三:** 上两个版本的结果都受数值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 } 测试结果如下: ![7.jpg](https://upload-images.jianshu.io/upload_images/18516712-eb3a156c0072c59f.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) 11.6ns ! 只有方案二里的1/3了! 不过在n为1的时候,表现稍差,达到了9.9ns 。 ![8.jpg](https://upload-images.jianshu.io/upload_images/18516712-3c86858babfacb5c.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) 将表的大小改为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 } ![9.jpg](https://upload-images.jianshu.io/upload_images/18516712-5252a16a77f7ac6f.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) 当输入n为1的时候,只需要3.06ns,表现要好很多: ![10.jpg](https://upload-images.jianshu.io/upload_images/18516712-27f5aa07aefd0511.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) 实际上,当输入从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 左右。 ![11.jpg](https://upload-images.jianshu.io/upload_images/18516712-bd51b7437a08bcab.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) 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% ![12.jpg](https://upload-images.jianshu.io/upload_images/18516712-5bf6fb5f9e823ca4.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) **附:** 查表法的实现,可以把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作为函数的局部变量: ![13.jpg](https://upload-images.jianshu.io/upload_images/18516712-d1d794aa54fa4c87.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) table作为全局变量: ![14.jpg](https://upload-images.jianshu.io/upload_images/18516712-8e3d3bea12dc69ef.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) 当n为0时,耗时: ![15.jpg](https://upload-images.jianshu.io/upload_images/18516712-32e9fb43b18f16e9.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) 当n为0xffffffffffffffff时,耗时: ![16.jpg](https://upload-images.jianshu.io/upload_images/18516712-55564759aef1d4e0.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) **总结:** 在上述实现的迭代优化过程中,主要思路是降低循环内代码块的执行次数,从固定的64降到取决于最高一个1的位置,再降到比特值为1的比特位的数量,最后通过查表或者分治降低到常数次数操作(按8bit建表时最多查8次,分治固定6次),查表需要执行一次函数栈内分配数组空间和赋值的过程,会耗时较多;而分治耗时低且表现稳定,是生产环境实现中最常采用的算法。 ![17.jpg](https://upload-images.jianshu.io/upload_images/18516712-76a908fb359b70a4.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) **参考:** 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

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

552 次点击  
加入收藏 微博
上一篇:Golang安装gRPC
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传