Android上哪个更好除以2还是位移1 [复制链接]

作者

JakeWharton

译者

孙薇，责编

夕颜

头图

CSDN下载自视觉中国

以下为译文：

我一直在将AndroidX集合库移植到Kotlinmultiplatform上，以试验二进制兼容性、性能、工具以及不同的内存模型。库中的某些数据结构使用了基于数组的二叉树来存储元素。Java代码中有大量位移来替代2的幂的乘除法。当移植到Kotlin之后，这些就成了略微有点别扭的中缀运算符，导致代码意图进一步被混淆。

我找了些人来调查对按位移位（bitwiseshifts）与乘除法的看法，很多人听说过移位性能更好的传闻，但每个人对其真实性仍持怀疑态度。一些人认为，代码在CPU上运行之前所见过的一个编译器可用来优化这个案例。

为了满足我的好奇心（部分也是为了避免Kotlin的中缀按位运算符），我打算回答哪个更优的问题，以及一些相关的问题。那么这就开始吧。

有人优化吗？

在代码进入CPU之前，主要经过三个编译器：`javac`/`kotlinc`，D8/R8，以及ART。

它们都有机会对代码进行优化，但它们会这样做吗？

javac

classExample{staticintmultiply(intvalue){returnvalue*2;}staticintdivide(intvalue){returnvalue/2;}staticintshiftLeft(intvalue){returnvalue1;}staticintshiftRight(intvalue){returnvalue1;}}

可以使用JDK14中的javac来编译这段Java代码，并通过javap来显示生成的字节码。

