Page 1 of 2
Division to shift optimization
Posted: Sat Dec 01, 2007 2:59 pm
by Trond
When the dividend is a multiple of two it's possible to change the division into a shift. This gives a huge speed increase, and since it's already done for modulo it shouldn't be too much work to do it on division as well.
Posted: Sat Dec 01, 2007 3:34 pm
by remi_meier
Posted: Sat Dec 01, 2007 3:35 pm
by thefool
a = -3
Debug a / 2
Debug a >> 1
When the dividend is a multiple of two
Posted: Sat Dec 01, 2007 3:40 pm
by remi_meier
Yeah, you're right, Trond means the Divisor.
Edit:
And actually, you don't need to be afraid of me changing the meaning of
my post after you posted. I would not do something like that to make you
look wrong.
Posted: Sat Dec 01, 2007 3:44 pm
by netmaestro
Ok, is there a significant speed gain given that you have to go an extra step to see if it's a multiple of two and then branch to a shift? A valid comparison needs to use the full process, not just compare the speed of a shift vs. the speed of a division. Did you do some tests?
Posted: Sat Dec 01, 2007 3:49 pm
by remi_meier
Actually, PB used to optimize it IIRC. It was removed because of the issue
in the second post.
Unless I'm totally misunderstanding something.
Trond wanted the optimization by the compiler that /2 gets changed to >>1
and 4 gets changed to >>2, etc. Like one does with *2 -> << 1, *4 -> <<2...
And the Modulo thing is actually a bit different. %2 -> & 1, %4 -> &3, ...
Posted: Sat Dec 01, 2007 3:55 pm
by milan1612
Code: Select all
m = ElapsedMilliseconds()
For i = 0 To 100000000
tmp = Random(500)
x = tmp / 2
Next
t = ElapsedMilliseconds() - m
m = ElapsedMilliseconds()
For i = 0 To 100000000
tmp = Random(500)
If tmp % 2 = 0
x = tmp >> 1
Else
x = tmp / 2
EndIf
Next
t2 = ElapsedMilliseconds() - m
MessageRequester("Normal Division by 2", Str(t))
MessageRequester("Shift Replacement if modulo 2", Str(t2))
Without debugger the second one is still faster...
Posted: Sat Dec 01, 2007 4:02 pm
by thefool
On my computer, the second one is definently not faster. In fact its 40% slower. Also this should be done with an equal set of numbers as there is a posibility you get more divisable numbers on the second round.
And actually, you don't need to be afraid of me changing the meaning of
my post after you posted. I would not do something like that to make you
look wrong.
I was actually just changing the size of the letters, but then decided to add the original post for readability
I know it would be stupid to get what i meant wrong but you know..
And ok i admit it, a tiny part of the reason was to protect myself against edited posts
Posted: Sat Dec 01, 2007 4:04 pm
by milan1612
thefool wrote:On my computer, the second one is definently not faster. In fact its 40% slower
Did you run it without debugger?
I get 3568 normal division, 3172 with shift optimization (average values)
Posted: Sat Dec 01, 2007 4:05 pm
by thefool
milan1612 wrote:thefool wrote:On my computer, the second one is definently not faster. In fact its 40% slower
Did you run it without debugger?
I get 3568 normal division, 3172 with shift optimization (average values)
NO I did not run it with the debugger on
This is my results:
---------------------------
Normal Division by 2
---------------------------
1373
---------------------------
Shift Replacement if modulo 2
---------------------------
1997
Posted: Sat Dec 01, 2007 4:06 pm
by milan1612
Must be my machine, damn slow crap
Any other results?
Posted: Sat Dec 01, 2007 4:06 pm
by remi_meier
ou wait, nobody here seems to know, what he's doing.
nothing against you, milan, but your speed-test is the worst I've seen in
a long time. at least 99% of the time in the loops is spent on the Random()
function. Nothing really to say about the >>1 thingy.
And I can swap the result:
Code: Select all
m = ElapsedMilliseconds()
!align 4
For i = 0 To 100000000
tmp = Random(500)
x = tmp / 2
Next
t = ElapsedMilliseconds() - m
m = ElapsedMilliseconds()
!align 4
For i = 0 To 100000000
tmp = Random(500)
If tmp % 2
x = tmp >> 1
Else
x = tmp / 2
EndIf
Next
t2 = ElapsedMilliseconds() - m
MessageRequester("", Str(t))
MessageRequester("", Str(t2))
Ok, last post by me in this thread. Everything was said after the first 2 posts.
@thefool: I know. I saw the previous size of the letters and was kinda offended.
But you know, it's a shitty day today anyway.
Don't mean to offend anyone, but today, it was just enough for me.
Posted: Sat Dec 01, 2007 4:09 pm
by thefool
@thefool: I know. I saw the previous size of the letters and was kinda offended.
Well I'll just write a small test which use the same set of numbers and finds an average instead
Posted: Sat Dec 01, 2007 4:09 pm
by milan1612
remi_meier wrote:ou wait, nobody here seems to know, what he's doing.
nothing against you, milan, but your speed-test is the worst I've seen in
a long time. at least 99% of the time in the loops is spent on the Random()
function. Nothing really to say about the >>1 thingy.
Why? In both loops the Random() gets called the same times, so it's irrelevant...
EDIT:
Anyway, here's one without Random...
Code: Select all
#nums = 50000000
Dim numbers.l(#nums)
For i = 0 To #nums
numbers(i) = Random(5000)
Next
m = ElapsedMilliseconds()
For i = 0 To #nums
x = numbers(i) / 2
Next
t = ElapsedMilliseconds() - m
m = ElapsedMilliseconds()
For i = 0 To #nums
If numbers(i) % 2 = 0
x = numbers(i) >> 1
Else
x = numbers(i) / 2
EndIf
Next
t2 = ElapsedMilliseconds() - m
MessageRequester("Normal Division by 2", Str(t))
MessageRequester("Shift Replacement if modulo 2", Str(t2))
On my machine, the second one is still faster...
Posted: Sat Dec 01, 2007 4:20 pm
by thefool
;first generate a set of numbers
Dim seta(30000000)
For i=0 To 30000000
seta(i)=Random(500)
Next i
;allright.
For a=1 To 20
m=ElapsedMilliseconds()
For i=0 To 30000000
;here goes the code
tmp=seta(i)
x=tmp/2
Next i
t=t+(ElapsedMilliseconds()-m)
Next a
t=t/20
For a=1 To 20
m=ElapsedMilliseconds()
For i=0 To 30000000
;here goes the code
tmp = seta(i)
If tmp % 2
x = tmp >> 1
Else
x = tmp / 2
EndIf
Next i
t2=t2+(ElapsedMilliseconds()-m)
Next a
t2=t2/20
MessageRequester("divide with 2",Str(t))
MessageRequester("the other",Str(t2))
warning: takes a bit time to run.
Here i still get a faster average for the first function
(i know i would get the same result if i multiplied the big loop count with 20 but then it would need a larger array)
HOWEVER I am not sure if this is how trond wants to implement this.