Golang中为什么这个函数的性能更好？

Golang中为什么这个函数的性能更好？ https://go-review.googlesource.com/c/go/+/245177

在此修改中，为什么右移后性能会大幅提升？根据我的测试，不同的数据集会影响性能效果。测试数据/e.txt文件效果很好。然而，对于文本文件，效果一般，原因是什么？ 有人感兴趣吗？

3 回复

感谢您的回复，我觉得我理解了这部分内容。

Nick Craig-Wood 通过 Go Forum forum@golangbridge.org 写道：

更多关于Golang中为什么这个函数的性能更好？的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


从提交信息中得知

在计算哈希值时，改变移位次数以生成更多哈希位置，从而避免存储冲突

LZW压缩的工作原理是在先前的输入中查找匹配项。这些匹配项是通过先前输入的哈希表找到的。

从源代码中可以看到

	// table 是从 20 位键到 12 位值的哈希表。每个表
	// 条目包含 key<<12|val，冲突通过线性探测解决。
	// 键由 12 位代码前缀和 8 位字节后缀组成。
	// 值是 12 位代码。
	table [tableSize]uint32

线性探测部分意味着如果检测到哈希冲突，它会以线性 O(n) 的方式在哈希表中向前探测。因此，如果哈希函数设计不当，操作复杂度将从 O(1) 降级为 O(n)。

这项改进优化了哈希函数。更少的冲突意味着更少的线性探测，从而带来更快的性能。

希望这能有所帮助！

这个修改性能提升的关键在于用右移操作替代了除法运算。在Go语言中，整数右移比除法运算更快，因为右移是位操作，而除法需要更复杂的算术运算。

具体分析代码修改：

// 修改前
bucket := hash & (uint32(1)<<lg - 1)

// 修改后  
bucket := hash >> (32 - lg)

当lg是2的幂时（比如哈希表大小是2的幂），这两种计算方式是等价的，但右移操作的性能更好。对于e.txt文件效果明显，可能是因为该文件的数据分布使得哈希冲突较少，位操作的优势更明显。

对于文本文件效果一般，原因可能是：

  1. 文本数据的哈希分布不同，导致更多的哈希冲突
  2. 文本数据可能使其他部分的代码成为瓶颈（如字符串处理）
  3. 不同的数据模式影响了CPU的分支预测和缓存行为

示例测试代码：

func benchmarkShiftVsDivide(b *testing.B) {
    hash := uint32(0x12345678)
    lg := uint32(4) // 16个桶
    
    b.Run("divide", func(b *testing.B) {
        for i := 0; i < b.N; i++ {
            _ = hash & ((1 << lg) - 1)
        }
    })
    
    b.Run("shift", func(b *testing.B) {
        for i := 0; i < b.N; i++ {
            _ = hash >> (32 - lg)
        }
    })
}

这种优化在哈希表实现中很常见，特别是当表大小是2的幂时，用位操作代替模运算能显著提升性能。

回到顶部