Java中对于位运算的优化以及运用与思考

Wesley13
• 阅读 711

引言

随着JDK的发展以及JIT的不断优化,我们很多时候都可以写读起来易读但是看上去性能不高的代码了,编译器会帮我们优化代码。之前大学里面学单片机的时候,由于内存以及处理器性能都极其有限(可能很多时候考虑内存的限制优先于处理器),所以很多时候,利用位运算来节约空间或者提高性能,那么这些优秀的思想,放到目前的Java中,是否还有必要这么做呢?我们逐一思考与验证下(其实这也是一个关于Premature optimization的界定的思考)

1. 乘法与左移位

左移一位,相当于乘以2,左移n位,相当于乘以2的n次方。

1 << 1 == 1 * 2 //true
1 << n == 1 * pow(2, n) // true

public int pow(int i, int n) {
    assert n >= 0;
    int result = 1;
    for (int i = 0; i < n; i++) {
        result *= i;
    }
    return result;
}

看上去,移位应该比乘法性能快。那么JIT与JVM虚拟机是否做了一些优化呢?优化分为两部分,一个是编译器优化,另一个是处理器优化。我们先来看看字节码是否一致判断是否有编译优化,例如直接将乘以2优化成左移一位,来编写两个函数:

public void multiply2_1() {
    int i = 1;
    i = i << 1;
}
public void multiply2_2() {
    int i = 1;
    i *= 2;
}

编译好之后,用javap -c来看下编译好的class文件,字节码是:

  public void multiply2_1();
    Code:
       0: iconst_1
       1: istore_1
       2: iload_1
       3: iconst_1
       4: ishl
       5: istore_1
       6: return

  public void multiply2_2();
    Code:
       0: iconst_1
       1: istore_1
       2: iload_1
       3: iconst_2
       4: imul
       5: istore_1
       6: return

可以看出左移是ishl,乘法是imul,从字节码上看编译器并没有优化。那么在执行字节码转换成处理器命令是否会优化呢?是会优化的,在底层,乘法其实就是移位,但是并不是简单地左移

我们来使用jmh验证下,添加依赖:

<dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-core</artifactId>
    <version>1.22</version>
</dependency>
<dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-generator-annprocess</artifactId>
    <version>1.22</version>
</dependency>
<!-- https://mvnrepository.com/artifact/site.ycsb/core -->
<dependency>
    <groupId>site.ycsb</groupId>
    <artifactId>core</artifactId>
    <version>0.17.0</version>
</dependency>

