[Testers Needed] Please give me feedback on which method is the fastest

[Blackholyman]

Hello,

I'd like your help

Can you try the piece of code below and tell me what the msgbox's tells you (simply press Ctrl+c when the msgbox is displayed to copy the text in it)

I'm trying to find out if one method of determining if an integer is between two integers (inclusive) is faster then the other

Code: Select all

#Persistent
#SingleInstance force
SetBatchLines, -1

f1:: ; speed testing fastest way to determine if an integer is between two integers (inclusive)
time1:=time2:=inrange:=inrange2:="" ; clear variables

lower := 50
upper := 100

InputBox, number, time test, Please Enter a number `n`ni.e 88

Y := number-lower
Y := NumGet( NumPut( Y, Var:="ABCD" )-4, 0,"UInt" ) ; Convert Y to unSigned Integer
Q := (upper-lower)+1

QPX( True ) ; Initialise Counter

loop 2073600 ; loop 1920x1080 times
   if (Y < Q)
      inrange := true

time1 := QPX( false ) ; Retrieve Time consumed ( & reset internal vars )

QPX( True ) ; Initialise Counter

loop 2073600 ; loop 1920x1080 times
   if (number >= lower && number <= upper)
      inrange2 := true

time2 := QPX( false ) ; Retrieve Time consumed ( & reset internal vars )

msgbox % "First check method:`nIf number " number " is between " lower "-" upper " is " (inrange?"true":"false") " and it took " time1 "`n`nSecond check method:`nIf number " number " is between " lower "-" upper " is " (inrange2?"true":"false") " and it took " time2
return

QPX( N=0 ) { ; Wrapper for QueryPerformanceCounter()by SKAN | CD: 06/Dec/2009
	Static F,A,Q,P,X ; www.autohotkey.com/forum/viewtopic.php?t=52083 | LM: 10/Dec/2009
	If	( N && !P )
		Return	DllCall("QueryPerformanceFrequency",Int64P,F) + (X:=A:=0) + DllCall("QueryPerformanceCounter",Int64P,P)
	DllCall("QueryPerformanceCounter",Int64P,Q), A:=A+Q-P, P:=Q, X:=X+1
	Return	( N && X=N ) ? (X:=X-1)<<64 : ( N=0 && (R:=A/X/F) ) ? ( R + (A:=P:=X:=0) ) : 1
}

Do try a few numbers both between and outside the range to see if one if faster then the other

Please let me know what you find

PS: Also let me know if you find something that's not working or is off with the way i'm doing this...

[WalkerOfTheDay]

Code: Select all

---------------------------
snippet2.ahk
---------------------------
First check method:
If number 10 is between 50-100 is false and it took 0.338900

Second check method:
If number 10 is between 50-100 is false and it took 0.317896
---------------------------
OK   
---------------------------
---------------------------
snippet2.ahk
---------------------------
First check method:
If number 101 is between 50-100 is false and it took 0.300923

Second check method:
If number 101 is between 50-100 is false and it took 0.549869
---------------------------
OK   
---------------------------
---------------------------
snippet2.ahk
---------------------------
First check method:
If number -1 is between 50-100 is false and it took 0.353718

Second check method:
If number -1 is between 50-100 is false and it took 0.318047
---------------------------
OK   
---------------------------
---------------------------
snippet2.ahk
---------------------------
First check method:
If number 121324548945454897987798945 is between 50-100 is false and it took 0.359450

Second check method:
If number 121324548945454897987798945 is between 50-100 is false and it took 0.520956
---------------------------
OK   
---------------------------

[BoBo]

---------------------------
_Test37.ahk
---------------------------
First check method:
If number 88 is between 50-100 is true and it took 2.075298

Second check method:
If number 88 is between 50-100 is true and it took 2.792947
---------------------------
OK
---------------------------

[jNizM]

Should this not be more like this? (Added a third example similar to first example but do the math every time)

Code: Select all

#NoEnv
SetBatchLines -1

global number_lower := 50
global number_upper := 100
global number_magic := 66
global number_found := true

; ==================================================================

number_diff := (number_upper - number_lower) + 1

QPC(True)

loop 2073600
    if ((number_magic - number_lower) < number_diff)
        number_found := true

