Issue with converting tiny classifier routine into a macro

[Skipper]

Hi all,

I'm trying to refactor this small snippet into a macro, to reduce procedure call overheads, as this is one of multiple such routines that is used in a tight loop that runs millions of times before ending. Any function call omitted is a good thing. The code:

Code: Select all

Procedure.i IsLetter(c.s)
  Protected code = Asc(c)
  ProcedureReturn Bool((code >= 65 And code <= 90) Or (code >= 97 And code <= 122) Or c = "_")
EndProcedure

I have quite a few of similar classifier procedures that I all need to convert. Ideally, within the loop, I do not want procedure calls to the classifier and the Bool() contained within.

Any ideas?

cheers
Skipper

[SMaag]

Code: Select all

Macro IsLetter (char)
  Bool((char >= 'A' And char <= 'Z') Or (char >= 'a' And char <= 'z') Or c = '_')
EndMacro

If IsLetter('a')
  Debug "it is a letter"  
Else
  Debug "it is not a letter"
EndIf

here you can find a lot of standard Macros which helps to improve PB-Code.

https://github.com/Maagic7/PureBasicFra ... dule_PX.pb

[STARGÅTE]

The overhead is not the procedure call, it is the usage of a strings and the boolean operations.
When you want to check a character for a certain character set, you should use a data section, for very fast true/false check.
In addition, you should avoid passing a string itself, but only use the pointer to the specific character to be checked.

Here is my code:

Code: Select all

Structure AsciiArray
	a.a[0]
EndStructure

Procedure IsLetter(*Character.Character)
	Protected *IsLetter.AsciiArray = ?IsLetter
	If *Character\c <= 127
		ProcedureReturn *IsLetter\a[*Character\c]
	Else
		ProcedureReturn #False
	EndIf
EndProcedure

DataSection
	IsLetter:
	Data.a 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
	Data.a 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
	Data.a 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
	Data.a 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
	Data.a 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
	Data.a 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1
	Data.a 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
	Data.a 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0
EndDataSection

Debug IsLetter(@"a")
Debug IsLetter(@"_")
Debug IsLetter(@"ß")
Debug IsLetter(@"1")

[Skipper]

Thank you both for your input!

My procedure always only checks a single wchar (Unicode item) from a long string. It's always that size, to I assumed it would make no difference whether I pass a pointer or a string this short. Experimentally I established that doing away with procedure calls speeds up the tight loop significantly, that's why I also wanted to remove them from the classifier code by using macros only - and this includes getting rid of the call to Bool() as well within the macros.

Thanks again, I need to experiment now...

Skipper

[STARGÅTE]

It's always that size, to I assumed it would make no difference whether I pass a pointer or a string this short.

No, unfortunately not.
Even, if the string is just a single character, by passing this small string to a procedure various internal functions have to be called like allocating a memory for this string, copying the string from source to the new target, freeing the allocated memory, ....

Of cause, if you remove the procedure call, you gain speed, but not because of the call itself, but you avoid the passing of a string.

Here is an example to check if the string is equal to "A".
The string version is over 20 times slower than passing the pointer of the string.

Code: Select all

CompilerIf #PB_Compiler_Debugger
	CompilerError "Disable debugger to time measurements!"
CompilerEndIf

Procedure WithString(s.s)
	If s = "A"
		ProcedureReturn #True
	Else
		ProcedureReturn #False
	EndIf
EndProcedure

Procedure WithPointer(*c.Character)
	If *c\c = 'A'
		ProcedureReturn #True
	Else
		ProcedureReturn #False
	EndIf
EndProcedure

OpenConsole()

String.s = "A"
Old = ElapsedMilliseconds()
For I = 1 To 20000000
	WithPointer(@String)
Next
PrintN("Pointer-Version: "+Str(ElapsedMilliseconds()-Old))
Old = ElapsedMilliseconds()
For I = 1 To 20000000
	WithString(String)
Next
PrintN("String-Version: "+Str(ElapsedMilliseconds()-Old))

Input()

[Skipper]

Thank you Stargate, for this insight and the demo code. The pointer based solution is about 34 times faster on my machine. Need to experiment with my application now....

cheers
Skipper

[Piero]

Of cause

My english is very poor, but please let me say that it seems to me like it was generated by a German AI while scraping pineapple pizza web pages

[HeX0R]

My Italian is very poor, but
Il tuo modo invadente di voler sempre fare battute che non sono divertenti è FASTIDIOSO

[Tawbie]

@STARGÅTE
I must say, your solution to Skipper's question is quite clever.
Also your comment/test results about speed of execution gains using pointers even when passing a single character string is very interesting.

[jacdelad]

Of cause

My english is very poor, but please let me say that it seems to me like it was generated by a German AI while scraping pineapple pizza web pages

Bold move accusing Stargate to be a bot (which wouldn't do this error) for using a wrong word which sound similar to the right one...

[DarkDragon]

My Italian is very poor, but
Il tuo modo invadente di voler sempre fare battute che non sono divertenti è FASTIDIOSO

Absolutely. It's not the first time.

[minimy]

What was the point??
DarkDragon, say the true please. Are you an AI? or who is the AI?

About the code +10, really nice to learn. Thanks for share and sorry for the joke

[idle]

Staying on topic

X64 only but was worth a crack, i tried a branchless version which took quite a bit of effort but it was slower and fasm couldn't handle the macro

Code: Select all

CompilerIf #PB_Compiler_Debugger
	CompilerError "Disable debugger to time measurements!"
CompilerEndIf

Global azaz.q = $3FFFFFF03FFFFFF  ;AZaz
Global azazu.q = $3FFFFFF43FFFFFF ;AZaz_   

Procedure IsAZazu(val) 
  If (val >= 65 And val <= 127)
    ProcedureReturn (azazu & (1<<(val - 65))) 
  EndIf
  
EndProcedure 

Macro _IsAZazu(val)     
    (azazu & ((1 << (val-65)) & ~(((val-65) >> 63) | ~((val-65)- 64) >> 63)))
EndMacro  


Structure AsciiArray
	a.a[0]
EndStructure

Procedure IsLetter(val)
	Protected *IsLetter.AsciiArray = ?IsLetter
	If val <= 127 
		ProcedureReturn *IsLetter\a[val]
	Else
		ProcedureReturn #False
	EndIf
EndProcedure

DataSection
	IsLetter:
	Data.a 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
	Data.a 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
	Data.a 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
	Data.a 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
	Data.a 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
	Data.a 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1
	Data.a 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
	Data.a 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0
EndDataSection

Define a,b,x,ra,rb,st,et,et1
x = 1<<21
ra = 0 
rb = 0 
st = ElapsedMilliseconds() 
For a = 0 To x 
  For b = 0 To 255
    If IsLetter(b)
      ra + b
    EndIf   
  Next   
Next   
et = ElapsedMilliseconds()   

For a = 0 To x 
  For b = 0 To 255
    If IsAZazu(b)
      rb+b 
    EndIf   
  Next   
Next   
et1 = ElapsedMilliseconds() 


out.s = "Isletter: " + Str(et-st) + #CRLF$ + "IsAZazu: " + Str(et1-et) + " " + Str(ra) + " " + Str(rb)

MessageRequester("test AZaz_",out) 

[Olli]

This is "SIMDable" :

Code: Select all

Dim NonLetter(65535)
For i = 0 to 65535
 NonLetter(i) = (((i & ~32) - 52) / 13 - 1) >> 1
Next