Jake Wharton asks: Divided by two, moved to the right by one, who is better?
January 25, 2024
by Melissa Pratt
No Comments
Jake Wharton
Which is Better on Android: Divide by 2 or Shift by 1?
The original address: https://jakewharton.com/which-is-better-on-android-divide-by-two-or-shift-by-one/
Translator: Bingxin said
I have been trying to port the AndroidX Collection Library to Kotlin Multiplatform to test binary compatibility, performance, ease of use and different memory models. Some data structures in the library use a binary tree based on an array-based implementation to store elements. There are many places in Java code where a shift operation is used instead of multiplying and dividing quadratic powers. When ported to Kotlin, this code is converted to a slightly twisted infix operator, which confuses the code’s intent.
I’ve done some research on whether shift or multiplication/division performs better, and most people have heard “shift performs better,” but are skeptical about whether it’s true. Some people think the compiler might make some optimizations before the code runs to the CPU.
To satisfy my curiosity and avoid using Kotlin’s infix shift operator, I’ll answer who’s better and some related questions. Let’s go !
I SHR 1, I SHL 1
Who optimized the code?
Before our code is executed by the CPU, there are several important compilers: Javac/Kotlinc, D8, R8, and ART.
Each of these steps had an opportunity to optimize, but did they?
javac
classExample{
staticintmultiply(int value){
return value * 2;
}
staticintdivide(int value){
return value / 2;
}
staticintshiftLeft(int value){
return value << 1;
}
staticintshiftRight(int value){
return value >> 1; }}Copy the code
Compile the above code under JDK 14 and present the bytecode through JavAP.
Each method begins with the iloAD_0 directive, indicating that the first parameter is loaded. Both multiplication and division use the iconst_2 instruction to load the literal 2. The imul and IDIV instructions are then executed to multiply and divide int. The shift operation also loads the literal 1 and then uses the ishl and ishr instructions to perform the shift operation.
No optimizations have been made, but if you know anything about Java, it’s no surprise. Javac is not an optimized compiler, leaving most of the work to the runtime compiler or AOT on the JVM.
kotlinc
funmultiply(value: Int) = value * 2fundivide(value: Int) = value / 2funshiftLeft(value: Int) = value shl 1funshiftRight(value: Int) = value shr 1Copy the code
Kotlin is compiled into Java bytecode through Kotlinc under Kotlin version 1.4-M1 and viewed using Javap.
Dalvik bytecode is register-based, while Java bytecode is stack based. In the end, each method actually uses just one bytecode to manipulate the associated integer operation. They both use the v1 register to hold the first method parameter, plus a literal 1 or 2.
So nothing changes, and D8 is not an optimization compiler (although it can do method-local optimization).
R8
To run R8, we need to configure obfuscation rules to prevent our code from being removed.
-keep,allowoptimization class ExampleKt {
<methods>;
}
Copy the code
The above rules are passed with the –pg-conf argument.
The x86 assembly code shows that ART intervenes in the math and replaces some of it with a shift operation.
First, multiply and shiftLeft now have the same implementation, and both use SHL to move one bit to the left. Otherwise, if you look at the file offset (the leftmost column), you’ll see exactly the same. ART recognized that the two methods had the same method body and de-duplicated them when they were translated into x86 assembly code.
Divide and shiftRight, however, are implemented differently in that they do not work together with SAR to move one bit to the right. The Divide method uses four additional instructions before calling SAR to handle negative input.
Execute the same instructions on an Android 10 Pixel4 device to see how ART compiles code into ARM assembly code.
Similarly, multiply and shiftLeft use LSLS to move the left one bit and remove the duplicate method body. ShiftRight does the right shift with the ASRS instruction, while division uses another right shift instruction, LSRS, to handle negative input.
At this point, we can safely say that using value << 1 instead of value * 2 does no good. Stop doing this in arithmetic operations and keep it only when bitwise operations are strictly required.
However, value / 2 and value >> 1 still produce different assembly instructions and therefore have different performance. Thankfully, value / 2 does not perform a generic division operation and is still based on a shift operation, so the performance differences may not be significant.
Is shift faster than division?
To determine which shift or division is faster, I tested it using Jetpack Benchmark.
classDivideOrShiftTest{
@JvmField@Ruleval benchmark = BenchmarkRule()
@Testfundivide(a) {
val value = "4".toInt() // Ensure not a constant.var result = 0
benchmark.measureRepeated {
result = value / 2
}
println(result) // Ensure D8 keeps computation.
}
@Testfunshift(a) {
val value = "4".toInt() // Ensure not a constant.var result = 0
benchmark.measureRepeated {
result = value shr 1
}
println(result) // Ensure D8 keeps computation.}}Copy the code
I don’t own an x86 device, so I tested it on Android 10 Pixel3, and here’s what I found:
There is really no difference between using division and shifting, the difference is nanosecond. Using negative numbers doesn’t make any difference.
At this point, we can safely say that using value >> 1 instead of value / 2 does no good. Stop doing this in arithmetic operations and keep it only when bitwise operations are strictly required.
Can D8/R8 reduce Apk volume?
If there are two ways to express the same operation, the one with better performance should be selected. If the performance is the same, you should choose the one that can reduce the Apk volume.
We now know that value * 2 and value << 1 produce the same assembly code on ART. Therefore, if one is more space-efficient in Dalvik, we should definitely use it instead of the other. Let’s look at D8’s output, which also produces bytecode of the same size:
#1 : (in LExampleKt;) Name: "multiply" ⋮ 000140: da00 0102 | 0000: the mul - int/lit8 where v0, v1, 2 / / # 02 # int
#2 : (in LExampleKt;) Name: 'shiftLeft ⋮Copy the code
The bytecode size above also changes when the literal size reaches 32768. Because of negative numbers, it is not absolutely safe to use a right shift unconditionally instead of division to the second power. We can make this substitution without making it negative.
Does the second power division of unsigned numbers also use shifts?
Java bytecode does not have unsigned numbers, but you can simulate them using signed numbers. Java provides static methods to convert signed numbers to unsigned numbers. Kotlin provides the unsigned type UInt, which provides the same functionality but, unlike Java, abstracts itself as a data type. As you can imagine, the division of a second power can definitely be rewritten with a right shift operation.
Use Kotlin to illustrate the following two cases.
funjavaLike(value: Int) = Integer.divideUnsigned(value, 2)
funkotlinLike(value: UInt) = value / 2U
Copy the code
Compiled by 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
Copy the code
Kotlin failed to recognize that this was a quadratic division, which could have been replaced by the IUSHR shift operation. I also submitted this issue to Jetbrain.
Using -xuse-i also doesn’t change anything (except to remove some loads/stores). However, working with Java8 is different.
$kotlinc - JVMS -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: ireturnCopy the code
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 methods are available as of Java 8. Since this makes the bodies of the two functions exactly the same, let’s go back to the old version for comparison.
And then R8. Significantly different from the above, we use the Kotlin library as input and specify the minimum API, — min-API 24. Because integer. divideUnsigned is only available in API 24 and beyond.
Kotlin has his own implementation of unsigned integers that are directly inlined inside functions. It does this by converting arguments and literals to long, dividing by long, and finally converting to int. When we eventually run them through ART they’re just translated to equivalent x86 so we’re going to leave this function Behind. This is a missed optimization opportunity.
For the Java version, R8 also does not use a shift operation to replace divideUnsigned. I have submitted the issue for continuous tracking.
ART does not make an inline call to divideUnsigned, instead making a regular method call. I submitted this issue for tracking.
The last
It’s been a long journey, congratulations on completing it (or just flipping to the bottom of the article). Let’s sum up.
ART rewrites multiplication/division for quadratic powers using left/right shift (there are additional instructions for negative numbers).
There is no significant performance difference between right shift and quadratic division.
The Dalvik bytecode size of shift and multiplication and division is the same.
No one has optimized unsigned division (at least not yet), but you probably haven’t either.
With these facts, you can answer the question at the beginning of the article.
On Android, divide by 2 or move right by 1?
All is not! Shift operations are used only when bitwise operations are actually required, and multiplication and division are used for other mathematical operations. I’m going to start switching bits from AndroidX Collection to multiplication and division. See you next time!
May translate more recently, encounter some good articles always can’t help but share with everyone.
In fact, the translation is not easier than the original text, I will write the translation at least on the basis of a thorough reading, intensive reading twice. If you think the article is good, feel free to read, forward, share!