$javacExample.java$javap-cExampleCompiledfromExample.javaclassExample{staticintmultiply(int);Code:0:iload_01:iconst_22:imul3:ireturnstaticintdivide(int);Code:0:iload_01:iconst_22:idiv3:ireturnstaticintshiftLeft(int);Code:0:iload_01:iconst_12:ishl3:ireturnstaticintshiftRight(int);Code:0:iload_01:iconst_12:ishr3:ireturn

以`iload_0`开头的每个方法会加载第一个实参值，之后乘法和除法都包含`iconst_2`，它们加载常量2，然后分别运行`imul`或者`idiv`，以执行整数乘法或整数除法。移位方法在`ishl`或`ishr`之前加载常量1，分别执行整数向左移位和整数向右移位。

这里没有优化，但如果你有对Java有所了解，就知道这并不意外。`javac`并不是一个优化编译器，它将大部分工作留给了JVM上的运行时编译器或者提前编译器。

kotlinc

funmultiply(value:Int)=value*2fundivide(value:Int)=value/2funshiftLeft(value:Int)=valueshl1funshiftRight(value:Int)=valueshr1

使用Kotlin1.4-M1中的`Kotlinc`将Kotlin编译为Java字节码，这样`javap`工具就能再次使用。

$kotlincExample.kt$javap-cExampleKtCompiledfromExample.ktpublicfinalclassExampleKt{publicstaticfinalintmultiply(int);Code:0:iload_01:iconst_22:imul3:ireturnpublicstaticfinalintdivide(int);Code:0:iload_01:iconst_22:idiv3:ireturnpublicstaticfinalintshiftLeft(int);Code:0:iload_01:iconst_12:ishl3:ireturnpublicstaticfinalintshiftRight(int);Code:0:iload_01:iconst_12:ishr3:ireturn

与Java的输出结果完全一致。这是运用了Kotlin原始的JVM后端，但使用基于IR的后端（通过`-Xuse-ir`）也能产生同样的输出。

D8

我们使用Kotlin示例中的Java字节码输出作为由`master`（在文本撰写时是SHA`2a2bfd`）所构建的最新D8的输入。

$java-jar$R8_HOME/build/libs/d8.jar\--release\--output.\ExampleKt.class$dexdump-dclasses.dexOpenedclasses.dex,DEXversionClass#0-ClassdescriptorExampleKt;Accessflags:0x(PUBLICFINAL)Superclassjava/lang/Object;Directmethods-#0inLExampleKt;)nameividetypeI)Iaccess:0x(PUBLICSTATICFINAL)code-08p>[08]ExampleKt.divideI)Ib

iv-int/lit8v0,v1,#int2//#c:0f00

:returnv0#1inLExampleKt;)name:multiplytypeI)Iaccess:0x(PUBLICSTATICFINAL)code-p>[]ExampleKt.multiply:(I)Ia

:mul-int/lit8v0,v1,#int2//#:0f00

:returnv0#2:(inLExampleKt;)name:shiftLefttype:(I)Iaccess:0x(PUBLICSTATICFINAL)code-p>[]ExampleKt.shiftLeft:(I)I:e101

:shl-int/lit8v0,v1,#int1//#c:0f00

:returnv0#3:(inLExampleKt;)name:shiftRighttype:(I)Iaccess:0x(PUBLICSTATICFINAL)code-p>[]ExampleKt.shiftRight:(I)I:e

:shr-int/lit8v0,v1,#int1//#:0f00

:return

(注：输出略微修剪)

Dalvik字节码是基于寄存器的，而不是像Java字节码那样基于堆栈。因此，每种方法只有一个实字节码来执行相关的整数运算。每个寄存器都使用v1寄存器，也是第一个实参值，以及2或1的整型常量。

因此没有更改行为，但D8也不是一个优化编辑器（尽管它可以执行局部方法的优化）。

R8

要运行R8，我们需要定义一项规则，以防止我们的方法被删除。

-keep,allowoptimizationclassExampleKt{methods;}

这些规则通过`--pg-conf`来传递，我们还提供了AndroidAPI来链接使用`--lib`。

$java-jar$R8_HOME/build/libs/r8.jar\--lib$ANDROID_HOME/platforms/android-29/android.jar\--release\--pg-confrules.txt\--output.\ExampleKt.class$dexdump-dclasses.dexOpenedclasses.dex,DEXversionClass#0-ClassdescriptorExampleKt;Accessflags:0x(PUBLICFINAL)Superclassjava/lang/Object;Directmethods-#0:(inLExampleKt;)nameividetype:(I)Iaccess:0x(PUBLICSTATICFINAL)code-08p>[08]ExampleKt.divide:(I)I:db

:div-int/lit8v0,v1,#int2//#c:0f00

:returnv0#1:(inLExampleKt;)name:multiplytype:(I)Iaccess:0x(PUBLICSTATICFINAL)code-:

[]ExampleKt.multiply:(I)I:da

:mul-int/lit8v0,v1,#int2//#:0f00

:returnv0#2:(inLExampleKt;)name:shiftLefttype:(I)Iaccess:0x(PUBLICSTATICFINAL)code-:

[]ExampleKt.shiftLeft:(I)I:e101

:shl-int/lit8v0,v1,#int1//#c:0f00

:returnv0#3:(inLExampleKt;)name:shiftRighttype:(I)Iaccess:0x(PUBLICSTATICFINAL)code-:

[]ExampleKt.shiftRight:(I)I:e

:shr-int/lit8v0,v1,#int1//#:0f00

:return

与D8的输出完全相同。

ART

我们使用R8示例中的Dalvik字节码输出，作为在x86模拟器上的Android10系统运行的ART的输入。

$adbpushclasses.dex/sdcard/classes.dex$adbshellgeneric_x86:/$sugeneric_x86:/#dex2oat--dex-file=/sdcard/classes.dex--oat-file=/sdcard/classes.oatgeneric_x86:/#oatdump--oat-file=/sdcard/classes.oatOatDexFile:0ExampleKt;(offset=0x03c0)(type_idx=1)(Initialized)(OatClassAllCompiled)0:intExampleKt.divide(int)(dex_method_idx=0)CODE:(code_offset=0x1010size_offset=0x100csize=15)...0x10109C8moveax,ecx0x1012Dleaedx,[eax+1]0x10155C0testeax,eax0x:0F4DD0cmovnl/geedx,eax0x101a1FAsaredx0x101c9D0moveax,edx0x101e:C3ret1:intExampleKt.multiply(int)(dex_method_idx=1)CODE:(code_offset=0x1030size_offset=0x0csize=5)...0x10301E1shlecx0x10329C8moveax,ecx0x1034:C3ret2:intExampleKt.shiftLeft(int)(dex_method_idx=2)CODE:(code_offset=0x1030size_offset=0x0csize=5)...0x10301E1shlecx0x1032:89C8moveax,ecx0x1034:C3ret3:intExampleKt.shiftRight(int)(dex_method_idx=3)CODE:(code_offset=0x0size_offset=0x103csize=5)...0x01F9sarecx0x1:89C8moveax,ecx0x4:C3ret

(注意：输出有大幅修剪)x86汇编显示，ART确实介入并规范化了算术运算符以使用移位。

首先，现在`multiply`和`shiftLeft的`实现完全一致。它们都使用`shl`来执行向左按位移位1，此外如果查看文件夹中的偏移量（最左边的列），会发现它们是完全一致的。ART认识到这些函数在编译到x86汇编时具有相同的主体，并已经删除了重复的数据。

下一步，尽管`divide`和`shiftRight`不一样，其对`sar`的用法是一样的，都是向右按位移位1，在`divide`中的四条附加指令通过给值加1，先于`sar`处理输入为负的情况（注释1）。

在Android10系统的Pixel4上运行相同的命令，会显示ART如何将此代码编译到ARM汇编中（注释2）。

OatDexFile:0:LExampleKt;(offset=0x05a4)(type_idx=1)(Verified)(OatClassAllCompiled)0:intExampleKt.divide(int)(dex_method_idx=0)CODE:(code_offset=0x1009size_offset=0x1004size=10)...0x1008:0fc8lsrsr0,r1,#x100a:addsr1,r0,r10x100c:asrsr1,#10x100e:movr0,r10x1010:bxlr1:intExampleKt.multiply(int)(dex_method_idx=1)CODE:(code_offset=0x01size_offset=0x101csize=4)...0x00:lslsr0,r1,#10x02:bxlr2:intExampleKt.shiftLeft(int)(dex_method_idx=2)CODE:(code_offset=0x01size_offset=0x101csize=4)...0x00:lslsr0,r1,#10x02:bxlr3:intExampleKt.shiftRight(int)(dex_method_idx=3)CODE:(code_offset=0x1031size_offset=0x0csize=4)...0x1030:asrsr0,r1,#10x1032:bxlr

同样，`multiply`和`shiftLeft`都使用`lsls`来执行向左位移，因此被去重了。`shiftRight`用`asrs`来执行向右位移。`divide`也使用`asrs`来执行向右位移，但它使用另一个向右位移`lsrs`来处理负值加一的操作（注释3）。

这样一来，我们现在可以肯定地说，用`value1`来替代`value*2`没有任何好处，不要再为了算术运算而这么做了，仅保留用于严格的按位运算。

然而，`value/2`和`value1`仍会产生不同的汇编指令，因而可能具有不同的性能特征。幸运的是，使用`value/2`可避免使用通用除法，并且仍旧主要基于向右位移，因此它们在性能方面差异可能不大。

位移会比除法快一些吗？

为了确定除法快还是位移更快，我们可以使用Jetpackbenchmark库。

classDivideOrShiftTest{