Timer1 := QPC(False)

; ==================================================================

QPC(True)

loop 2073600
    if (number_magic >= number_lower) && (number_magic <= number_upper)
        number_found := true

Timer2 := QPC(False)

; ==================================================================

QPC(True)

loop 2073600
    if ((number_magic - number_lower) <= (number_upper - number_lower))
        number_found := true

Timer3 := QPC(False)

; ==================================================================

MsgBox % Timer1 "`n" Timer2 "`n" Timer3

; ==================================================================

QPC(R := 0)
{
    static P := 0, F := 0, Q := DllCall("QueryPerformanceFrequency", "Int64P", F)
    return ! DllCall("QueryPerformanceCounter", "Int64P", Q) + (R ? (P := Q) / F : (Q - P) / F) 
}

Code: Select all

0.371957
0.458114
0.384696

[IMEime]

캡처.jpg (24.79 KiB) Viewed 3731 times

i7 3.6GHz
AHK 64 Unicode

[Blackholyman]

Thank you for helping

@WalkerOfTheDay, @BoBo and @IMEime you seem to be getting something along the same line as me

@jNizM

well I think you did an edit after the first time i read your post something about the first part of the first method needing to be in the timer this i'd say you are right about as below

Code: Select all

As to the code in your post now, about doing the every time, this i'm not sure about, I did a few tests on the code you posted and two of the methods did not work the correct way aka assigning true when the magic number is outside the range

eksample:

Code: Select all

#NoEnv
SetBatchLines -1

global number_lower := 50
global number_upper := 100
global number_magic := 33
global number_found1 := 0
global number_found2 := 0
global number_found3 := 0

; ==================================================================

number_diff := (number_upper - number_lower) + 1

QPC(True)

loop 2073600
    if ((number_magic - number_lower) < number_diff)
        number_found1 := true

Timer1 := QPC(False)

; ==================================================================

QPC(True)

loop 2073600
    if (number_magic >= number_lower) && (number_magic <= number_upper)
        number_found2 := true

Timer2 := QPC(False)

; ==================================================================

QPC(True)

loop 2073600
    if ((number_magic - number_lower) <= (number_upper - number_lower))
        number_found3 := true

Timer3 := QPC(False)

; ==================================================================

MsgBox % "found:" number_found1 " time:" Timer1 "`nfound:" number_found2 " time:" Timer2 "`nfound:" number_found3 " time:" Timer3

; ==================================================================

QPC(R := 0)
{
    static P := 0, F := 0, Q := DllCall("QueryPerformanceFrequency", "Int64P", F)
    return ! DllCall("QueryPerformanceCounter", "Int64P", Q) + (R ? (P := Q) / F : (Q - P) / F) 
}

the method that works if (number_magic >= number_lower) && (number_magic <= number_upper) was the one i'm trying to beat

so with the assignment inside the time it looks like this

Code: Select all

#NoEnv
SetBatchLines, -1

 ; speed testing fastest way to determine if an integer is between two integers (inclusive)
time1:=time2:=inrange:=inrange2:="" ; clear variables

lower := 50
upper := 100

InputBox, number, time test, Please Enter a number `n`ni.e 88

Y := NumGet( NumPut( number-lower, Var:="ABCD" )-4, 0,"UInt" ) ; Convert Y to unSigned Integer
Q := (upper-lower)+1

QPc( True ) ; Initialise Counter

Y := NumGet( NumPut( number-lower, Var:="ABCD" )-4, 0,"UInt" ) ; Convert Y to unSigned Integer
Q := (upper-lower)+1

loop 2073600 ; loop 1920x1080 times
   if (Y < Q)
      inrange := true

time1 := QPc( false ) ; Retrieve Time consumed ( & reset internal vars )

QPc( True ) ; Initialise Counter

loop 2073600 ; loop 1920x1080 times
   if (number >= lower && number <= upper)
      inrange2 := true

time2 := QPc( false ) ; Retrieve Time consumed ( & reset internal vars )

msgbox % "First check method:`nIf number " number " is between " lower "-" upper " is " (inrange?"true":"false") " and it took " time1 "`n`nSecond check method:`nIf number " number " is between " lower "-" upper " is " (inrange?"true":"false") " and it took " time2
return

