Why are ValF & ValD so slow?

[pjay]

I was recently asked to look at improving the performance of some ascii .OBJ parsing code that I wrote a fair few years ago.

Some gains were made by improving the string processing but a large bottleneck was surprisingly the performance of the VaLD() command.

I looked for an alternative solution and landed on a function that Infratec had posted a few years ago, this worked really well but needed expanding to handle some special cases - this is now done & it's still running substantially faster than PBs own function (> 20x).

I handled the exponent, Nan / Infinity states etc., so my question is; what is PBs' ValD() doing that takes up so much more time that I might be missing?

[skywalk]

ValD() is slower than FindString() or CountString()?
How much improvement are you expecting?
Did you compare C atof()?

[STARGÅTE]

Surprisingly, ValD() is indeed relatively slow.
On my system ValD() needs roughly 1.4 µs itself for one call.
With the same string CountString() e.g. just needs 0.012 µs.
And also Val() needs just a small fraction of µs. So it is not the digit to string conversion itself, which makes the function slow.

Code: Select all

#Counts = 1000000

Time = ElapsedMilliseconds()
String.s = "31415.92e-4"
For I = 1 To #Counts
	Double.d = ValD(String)
	;Integer.i = Val(String)
	;CountString(String, "1")
Next
Time = ElapsedMilliseconds()-Time

