More speed to know if it is even

[AZJIO]

but most likely there will be other code inside your subroutine that can be optimized and have a much bigger impact on performance.

+1
people get hung up on little things, for nanoseconds, without even thinking that a nearby line can ruin all their efforts

[fvillanova]

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.

Hi Wilbert, Yes, you're right.
I'll post the subroutine of my system that needs to check for even results so you can understand it better and see if you have any ideas to speed it up.
I'll have to prepare a real example of the subroutine with the input and output data I need. I'll send it in a few hours. Thanks for your help.

[fvillanova]

Here is the segment of my program that needs to quickly know if two numbers are "even":

Code: Select all

DisableDebugger
Structure FiltroElement
  N.i  
  N1.i
EndStructure
Procedure Split(String.s, Array new.i(1), Separator.s = ",")
  Protected S.String, *S.Integer = @S
  Protected.i asize, i, p
  asize = CountString(String, Separator)
  *S\i = @String
  While i < asize
    p = FindString(S\s, Separator)
    new(i) = Val(PeekS(*S\i, p - 1))
    *S\i + p << #PB_Compiler_Unicode
    i + 1
  Wend
  new(i) = Val(S\s)
  *S\i = 0
 EndProcedure
Define.i i,j,k,n,total_results
Define.s aux
Dim answers.i(27)  ; in this array are the 28 results of an extensive previous processing

; this is an example of processed result ... are always in increasing order of value
aux="1,3,5,6,8,9,10,11,18,32,33,34,38,44,51,72,73,76,80,82,87,88,90,91,93,95,96,98": split(aux,answers(),",")
total_results=28   ;  ( 0 to 27 )

t1 = ElapsedMilliseconds()
For i=1 To 2000000 ; This "for" is not part of the subroutine, it is just here to simulate the processing many times so that we can evaluate the performance of solutions.

; here is the beginning of the subroutine that I need to speed up ( option one )
k=0: n=0: *mat.FiltroElement=@answers() 
For j=0 To total_results-2
If (*mat\N+1) & 1 And (*mat\N1+1) & 1: k+1          
    If k>n: n=k: EndIf 
Else
    k=0
EndIf  
*mat+8
Next 
If n: n+1: EndIf ; here is the result I need, n = what is the highest occurrence of consecutive even answers
; end of subroutine

Next 
Result$+"*mat\ "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms n="+Str(n)+Chr(13)

t1 = ElapsedMilliseconds()
For i=1 To 2000000 ; This "for" is not part of the subroutine, it is just here to simulate the processing many times so that we can evaluate the performance of solutions.

; here is the beginning of the subroutine that I need to speed up ( option two: faster)
k=0: n=0
For j=0 To total_results-2
If (answers(j)+1) & 1 And (answers(j+1)+1) & 1: k+1          
    If k>n: n=k: EndIf 
Else
    k=0
EndIf  
Next 
If n: n+1: EndIf ; here is the result I need, n = what is the highest occurrence of consecutive even answers
; end of subroutine

Next 
Result$+"answers() "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms n="+Str(n)+Chr(13)

EnableDebugger
Debug Result$

Currently the second option above is the fastest.

[Demivec]

Are you compiling as 32 bit or 64 bit? I'm betting it is 64 bit.
Also, are you using the C compiler or assembler compiler?

Either way, here is my entry: Option 3.

Code: Select all

DisableDebugger
Structure FiltroElement
  N.i  
  N1.i
EndStructure

Structure ptr_integer_array
  i.i[0]
EndStructure


Procedure Split(String.s, Array new.i(1), Separator.s = ",")
  Protected S.String, *S.Integer = @S
  Protected.i asize, i, p
  
  asize = CountString(String, Separator)
  *S\i = @String
  While i < asize
    p = FindString(S\s, Separator)
    new(i) = Val(PeekS(*S\i, p - 1))
    *S\i + p << #PB_Compiler_Unicode
    i + 1
  Wend
  new(i) = Val(S\s)
  *S\i = 0
EndProcedure

Define.i i,j,k,n,total_results
Define.s aux
Dim answers.i(27)  ; in this array are the 28 results of an extensive previous processing

; this is an example of processed result ... are always in increasing order of value
aux="1,3,5,6,8,9,10,11,18,32,33,34,38,44,51,72,73,76,80,82,87,88,90,91,93,95,96,98": split(aux,answers(),",")
total_results=28   ;  ( 0 to 27 )

#loop_reps = 2000000