QPC(R := 0)
{
    static P := 0, F := 0, Q := DllCall("QueryPerformanceFrequency", "Int64P", F)
    return ! DllCall("QueryPerformanceCounter", "Int64P", Q) + (R ? (P := Q) / F : (Q - P) / F) 
}

tests:

First check method:
If number 11 is between 50-100 is false and it took 0.251963

Second check method:
If number 11 is between 50-100 is false and it took 0.242396

First check method:
If number 77 is between 50-100 is true and it took 0.453627

Second check method:
If number 77 is between 50-100 is true and it took 0.655962

First check method:
If number 133 is between 50-100 is false and it took 0.249932

Second check method:
If number 133 is between 50-100 is false and it took 0.467136

unsure if this answers what you're asking about jNizM please let me know

[BoBo]

Code: Select all

First check method:
If number 1234567890 is between 50-100 is true and it took 2.072417

Second check method:
If number 1234567890 is between 50-100 is true and it took 2.006599

Without any doubt (and any other tranquilizing noobish effort ) I proclaim to have the slowest box east of Covfefe
Ooops, that wasn't the requested task

OK, I've to admit that I've added an additional line of real sophisticated code to the script - what might have cost ~1.999999 sec
ClipBoard := "First check method:`nIf number " number " is between " lower "-" upper " is " (inrange?"true":"false") " and it took " time1 "`n`nSecond check method:`nIf number " number " is between " lower "-" upper " is " (inrange?"true":"false") " and it took " time2

[evilC]

FYI, the code does not check the value of inrange2, it always uses inrange, so if method #2 gets the wrong answer, you would not know:

msgbox % "First check method:`nIf number " number " is between " lower "-" upper " is " (inrange?"true":"false") " and it took " time1 "`n`nSecond check method:`nIf number " number " is between " lower "-" upper " is " (inrange?"true":"false") " and it took " time2

[evilC]

On my work PC, #1 is quicker (Xeon E5-2630 @ 2.3 Ghz)

Code: Select all

First check method:
If number 60 is between 50-100 is true and it took 0.627079

Second check method:
If number 60 is between 50-100 is true and it took 1.016142

===============================

First check method:
If number 60 is between 50-100 is true and it took 0.528602

Second check method:
If number 60 is between 50-100 is true and it took 0.850187

==============================

First check method:
If number 10 is between 50-100 is false and it took 0.299013

Second check method:
If number 10 is between 50-100 is false and it took 0.315044

=============================

First check method:
If number 1 is between 50-100 is false and it took 0.294097

Second check method:
If number 1 is between 50-100 is false and it took 0.319882

=============================

First check method:
If number 200 is between 50-100 is false and it took 0.297801

Second check method:
If number 200 is between 50-100 is false and it took 0.599777

=============================

First check method:
If number 99 is between 50-100 is true and it took 0.526438

Second check method:
If number 99 is between 50-100 is true and it took 0.843814

[Blackholyman]

hehe @BoBo it happens

Thanks @evilC

nice catch and you're the first where the first method is also faster when the needle is below the range that is nice to know

@jNizM still hoping to hear more on your take on this as i'm not sure if this is truly fast enough to be of real use...

[evilC]

I wonder if I could make you a C# DLL that would be quicker?
I guess if the code is compiled, not only would it run quicker, but the compiler could potentially optimize it.
I dunno if the overhead of calling a DLL would negate any of those benefits though.

[evilC]

I keep forgetting you can inline compile... duh.

Here you go, two methods to play with:
(Obviously, both examples require CLR)

Syntax is same for both - IsInRange(number, low, high)

#1
Returns an Int

Code: Select all

c# =
(
using System;

public class RangeHelper
{
    public int IsInRange(int num, int low, int high)
    {
        return Convert.ToInt32(num >= low && num <= high);
    }
}
)
asm := CLR_CompileC#(c#, "System.dll")
rh := CLR_CreateObject(asm, "RangeHelper")

msgbox % rh.IsInRange(50, 61, 100)

#2
Returns a bool (AHK seems to interpret as -1 for true ?)

Code: Select all

