Java求余% Java求余%操作引发的一连串故事

软件发布|下载排行|最新软件

当前位置:首页IT学院IT技术

Java求余% Java求余%操作引发的一连串故事

kelthuzadx   2021-05-28 我要评论
想了解Java求余%操作引发的一连串故事的相关内容吗,kelthuzadx在本文为您仔细讲解Java求余%的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Java求余%,Java求余,下面大家一起来学习吧。

操作符%通常用在正整数上,但同样可以用在负整数和浮点数上。
  注意:只有当被除数是负数时, 余数才是负的。

C1 RCE对%的处理

HotSpot VM的C1有个RCE(Range Check Elimination,范围检查消除)优化,所谓范围检查消除,就是为了正确的抛出数组越界异常,虚拟机需要在数组访问的一些地方插入隐式的检查,但是这些检查会降低性能,比如在循环中每次循环都得检查一次,所以HotSpot VM会想办法在可能的地方消除这些检查。我在看C1 RCE的时候发现目前它对求余符号的支持较为薄弱,它只能处理形如下面的代码:

arr[x%arr.length] // 只有除数是x.length的时候,才能应用RCE优化

如果余数是整数常量,它就不能工作了:

arr[x%3]
for(int i=0;i<10;i++){
  arr[x%10]
}

实际上,根据JLS的定义,我们知道如果除数为整数常量(且等于零,因为0作为除数会抛出运行时异常),是可以推导出结果的上下界的(也取决于被除数的正负),规则如下:

  • x % -y ==> [0, y - 1]
  • x % y ==> [0, y - 1]
  • -x % y ==> [-y + 1, 0]
  • -x % -y ==> [-y + 1, 0]

于是,我给JDK发了个patch,这个问题算是解决了。但是Nils提到,C2是否有相同的优化呢?后面Tobias帮忙确认了一下C2没有,我再后来也进一步确认了,所以下一步是调研C2是否能应用同样的优化。

调研为C2应用同样的优化

本来以为是比较trivial的事情,为求余节点的类型系统加点代码,推导一下上下界即可,实际上我也这么做的,但是最后发现这样没有消除上下界。默认开启-XX:+GenerateRangeChecks后,在数组访问过程中(Parse::array_addressing),C2仍然生成了范围检查。

调试后发现推导上下界根本没有执行,因为C2创建完求余节点后,会执行一个IGVN的过程,即迭代的应用多种优化,其中就包括理想化,C2理想化是指应用很多局部小优化的过程,在这个例子中就是特殊处理形如x%2^n,x%2^n-1x%1的情况,如果除数是整数常量,它还会使用一个来自https://book.douban.com/subject/1784887/书里面的算法,即Division by Invariant Integers using Multiplication(by Granlund and Montgomery),搜了一下知乎有类似的文章,想要了解细节可以读读https://zhuanlan.zhihu.com/p/151038723。知道了原因,于是我改了下代码,禁止了求余节点的理想化,心想这总可以了吧。

还是不行

是的,还是不行。尽管我已经禁止了对求余符号的理想化优化,但是范围检查还是生成了。。。我又继续看代码,发现除了理想化的这个优化之外,C2在IR(中间表示)构造的过程中又 又 又 又 又对求余运算做了个优化!如果除数是正整数常量,且是2^n,那么C2会对它进行变形,IR如图所示:

左边的IR是 IR构造的时候C2做的优化后的效果,右边是理想化优化后的效果。实际上它们做的事情本身是比较重复的,而且经过测试发现,理想化优化的算法要好于IR构造过程中的优化,所以我又提了个patch解决这个问题(不过还在review中)。

结语

我认为为求余节点推导上下界也是有意义的,如果以后有其他优化会变形为求余运算,那么它们可以应用这个推导,同时,为求余做统一完善的类型推导这件事本身也是正确的,所以我又提了个patch。可以看到,最终我只消除了C1 arr[x%4]的范围检查,还是没能消除C2 arr[x%4]的范围检查,是不是以后可以说C1有的地方做的比C2好了(狗头hh。

猜您喜欢

Copyright 2022 版权所有 软件发布 访问手机版

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 联系我们