Android 上哪个更好：除以 2 还是位移 1？

打开网易新闻 查看更多图片

作者 | Jake Wharton

译者 | 孙薇，责编 | 夕颜

头图 | CSDN下载自视觉中国

出品 | CSDN（ID:CSDNnews）

以下为译文：

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

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

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

有人优化吗？

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

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

javac

class Example {static int multiply(int value) {return value * 2;}static int divide(int value) {return value / 2;}static int shiftLeft(int value) {return value << 1;}static int shiftRight(int value) {return value >> 1;}}

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

$ javac Example.java$ javap -c ExampleCompiled from "Example.java"class Example {static int multiply(int);Code:0: iload_01: iconst_22: imul3: ireturn

static int divide(int);Code:0: iload_01: iconst_22: idiv3: ireturn

static int shiftLeft(int);Code:0: iload_01: iconst_12: ishl3: ireturn

static int shiftRight(int);Code:0: iload_01: iconst_12: ishr3: ireturn

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

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

kotlinc

fun multiply(value: Int) = value * 2fun divide(value: Int) = value / 2fun shiftLeft(value: Int) = value shl 1fun shiftRight(value: Int) = value shr 1

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

$ kotlinc Example.kt$ javap -c ExampleKtCompiled from "Example.kt"public final class ExampleKt {public static final int multiply(int);Code:0: iload_01: iconst_22: imul3: ireturn

public static final int divide(int);Code:0: iload_01: iconst_22: idiv3: ireturn

public static final int shiftLeft(int);Code:0: iload_01: iconst_12: ishl3: ireturn

public static final int shiftRight(int);Code:0: iload_01: iconst_12: ishr3: ireturn

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

D8

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

$ java -jar $R8_HOME/build/libs/d8.jar \--release \--output . \ExampleKt.class$ dexdump -d classes.dexOpened 'classes.dex', DEX version '035'Class #0 -Class descriptor : 'LExampleKt;'Access flags : 0x0011 (PUBLIC FINAL)Superclass : 'Ljava/lang/Object;'Direct methods -#0 : (in LExampleKt;)name : 'divide'type : '(I)I'access : 0x0019 (PUBLIC STATIC FINAL)code -000118: |[000118] ExampleKt.divide:(I)I000128: db00 0102 |0000: div-int/lit8 v0, v1, #int 2 // #0200012c: 0f00 |0002: return v0

#1 : (in LExampleKt;)name : 'multiply'type : '(I)I'access : 0x0019 (PUBLIC STATIC FINAL)code -000130: |[000130] ExampleKt.multiply:(I)I000140: da00 0102 |0000: mul-int/lit8 v0, v1, #int 2 // #02000144: 0f00 |0002: return v0

#2 : (in LExampleKt;)name : 'shiftLeft'type : '(I)I'access : 0x0019 (PUBLIC STATIC FINAL)code -000148: |[000148] ExampleKt.shiftLeft:(I)I000158: e000 0101 |0000: shl-int/lit8 v0, v1, #int 1 // #0100015c: 0f00 |0002: return v0

#3 : (in LExampleKt;)name : 'shiftRight'type : '(I)I'access : 0x0019 (PUBLIC STATIC FINAL)code -000160: |[000160] ExampleKt.shiftRight:(I)I000170: e100 0101 |0000: shr-int/lit8 v0, v1, #int 1 // #01000174: 0f00 |0002: return


(注：输出略微修剪)

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

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

R8

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

-keep,allowoptimization class ExampleKt {;}

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

$ java -jar $R8_HOME/build/libs/r8.jar \--lib $ANDROID_HOME/platforms/android-29/android.jar \--release \--pg-conf rules.txt \--output . \ExampleKt.class$ dexdump -d classes.dexOpened 'classes.dex', DEX version '035'Class #0 -Class descriptor : 'LExampleKt;'Access flags : 0x0011 (PUBLIC FINAL)Superclass : 'Ljava/lang/Object;'Direct methods -#0 : (in LExampleKt;)name : 'divide'type : '(I)I'access : 0x0019 (PUBLIC STATIC FINAL)code -000118: |[000118] ExampleKt.divide:(I)I000128: db00 0102 |0000: div-int/lit8 v0, v1, #int 2 // #0200012c: 0f00 |0002: return v0

#1 : (in LExampleKt;)name : 'multiply'type : '(I)I'access : 0x0019 (PUBLIC STATIC FINAL)code -000130: |[000130] ExampleKt.multiply:(I)I000140: da00 0102 |0000: mul-int/lit8 v0, v1, #int 2 // #02000144: 0f00 |0002: return v0

#2 : (in LExampleKt;)name : 'shiftLeft'type : '(I)I'access : 0x0019 (PUBLIC STATIC FINAL)code -000148: |[000148] ExampleKt.shiftLeft:(I)I000158: e000 0101 |0000: shl-int/lit8 v0, v1, #int 1 // #0100015c: 0f00 |0002: return v0

#3 : (in LExampleKt;)name : 'shiftRight'type : '(I)I'access : 0x0019 (PUBLIC STATIC FINAL)code -000160: |[000160] ExampleKt.shiftRight:(I)I000170: e100 0101 |0000: shr-int/lit8 v0, v1, #int 1 // #01000174: 0f00 |0002: return

与D8的输出完全相同。

ART

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

$ adb push classes.dex /sdcard/classes.dex$ adb shellgeneric_x86:/ $ sugeneric_x86:/ # dex2oat --dex-file=/sdcard/classes.dex --oat-file=/sdcard/classes.oatgeneric_x86:/ # oatdump --oat-file=/sdcard/classes.oatOatDexFile:0: LExampleKt; (offset=0x000003c0) (type_idx=1) (Initialized) (OatClassAllCompiled)0: int ExampleKt.divide(int) (dex_method_idx=0)CODE: (code_offset=0x00001010 size_offset=0x0000100c size=15)...0x00001010: 89C8 mov eax, ecx0x00001012: 8D5001 lea edx, [eax + 1]0x00001015: 85C0 test eax, eax0x00001017: 0F4DD0 cmovnl/ge edx, eax0x0000101a: D1FA sar edx0x0000101c: 89D0 mov eax, edx0x0000101e: C3 ret1: int ExampleKt.multiply(int) (dex_method_idx=1)CODE: (code_offset=0x00001030 size_offset=0x0000102c size=5)...0x00001030: D1E1 shl ecx0x00001032: 89C8 mov eax, ecx0x00001034: C3 ret2: int ExampleKt.shiftLeft(int) (dex_method_idx=2)CODE: (code_offset=0x00001030 size_offset=0x0000102c size=5)...0x00001030: D1E1 shl ecx0x00001032: 89C8 mov eax, ecx0x00001034: C3 ret3: int ExampleKt.shiftRight(int) (dex_method_idx=3)CODE: (code_offset=0x00001040 size_offset=0x0000103c size=5)...0x00001040: D1F9 sar ecx0x00001042: 89C8 mov eax, ecx0x00001044: C3 ret

(注意：输出有大幅修剪)

x86汇编显示，ART确实介入并规范化了算术运算符以使用移位。

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

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

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

OatDexFile:0: LExampleKt; (offset=0x000005a4) (type_idx=1) (Verified) (OatClassAllCompiled)0: int ExampleKt.divide(int) (dex_method_idx=0)CODE: (code_offset=0x00001009 size_offset=0x00001004 size=10)...0x00001008: 0fc8 lsrs r0, r1, #310x0000100a: 1841 adds r1, r0, r10x0000100c: 1049 asrs r1, #10x0000100e: 4608 mov r0, r10x00001010: 4770 bx lr1: int ExampleKt.multiply(int) (dex_method_idx=1)CODE: (code_offset=0x00001021 size_offset=0x0000101c size=4)...0x00001020: 0048 lsls r0, r1, #10x00001022: 4770 bx lr2: int ExampleKt.shiftLeft(int) (dex_method_idx=2)CODE: (code_offset=0x00001021 size_offset=0x0000101c size=4)...0x00001020: 0048 lsls r0, r1, #10x00001022: 4770 bx lr3: int ExampleKt.shiftRight(int) (dex_method_idx=3)CODE: (code_offset=0x00001031 size_offset=0x0000102c size=4)...0x00001030: 1048 asrs r0, r1, #10x00001032: 4770 bx lr

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

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

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

位移会比除法快一些吗？

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

class DivideOrShiftTest {@JvmField @Rule val benchmark = BenchmarkRule()

@Test fun divide() {val value = "4".toInt() // Ensure not a constant.var result = 0benchmark.measureRepeated {result = value / 2}println(result) // Ensure D8 keeps computation.}

@Test fun shift() {val value = "4".toInt() // Ensure not a constant.var result = 0benchmark.measureRepeated {result = value shr 1}println(result) // Ensure D8 keeps computation.}

我没有x86设备，但有一台运行Android 10系统的基于ARM的Pixel 3，结果如下：

android.studio.display.benchmark=4 ns DivideOrShiftTest.dividecount=4006mean=4median=4min=4standardDeviation=0

android.studio.display.benchmark=3 ns DivideOrShiftTest.shiftcount=3943mean=3median=3min=3standardDeviation=0

对如此小的数字使用除法或位移之间的区别几近于无，毕竟差异太小了。使用负数显示结果并无差异。

这样一来，我们现在可以肯定，用`value >> 1`代替`value / 2`并无好处，不要再为算术运算这么做了，仅保留用于严格的按位运算。

D8/R8能用这些信息来保存APK大小吗？

针对两个操作相同的表达方式，我们应该选择性能更佳的。但如果两者性能相同的话，则应选择APK更小的。

我们知道，ART中`value * 2`和`value << 1`会产生相同的汇编，因此如果在Dalvik字节码中，一个比另一个更省空间，我们应该无条件地以更小的形式将其重写。查看D8中的输出，它们产生的字节码大小相同：

#1 : (in LExampleKt;) name : 'multiply'000140: da00 0102 |0000: mul-int/lit8 v0, v1, #int 2 // #02

#2 : (in LExampleKt;)name : 'shiftLeft'000158: e000 0101 |0000: shl-int/lit8 v0, v1, #int 1 // #01

尽管使用2的幂没有收益，但在移位以存储常量值之前，乘法用完了字节码空间，下面是`value * 32_768`与`value << 15`的对比：

#1 : (in LExampleKt;) name : 'multiply'000128: 1400 0080 0000 |0000: const v0, #float 0.000000 // #0000800000012e: 9201 0100 |0003: mul-int v1, v1, v0

#2 : (in LExampleKt;)name : 'shiftLeft'00015c: e000 000f |0000: shl-int/lit8 v0, v0, #int 15 // #0f

我在D8上提了个问题以调查如何自动优化此问题，但我强烈怀疑这种适用情况接近于零，因此很可能并不值得。

D8和R8的输出也告诉我们，在Dalvik字节码方面，`value / 2`和`value >> 1`的代价是相同的。

#0 : (in LExampleKt;) name : 'divide'000128: db00 0102 |0000: div-int/lit8 v0, v1, #int 2 // #02

#2 : (in LExampleKt;)name : 'shiftLeft'000158: e000 0101 |0000: shl-int/lit8 v0, v1,#int 1 // #01

当常量达到32768时，其字节码大小也会有所不同。无条件地将2的幂除法换成向右位移永远不是安全的选项，这是因为负数的存在。如果能保证其值非负，那我们可以这样替换，但此时D8和R8并不会追踪可能的整数值范围。

无符号的“2的幂除法”使用位移吗？

Java字节码缺少无符号的数字，但使用符号的对应部分是可以模拟的。在Java中，有一些将符号类型当作无符号值运算的静态辅助方法。Kotlin提供了类似 `UInt` 这样的类型完成类似的功能，但在类型后完全抽象了。可以想象的是，当使用除以2的幂时，应当以移位方式重写。

我们可以使用Kotlin来为两种情况建模。

fun javaLike(value: Int) = Integer.divideUnsigned(value, 2)fun kotlinLike(value: UInt) = value / 2U

在某些情况下，仅需考虑代码的编译方式。我们从普通的 `kotlinc`开始（还是从Kotlin 1.4-M1开始）。

$ kotlinc Example.kt$ javap -c ExampleKtCompiled from "Example.kt"public final class ExampleKt {public static final int javaLike(int);Code:0: iload_01: iconst_22: invokestatic #12 // Method java/lang/Integer.divideUnsigned:(II)I5: ireturn

public static final int kotlinLike-WZ4Q5Ns(int);Code:0: iload_01: istore_12: iconst_23: istore_24: iconst_05: istore_36: iload_17: iload_28: invokestatic #20 // Method kotlin/UnsignedKt."uintDivide-J1ME1BU":(II)I11: ireturn}

Kotlin无法将其识别为可使用`iushr`字节码的“2的幂除法”，我提交了KT-38493以追踪此行为的添加。

使用`-Xuse-ir`不会有任何改变（除非移除某些负载/存储噪音），然而以Java 8为目标则会有变化。

$ kotlinc -jvm-target 1.8 Example.kt$ javap -c ExampleKtCompiled from "Example.kt"public final class ExampleKt {public static final int javaLike(int);Code:0: iload_01: iconst_22: invokestatic #12 // Method java/lang/Integer.divideUnsigned:(II)I5: ireturn

public static final int kotlinLike-WZ4Q5Ns(int);Code:0: iload_01: iconst_22: invokestatic #12 // Method java/lang/Integer.divideUnsigned:(II)I5: ireturn}

`Integer.divideUnsigned`方法在Java 8中可以使用，因此在1.8或更高版本中较多使用，由于这会使得两个函数体完全相同，我们还是返回旧输出，对比看看会发生什么。

接下来是R8，与上面调用明显不同，我们将Kotlin stdlib作为输入引入，同时由于 `Integer.divideUnsigned` 仅在API 24和更高版本中可用，也传递了`--min-api 24`。

$ java -jar $R8_HOME/build/libs/r8.jar \--lib $ANDROID_HOME/platforms/android-29/android.jar \--min-api 24 \--release \--pg-conf rules.txt \--output . \ExampleKt.class kotlin-stdlib.jar$ dexdump -d classes.dexOpened 'classes.dex', DEX version '039'Class #0 -Class descriptor : 'LExampleKt;'Access flags : 0x0011 (PUBLIC FINAL)Superclass : 'Ljava/lang/Object;'Direct methods -#0 : (in LExampleKt;)name : 'javaLike'type : '(I)I'access : 0x0019 (PUBLIC STATIC FINAL)code -0000f8: |[0000f8] ExampleKt.javaLike:(I)I000108: 1220 |0000: const/4 v0, #int 2 // #200010a: 7120 0200 0100 |0001: invoke-static {v1, v0}, Ljava/lang/Integer;.divideUnsigned:(II)I // method@0002000110: 0a01 |0004: move-result v1000112: 0f01 |0005: return v1

#1 : (in LExampleKt;)name : 'kotlinLike-WZ4Q5Ns'type : '(I)I'access : 0x0019 (PUBLIC STATIC FINAL)code -000114: |[000114] ExampleKt.kotlinLike-WZ4Q5Ns:(I)I000124: 8160 |0000: int-to-long v0, v6000126: 1802 ffff ffff 0000 0000 |0001: const-wide v2, #double 0.000000 // #00000000ffffffff000130: c020 |0006: and-long/2addr v0, v2000132: 1226 |0007: const/4 v6, #int 2 // #2000134: 8164 |0008: int-to-long v4, v6000136: c042 |0009: and-long/2addr v2, v4000138: be20 |000a: div-long/2addr v0, v200013a: 8406 |000b: long-to-int v6, v000013c: 0f06 |000c: return v6

Kotlin有自己的无符号整数除法的实现方式，已经与我们的函数内联。它会将输入实参和常量转化为longs，执行longs除法，然后再转回整数。当我们最终通过ART来运行时，它们会转成等效的x86，因此我们将保留此函数，这里优化的机会已经失去了。

对于Java版本，R8无法将`divideUnsigned`调用替换成位移，我针对D8和R8提交了issue 154712996来跟踪这个问题。

最后一个优化的机会是ART。

$ adb push classes.dex /sdcard/classes.dex$ adb shellgeneric_x86:/ $ sugeneric_x86:/ # dex2oat --dex-file=/sdcard/classes.dex --oat-file=/sdcard/classes.oatgeneric_x86:/ # oatdump --oat-file=/sdcard/classes.oatOatDexFile:0: LExampleKt; (offset=0x000003c0) (type_idx=1) (Initialized) (OatClassAllCompiled)0: int ExampleKt.javaLike(int) (dex_method_idx=0)CODE: (code_offset=0x00001010 size_offset=0x0000100c size=63)...0x00001010: 85842400E0FFFF test eax, [esp + -8192]StackMap[0] (native_pc=0x1017, dex_pc=0x0, register_mask=0x0, stack_mask=0b)0x00001017: 55 push ebp0x00001018: 83EC18 sub esp, 240x0000101b: 890424 mov [esp], eax0x0000101e: 6466833D0000000000 cmpw fs:[0x0], 0 ; state_and_flags0x00001027: 0F8519000000 jnz/ne +25 (0x00001046)0x0000102d: E800000000 call +0 (0x00001032)0x00001032: 5D pop ebp0x00001033: BA02000000 mov edx, 20x00001038: 8B85CE0F0000 mov eax, [ebp + 4046]0x0000103e: FF5018 call [eax + 24]StackMap[1] (native_pc=0x1041, dex_pc=0x1, register_mask=0x0, stack_mask=0b)0x00001041: 83C418 add esp, 240x00001044: 5D pop ebp0x00001045: C3 ret0x00001046: 64FF15E0020000 call fs:[0x2e0] ; pTestSuspendStackMap[2] (native_pc=0x104d, dex_pc=0x0, register_mask=0x0, stack_mask=0b)0x0000104d: EBDE jmp -34 (0x0000102d)1: int ExampleKt.kotlinLike-WZ4Q5Ns(int) (dex_method_idx=1)CODE: (code_offset=0x00001060 size_offset=0x0000105c size=67)...

ART内化调用 `divideUnsigned`，因此我们让机器跳至常规方法的实现。我提交了issue 154693569以跟踪为无符号除法添加ART内化的问题。

好吧，这确实费了不少劲。恭喜你到达此步（或只是快速翻到这里），我们总结一下：

1. ART将2的幂乘法重写为向左位移，将2的幂除法重写为向右位移（通过一些额外的指令来处理负数）；

2. 向右位移和2的幂除法之间没有明显的性能差异；

3. Dalvik字节码中，位移和乘法/除法之间没有大小差异；

4. 截至目前还没有人优化无签名除法，但也许你也不会用到。

通过以上事实，我们可以回答本文题目中提出的问题了：

Android上哪个更好：除以2还是位移1？

都不好！因此将除法用于算术运算中，对于真实的按位操作只使用位移，我会将AndroidX集合端口从位移切换到乘除法。下次见！

注释：

1. 二进制中的-3为0b11111101，如果我们尝试仅向右位移来实现除以2，结果是0b11111110，即-2，这是错误的结果。通过给-3加1，首先我们会得到-2，二进制表达是0b11111110，向右位移则得出0b11111111，也就是-1，这是正确的结果。

根据实际中的指令：

• `mov eax, ecx` 将原始输入实参值保存在`eax`中；

• `lea edx, [eax + 1]` 给输入实参加1，并将结果存储在`edx`中，即我们要位移的寄存器；

• `test eax, eax`对自身的输入实参进行按位操作，导致一些寄存器会根据输入实参的属性来设置；

• 之后`cmovnl/ge edx, eax`可能会基于`test`的结果，以`eax` (值)重写`edx` (值+1)。

之后指令会执行普通的向右位移，与 `(value < 0 ? value + 1 : value) >> 1`. 基本相同。

2. 感谢Sergey Vasilinets提供的相关内容，`dex2oat`只能在现代Android版本中以root身份来运行，因此普通的Android（如在Pixel3上的）就无法运行。

3. 就实际指令而言：

• `lsrs r0, r1, #31` 对输入实参进行逻辑（即不对符号进行扩展）31位的位移到`r0`，导致负数结果为1，正数结果为0。

• `adds r1, r0, r1` 会将前一条指令的结果与输入实参相加，实际上是给负值输入加1。

自此指令会执行普通的向右位移，基本上等同于`(value + (value >>> 31)) >> 1`。

https://jakewharton.com/which-is-better-on-android-divide-by-two-or-shift-by-one/

本文为CSDN翻译文章，转载请注明出处。