c# =
(
using System;

public class RangeHelper
{
    public bool IsInRange(int num, int low, int high)
    {
		return num >= low && num <= high;
    }
}
)
asm := CLR_CompileC#(c#, "System.dll")
rh := CLR_CreateObject(asm, "RangeHelper")

msgbox % rh.IsInRange(50, 61, 100)

[Blackholyman]

Hey thank you evilC

the idea for all of this comes from me looking at the c++ source of Autohotkey

and in a well known command i fell over something that looked as if it may hold a chance for optimization

here is the ahk version of what i was looking at

Code: Select all

#NoEnv
SetBatchLines, -1

Haystack_height:=1080
Haystack_width:=1980
Haystack_count := Haystack_height*Haystack_width

Needle_height:=2
Needle_width:=2
Needle_part_count := Needle_height*Needle_width

Haystack_part := Object()

Loop %Haystack_width%
{
	rowArray := []  ;Creates the rowArray
	Haystack_part.push(rowArray)
	Loop %Haystack_height%
		rowArray.Push( A_index )
}	

Needle_part := Object()
index := 100
Loop %Needle_height%
{
	rowArray := [] 
	Needle_part.push(rowArray)
	Loop %Needle_width%
		rowArray.Push( ++index )
}	

search_T := 100
search_H := 100
search_N := 100
Variation := 25

T_low := (Variation > search_T) ? 0 : search_T - Variation
H_low := (Variation > search_H) ? 0 : search_H - Variation
N_low := (Variation > search_N) ? 0 : search_N - Variation
T_high := (Variation > 0xFF - search_T) ? 0xFF : search_T + Variation
H_high := (Variation > 0xFF - search_H) ? 0xFF : search_H + Variation
N_high := (Variation > 0xFF - search_N) ? 0xFF : search_N + Variation

QPC(true)
Loop % Haystack_count
{
	i := A_index-1
	if (Needle_height <= Haystack_height - i/Haystack_width   ; Needle is short enough to fit in the remaining rows of the Haystack.
		&& Needle_width <= Haystack_width - Mod(i,Haystack_width))  ; Needle is narrow enough not to exceed the right-side boundary of the Haystack.
	{
		; Since the first part is a match, check the other parts.
		x := 0, y := 0, j := 0, k := i
		while ( j < Needle_part_count )
		{
			++j

			search_N := Needle_part[k, j]
			search_H := Needle_part[k, j]
			search_T := Needle_part[k, j]

			N := Haystack_part[k, j]
			H := Haystack_part[k, j]
			T := Haystack_part[k, j]
			
			T_Y := NumGet( NumPut( search_T-T_low, Var:="ABCD" )-4, 0,"UInt" ) ; Convert Y to unSigned Integer
			T_Q := (T_high-T_low)+1
			H_Y := NumGet( NumPut( search_H-H_low, Var:="ABCD" )-4, 0,"UInt" ) ; Convert Y to unSigned Integer
			H_Q := (H_high-H_low)+1
			N_Y := NumGet( NumPut( search_N-N_low, Var:="ABCD" )-4, 0,"UInt" ) ; Convert Y to unSigned Integer
			N_Q := (N_high-N_low)+1
			
			
			if (!(found := T_Y < T_Q && H_Y < H_Q && N_Y < N_Q))
				break ; At least one doesn't match, so this candidate is discarded.
			if (++x < Needle_width) ; We're still within the same row of the Needle, so just move on to the next Haystack part.
				++k ;
			else ; We're starting a new row of the Needle.
			{
				x := 0						; Return to the leftmost column of the Needle.
				++y 						; Move one row downward in the Needle.
				k := i + y*Haystack_width	; Verified correct.
			}
		}
		if (found) ; Complete match found.
			break
	}
}
time1 := QPC(false)

