More speed to know if it is even

[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$

[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.

[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.

[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.

[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.

[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

[NicTheQuick]

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

[BarryG]

Thanks, Nic. I will update my code.

[fvillanova]

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.

[fvillanova]

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$

[RASHAD]

1 Odd
0 Even

Code: Select all

Debug 5 % 2
Debug 4 % 2

[fvillanova]

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.

[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.

[fvillanova]

1 Odd
0 Even

Code: Select all

Debug 5 % 2
Debug 4 % 2

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.

[wilbert]

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.

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.