Android Question Shifting right versus division by power of two

Brian Dean

Well-Known Member
Licensed User
Longtime User
Does B4X (or the underlying Java) replace division by factors of two with a logical shift. That is ...
B4X:
    Dim n as Int
    
    n = Bit.ShiftRight(n, 8)
or :
    n = n / 256
... produce the same outcome, but the second one is quicker to code. Do they both execute equally quickly? I am working on an app with a lot of bit shifting and I just wondered whether, when the B4X finishes up in its Java form, division and multiplication by powers of two is replaced by a bit shift anyway.
 

Star-Dust

Expert
Licensed User
Longtime User
I have only studied the architecture of the 8080 and z80. Bit shifting is certainly faster than one division in the Intel 808x processor.
For later models I do not guarantee. Test a thousand operations
 
Upvote 0

Brian Dean

Well-Known Member
Licensed User
Longtime User
Test a thousand operations

Well - that's a pretty obvious answer, although clearly better than anything that I could come up with. I thought that 1000 operations might not be enough, so I tried one million. Here is the code ...
B4X:
Sub testbed
    Dim i, m, n As Int
    Dim start, stop, duration As Long
    n = 0xFFFFFF
    start = DateTime.Now
    For i = 0 To 999999
        m = Bit.ShiftRight(n, 8)
    Next
    stop = DateTime.Now
    duration = stop - start
    Log("Time = " & duration)
    
    start = DateTime.Now
    For i = 0 To 999999
        m = n / 256
    Next
    stop = DateTime.Now
    duration = stop - start
    Log("Time = " & duration)
End Sub
I ran it first on my desktop PC with B4J. Here is the result from the log ...
Time = 3
Time = 2
This was a bit unexpected - it suggests that the bit shifting route takes longer than division. So then I ran it in Android (two-year old Google Pixel; Android 10) and got this result ...
Time = 37
Time = 6
I have been poring over this to see where I might have gone wrong, but if I have I cannot see where it is. So what is happenning?
 
Upvote 0

agraham

Expert
Licensed User
Longtime User
You can't believe trivial benchmarks like these. The Java compiler is quite sophisticated and is likely to optimise out loops like yours whose inner result is never used. To be sure you would have to decompile the final jar to see what, if anything, the compiler has optimised away. Try logging m at the end of each loop and assigning it to another variable and see if that changes things.
 
Upvote 0

Star-Dust

Expert
Licensed User
Longtime User
Well - that's a pretty obvious answer, although clearly better than anything that I could come up with. I thought that 1000 operations might not be enough, so I tried one million. Here is the code ...
B4X:
Sub testbed
    Dim i, m, n As Int
    Dim start, stop, duration As Long
    n = 0xFFFFFF
    start = DateTime.Now
    For i = 0 To 999999
        m = Bit.ShiftRight(n, 8)
    Next
    stop = DateTime.Now
    duration = stop - start
    Log("Time = " & duration)
 
    start = DateTime.Now
    For i = 0 To 999999
        m = n / 256
    Next
    stop = DateTime.Now
    duration = stop - start
    Log("Time = " & duration)
End Sub
I ran it first on my desktop PC with B4J. Here is the result from the log ...

This was a bit unexpected - it suggests that the bit shifting route takes longer than division. So then I ran it in Android (two-year old Google Pixel; Android 10) and got this result ...

I have been poring over this to see where I might have gone wrong, but if I have I cannot see where it is. So what is happenning?
I am impressed with the results. If, as @agraham supposed, the compiled optimizes the code. It will also optimize the software you are developing.I would stay with the divisions without doing further tests.

But if you are intrigued or speeding up is extremely necessary, do other tests.
 
Upvote 0

agraham

Expert
Licensed User
Longtime User
It will also optimize the software you are developing.
Not true! You cannot make that assumption. It depends entirely upon what the production code is actually doing. Like I said, to be sure you would need to look at the final compiled code - and to complicate things more there is a further compilation/optimisation step taking place when the Dex/Java code is Just In Time Compiled (jitted) to native code on both desktop and Android. The only timings that you can be sure of are those that the final code produces when it is run in the final app.
 
Upvote 0

Brian Dean

Well-Known Member
Licensed User
Longtime User
Sorry - I have been tied up for a while so have been delayed in replying.

Thank you for your thoughts. I was aware when writing the testbed that there would be some code optimisation, but I was also trying to keep the overhead down. I think that, in spite of @agraham's warning, I will agree with @Star-Dust that it is inconceivable that the compiler wouldn't be able to sort out the most efficient path in this situation, and trust that it knows what it is doing. But I have nearly finished my project now, anyway, and I have bit-shifted throughout.

By the way, I had Googled this question before I raised it and had failed to find anything definitive. Thanks again for your interest.
 
Upvote 0
Top