我一直在尝试将 AndroidX collection library 移植到 Kotlin multiplatform，来测试二进制兼容性，性能，易用性和不同的内存模型。类库中的一些数据结构使用基于数组实现的二叉树来存储元素。在 Java 代码中有许多地方使用 移位操作 来代替二次幂的乘除法。当移植到 Kotlin 时，这些代码会被转化为略显变扭的中缀操作符，这有点混淆了代码意图。
关于移位运算和乘/除法谁的性能更好，我做过一些调研，大多数人都听说过 “移位运算性能更好”，但也对其真实性保持质疑。一些人认为代码运行到 CPU 之前，编译器可能会做一些优化。
为了满足我的好奇心，同时避免使用 Kotlin 的中缀移位操作符，我会来回答谁更好以及一些相关问题。Let's go !
译者注：Jake Wharton 吐槽的 Kotlin 移位操作是这么写的：
i shr 1、i shl 1
谁优化了代码 ?
在我们的代码被 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; } } 复制代码
在 JDK 14 下编译上面的代码，并通过 javap 展示字节码。
$ javac Example.java $ javap -c Example Compiled from "Example.java" class Example { static int multiply(int); Code: 0: iload_0 1: iconst_2 2: imul 3: ireturn static int divide(int); Code: 0: iload_0 1: iconst_2 2: idiv 3: ireturn static int shiftLeft(int); Code: 0: iload_0 1: iconst_1 2: ishl 3: ireturn static int shiftRight(int); Code: 0: iload_0 1: iconst_1 2: ishr 3: ireturn } 复制代码
每个方法都以 iload_0 指令开头，表示加载第一个参数。乘法和除法都是用 iconst_2 指令来加载字面量 2 。然后分别执行 imul 和 idiv 指令来进行 int 类型的乘除法。移位操作也是先加载字面量 1，然后利用 ishl 和 ishr 指令进行移位运算。
这里没有进行任何优化，但是如果你对 java 有所了解的话，也不会感到意外。javac 并不是一个会进行优化的编译器，而是把大部分工作留给了 JVM 上的运行时编译器或者 AOT 。
kotlinc
fun multiply(value: Int) = value * 2 fun divide(value: Int) = value / 2 fun shiftLeft(value: Int) = value shl 1 fun shiftRight(value: Int) = value shr 1 复制代码
在 Kotlin 1.4-M1 版本下通过 kotlinc 将 Kotlin 编译成 Java 字节码，再使用 javap 查看。
$ kotlinc Example.kt $ javap -c ExampleKt Compiled from "Example.kt" public final class ExampleKt { public static final int multiply(int); Code: 0: iload_0 1: iconst_2 2: imul 3: ireturn public static final int divide(int); Code: 0: iload_0 1: iconst_2 2: idiv 3: ireturn public static final int shiftLeft(int); Code: 0: iload_0 1: iconst_1 2: ishl 3: ireturn public static final int shiftRight(int); Code: 0: iload_0 1: iconst_1 2: ishr 3: ireturn } 复制代码
输出结果和 Java 完全一致。
This is using the original JVM backend of Kotlin, but using the forthcoming IR-based backend (via -Xuse-ir) also produces the same output.
上面这句裱起来，因为我看不懂 ~
D8
使用最新的 D8 编译器将上面示例的 Kotlin 代码转换的字节码生成 DEX 文件。
$ java -jar $R8_HOME/build/libs/d8.jar \ --release \ --output . \ ExampleKt.class $ dexdump -d classes.dex Opened '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)I 000128: db00 0102 |0000: div-int/lit8 v0, v1, #int 2 // #02 00012c: 0f00 |0002: return v0 #1 : (in LExampleKt;) name : 'multiply' type : '(I)I' access : 0x0019 (PUBLIC STATIC FINAL) code - 复制代码 000130: |[000130] ExampleKt.multiply:(I)I 000140: da00 0102 |0000: mul-int/lit8 v0, v1, #int 2 // #02 000144: 0f00 |0002: return v0 #2 : (in LExampleKt;) name : 'shiftLeft' type : '(I)I' access : 0x0019 (PUBLIC STATIC FINAL) code - 复制代码 000148: |[000148] ExampleKt.shiftLeft:(I)I 000158: e000 0101 |0000: shl-int/lit8 v0, v1, #int 1 // #01 00015c: 0f00 |0002: return v0 #3 : (in LExampleKt;) name : 'shiftRight' type : '(I)I' access : 0x0019 (PUBLIC STATIC FINAL) code - 复制代码 复制代码000160: |[000160] ExampleKt.shiftRight:(I)I 000170: e100 0101 |0000: shr-int/lit8 v0, v1, #int 1 // #01 000174: 0f00 |0002: return v0
(略微优化了输出结果)
Dalvik 字节码是基于寄存器的，Java 字节码是基于栈的。最终，每个方法实际上都仅仅使用了一个字节码来操作相关联的整型数运算。它们都使用了 v1 寄存器来保存第一个方法参数，另外还需要一个字面量 1 或者 2。
所以不会产生任何改变，D8 并不是一个优化编译器(尽管它可以做 method-local optimization) 。
R8
为了运行 R8，我们需要配置混淆规则防止我们的代码被移除。
-keep,allowoptimization class ExampleKt { <methods>; } 复制代码
上面的规则通过 --pg-conf 参数传递。
$ 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.dex Opened '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)I 000128: db00 0102 |0000: div-int/lit8 v0, v1, #int 2 // #02 00012c: 0f00 |0002: return v0 #1 : (in LExampleKt;) name : 'multiply' type : '(I)I' access : 0x0019 (PUBLIC STATIC FINAL) code - 000130: |[000130] ExampleKt.multiply:(I)I 000140: da00 0102 |0000: mul-int/lit8 v0, v1, #int 2 // #02 000144: 0f00 |0002: return v0 #2 : (in LExampleKt;) name : 'shiftLeft' type : '(I)I' access : 0x0019 (PUBLIC STATIC FINAL) code - 000148: |[000148] ExampleKt.shiftLeft:(I)I 000158: e000 0101 |0000: shl-int/lit8 v0, v1, #int 1 // #01 00015c: 0f00 |0002: return v0 #3 : (in LExampleKt;) name : 'shiftRight' type : '(I)I' access : 0x0019 (PUBLIC STATIC FINAL) code - 000160: |[000160] ExampleKt.shiftRight:(I)I 000170: e100 0101 |0000: shr-int/lit8 v0, v1, #int 1 // #01 000174: 0f00 |0002: return v0 复制代码
和 D8 的输出一模一样。
ART
使用上面 R8 输出的 Dalvik 字节码作为 ART 的输入，在 Android 10 的 x86 虚拟机上运行。
$ adb push classes.dex /sdcard/classes.dex $ adb shell generic_x86:/ $ su generic_x86:/ # dex2oat --dex-file=/sdcard/classes.dex --oat-file=/sdcard/classes.oat generic_x86:/ # oatdump --oat-file=/sdcard/classes.oat OatDexFile: 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, ecx 0x00001012: 8D5001 lea edx, [eax + 1] 0x00001015: 85C0 test eax, eax 0x00001017: 0F4DD0 cmovnl/ge edx, eax 0x0000101a: D1FA sar edx 0x0000101c: 89D0 mov eax, edx 0x0000101e: C3 ret 1: int ExampleKt.multiply(int) (dex_method_idx=1) CODE: (code_offset=0x00001030 size_offset=0x0000102c size=5)... 0x00001030: D1E1 shl ecx 0x00001032: 89C8 mov eax, ecx 0x00001034: C3 ret 2: int ExampleKt.shiftLeft(int) (dex_method_idx=2) CODE: (code_offset=0x00001030 size_offset=0x0000102c size=5)... 0x00001030: D1E1 shl ecx 0x00001032: 89C8 mov eax, ecx 0x00001034: C3 ret 3: int ExampleKt.shiftRight(int) (dex_method_idx=3) CODE: (code_offset=0x00001040 size_offset=0x0000103c size=5)... 0x00001040: D1F9 sar ecx 0x00001042: 89C8 mov eax, ecx 0x00001044: C3 ret 复制代码
(略微优化了输出结果)
x86 的汇编代码表明 ART 介入了数学运算，并使用移位操作代替了其中的一部分。
首先，multiply 和 shiftLeft 现在具有同样的实现，它们都使用 shl 来进行左移一位的操作。除此之外，如果你查看文件偏移量(最左边一列)的话，你会发现是完全一样的。ART 识别到了这两个方法具有一样的方法体，并在编译成 x86 汇编代码时进行了去重操作。
然后，divide 和 shiftRight 的实现是不一样的，它们没有共同使用 sar 来进行右移一位的操作。divide 方法在调用 sar 之前额外使用了四条指令，来处理输入是负数的情况。
在 Android 10 Pixel4 的设备上执行相同的指令，来看看 ART 是如何将代码编译成 ARM 汇编代码的。
OatDexFile: 0: LExampleKt; (offset=0x000005a4) (type_idx=1) (Verified) (OatClassAllCompiled) 0: int ExampleKt.divide(int) (dex_mmultiply and shiftLeft ethod_idx=0) CODE: (code_offset=0x00001009 size_offset=0x00001004 size=10)... 0x00001008: 0fc8 lsrs r0, r1, #31 0x0000100a: 1841 adds r1, r0, r1 0x0000100c: 1049 asrs r1, #1 0x0000100e: 4608 mov r0, r1 0x00001010: 4770 bx lr 1: int ExampleKt.multiply(int) (dex_method_idx=1) CODE: (code_offset=0x00001021 size_offset=0x0000101c size=4)... 0x00001020: 0048 lsls r0, r1, #1 0x00001022: 4770 bx lr 2: int ExampleKt.shiftLeft(int) (dex_method_idx=2) CODE: (code_offset=0x00001021 size_offset=0x0000101c size=4)... 0x00001020: 0048 lsls r0, r1, #1 0x00001022: 4770 bx lr 3: int ExampleKt.shiftRight(int) (dex_method_idx=3) CODE: (code_offset=0x00001031 size_offset=0x0000102c size=4)... 0x00001030: 1048 asrs r0, r1, #1 0x00001032: 4770 bx lr 复制代码
同样的，multiply 和 shiftLeft 使用 lsls 来完成左移一位的操作并去除了重复方法体。shiftRight 通过 asrs 指令完成右移，而除法使用了另一个右移指令 lsrs来处理输入是负数的情况。
到此为止，我们可以肯定的说，使用 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 = 0 benchmark.measureRepeated { result = value / 2 } println(result) // Ensure D8 keeps computation. } @Test fun shift() { val value = "4".toInt() // Ensure not a constant. var result = 0 benchmark.measureRepeated { result = value shr 1 } println(result) // Ensure D8 keeps computation. } } 复制代码
我没有 x86 设备，所以我在 Android 10 Pixel3 上进行了测试，结果如下：
android.studio.display.benchmark=4 ns DivideOrShiftTest.divide count=4006 mean=4 median=4 min=4 standardDeviation=0 复制代码android.studio.display.benchmark=3 ns DivideOrShiftTest.shift count=3943 mean=3 median=3 min=3 standardDeviation=0
使用除法和移位实际上并没有什么区别，它们的差距是纳秒级的。使用负数的话，结果不会有任何差异。
到此为止，我们可以肯定的说，使用 value >> 1 来代替 value / 2 不会带来任何好处。 停止在算数运算中做这样的事情吧，仅在严格要求按位运算的情况下保留。
D8/R8 可以减小 Apk 体积吗？
对于同一操作有两种表达方式的话，应该选择性能更优的。如果性能相同，就应该选择能降低 Apk 体积的。
现在我们都知道了 value * 2 和 value << 1 在 ART 上产生了相同的汇编代码。因此，如果哪一种能够在 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
乘法有可能会耗费更多的空间用来存储字面量。比较一下 value * 32_768 和 value << 15 。
#1 : (in LExampleKt;) name : 'multiply' ⋮ 000128: 1400 0080 0000 |0000: const v0, #float 0.000000 // #00008000 00012e: 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 上提过这个 issue，但我强烈怀疑出现这一情况的概率为 0，所以这并不值得。
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 次幂的除法并不是绝对安全的。我们可以在保证非负数的情况下进行替换。
无符号数的二次幂除法也使用移位吗？
Java 字节码并没有无符号数，但你可以使用有符号数来模拟。Java 提供了静态方法可以将有符号数转化为无符号数。Kotlin 提供了无符号类型 UInt ，它提供了一样的功能，但和 Java 不一样的是，它独立抽象为一个数据类型。可以想象到的是，二次幂的除法肯定可以用右移操作重写。
使用 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 ExampleKt Compiled from "Example.kt" public final class ExampleKt { public static final int javaLike(int); Code: 0: iload_0 1: iconst_2 2: invokestatic #12 // Method java/lang/Integer.divideUnsigned:(II)I 5: ireturn 复制代码public static final int kotlinLike-WZ4Q5Ns(int); Code: 0: iload_0 1: istore_1 2: iconst_2 3: istore_2 4: iconst_0 5: istore_3 6: iload_1 7: iload_2 8: invokestatic #20 // Method kotlin/UnsignedKt."uintDivide-J1ME1BU":(II)I 11: ireturn }
Kotlin 没有识别到这是一个二次幂的除法，它本来可以用 iushr 移位操作来代替。我向 Jetbrain 也提交过这个 issue 。
使用 -Xuse-i 也不会带来任何改变(除了移除了一些 load/store)。但是，面向 Java8 就不一样了。
$ kotlinc -jvm-target 1.8 Example.kt $ javap -c ExampleKt Compiled from "Example.kt" public final class ExampleKt { public static final int javaLike(int); Code: 0: iload_0 1: iconst_2 2: invokestatic #12 // Method java/lang/Integer.divideUnsigned:(II)I 5: ireturn 复制代码public static final int kotlinLike-WZ4Q5Ns(int); Code: 0: iload_0 1: iconst_2 2: invokestatic #12 // Method java/lang/Integer.divideUnsigned:(II)I 5: ireturn }
Integer.divideUnsigned 方法从 Java 8 开始可用。由于这样让两个函数体完全相同了，还是回到旧版本来进行对比。
接下来是 R8。与上面明显不同的是，我们使用 Kotlin 标准库作为输入，还指定了最低 api ，--min-api 24 。因为 Integer.divideUnsigned 仅在 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.dex Opened '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)I 000108: 1220 |0000: const/4 v0, #int 2 // #2 00010a: 7120 0200 0100 |0001: invoke-static {v1, v0}, Ljava/lang/Integer;.divideUnsigned:(II)I // method@0002 000110: 0a01 |0004: move-result v1 000112: 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)I 000124: 8160 |0000: int-to-long v0, v6 000126: 1802 ffff ffff 0000 0000 |0001: const-wide v2, #double 0.000000 // #00000000ffffffff 000130: c020 |0006: and-long/2addr v0, v2 000132: 1226 |0007: const/4 v6, #int 2 // #2 000134: 8164 |0008: int-to-long v4, v6 000136: c042 |0009: and-long/2addr v2, v4 000138: be20 |000a: div-long/2addr v0, v2 00013a: 8406 |000b: long-to-int v6, v0 00013c: 0f06 |000c: return v6
Kotlin 有自己的无符号整数的实现，并直接内联到了函数体内。它是这样实现的，将参数和字面量转化为 long ，进行 long 的除法，最后转换为 int 。When we eventually run them through ART they’re just translated to equivalent x86 so we’re going to leave this function behind. (这句没太懂) 。这里已经错失了优化机会。
对于 Java 版本，R8 也没有使用移位运算来代替 divideUnsigned 。我已经提交 issue 来持续进行追踪。
最后的优化机会就是 ART 。
$ adb push classes.dex /sdcard/classes.dex $ adb shell generic_x86:/ $ sugenzong generic_x86:/ # dex2oat --dex-file=/sdcard/classes.dex --oat-file=/sdcard/classes.oat generic_x86:/ # oatdump --oat-file=/sdcard/classes.oat OatDexFile: 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 ebp 0x00001018: 83EC18 sub esp, 24 0x0000101b: 890424 mov [esp], eax 0x0000101e: 6466833D0000000000 cmpw fs:[0x0], 0 ; state_and_flags 0x00001027: 0F8519000000 jnz/ne +25 (0x00001046) 0x0000102d: E800000000 call +0 (0x00001032) 0x00001032: 5D pop ebp 0x00001033: BA02000000 mov edx, 2 0x00001038: 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, 24 0x00001044: 5D pop ebp 0x00001045: C3 ret 0x00001046: 64FF15E0020000 call fs:[0x2e0] ; pTestSuspend StackMap[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 进行跟踪。
最后
真是一段漫长的旅程，恭喜你已经完成了(或者只是翻到了文章底部)。让我们总结一下。
- ART 使用左移/右移重写了二次幂的乘法/除法(处理负数时会有增加额外的指令)。
- 右移和二次幂除法之间并没有明显的性能差距。
- 移位和乘除法的 Dalvik 字节码大小是一样的。
- 没有人优化了无符号除法(至少现在没有)，但是你应该也没有用过。
通过这些事实，你可以回答文章开头的问题了。
在 Android 上，选择 除以2 还是 右移1 ？
都不是！仅在实际需要按位操作时使用移位运算，其他数学运算使用乘除法。我将着手将 AndroidX collection 的位运算切换到乘除法。下次见！