QPC(true)
Loop % Haystack_count
{
	i := A_index-1
	if (Needle_height <= Haystack_height - i/Haystack_width   ; Needle is short enough to fit in the remaining rows of the Haystack.
		&& Needle_width <= Haystack_width - Mod(i,Haystack_width))  ; Needle is narrow enough not to exceed the right-side boundary of the Haystack.
	{
		; Since the first part is a match, check the other parts.
		x := 0, y := 0, j := 0, k := i
		while ( j < Needle_part_count )
		{
			++j

			search_N := Needle_part[k, j]
			search_H := Needle_part[k, j]
			search_T := Needle_part[k, j]

			N := Haystack_part[k, j]
			H := Haystack_part[k, j]
			T := Haystack_part[k, j]
			
			if (!(found := T >= T_low && T <= T_high && H >= H_low && H <= H_high && N >= N_low && N <= N_high))
				break ; At least one doesn't match, so this candidate is discarded.
			if (++x < Needle_width) ; We're still within the same row of the Needle, so just move on to the next Haystack part.
				++k ;
			else ; We're starting a new row of the Needle.
			{
				x := 0						; Return to the leftmost column of the Needle.
				++y 						; Move one row downward in the Needle.
				k := i + y*Haystack_width	; Verified correct.
			}
		}
		if (found) ; Complete match found.
			break
	}
}
time2 := QPC(false)

msgbox % "time1=" time1 "`ntime2=" time2
return



QPC(R := 0)
{
    static P := 0, F := 0, Q := DllCall("QueryPerformanceFrequency", "Int64P", F)
    return ! DllCall("QueryPerformanceCounter", "Int64P", Q) + (R ? (P := Q) / F : (Q - P) / F) 
}

^ this is not really working code but it may give you a better idea of what i'm trying to test... i've never worked with C++ so i had the idea to first try it in AHK and see if that worked better and if so try and do it in c++

AHK

Code: Select all

N_Y := NumGet( NumPut( search_N-N_low, Var:="ABCD" )-4, 0,"UInt" )
N_Q := (N_high-N_low)+1
if (!(N_Y < N_Q))
    in_range(search_N)

c++

Code: Select all

if ((unsigned)(search_N-N_low) <= (N_high-N_low))
        in_range(search_N);

[masheen]

[evilC]

What is this, pixel search?

If you are replicating AHK's C++ source in AHK, then surely you might see quite different results?
AHK's C source will be optimized by the compiler I would guess, but AHK code would not be? So if a certain way of doing the maths runs quicker in AHK, it may not run quicker in C?

If you want the most efficient pixel operations, then why not look around for some highly optimized code, then we can try to make it available from AHK? This looks like it could form the basis of a candidate: https://www.codeproject.com/Articles/61 ... thout-unsa

[Blackholyman]

modified but yes it comes from the pixel/imagesearch source https://github.com/Lexikos/AutoHotkey_L ... .cpp#L5052

And together with this post https://stackoverflow.com/questions/170 ... usive-with

I just wished to test that method out, and to me, it seems that when using the method in Autohotkey it does give a speed improvement, just as the poster doing it in c/c++ says it does for him in he's complied project.

[evilC]

Yeah, but what happens if you do the same technique in C# and call it from AHK? Is it even quicker?

Also, is the code not giving a fair comparison?

Should QPX( True ) ; Initialise Counter not be before

Code: Select all

Y := number-lower
Y := NumGet( NumPut( Y, Var:="ABCD" )-4, 0,"UInt" ) ; Convert Y to unSigned Integer
Q := (upper-lower)+1

?

[Blackholyman]

Well Im not sure if calling from C# or submitting the changed c++ on github is better.

As to the numput and numget being inside the timer well kinda but i was only trying to test the speed of the if compaisum

As in c++ it looks as if you simply tell the if to do the if without the sign on the first value if ((unsigned)

[jNizM]

You can also try mcode =)

and this is what I did in my post

// diff = (end - start) + 1
#define POINT_IN_RANGE_AND_INCREMENT(p, range) ((p++ - range.start) < range.diff)

Code: Select all

; number_diff := (number_upper - number_lower) + 1    ; for fixed values outside of timer

QPC(True)

number_diff := (number_upper - number_lower) + 1    ; for changing values inside of timer

loop 2073600
    if ((number_magic - number_lower) < number_diff)
        number_found := true

Timer1 := QPC(False)

[Helgef]

You have to compile the loop to gain a performance vs script. You cannot loop DllCall(.). You need 1 DllCall doing 2M compairisons, not 2M DllCAll doing 1 compairson.