;option 1
Debug "option 1"
t1 = ElapsedMilliseconds()
For i=1 To #loop_reps ; This "for" is not part of the subroutine, it is just here to simulate the processing many times so that we can evaluate the performance of solutions.
  
  ; here is the beginning of the subroutine that I need to speed up ( option one )
  k=0: n=0: *mat.FiltroElement=@answers() 
  For j=0 To total_results-2
    If (*mat\N+1) & 1 And (*mat\N1+1) & 1: k+1          
      If k>n: n=k: EndIf 
    Else
      k=0
    EndIf  
    *mat+8
  Next 
  If n: n+1: EndIf ; here is the result I need, n = what is the highest occurrence of consecutive even answers
                   ; end of subroutine
  
Next 
Result$+"*mat\ "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms n="+Str(n)+Chr(13)

;option 2
Debug "option 2"
t1 = ElapsedMilliseconds()
For i=1 To #loop_reps ; This "for" is not part of the subroutine, it is just here to simulate the processing many times so that we can evaluate the performance of solutions.
  
  ; here is the beginning of the subroutine that I need to speed up ( option two: faster)
  k=0: n=0
  For j=0 To total_results-2
    If (answers(j)+1) & 1 And (answers(j+1)+1) & 1: k+1          
      If k>n: n=k: EndIf 
    Else
      k=0
    EndIf  
  Next 
  If n: n+1: EndIf ; here is the result I need, n = what is the highest occurrence of consecutive even answers
                   ; end of subroutine
  
Next 
Result$+"answers() "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms n="+Str(n)+Chr(13)

;option 3
Debug "option 3"
Define *mat_ia.ptr_integer_array
t1 = ElapsedMilliseconds()
For i=1 To #loop_reps ; This "for" is not part of the subroutine, it is just here to simulate the processing many times so that we can evaluate the performance of solutions.
                      ; here is the beginning of the subroutine that I need to speed up ( option three: fastest )
  *mat_ia=@answers()
  For j = total_results - 1 To 0 Step -1
    If *mat_ia\i[j] & 1
      k=0 
    Else: k+1
      If k > n: n = k: EndIf
    EndIf   
  Next 
  
  Debug "-------"
  ; here is the result I need, n = what is the highest occurrence of consecutive even answers end of subroutine
  If n = 1: n = 0: EndIf
  Debug n
  Debug "============"
Next 
Result$+"*mat\ "+Str(i-1)+" in "+StrF((ElapsedMilliseconds()-t1),0)+" ms n="+Str(n)+Chr(13)


EnableDebugger
Debug Result$

I clock option 3 in as faster with my run times below.

Code: Select all

;All results are for PureBasic v6.11 LTS
;x64 compiler times
*mat\ 2000000 in 103 ms n=3
answers() 2000000 in 94 ms n=3
*mat\ 2000000 in 87 ms n=3

;x64 c compiler times
*mat\ 2000000 in 112 ms n=3
answers() 2000000 in 108 ms n=3
*mat\ 2000000 in 78 ms n=3

;x86 compiler times
*mat\ 2000000 in 112 ms n=13
answers() 2000000 in 88 ms n=3
*mat\ 2000000 in 86 ms n=3

;x86 c compiler times
*mat\ 2000000 in 110 ms n=13
answers() 2000000 in 112 ms n=3
*mat\ 2000000 in 79 ms n=3

