use table to accelerate bsr calculate

[zdyj3170101136]

在计算bsr的时候，某些操作系统上使用一种for循环的方式计算，时间复杂度是O(n)，n是这个数第从小到大最大的为1的位。
经过golang sdk库math/bits/bits.go/Len函数的启发，我想出了一种算法，具有O（1）的复杂度, 并且计算时间稳定。
并且针对64位操作系统和32位操作系统有不同的优化。
几乎减少了百分之九十的计算时间。

[zdyj3170101136]

性能测试的代码

// Exported (global) variable serving as input for some
// of the benchmarks to ensure side-effect free calls
// are not optimized away.
var Input uint64 = 285870213051353865

// Exported (global) variable to store function results
// during benchmarking to ensure side-effect free calls
// are not optimized away.
var Output int

func BenchmarkLeadingZeros(b *testing.B) {
   var s int
   for i := 0; i < b.N; i++ {
      s += bsr2(uint(Input) >> (uint(i) % bits.UintSize))
   }
   Output = s
}

[zdyj3170101136]

用于对比的代码

func bsr(x uint) int {
	r := 0
	for x != 0 {
		x = x >> 1
		r += 1
	}
	return r - 1
}

[zdyj3170101136]

我写的代码

func bsr2(x uint) int {
	if bits.UintSize == 32 {
		return Len32(uint32(x))
	}
	return Len64(uint64(x))
}

// Len32 returns the minimum number of bits required to represent x; the result is 0 for x == 0.
func Len32(x uint32) (n int) {
	if x >= 1<<16 {
		x >>= 16
		n = 16
	}
	if x >= 1<<8 {
		x >>= 8
		n += 8
	}
	return n + int(bsr8tab[x])
}

// Len64 returns the minimum number of bits required to represent x; the result is 0 for x == 0.
func Len64(x uint64) (n int) {
	if x >= 1<<32 {
		x >>= 32
		n = 32
	}
	if x >= 1<<16 {
		x >>= 16
		n += 16
	}
	if x >= 1<<8 {
		x >>= 8
		n += 8
	}
	return n + int(bsr8tab[x])
}

var bsr8tab = [256]uint8{
	0x00, 0x00, 0x01, 0x01, 0x02, 0x02, 0x02, 0x02, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
	0x03, 0x03, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
	0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
	0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
}

[zdyj3170101136]

性能测试结果对比

goos: darwin
goarch: amd64
pkg: code.byted.org/middleware/mcache
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkLeadingZeros
BenchmarkLeadingZeros-12    	610674840	         1.927 ns/op

goos: darwin
goarch: amd64
pkg: code.byted.org/middleware/mcache
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkLeadingZeros
BenchmarkLeadingZeros-12    	98333178	        12.16 ns/op

[zdyj3170101136]

证明结果无误的例子

func TestBsr(t *testing.T) {
	assert.Equal(t, bsr(4), bsr2(4), 2)
	assert.Equal(t, bsr(24), bsr2(24), 4)
	assert.Equal(t, bsr((1<<10)-1), bsr2((1<<10)-1), 9)
	assert.Equal(t, bsr((1<<30)+(1<<19)+(1<<16)+(1<<1)), bsr2((1<<30)+(1<<19)+(1<<16)+(1<<1)), 30)
}

/usr/local/go/bin/go tool test2json -t /private/var/folders/41/3lxydnv150369kfnhqjbr2j40000gn/T/___TestBsr_in_code_byted_org_middleware_mcache.test -test.v -test.paniconexit0 -test.run ^\QTestBsr\E$
=== RUN TestBsr
--- PASS: TestBsr (0.00s)
PASS

[PureWhiteWu]

要不提个 pr，顺便，Len32 和 Len64 我觉得可以不用暴露出去，改为小写？

[jxskiss]

Len32 和 Len64 合并成单个函数是不是就可以呀，
if bits.UintSize == 32 是常量比较，我理解编译器可以优化掉，所以单个函数也不会增加额外的计算成本吧。

[jxskiss]

个人看法，bits.Len32 和 bits.Len64 这些标准库的函数没必要复制一份？
bits.Len64(x) - 1 跟上面的代码是等价的吧。

[zdyj3170101136]

个人看法，bits.Len32 和 bits.Len64 这些标准库的函数没必要复制一份？
bits.Len64(x) - 1 跟上面的代码是等价的吧。

是的。
我是写完之后才意识到这一点。

[luchsh]

并且针对64位操作系统和32位操作系统有不同的优化。

能贴一下你发现的是哪个库会用到吗？

[zdyj3170101136]

sdk里的一个库 bits.Length

…

2021年6月24日 下午5:18，Jonathan Lu ***@***.***> 写道： 并且针对64位操作系统和32位操作系统有不同的优化。 能贴一下你发现的是哪个库会用到吗？ — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#34 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AMR6Z4PDN75SWKWEFXAD6J3TULZ4ZANCNFSM45DX3TZQ>.

[zdyj3170101136]

go sdk里的一个库bits.length发自我的荣耀手机-------- 原始邮件 --------发件人： Jonathan Lu ***@***.***>日期： 2021年6月24日周四 傍晚5:18收件人： bytedance/gopkg ***@***.***>抄送： 杨杰 ***@***.***>, Author ***@***.***>主 题： Re: [bytedance/gopkg] use table to accelerate bsr calculate (#34) 并且针对64位操作系统和32位操作系统有不同的优化。 能贴一下你发现的是哪个库会用到吗？ —You are receiving this because you authored the thread.Reply to this email directly, view it on GitHub, or unsubscribe.