OpenConsole()
PrintN("Single call time: "+StrD(1000.0*Time/#Counts)+" µs")
Input()

[pjay]

ValD() is slower than FindString() or CountString()?

I don't use PBs string functions in this particular code skywalk, but a quick test still suggested so:

Code: Select all

-------------------------------------------------
ValD() Performance comparison:
Backend: ASM
-------------------------------------------------

Time for 2500000 iterations of PB ValD: 2072ms - checksum: 4035780.1119999746
Time for 2500000 iterations of modified ValD: 98ms - checksum: 4035780.1119999746
 - 21.1 times faster

Time for 2500000 iterations of CountString & FindString: 117ms

I had previously tried your atof suggestion but it resulted in an undefined symbol error (on Win x64).

[AZJIO]

Why should the CountString() function be slower? It iterates over the characters in one pass, increasing the counter when a match is found.
The ValD() function checks different record formats, including 1.2345e-2.
Why is ValD() used instead of Val()?

[pjay]

Why should the CountString() function be slower? It iterates over the characters in one pass, increasing the counter when a match is found.
The ValD() function checks different record formats, including 1.2345e-2.
Why is ValD() used instead of Val()?

Who were these questions directed towards?

[AZJIO]

Code: Select all

EnableExplicit
DisableDebugger

Procedure.d StrToNum(*c.Character)
	Protected isLeftPart = 1
	Protected WholePart, FractionalPart, negative
	Protected *c0
	Protected res.d
	
	If *c = 0 Or *c\c = 0
		ProcedureReturn 0
	EndIf
	
	If *c\c = '-'
		*c + SizeOf(Character)
		negative = 1
	EndIf
	
	While *c\c = '0'
		*c + SizeOf(Character)
	Wend
	*c0 = *c
	
	While *c\c
		If *c\c > '9' Or *c\c < '0'
			Break
		Else
			WholePart + 1
		EndIf
		*c + SizeOf(Character)
	Wend
	
	*c = *c0
	While *c\c
		Select *c\c
			Case '0' To '9'
				If isLeftPart
					WholePart - 1
					res + (*c\c - 48) * Pow(10, WholePart)
				Else
					FractionalPart + 1
					res + (*c\c - 48) / Pow(10, FractionalPart)
				EndIf
			Case '.'
				isLeftPart = 0
; 			Case 'e', 'E'
			Default
				Break
		EndSelect
		*c + SizeOf(Character)
	Wend
	If negative
		res = -res
	EndIf
	
	ProcedureReturn res
EndProcedure


; Debug StrToNum(@"00123")
; Debug StrToNum(@"-12 3")
; Debug StrToNum(@"567.123")
; Debug StrToNum(@"000123.00456")
; Debug StrToNum(@".789")
; Debug StrToNum(@"789.")

#Counts = 1000000
Define Time, String.s, Double.d, i

Time = ElapsedMilliseconds()
String = "567.123"
For i = 1 To #Counts
	Double = StrToNum(@String)
Next
Time = ElapsedMilliseconds()-Time

OpenConsole()
PrintN("Single call time: "+StrD(1000.0*Time/#Counts)+" µs")
Input()

[pjay]

I appreciate you trying to help, but what you've posted wasn't relevant to my original question.

Besides, your StrToNum() procedure doesn't support exponent & is still slower than the modified Infratec version I used.

[AZJIO]

Give a link to what you are using.
2. There is always an opportunity to simplify for special cases. The function eats different formats. If you have one format, then you can eliminate some checks, thereby speeding up the function. To do this, we need to see what you are using and your data format.

[pjay]

You've missed my point - I don't need help with speeding anything up as that's already done.

I was merely curious as to why the built-in ValD() & ValF() functions were relatively slow in comparison to Infratecs code (even after modifications to cover special cases, such as the exponent).

Infratecs original code can be found in the thread here: viewtopic.php?p=493922

[AZJIO]

1. The ValD() function ignores spaces at the beginning of a string.
2. The ValD() function works with negative numbers.
3. The ValD() function works with exponential notation of numbers, such as 1.2345e-2.
4. Try writing letters at the end of the number and compare the results.

[Fred]

We set the locale everytime, that why it's slow. I will try to rework this and use wtof() which seems to be fastest than sscanf(). Could you post the PB version you are using so I can do some speed tests ?

[pjay]

Hi Fred, thanks for looking (and the reason for performance).

I'm using PB versions Win x64 v6.21 & v6.3b2, the test code I used is below:

Code: Select all

EnableExplicit
OpenConsole()

#doPerf = #True ; enable / disable performance check

Procedure.d _ValD(*pString.ascii, decimalChar.a = '.', expChar.a = 'e', endChar.a = #Null, charSize.l = 2) ; extension of infratecs code from https://www.purebasic.fr/english/viewtopic.php?p=493922 - pjay25
  DisableDebugger
  Protected MainValue.q, DecimalValue.q, Factor.q = 1, ValueSign.l = 1, exponent.d = 1.0, expSign.l = 1, expVal.q, *pLong.long, txt.s

  If Not *pString : ProcedureReturn 0.0 : EndIf ; null pointer exit check
   
  While *pString\a = ' ' : *pString + charSize : Wend ; trim the start
  
  If *pString\a = '-' : *pString + charSize : ValueSign = -1 : EndIf ; is a negative?
  If *pString\a = '+' : *pString + charSize : EndIf   ; ignore positive.
  While *pString\a = '0' : *pString + charSize : Wend ; ignore leading zeroes.
  
  If *pString\a < 46 Or *pString\a > 57 Or *pString\a = 47 ; first char not a numeric?
    
    ; is it a PB or C Hexadecimal or Binary?
    If *pString\a = 'x' Or *pString\a = 'X' Or *pString\a = '$' Or *pString\a = '%' Or *pString\a = 'b'  Or *pString\a = 'B' ;
      If *pString\a = 'x' Or *pString\a = 'X' : *pString + charSize : txt = "$"  ; if is 'c' hex, add '$' prefix and skip char
      ElseIf *pString\a = 'b' Or *pString\a = 'B' : *pString + charSize : txt = "%"  : EndIf ; if is 'b' binary, add '%' prefix and skip char
      Protected *store  = *pString
      While *pString\a <> endChar : *pString + charSize : Wend ; get length
      ProcedureReturn Val(txt +  PeekS(*store, (*pString - *Store) / charSize)) * ValueSign
    EndIf
    
    ; NaN & infinity - a bit hacky but should be safe...
    *pLong = *pString
    If *pLong\l = 6357070 : ProcedureReturn NaN() * ValueSign : EndIf
    If *pLong\l = 4784171 : ProcedureReturn Infinity() * ValueSign : EndIf
    If *pLong\l = 7209033 : ProcedureReturn Infinity() * ValueSign : EndIf
    
    ProcedureReturn 0.0 ; exit on basis of non-numeric first character
  EndIf
  If *pString\a < 46 Or *pString\a = 47 : ProcedureReturn 0.0 : EndIf ; first char not a numeric?

  While *pString\a <> endChar : If *pString\a = decimalChar : *pString + charSize : Break : Else : MainValue * 10 + *pString\a - '0' : EndIf : *pString + charSize
    If *pString\a = expChar Or *pString\a = expChar - 32 : *pString + charSize ; is an exponent? (e / E / d / D)
      If *pString\a = '-' : *pString + charSize : expSign = -1 : EndIf ; is negative?
      While *pString\a : If *pString\a = decimalChar : *pString + charSize : Break : Else : expVal * 10 + (*pString\a - '0') : EndIf : *pString + charSize : Wend
      exponent = Pow(10.0, expVal * expSign) : Break
    EndIf
    If *pString\a < 46 Or *pString\a > 57 Or *pString\a = 47 : Break : EndIf ; exit if non numeric seen
  Wend
  
  If *pString\a > 47 And *pString\a < 58 ; is next char numeric?
    While *pString\a <> endChar
      If *pString\a = 46 Or *pString\a = decimalChar : Break : EndIf ; exit if secondary decimal point seen
      If *pString\a > 47 And *pString\a < 58 : DecimalValue * 10 + *pString\a - '0' : Factor * 10 : : EndIf : *pString + charSize
      If *pString\a = expChar Or *pString\a = expChar - 32 : *pString + charSize ; is an exponent? (e / E / d / D)
        If *pString\a = '-' : *pString + charSize : expSign = -1 : EndIf ; is negative?
        While *pString\a : If *pString\a = decimalChar : *pString + charSize : Break : Else : expVal * 10 + *pString\a - '0' : EndIf : *pString + charSize : Wend
        exponent = Pow(10.0, expVal * expSign) : Break
      EndIf
    Wend
  EndIf
  
  ProcedureReturn ((MainValue + (DecimalValue / Factor)) * ValueSign) * exponent
  EnableDebugger
EndProcedure

; --- uncomment the 2 lines below for drop-in replacement ---
;Procedure.d __ValD(txt.s) : ProcedureReturn _ValD(@txt) : EndProcedure
;Macro ValD(txt) : __ValD(txt) : EndMacro

ImportC ""
  wtof.d(*txt) As "_wtof"
EndImport

PrintN("-------------------------------------------------")
PrintN("Output comparison:")
PrintN("-------------------------------------------------") : 
Procedure testString(tst.s)
  Protected pj.s = StrD(_ValD(@tst)), pb.s = StrD(ValD(tst)), c.s = StrD(wtof(tst)), txt.s
  txt.s = "Input: '" + tst + "'" : txt + Space(20 - Len(txt))
  txt.s + "_ValD(): '" + pj + "'" : txt + Space(40 - Len(txt))
  txt.s + "wtof(): '" + c + "'" : txt + Space(60 - Len(txt))
  txt.s + "PB ValD(): '" + pb +"'"  : txt + Space(83 - Len(txt))
  If pb = pj And pj = c : txt + ": Pass." : Else : txt + ":<<< Difference." : EndIf 
  PrintN(txt)
EndProcedure
Define stringCount.l, myLoop.l, loop, time, time1, time2, time3, ttl1.d, ttl2.d, ttl3.d, count.l, count3.l

;/ read in the test strings from the datasection
Read.l stringCount : Dim stringlist.s(stringCount) : stringCount - 1
For myLoop = 0 To stringCount : Read.s stringlist.s(myLoop) : testString(stringlist.s(myLoop)) : Next

Procedure.s getBackendStr()
  Protected txt.s = "Backend: "
  CompilerIf #PB_Compiler_Backend = #PB_Backend_C
    CompilerIf #PB_Compiler_Optimizer : txt + "C Optimized" : CompilerElse : txt + "C" : CompilerEndIf
  CompilerElse
    txt + "ASM"
  CompilerEndIf
  ProcedureReturn txt
EndProcedure

CompilerIf #doPerf = #True
  
  PrintN("")
  PrintN("-------------------------------------------------") : PrintN("ValD Performance comparison: " + getBackendStr())
  
  ;{ build random numeric string array
  #Loops = 50
  #arraySize = 50000
  Dim strings.s(#arraySize)
  RandomSeed(2)
  For myloop = 0 To #arraySize
    Define.s tstval.s = ""
    
    If Random(1) = 0 : tstval = "-" : EndIf
    If Random(8) = 1
      tstval + Str(Random(9))
    Else  
      tstval.s + Str(Random(5000))
      If Random(1) = 0
        tstval + "." + Str(1 + Random(500))
        If Random(1) = 0 : tstval + "e-" + Str(2 + Random(5)) : EndIf
      EndIf
    EndIf
    
    strings.s(myloop) = tstval
  Next
  ;}
  
  PrintN("-------------------------------------------------")
  ;Debug wtof(0) ; null check - will crash
  ;Debug _vald(0) ; null check - crash prevented
  
  time = ElapsedMilliseconds()
  For loop = 1 To #Loops
    For myLoop = 0 To #arraySize : ttl1 + ValD(strings.s(myLoop)) : Next : count + #arraySize + 1
  Next
  time1 = ElapsedMilliseconds() - time
  PrintN("Time for PB ValD: " + Str(time1) + "ms - checksum: " + StrD(ttl1))
  
  time = ElapsedMilliseconds()
  For loop = 1 To #Loops
    For myLoop = 0 To #arraySize : ttl2 + _ValD(@strings.s(myLoop)) : Next
  Next
  time2 = ElapsedMilliseconds() - time
  PrintN("Time for modified ValD: " + Str(time2) + "ms - checksum: " + StrD(ttl2))
  
  time = ElapsedMilliseconds()
  For loop = 1 To #Loops
    For myLoop = 0 To #arraySize : ttl3 + wtof(@strings.s(myLoop)) : Next
  Next
  time3 = ElapsedMilliseconds() - time
  
  PrintN("Time for wtof: " + Str(time3) + "ms - checksum: " + StrD(ttl3))
  PrintN(" - _ValD is " + StrF((time1 / time2) , 1) + " times faster than ValD - Iterations: " + Str(Count))
CompilerEndIf

Input()

DataSection
  Data.l 32
  Data.s "230199", "-230199", "1.1", "-1.1", "+1.1", "--1.1", ".1", "2.23e-03", "-2.923e01", "-2.923E01", "300e05", "NaN12345", "NaN", "Infinity", "-Infinity", "+Infinity", "808pj", "pj808", " 808", "808 ", "1.1a", "1.1.1", "1.1.1.1", "1a1.1a1"
  Data.s "0.1.010", "-.010", "--10.5", "%10001", "0b10001", "$beef", "0xbeef" , "0xboof" ;
EndDataSection

Edit #4 - Added endpoint delimiter, hex and binary conversion fallback, parameterized decimal & exponent character for locale purposes.

[SPH]

Hi Fred, thanks for looking (and the reason for performance).

The test code I used is below:

Code: Select all

EnableExplicit
OpenConsole()

Procedure.d _ValD(*pUniString.string, endChar.a = #Null) ; extension of infratecs code from https://www.purebasic.fr/english/viewtopic.php?p=493922 
  DisableDebugger
  Protected MainValue.q, DecimalValue.q, Factor.q = 1, ValueSign.q = 1, *pString.character = *pUniString, exponent.d = 1.0, expSign.q = 1, expVal.q, *scTest.character
  Protected decimalChar.l = '.'
  
  While *pString\c = ' ' : *pString + 2 : Wend ; trim the start
  
  ; single digit quicky?
  *scTest = *pString + 2 : If *scTest\c = 0 : If *pString\c > 47 And *pString\c < 58 : ProcedureReturn *pString\c - '0' : Else : ProcedureReturn 0.0 : EndIf : EndIf
  
  Protected *pLong.long = *pString 
  If *pLong\l = 6357070 : ProcedureReturn NaN() : EndIf
  If *pLong\l = 4784171 : ProcedureReturn Infinity() : EndIf
  If *pLong\l = 7209033 : ProcedureReturn Infinity() : EndIf
  If *pLong\l = 4784173 : ProcedureReturn -Infinity() : EndIf
  If *pString\c = '-' : *pString + 2 : ValueSign = -1 : EndIf
  If *pString\c = '+' : *pString + 2 : EndIf
  If *pString\c < 46 Or *pString\c > 57 Or *pString\c = 47 : ProcedureReturn 0.0 : EndIf
  
  While *pString\c <> endChar : If *pString\c = decimalChar : *pString + 2 : Break : Else : MainValue * 10 + (*pString\c - '0') : EndIf : *pString + 2
    If *pString\c = 'e' Or *pString\c = 'E' : *pString + 2
      If *pString\c = '-' : *pString + 2 : expSign = -1 : EndIf
      While *pString\c : If *pString\c = decimalChar : *pString + 2 : Break : Else : expVal * 10 + (*pString\c - '0') : EndIf : *pString + 2 : Wend
      exponent = Pow(10, expVal * expSign) : Break
    EndIf
    If *pString\c < 46 Or *pString\c > 57 Or *pString\c = 47 : Break : EndIf
  Wend
  
  If *pString\c > 47 And *pString\c < 58
    While *pString\c <> endChar
      DecimalValue * 10 + (*pString\c - '0') : Factor * 10 : *pString + 2
      If *pString\c = 'e' Or *pString\c = 'E' : *pString + 2
        If *pString\c = '-' : *pString + 2 : expSign = -1 : EndIf
        While *pString\c : If *pString\c = decimalChar : *pString + 2 : Break : Else : expVal * 10 + (*pString\c - '0') : EndIf : *pString + 2 : Wend
        exponent = Pow(10, expVal * expSign) : Break
      EndIf
    Wend
  EndIf
  ProcedureReturn ((MainValue + (DecimalValue / Factor)) * ValueSign) * exponent
EndProcedure
;Procedure.d __ValD(txt.s) : ProcedureReturn _ValD(@txt) : EndProcedure
;Macro ValD(txt) : __ValD(txt) : EndMacro


PrintN("-------------------------------------------------")
PrintN("Output comparison:")
PrintN("-------------------------------------------------") : 
Procedure testString(tst.s)
  Protected pj.s = StrD(_ValD(@tst)), pb.s = StrD(ValD(tst)), txt.s
  txt.s = "'" + tst + "'" : txt + Space(15 - Len(txt))
  txt.s + "_ValD(): '" + pj + "'" : txt + Space(40 - Len(txt))
  txt.s + "PB ValD(): '" + pb +"'"  : txt + Space(65 - Len(txt))
  If pb = pj : txt + ": Pass." : Else : txt + ":<<< Difference." : EndIf 
  PrintN(txt)
EndProcedure
Define stringCount.l, myLoop.l, loop, time, time1, time2, time3, ttl1.d, ttl2.d, ttl3.d, count.l, count3.l

;/ read in the test strings from the datasection
Read.l stringCount : Dim stringlist.s(stringCount) : stringCount - 1
For myLoop = 0 To stringCount : Read.s stringlist.s(myLoop) : testString(stringlist.s(myLoop)) : Next

Procedure.s getBackendStr()
  Protected txt.s = "Backend: "
  CompilerIf #PB_Compiler_Backend = #PB_Backend_C
    CompilerIf #PB_Compiler_Optimizer : txt + "C Optimized" : CompilerElse : txt + "C" : CompilerEndIf
  CompilerElse
    txt + "ASM"
  CompilerEndIf
  ProcedureReturn txt
EndProcedure

PrintN("")
PrintN("-------------------------------------------------") : PrintN("ValD Performance comparison: " + getBackendStr())


;/ build random numeric string array
#Loops = 50
#arraySize = 50000
Dim strings.s(#arraySize)
RandomSeed(2)
For myloop = 0 To #arraySize
  Define.s tstval.s = ""
  If Random(1) = 0 : tstval = "-" : EndIf
  tstval.s + Str(Random(5000))
  If Random(1) = 0
    tstval + "." + Str(1 + Random(500))
    If Random(1) = 0 : tstval + "e-" + Str(2 + Random(8)) : EndIf
  EndIf
  strings.s(myloop) = tstval
Next

PrintN("-------------------------------------------------")

time = ElapsedMilliseconds()
For loop = 1 To #Loops
  For myLoop = 0 To #arraySize : ttl1 + ValD(strings.s(myLoop)) : Next : count + #arraySize + 1
Next
time1 = ElapsedMilliseconds() - time
PrintN("Time for PB ValD: " + Str(time1) + "ms - checksum: " + StrD(ttl1))

time = ElapsedMilliseconds()
For loop = 1 To #Loops
  For myLoop = 0 To #arraySize : ttl2 + _ValD(@strings.s(myLoop)) : Next
Next
time2 = ElapsedMilliseconds() - time
PrintN("Time for modified ValD: " + Str(time2) + "ms - checksum: " + StrD(ttl2))
PrintN(" - " + StrF((time1 / time2) , 1) + " times faster - Iterations: " + Str(Count))

Input()

DataSection
  Data.l 19
  Data.s "230199", "-230199", "1.1", "-1.1", "+1.1", "--1.1", ".1", "2.23e-03", "-2.923e01", "-2.923E01", "300e05", "NaN12345", "NaN", "Infinity", "-Infinity", "+Infinity", "808pj", "pj808", " 808", "808 "
EndDataSection

With which version of PB?

[AZJIO]

Since the Val() function is fast, I used it instead of calculating it myself. I added the Pow2() function because I think it will be faster with integers.

Code: Select all

EnableExplicit
DisableDebugger

Procedure Pow2(n, replay)
	Protected i, res = 1
	For i = 1 To replay
		res * n
	Next
	ProcedureReturn res
EndProcedure

	
Procedure.d StrToNum(*c.Character)
	Protected pos, negative
	Protected *c0
	Protected res.d
	
	If *c = 0 Or *c\c = 0
		ProcedureReturn 0
	EndIf
	
	While *c\c = ' ' Or *c\c = '	'
		*c + SizeOf(Character)
	Wend
	
	If *c\c = '-'
		*c + SizeOf(Character)
		negative = 1
	EndIf
	
	While *c\c = '0'
		*c + SizeOf(Character)
	Wend
	
	*c0 = *c ; запоминаем позицию целой части
	While *c\c
		Select *c\c
			Case '0' To '9'
				pos + 1
			Case '.'
				res = Val(PeekS(*c0, pos)) ; получаем целую часть
				*c + SizeOf(Character)
				pos = 0
				*c0 = *c ; запоминаем позицию дробной части
				While *c\c
					Select *c\c
						Case '0' To '9'
							pos + 1
						Default
							Break
					EndSelect
					*c + SizeOf(Character)
				Wend
				If pos
					res + Val(PeekS(*c0, pos)) / Pow2(10, pos) ; получаем дробную часть
				EndIf
				pos = 0
				Break
			Default
				; если нет точки, то выпрыгиваем, это целое число
				Break
		EndSelect
		*c + SizeOf(Character)
	Wend
	If pos
; 		Debug pos
		res = Val(PeekS(*c0, pos)) ; получаем целую часть
	EndIf
	
	If negative
		res = -res
	EndIf
	
	ProcedureReturn res
EndProcedure

; Debug StrToNum(@"00123")
; Debug StrToNum(@"-12 3")
; Debug StrToNum(@"567.123")
; Debug StrToNum(@"000123.00456")
; Debug StrToNum(@".789")
; Debug StrToNum(@"789.")

#Counts = 1000000
Define Time, String.s, Double.d, i

Time = ElapsedMilliseconds()
String = "567.123"
For i = 1 To #Counts
	Double = StrToNum(@String)
Next
Time = ElapsedMilliseconds()-Time

OpenConsole()
PrintN("Single call time: "+StrD(1000.0*Time/#Counts)+" µs")
Input()