前两天在帮女朋友写代码进行一些数学计算，开始量很小，但后来需要对所有的 32 位数字进行计算。之前的代码无法完成这么大的运算量，所以进行了优化，这篇博客记录代码的优化点。
先通过例子解释一个名词：移位等价
- 二进制数 0001 的移位等价的数有且只有 0010/0100/1000
- 0000/0001/0011/0101/0111/1111 这些数移位不等价
下面按照我优化的顺序记录，其中的截图是使用 pprof 生成的，用来找出占用 cpu 时间较多的操作。
优化算法
程序中首先要做的是要找出 32 位数中所有移位不等价的数，我开始的方法是这样的：
- 使用数组保存所有移位不等价的数
- 使用两个嵌套的循环分别遍历所有 32 位数和所有已经加入到数组中的数，找出所有移位不等价的数
这个方法的时间复杂度是O(n^2)。而 32 位数一共有 42 亿个，这么大的量级使用 O(n^2）的算法是自寻死路。
优化方法很简单：将数组换成 map，如果一个数的所有移位等价的数都不在 map 中，那么将这个数放入 map。这样时间复杂度就从 O(n^2) 降到 O(n)。
我又做了进一步优化，先算出数 a 最小的移位等价的值 min，再判断一次 min 是否在 map中（减少读 map 的次数）。
移除不必要的重复计算
第一次 pprof 显示耗时最多的是 math.Pow()，查看代码发现数值的移位函数中会使用 math.Pow() 计算 2^n（n 的范围是 [0, 32]），并且移位函数调用的次数非常多。这种情况没必要每次都计算一遍 2^n，修改成当程序启动时计算出需要的平方值然后保存到 map 中，需要时直接从 map 取结果即可。
以数组替换 map
pprof 显示访问 map 耗时较长，是因为上面把 2^n 结果保存在了 map 中，因为此 map 的 key 是 [0, 32]，所以可以用数组替换 map，以 [0, 32] 做为数组索引来取得对应的平方值。
定义 slice 时指定容量
growslice 表示 slice 进行了扩容，扩容需要在堆中查找足够大的空间并复制原数据。通过排查找到了有问题的代码，幸运的是这个 slice 的最大长度不会超过32，所以修改为 s := make([]T, 0, 32)。
串行改为并行
整个程序可简单的划为两步：1.找出所有移位不等价的数 2.将这些数进行后续计算。
32 位数一共有 42 亿个数字，要等第一步全部执行完后再执行第二步的话肯定会拉长整个程序的处理时间。
可以将第一步看做生产者，第二步看成消费者，生产者计算出一个有效的数值后将其写入 channel，消费者再从 channel 中取得这些值进行后续计算，这样两步运算能够并行执行，提高效率。
避免加锁
除了使生产者和消费者并行执行外，还可以创建多个生产者和多个消费者，充分利用多核。但生产者在计算移位不等价的数值时需要读写全局的 map，并发情况下肯定需要加锁，对于单个计算耗时很短但量特别大的情况下并行并加锁可能会有反作用。
但是具体到这个 case，因为重量（1 的个数，例如 0101 的重量是 2）不同的数肯定是移位不等价的，这样就可以将一个全局的 map 按重量拆分成多个 map（一个重量用一个 map，32 位的数使用 33 个 map），相同重量的数只在同一个 goroutine 中计算，这样一个 map 只会被一个 goroutine 读写，就没有加锁的必要了。
减少 channel 的读写次数
优化为并行后再次使用 pprof 测试，得到了上图结果。可以看出从 channel 中读数据成了耗时最多的操作。
go 有一句名言:
Do not communicate by sharing memory;
instead, share memory by communicating.
虽然推荐用 channel 来共享数据，但 channel 并不是对性能没有影响的。我的代码会通过 channel 共享大量数据（10 亿的数量级），而且数据的生产和消费耗时很短，这时对 channel 的操作就成了瓶颈。所以要将操作 channel 的次数降低。
优化方法很简单，之前 channel 的类型是 chan T，将其改为 chan []T，生产者计算出一个值后先保存到 slice ，待 slice 长度达到指定值时再将 slice 写入 channel，相当于将大量小数据打包后再通过 channel 传递。这样明显降低了 channel 的读写次数，优化后读 channel 的 cpu 占用从 54% 降到了 1.6%。
使用高性能机器
公司 32 核测试机比我的 4 核 mac 计算快多了😂
就写到这吧，我要去给女朋友买炸鸡腿了🐔
