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

干货满满张哈希

发布于 2021-04-12 14:08:53

8190

发布于 2021-04-12 14:08:53

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

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

十进制中，对于 10 的 N 次方取余，直观来看就是：

其实就是将最后 n 位取出，就是余数。对于二进制，是一样的：

这个运算相当于，对于 n-1 取与：

这个是一个很经典的位运算运用，广泛用于各种高性能框架。例如在生成缓存队列槽位的时候，一般生成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为正整数。