每日一面 - 为何我们经常使用 2 的 N 次方作为分片数量？

Love The Way You Lie 2023-01-09 15:44 103阅读 0赞

分片算法经常是计算一个值之后，对于分片个数取模，计算到底使用哪个分片。我们经常看到很多地方高性能的代码设计，都是将分片数量设置为 2 的 N 次方。例如 ForkJoinPool 的任务队列 WorkQueue 的大小，MyCat 的某些分片算法在计算分片的时候对于分片数量如果是 2 的 N 次方也有优化，那么为什么呢？

**对于 2 的 N 次方取余，相当于对 2 的 N 次方减一取与运算**， N 为正整数。为什么呢？通过下图就能很容易理解：

十进制中，对于 10 的 N 次方取余，直观来看就是：  
![image][]  
其实就是将最后 n 位取出，就是余数。  
对于二进制，是一样的：  
![image][image 1]  
这个运算相当于，对于 n-1 取与：  
![image][image 2]

这个是一个很经典的位运算运用，广泛用于各种高性能框架。例如在生成缓存队列槽位的时候，一般生成2的n次方个槽位，因为这样在选择槽位的时候，就可以用取与代替取余；java 中的 ForkJoinPool 的队列长度就是定为 2 的 N 次方；netty 中的缓存池的叶子节点都是 2 的 N 次方，当然这也是因为是平衡二叉查找树算法的实现。

我们来看下性能会好多少：

@Benchmark
    @Warmup(iterations = 0)
    @Measurement(iterations = 300)
    public void mod2_n_1(Generator generator) {
        int result = 0;
        for (int j = 0; j < generator.divide.length; j++) {
            int l = generator.divide[j];
            result += Integer.MAX_VALUE % l;
        }
    }
    
    @Benchmark
    @Warmup(iterations = 0)
    @Measurement(iterations = 300)
    public void mod2_n_2(Generator generator) {
        int result = 0;
        for (int j = 0; j < generator.divide.length; j++) {
            int l = generator.divide[j];
            result += Integer.MAX_VALUE & (l - 1);
        }
    }

结果：

Benchmark                                    Mode  Cnt         Score           Error  Units
    BitUtilTest.mod2_n_1                        thrpt  300  10632698.855 ±   5843378.697  ops/s
    BitUtilTest.mod2_n_2                        thrpt  300  80339980.989 ±  21905820.262  ops/s

同时，我们从这里也可以引申出，**判断一个数是否是2的 N 次方的方法，就是看这个数与这个数减一取与运算看是否是0，如果是，则是 2 的 N 次方， N为正整数**。  
![image][image 3]

**每日一刷，轻松提升技术，斩获各种offer：**

![image][image 4]

[image]: /images/20221119/12623ba083a942d79c51817521c98796.png
[image 1]: /images/20221119/dcbdf0c4e86e4cb2b8ba1fbac78c2b34.png
[image 2]: /images/20221119/3f513a8c974948b6953a6214e4ed0321.png
[image 3]: /images/20221119/d0c0c1a6290c4a22a1ab5a4124eee4fe.png
[image 4]: /images/20221119/b1300b4641bb4e7d91a96ccd8ef8e48e.png