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

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, #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`来执行向右位移。`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 = 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系统的基于ARM的Pixel 3，结果如下：

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更小的。

我们知道，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 // #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上提了个 问题 以调查如何自动优化此问题，但我强烈怀疑这种适用情况接近于零，因此很可能并不值得。

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 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`字节码的“2的幂除法”，我提交了 KT-38493 以追踪此行为的添加。

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

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

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

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

$ 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.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 154693569 以跟踪为无符号除法添加ART内化的问题。