Division to shift optimization

Trond · Post by **Trond** » Sat Dec 01, 2007 5:18 pm

Yes, I meant the divisor.
Obviously I meant it should only happen with constants, so you don't need to check anything at run-time. But I wasn't aware of the problem with rounding and negative numbers.

As you can see, it's much faster:

Code: Select all

tmp = 123495
t = ElapsedMilliseconds()
For i = 0 To 100000000
  x = tmp/2
Next
t - ElapsedMilliseconds()

t2 = ElapsedMilliseconds()
For i = 0 To 100000000
  x = tmp >> 1
Next
t2 - ElapsedMilliseconds()

MessageRequester("divide with 2",Str(-t))
MessageRequester("the other",Str(-t2))

tinman · Post by **tinman** » Sat Dec 01, 2007 5:36 pm

Edit 3: Post was full of wrong info, removed it. See below.

thefool · Post by **thefool** » Sat Dec 01, 2007 5:41 pm

Trond wrote: Obviously I meant it should only happen with constants, so you don't need to check anything at run-time.

Good then I didn't get it all wrong

Foz · Post by **Foz** » Sat Dec 01, 2007 5:50 pm

On mine, the shift by itself is quicker (2400) than the divide (3500), but if you include the If then the total time is 4700, and if you include the If and the increment, then it pushes it to a whopping 5400.

Could really do with a quick if and increment...

tinman · Post by **tinman** » Sat Dec 01, 2007 6:23 pm

Edit2: Removed code for incorrect algorithm. See below.

Foz · Post by **Foz** » Sat Dec 01, 2007 6:32 pm

that is sloooow! 9900 for me!

Trond · Post by **Trond** » Sat Dec 01, 2007 6:33 pm

Turn off the debugger...

Foz · Post by **Foz** » Sat Dec 01, 2007 6:35 pm

Ah!

Thanks!

tinman · Post by **tinman** » Sat Dec 01, 2007 7:21 pm

OK, I think I've figured out the correct algorithm. Code below, with some example ASM.

In fact, looking at the ASM that PB currently produces it converts the long to a quad, then performs the division. So the same code works for longs and quads quite easily. I don't know how to do this shifting nicely for quads so perhaps thats another issue doing it this way.

Code: Select all

Define.l b
Define.l a

#MAX_RANGE = 100000000
;#MAX_RANGE = 10
#DIVIDE_BY = 2
#SHIFT_BY = 1

st=GetTickCount_()
For a = -#MAX_RANGE To #MAX_RANGE
    b = a / #DIVIDE_BY
Next
et=GetTickCount_()
MessageRequester("Duration", Str(et-st))

st=GetTickCount_()
For a = -#MAX_RANGE To #MAX_RANGE
    ;b = a >> #SHIFT_BY
    ;If b < 0 And (a & ((1 << #SHIFT_BY)-1))
    ;    b + 1
    ;EndIf

    #ADJUST_MASK = (1 << #SHIFT_BY)-1
    ;Debug #ADJUST_MASK
    
    MOV    ebx, dword [v_a]
    MOV    eax, ebx
    AND    eax, #ADJUST_MASK
    SETNZ  al
    AND    eax, 1
    ROL    ebx, 1
    AND    eax, ebx
    ROR    ebx, 1
    SAR    ebx, #SHIFT_BY
    ADD    ebx, eax
    MOV    dword [v_b],ebx
    
    Debug b
Next
et=GetTickCount_()
MessageRequester("Duration", Str(et-st))