The secret to option three is simplification. I record the longest series of even numbers by looking only at one number at a time. I then eliminate the case of only one number in a sequence (results of a sequence count are in the set {n = 0; n > 1}. I just happen to look at the series in reverse to avoid recalculating the loop limit (whether forward or reversed it doesn't change the number in a sequence).

[wilbert]

Here's my approach.
It's quite similar to that of Demivec.

Handcoded asm would still be a bit faster but I don't know if you are using the c or asm backend.

Code: Select all

  ; here is the beginning of the subroutine that I need to speed up
  n = 0: k = 0
  *n_cur.Integer = @answers(0)
  *n_end = *n_cur + total_results*SizeOf(Integer)
  While *n_cur < *n_end
    If *n_cur\i & 1
      k = 0
    Else
      k + 1
      If k > n: n = k: EndIf
    EndIf
    *n_cur + SizeOf(Integer)
  Wend
  If n = 1: n = 0: EndIf
  ; end of subroutine

[Demivec]

I rate wilbert's solution a few more 'clicks' faster (about 7%) than my option.

[wilbert]

When using the c backend with optimization turned on, this is also pretty fast.

Code: Select all

  ; here is the beginning of the subroutine that I need to speed up
  n = 0: k = 0
  For j = total_results-1 To 0 Step -1
    k = (k + 1) & ((answers(j) & 1) - 1)
    If k > n: n = k: EndIf
  Next
  If n = 1: n = 0: EndIf
  ; end of subroutine

When using x64 asm, this can be converted to an asm routine with no jumps inside the main loop that can be used as
n = MaxEvenSequence(@answers(), total_results)

Code: Select all

Procedure.i MaxEvenSequence(*Array, NumItems)
  ; rax is used for max even sequence length
  ; r9 is used for current even sequence length
  !xor rax, rax
  !mov ecx, [p.v_NumItems]
  !sub ecx, 1
  ; exit if NumItems was 0
  !jc .l1
  !mov rdx, [p.p_Array]
  ; clear r9 for temporary use
  !xor r9, r9
  ; main loop
  !.l0:
  !mov r8, [rdx + rcx*8]
  !add r9, 1
  !and r8, 1
  !sub r8, 1
  !and r9, r8
  !cmp r9, rax
  !cmovg rax, r9
  !sub ecx, 1
  !jnc .l0
  ; set rax to 0 when it was 1
  !xor r8, r8
  !cmp rax, 1
  !cmove rax, r8
  !.l1:
  ; return result
  ProcedureReturn
EndProcedure

[fvillanova]

The secret to option three is simplification. I record the longest series of even numbers by looking only at one number at a time. I then eliminate the case of only one number in a sequence (results of a sequence count are in the set {n = 0; n > 1}. I just happen to look at the series in reverse to avoid recalculating the loop limit (whether forward or reversed it doesn't change the number in a sequence).

Thanks for sharing your idea, yes, your simplification is very good but you forgot one small detail:

Code: Select all

  *mat_ia=@answers()
k=0: n=0  ; <<<<<<<< reset the control variables >>>>>>>>>>
  For j = total_results - 1 To 0 Step -1

I am preparing a new post with a modification of your idea and also with Wilbert's solution, I will finish it soon.

[fvillanova]

Code: Select all

Results on windows 11 64
PureBasic 5.73 x64 (for many compatibility reasons) I can't change it, I've already explained this in another topic, this
is the fastest and most efficient version for my systems:
*mat\                         100 ms n=4
answers()                     104 ms n=4
Demivec solution              111 ms n=4
Demivec modified               81 ms n=4
Wilbert solution 1            114 ms n=4
Wilbert solution modified     101 ms n=4
Wilbert solution 2             37 ms n=4  <<<< fantastic, my processing will be much faster

Once again, many thanks to everyone who commented and sent solutions for this increase in the speed of my routine.
To Wilbert, my congratulations for the great solution.
I will show below the changes I made to generate the times shown above.
many thanks again.

Code: Select all

DisableDebugger
Structure FiltroElement
  N.i  
  N1.i
EndStructure
Structure ptr_integer_array
  i.i[0]
EndStructure
Procedure Split(String.s, Array new.i(1), Separator.s = ",")
  
  Protected S.String, *S.Integer = @S
  Protected.i asize, i, p
  asize = CountString(String, Separator)
  *S\i = @String
  While i < asize
    p = FindString(S\s, Separator)
    new(i) = Val(PeekS(*S\i, p - 1))
    *S\i + p << #PB_Compiler_Unicode
    i + 1
  Wend
  new(i) = Val(S\s)
  *S\i = 0
 EndProcedure
Procedure.i MaxEvenSequence(*Array, NumItems)
  ; rax is used for max even sequence length
  ; r9 is used for current even sequence length
  !xor rax, rax
  !mov ecx, [p.v_NumItems]
  !sub ecx, 1
  ; exit if NumItems was 0
  !jc .l1
  !mov rdx, [p.p_Array]
  ; clear r9 for temporary use
  !xor r9, r9
  ; main loop
  !.l0:
  !mov r8, [rdx + rcx*8]
  !add r9, 1
  !and r8, 1
  !sub r8, 1
  !and r9, r8
  !cmp r9, rax
  !cmovg rax, r9
  !sub ecx, 1
  !jnc .l0
  ; set rax to 0 when it was 1
  !xor r8, r8
  !cmp rax, 1
  !cmove rax, r8
  !.l1:
  ; return result
  ProcedureReturn
EndProcedure 
 Define.i i,j,k,n,total_results
Define.s aux
Dim answers.i(27)  ; in this array are the 28 results of an extensive previous processing

; this is an example of processed result ... are always in increasing order of value
;aux="1,3,5,6,8,9,10,11,18,32,33,34,38,44,51,72,73,76,80,82,87,88,90,91,93,95,96,98": split(aux,answers(),",")  ; <<<< Old
 aux="2,4,6,8,9,10,11,12,18,32,33,34,38,44,51,72,73,76,81,82,87,88,90,91,93,95,96,98": split(aux,answers(),",") ; <<<< New
total_results=28   ;  ( 0 to 27 )


#loop_reps = 2000000

t1 = ElapsedMilliseconds()
For i=1 To #loop_reps ; This "for" is not part of the subroutine, it is just here to simulate the processing many times so that we can evaluate the performance of solutions.

; here is the beginning of the subroutine that I need to speed up ( option one )
k=0: n=0: *mat.FiltroElement=@answers() 
For j=0 To total_results-2
If (*mat\N+1) & 1 And (*mat\N1+1) & 1: k+1          
    If k>n: n=k: EndIf 
Else
    k=0
EndIf  
*mat+8
Next 
If n: n+1: EndIf ; here is the result I need, n = what is the highest occurrence of consecutive even answers
; end of subroutine

Next 
Result$+LSet("*mat\ in ",30," ")+StrF((ElapsedMilliseconds()-t1),0)+" ms n="+Str(n)+Chr(13)


t1 = ElapsedMilliseconds()
For i=1 To #loop_reps ; This "for" is not part of the subroutine, it is just here to simulate the processing many times so that we can evaluate the performance of solutions.

; here is the beginning of the subroutine that I need to speed up ( option two: faster)
k=0: n=0
For j=0 To total_results-2
If (answers(j)+1) & 1 And (answers(j+1)+1) & 1: k+1          
    If k>n: n=k: EndIf 
Else
    k=0
EndIf  
Next 
If n: n+1: EndIf ; here is the result I need, n = what is the highest occurrence of consecutive even answers
; end of subroutine

Next 
Result$+LSet("answers() ",30," ")+StrF((ElapsedMilliseconds()-t1),0)+" ms n="+Str(n)+Chr(13)

Define *mat_ia.ptr_integer_array
t1 = ElapsedMilliseconds()
For i=1 To #loop_reps 
  *mat_ia=@answers()
k=0: n=0  
  For j = total_results - 1 To 0 Step -1
    If *mat_ia\i[j] & 1
      k=0 
    Else: k+1
      If k > n: n = k: EndIf
    EndIf   
  Next 
  If n = 1: n = 0: EndIf
Next 
Result$+LSet("Demivec solution ",30," ")+StrF((ElapsedMilliseconds()-t1),0)+" ms n="+Str(n)+Chr(13)


t1 = ElapsedMilliseconds()
For i=1 To #loop_reps 
  *mat_ia=@answers()
k=0: n=0: j=total_results  
!MOV   r13, qword [v_j]  
!l_loopj:
!mov qword [v_j],r13   
    If *mat_ia\i[j-1] & 1
      k=0 
    Else: k+1
      If k > n: n = k: EndIf
    EndIf   
!sub r13, 1
!jnz l_loopj
  If n = 1: n = 0: EndIf
Next 
Result$+LSet("Demivec modified ",30," ")+StrF((ElapsedMilliseconds()-t1),0)+" ms n="+Str(n)+Chr(13)

t1 = ElapsedMilliseconds()
For i=1 To #loop_reps 
; here is the beginning of the subroutine that I need to speed up
  n = 0: k = 0
  For j = total_results-1 To 0 Step -1
    k = (k + 1) & ((answers(j) & 1) - 1)
    If k > n: n = k: EndIf
  Next
  If n = 1: n = 0: EndIf
  ; end of subroutine

Next 
Result$+LSet("Wilbert solution one ",30," ")+StrF((ElapsedMilliseconds()-t1),0)+" ms n="+Str(n)+Chr(13)


t1 = ElapsedMilliseconds()
For i=1 To #loop_reps 
; here is the beginning of the subroutine that I need to speed up
  n = 0: k = 0: j=total_results  
!MOV   r13, qword [v_j]  
!l_loopj1:
!mov qword [v_j],r13  
    k = (k + 1) & ((answers(j-1) & 1) - 1)
    If k > n: n = k: EndIf
!sub r13, 1
!jnz l_loopj1
  If n = 1: n = 0: EndIf
  ; end of subroutine

Next 
Result$+LSet("Wilbert solution modified ",30," ")+StrF((ElapsedMilliseconds()-t1),0)+" ms n="+Str(n)+Chr(13)

t1 = ElapsedMilliseconds()
For i=1 To #loop_reps 
; here is the beginning of the subroutine that I need to speed up
n = MaxEvenSequence(@answers(), total_results)  
; end of subroutine
Next 
Result$+LSet("Wilbert solution 2 ",30," ")+StrF((ElapsedMilliseconds()-t1),0)+" ms n="+Str(n)+Chr(13)



EnableDebugger
Debug Result$

[fvillanova]

I hadn't noticed, with this small change the times
are shorter in the routines modified by me.

Code: Select all

k=0: n=0 
!MOV   r13, qword [v_total_results ]

Removing the instruction: "j=total_results"

[chi]

Code: Select all

Macro isOdd(n)
  1&n
EndMacro

Macro isEven(n)
  1-1&n
EndMacro

Debug isOdd(69)
Debug isEven(420)