Page 1 of 2
More speed to know if it is even
Posted: Fri Aug 02, 2024 11:19 am
by fvillanova
Hello everyone, here I am again, asking for help to make a routine as fast as possible.
I just need to know if the number "n" is even or not.
Here on my computer the last option "n & 1" is the fastest, does anyone have an idea to speed it up?
See:
Code: Select all
DisableDebugger
Define.i i,n,e
; the value of n will never be greater than 99
t1 = ElapsedMilliseconds(): RandomSeed(0): e=0
For i=1 To 20000000
n=Random(99,0): If Not Val(Right(Bin(n),1)): e+1: EndIf
Next
Result$+"Bin(n) = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13)
t1 = ElapsedMilliseconds(): RandomSeed(0): e=0
For i=1 To 20000000
n=Random(99,0): If Not Mod(n,2): e+1: EndIf
Next
Result$+"Mod(n,2) = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13)
t1 = ElapsedMilliseconds(): RandomSeed(0): e=0
For i=1 To 20000000
n=Random(99,0): If Not n % 2: e+1: EndIf
Next
Result$+"n % 2 = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13)
t1 = ElapsedMilliseconds(): RandomSeed(0): e=0
Dim even.i(99): For i=0 To 99: even(i)=1-Mod(i,2): Next
For i=1 To 20000000
n=Random(99,0): If even(n): e+1: EndIf
Next
Result$+"even(n) = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13)
t1 = ElapsedMilliseconds(): RandomSeed(0): e=0
For i=1 To 20000000
n=Random(99,0)+1: If n & 1: e+1: EndIf
Next
Result$+"n & 1 = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13)
EnableDebugger
Debug Result$
Re: More speed to know if it is even
Posted: Fri Aug 02, 2024 11:41 am
by infratec
Using the C compiler with optimize is faster: 159ms to 183ms
A binary AND is always the fastest solution.
Maybe you can use inline assembler to speed it up a bit more.
Re: More speed to know if it is even
Posted: Fri Aug 02, 2024 11:59 am
by infratec
Code: Select all
t1 = ElapsedMilliseconds(): RandomSeed(0): e=0
For i=1 To 20000000
n=Random(99,0)+1
EnableASM
MOV EAX, n
TEST EAX, 1
JZ l_labelend
INC e
LabelEnd:
DisableASM
Next
Result$+"n & 1 = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13)
Not Really faster. (1 -2 ms)
Maybe you need RAX instead of EAX.
Re: More speed to know if it is even
Posted: Fri Aug 02, 2024 12:23 pm
by wilbert
It depends that you need it for.
If you need to count the number of evens like in your example, get rid of the if construction.
Code: Select all
For i=1 To 20000000
n=Random(99,0)+1: e+(n&1)
Next
This is a lot faster.
Re: More speed to know if it is even
Posted: Fri Aug 02, 2024 12:41 pm
by BarryG
This returns 1 for odd and 0 for even:
Code: Select all
Macro IsOdd(num)
((num) & 1)
EndMacro
DisableDebugger
start.q=ElapsedMilliseconds()
For i=1 To 20000000
n=IsOdd(i)
Next
stop.q=ElapsedMilliseconds()
EnableDebugger
Debug "Time: "+Str(stop-start)+"ms" ; 58 ms on my old PC.
Re: More speed to know if it is even
Posted: Fri Aug 02, 2024 12:49 pm
by pjay
For timing of a particular function, you'd be wise to remove the Random() calls, as they can contribute to ~50% of your measured time.
Fred updated the GCC compiler version a few PureBasic releases ago (certainly from 6.10 onwards). I discovered that using this updated C compiler (with the optimizer enabled) can now make a *huge* difference to performance, as it appears to have the ability to auto-vectorize / auto-SIMD its output. In my tests so far it only works when you code in a particular way that it can work with, but when you get it right it can really fly.
The best method I've found is to put this type of code into a procedure, pass the array into the procedure as an argument, along with the size of the array, and the compiler should take care of the rest & you get a speedup of ~16x (at least on my PC). It can also greatly benefit the ASM compiler.
Code: Select all
Mod(n,2) = 20000000 in 260 ms even=9998486
n % 2 = 20000000 in 66 ms even=9998486
even(n) = 20000000 in 76 ms even=9998486
n & 1 = 20000000 in 69 ms even=9998486
*** n & 1 AutoVectorized = 20000000 in 4 ms even=9998486
Done...
Code: Select all
Define.i i,n,e ; the value of n will never be greater than 99
DisableDebugger
OpenConsole()
#Size = 20000000
Dim RndLup.a(#Size) : RandomSeed(0)
For i = 1 To #Size : RndLup(i) = Random(99) : Next
t1 = ElapsedMilliseconds() : e=0
For i=1 To #Size
n=RndLup(i) : If Not Val(Right(Bin(n),1)): e+1: EndIf
Next
Result$+"Bin(n) = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13)
t1 = ElapsedMilliseconds() : e=0
For i=1 To #Size
n=RndLup(i) : If Not Mod(n,2): e+1: EndIf
Next
PrintN("Mod(n,2) = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13))
t1 = ElapsedMilliseconds() : e=0
For i=1 To #Size
n=RndLup(i) : If Not n % 2: e+1: EndIf
Next
PrintN("n % 2 = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13))
t1 = ElapsedMilliseconds() : e=0
Dim even.i(99): For i=0 To 99: even(i)=1-Mod(i,2): Next
For i=1 To #Size
n=RndLup(i) : If even(n): e+1: EndIf
Next
PrintN("even(n) = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13))
t1 = ElapsedMilliseconds() : e = 0
For i=1 To #Size
n = RndLup(i) + 1 : If n & 1 : e + 1 : EndIf
Next
PrintN("n & 1 = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13))
Procedure EvenChk_AutoVectorized(Array arr.a(1),Size)
t1 = ElapsedMilliseconds() : e = 0
For i = 1 To Size : e + 1 - (arr(i) & 1) : Next
PrintN("*** n & 1 AutoVectorized = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13))
EndProcedure
EvenChk_AutoVectorized(RndLup(),#Size)
PrintN("") : PrintN("Done...") : Input()
EnableDebugger
Re: More speed to know if it is even
Posted: Fri Aug 02, 2024 1:50 pm
by NicTheQuick
BarryG wrote: Fri Aug 02, 2024 12:41 pm
This returns 1 for odd and 0 for even:
Code: Select all
Macro IsOdd(num)
num & 1
EndMacro
DisableDebugger
start.q=ElapsedMilliseconds()
For i=1 To 20000000
n=IsOdd(i)
Next
stop.q=ElapsedMilliseconds()
EnableDebugger
Debug "Time: "+Str(stop-start)+"ms" ; 58 ms on my old PC.
Always put the parameters and the whole term into brackets if you use macros, or else you will run into operator priority issues when you use it in a more complex scenario:
Code: Select all
Macro IsOdd(num)
((num) & 1)
EndMacro
Re: More speed to know if it is even
Posted: Sat Aug 03, 2024 1:36 am
by BarryG
Thanks, Nic. I will update my code.
Re: More speed to know if it is even
Posted: Sat Aug 03, 2024 2:12 am
by fvillanova
wilbert wrote: Fri Aug 02, 2024 12:23 pm
It depends that you need it for.
If you need to count the number of evens like in your example, get rid of the if construction.
Code: Select all
For i=1 To 20000000
n=Random(99,0)+1: e+(n&1)
Next
This is a lot faster.
In my program I need to ask if the number is even, it can't just be counting the number of even numbers.
Re: More speed to know if it is even
Posted: Sat Aug 03, 2024 2:19 am
by fvillanova
infratec wrote: Fri Aug 02, 2024 11:59 am
Code: Select all
t1 = ElapsedMilliseconds(): RandomSeed(0): e=0
For i=1 To 20000000
n=Random(99,0)+1
EnableASM
MOV EAX, n
TEST EAX, 1
JZ l_labelend
INC e
LabelEnd:
DisableASM
Next
Result$+"n & 1 = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13)
Not Really faster. (1 -2 ms)
Maybe you need RAX instead of EAX.
Via RAX it was the same speed, I thought it would be faster.
Code: Select all
DisableDebugger
Define.i i,n,e
; the value of n will never be greater than 99
t1 = ElapsedMilliseconds(): RandomSeed(0): e=0
For i=1 To 20000000
n=Random(99,0)+1: If n & 1: e+1: EndIf
Next
Result$+"n & 1 = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13)
t1 = ElapsedMilliseconds(): RandomSeed(0): e=0
For i=1 To 20000000
n=Random(99,0)+1
!MOV RAX, qword [v_n]
!Test RAX,1
!jz l_end
e+1
!l_end:
Next
Result$+"RAX = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13)
EnableDebugger
Debug Result$
Re: More speed to know if it is even
Posted: Sat Aug 03, 2024 2:23 am
by RASHAD
Re: More speed to know if it is even
Posted: Sat Aug 03, 2024 2:29 am
by fvillanova
pjay wrote: Fri Aug 02, 2024 12:49 pm
For timing of a particular function, you'd be wise to remove the Random() calls, as they can contribute to ~50% of your measured time.
Fred updated the GCC compiler version a few PureBasic releases ago (certainly from 6.10 onwards). I discovered that using this updated C compiler (with the optimizer enabled) can now make a *huge* difference to performance, as it appears to have the ability to auto-vectorize / auto-SIMD its output. In my tests so far it only works when you code in a particular way that it can work with, but when you get it right it can really fly.
The best method I've found is to put this type of code into a procedure, pass the array into the procedure as an argument, along with the size of the array, and the compiler should take care of the rest & you get a speedup of ~16x (at least on my PC). It can also greatly benefit the ASM compiler.
Code: Select all
Mod(n,2) = 20000000 in 260 ms even=9998486
n % 2 = 20000000 in 66 ms even=9998486
even(n) = 20000000 in 76 ms even=9998486
n & 1 = 20000000 in 69 ms even=9998486
*** n & 1 AutoVectorized = 20000000 in 4 ms even=9998486
Done...
Code: Select all
Define.i i,n,e ; the value of n will never be greater than 99
DisableDebugger
OpenConsole()
#Size = 20000000
Dim RndLup.a(#Size) : RandomSeed(0)
For i = 1 To #Size : RndLup(i) = Random(99) : Next
t1 = ElapsedMilliseconds() : e=0
For i=1 To #Size
n=RndLup(i) : If Not Val(Right(Bin(n),1)): e+1: EndIf
Next
Result$+"Bin(n) = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13)
t1 = ElapsedMilliseconds() : e=0
For i=1 To #Size
n=RndLup(i) : If Not Mod(n,2): e+1: EndIf
Next
PrintN("Mod(n,2) = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13))
t1 = ElapsedMilliseconds() : e=0
For i=1 To #Size
n=RndLup(i) : If Not n % 2: e+1: EndIf
Next
PrintN("n % 2 = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13))
t1 = ElapsedMilliseconds() : e=0
Dim even.i(99): For i=0 To 99: even(i)=1-Mod(i,2): Next
For i=1 To #Size
n=RndLup(i) : If even(n): e+1: EndIf
Next
PrintN("even(n) = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13))
t1 = ElapsedMilliseconds() : e = 0
For i=1 To #Size
n = RndLup(i) + 1 : If n & 1 : e + 1 : EndIf
Next
PrintN("n & 1 = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13))
Procedure EvenChk_AutoVectorized(Array arr.a(1),Size)
t1 = ElapsedMilliseconds() : e = 0
For i = 1 To Size : e + 1 - (arr(i) & 1) : Next
PrintN("*** n & 1 AutoVectorized = "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms even="+Str(e)+Chr(13))
EndProcedure
EvenChk_AutoVectorized(RndLup(),#Size)
PrintN("") : PrintN("Done...") : Input()
EnableDebugger
The random function I put in the examples was just to generate test numbers to see performance between different techniques. In reality, in my system (program) there is no random function, only numerical results of mathematical equations, which can be EVEN or ODD, and I need to divert the program flow when it is EVEN.
Re: More speed to know if it is even
Posted: Sat Aug 03, 2024 7:03 am
by idle
you won't get much faster than if n & 1 just put the preferred branch as the true clause rather than the else clause.
The objective is to eliminate branching and dependencies between branches so you can gain more from out of order execution so it would effectively execute both of the branches in parallel and then give you the desired result but that's easier said than done.
Re: More speed to know if it is even
Posted: Sat Aug 03, 2024 3:48 pm
by fvillanova
RASHAD wrote: Sat Aug 03, 2024 2:23 am
1 Odd
0 Even
Hi Rashad, using the "n & 1" command the performance is much faster.
But I am looking for an even faster technique because I need to put this inside a subroutine that is processed tens of billions of times in a simulation system that I made and that is processing correctly, I just want to speed up the process.
Re: More speed to know if it is even
Posted: Sat Aug 03, 2024 4:06 pm
by wilbert
fvillanova wrote: Sat Aug 03, 2024 3:48 pm
Hi Rashad, using the "n & 1" command the performance is much faster.
Replacing
n % 2 with
n & 1 is much faster when using the asm backend.
When using the c backend, the c compiler will do the optimization for you.
fvillanova wrote: Sat Aug 03, 2024 3:48 pm
But I am looking for an even faster technique because I need to put this inside a subroutine that is processed tens of billions of times in a simulation system that I made and that is processing correctly, I just want to speed up the process.
I doubt if you will find anything faster as
n & 1 .
I don't know if you can share anything from your subroutine but most likely there will be other code inside your subroutine that can be optimized and have a much bigger impact on performance.