实现思路:

  1. 被乘数的选择:被乘数固定为1,或者是一个极小值或者极大值或者是稀疏值(转换成2进制很多位是0),测试结果没啥太大的参考意义,所以我们选择2的n次方减某一数字作为被乘数

  2. 乘数生成的性能损耗:乘数是2的随机n次方,生成这个的方式要一致,我们这里要测试的仅仅是移位还有乘法运算速度,和实现复杂度没有关系。 实现代码:

    @Benchmark @Warmup(iterations = 0) @Measurement(iterations = 300) public void multiply2_n_shift_not_overflow(Generator generator) { int result = 0; int y = 0; for (int j = 0; j < generator.divide.length; j++) { //被乘数x为2^n - j int x = generator.divide[j] - j; int ri = generator.divide.length - j - 1; y = generator.divide[ri]; result += x * y; //为了和移位测试保持一致所以加上这一步 result += y; } }

    @Benchmark @Warmup(iterations = 0) @Measurement(iterations = 300) public void multiply2_n_mul_not_overflow(Generator generator) { int result = 0; int y = 0; for (int j = 0; j < generator.divide.length; j++) { int x = generator.divide[j] - j; int ri = generator.divide.length - j - 1; //为了防止乘法多了读取导致性能差异,这里虽然没必要,也读取一下 y = generator.divide[ri]; result += x << ri; //为了防止虚拟机优化代码将上面的给y赋值踢出循环,加上下面这一步 result += y; } }

测试结果:

Benchmark                 Mode  Cnt         Score         Error  Units
BitUtilTest.multiply2_n_mul_not_overflow    thrpt  300  35882831.296 ±  48869071.860  ops/s
BitUtilTest.multiply2_n_shift_not_overflow  thrpt  300  59792368.115 ±  96267332.036  ops/s

可以看出,左移位相对于乘法还是有一定性能提升的

2. 除法和右移位

这个和乘法以及左移位是一样的.直接上测试代码:

@Benchmark
@Warmup(iterations = 0)
@Measurement(iterations = 300)
public void divide2_1_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 divide2_1_2(Generator generator) {
    int result = 0;
    for (int j = 0; j < generator.divide.length; j++) {
        int l = generator.divide[j];
        result += Integer.MAX_VALUE >> j;
    }
}

结果:

Benchmark                                    Mode  Cnt         Score           Error  Units
BitUtilTest.divide2_n_div                   thrpt  300  10219904.214 ±   5787618.125  ops/s
BitUtilTest.divide2_1_shift                 thrpt  300  44536470.740 ± 113360206.643  ops/s

可以看出,右移位相对于除法还是有一定性能提升的

3. “取余”与“取与”运算

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

十进制中,对于10的n次方取余,直观来看就是: Java中对于位运算的优化以及运用与思考 其实就是将最后n位取出,就是余数。 对于二进制,是一样的: Java中对于位运算的优化以及运用与思考 这个运算相当于,对于n-1取与: Java中对于位运算的优化以及运用与思考

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

进一步的,奇偶性判断就是看对2取余是否为0,那么就相当于对(2-1)=1取与

4. 求与数字最接近的2的n次方

这个广泛运用于各种API优化,上文中提到,2的n次方是一个好东西。我们在写框架的很多时候,想让用户传入一个必须是2的n次方的参数来初始化某个资源池,但这样不是那么灵活,我们可以通过用户传入的数字N,来找出不大于N的最大的2的n次方,或者是大于N的最小的2的N次方。

抽象为比较直观的理解就是,找一个数字最左边的1的左边一个1(大于N的最小的2的N次方),或者是最左边的1(小于N的最大的2的N次方),前提是这个数字本身不是2的n次方。

Java中对于位运算的优化以及运用与思考

那么,如何找呢?一种思路是,将这个数字最高位1之后的所有位都填上1,最后加一,就是大于N的最小的2的N次方。右移一位,就是小于N的最大的2的N次方。

如何填补呢?可以考虑按位或计算,我们知道除了0或0=0以外,其他的都是1. 我们现在有了最左面的1,右移一位,与原来按位或,就至少有了两位是1,再右移两位并按位或,则至少有四位为1。。。以此类推:

Java中对于位运算的优化以及运用与思考

用代码表示是:

n |= n >>> 1; 
n |= n >>> 2; 
n |= n >>> 4; 
n |= n >>> 8; 
n |= n >>> 16;
n += 1;  //大于N的最小的2的N次方
n = n >>> 1; //小于N的最大的2的N次方

如果有兴趣,可以看一下Java的ForkJoinPool类的构造器,其中的WorkQueue大小,就是通过这样的转换得来的。

5. 交换两个数字

这个在单片机编程中经常会使用这个位运算性质:一个数字异或自己为零,一个数字异或0为自己本身。那么我们就可以利用这个性质交换两个数字。

假设有数字x,y。 我们有x^y^y = x^(y^y)= x^0 = x 还有x^y^y^x^y = 0^y = y 那么我们可以利用:

x = x ^ y;
y = x ^ y; //代入后就是x^y^y
x = x ^ y; //代入后就是x^y^y^x^y

这个方法虽然很巧妙,但是是一种时间换空间的方式; 我们常用的利用另一个变量实现交换是一种空间换时间的方式,来对比下性能:

@Benchmark
@Warmup(iterations = 0)
@Measurement(iterations = 300)
public int swap_1() {
    int x = Integer.MAX_VALUE, y = Integer.MAX_VALUE / 2;
    int z = x;
    x = y;
    y = z;
    return x + y;
}


@Benchmark
@Warmup(iterations = 0)
@Measurement(iterations = 300)
public int swap_2() {
    int x = Integer.MAX_VALUE, y = Integer.MAX_VALUE / 2;
    x ^= y;
    y ^= x;
    x ^= y;
    return x + y;
}

结果:

Benchmark            Mode  Cnt          Score           Error  Units
BitUtilTest.swap_1  thrpt  300  267787894.370 ± 559479133.393  ops/s
BitUtilTest.swap_2  thrpt  300  265768807.925 ± 387039155.884  ops/s

测试来看,性能差异并不明显,利用位运算减少了空间占用,减少了GC,但是交换减少了cpu运算,但是GC同样是消耗cpu计算,所以,很难界定。目前还是利用中间变量交换的更常用,也更易读一些

6. bit状态位

我们为了节省空间,尝尝利用一个数字类型(例如long类型)作为状态数,每一位代表一个状态是true还是false。假设我们使用long类型,则一个状态数可以最多表示64个属性。代码上一般这么写:

public static class Test {
    //如果你的field是会被并发修改访问,那么最好还是加上缓存行填充防止false sharing
    @jdk.internal.vm.annotation.Contended
    private long field;

    private static final long SWITCH_1_MASK = 1;
    private static final long SWITCH_2_MASK = 1 << 1;
    private static final long SWITCH_3_MASK = 1 << 2;

    public boolean isSwitch1On() {
        return (field & SWITCH_1_MASK) == 1;
    }

    public void turnOnSwitch1() {
        field |= SWITCH_1_MASK;
    }

    public void turnOffSwitch1() {
        field &= ~SWITCH_1_MASK;
    }
}

这样能节省大量空间,在实际应用中,很多地方做了这种优化。最直接的例子就是,Java对象的对象头:

|-------------------------------------------------------|--------------------|
|                  Mark Word (32 bits)                  |       State        |
|-------------------------------------------------------|--------------------|
| identity_hashcode:25 | age:4 | biased_lock:1 | lock:2 |       Normal       |
|-------------------------------------------------------|--------------------|
|  thread:23 | epoch:2 | age:4 | biased_lock:1 | lock:2 |       Biased       |
|-------------------------------------------------------|--------------------|
|               ptr_to_lock_record:30          | lock:2 | Lightweight Locked |
|-------------------------------------------------------|--------------------|
|               ptr_to_heavyweight_monitor:30  | lock:2 | Heavyweight Locked |
|-------------------------------------------------------|--------------------|
|                                              | lock:2 |    Marked for GC   |
|-------------------------------------------------------|--------------------|

7. 位计数

基于6,有时候我们想某个状态数里面,有多少个状态是true,就是计算这个状态数里面多少位是1.

比较朴素的方法就是:先判断n的奇偶性,为奇数时计数器增加1,然后将n右移一位,重复上面的步骤,直到移位完毕。

高效一点的方法通过:

  1. n & (n - 1) 可以移除最后一位1 (假设最后一位本来是0, 减一后必为1,0 & 1为 0, 最后一位本来是1,减一后必为0,0 & 1为 0)

  2. 移除了最后一位1之后,计数加1,如果结果不为零,则用结果继续第一步。

    int n = Integer.MAX_VALUE; int count = 0; while(n != 0) { n &= n -1; count++; }

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Souleigh ✨ Souleigh ✨
3年前
前端性能优化 - 雅虎军规
无论是在工作中,还是在面试中,web前端性能的优化都是很重要的,那么我们进行优化需要从哪些方面入手呢?可以遵循雅虎的前端优化35条军规,这样对于优化有一个比较清晰的方向.35条军规1.尽量减少HTTP请求个数——须权衡2.使用CDN(内容分发网络)3.为文件头指定Expires或CacheControl,使内容具有缓存性。4.避免空的
Wesley13 Wesley13
3年前
Java多线程优化
\以下文章来源于51CTO技术栈 ,作者崔皓今天,我们从Java内部锁优化,代码中的锁优化,以及线程池优化几个方面展开讨论。Java 内部锁优化当使用Java多线程访问共享资源的时候,会出现竞态的现象。即随着时间的变化,多线程“写”共享资源的最终结果会有所不同。为了解决这个问题,让多线程“写”资源的时候有先后顺序,引入
Easter79 Easter79
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Stella981 Stella981
3年前
Redis企业级应用
   我们在做项目的时候经常会遇到很多性能的问题,也成为整个系统优化最疼痛的问题,主要还是因为在用户量大的时候或者就是说高并发访问的时候,我们系统的数据库会有一个限制。当然也可以通过对数据库的优化对系统进行优化,(最常见的数据库优化手段无非就是建索引,explain分析慢sql,以及sql语句的优化或者分库分表等一系列的策略,当然后面我会专门写一篇文章专
为什么mysql不推荐使用雪花ID作为主键
作者:毛辰飞背景在mysql中设计表的时候,mysql官方推荐不要使用uuid或者不连续不重复的雪花id(long形且唯一),而是推荐连续自增的主键id,官方的推荐是auto_increment,那么为什么不建议采用uuid,使用uuid究
京东云开发者 京东云开发者
2个月前
聊聊JVM如何优化
首先应该明确的是JVM调优不是常规手段,JVM的存在本身就是为了减轻开发对于内存管理的负担,当出现性能问题的时候第一时间考虑的是代码逻辑与设计方案,以及是否达到依赖中间件的瓶颈,最后才是针对JVM进行优化。1.JVM内存模型针对JAVA8的模型进行讨论,J