Faster ways to convert strings to doubles?

[Samuel]

I'm loading very large data files and the process of converting the strings to doubles is one of the bigger bottlenecks.
Does anyone know of a faster method or do I just have to live with it as it is?

Code: Select all

;Runs at about 1600 milliseconds for me with the debugger off.
;I haven't noticed any major speed differences between floats and doubles.

EnableExplicit

Define.i CTR
Define.i StartTime
Define.i ElapsedTime
Define.d Value
Define.s String

StartTime = ElapsedMilliseconds()

For CTR = 1 To 1000000
  String = "13215.33414554664"
  Value = ValD(String)
Next
  
ElapsedTime = ElapsedMilliseconds() - StartTime
MessageRequester("Time!", "Elapsed Milliseconds : " + Str(ElapsedTime))

[J. Baker]

Turning unicode off will give some speed. Otherwise someone who knows asm may be of help.

[JHPJHP]

Removed; unhelpful results.

[wilbert]

Does anyone know of a faster method or do I just have to live with it as it is?

ValD has to be able to handle a lot of different situations. For example

Code: Select all

Debug ValD("-1.5E-3")

It also has to check for invalid characters.
If the strings you have to parse are all positive decimal values like the example you posted and you don't have to check for invalid characters, you could try to write your own parser.
Otherwise I think you just have to live with it.

[J. Baker]

It also has to check for invalid characters.

That's a good point. Maybe a #PB_Numeric_Only optional flag could be requested for speed optimization. The developer would have to know that the string(s) only use numeric characters of course.

Code: Select all

ValD(String$, #PB_Numeric_Only)

[infratec]

Hi,

a first step:

Code: Select all

Procedure.d CustomValD(String$)
  
  Protected DoubleValue.d, MainValue.i, DezimalValue.i, Factor.i, *pString.Character, Length.i, i.i, PointFlag.i
  
  
  *pString = @String$
  
  Length = Len(String$) - 1
  
  Factor = 1
  
  For i = 0 To Length
    
    Debug *pString\c
    
    If PointFlag
      DezimalValue * 10
      DezimalValue + (*pString\c - '0')
      Factor * 10
    Else
      If *pString\c = '.'
        PointFlag = #True
      Else
        MainValue * 10
        MainValue + (*pString\c - '0')
      EndIf
    EndIf
    
    *pString + 2
    
  Next i
  
  Debug "----"
  
  ProcedureReturn MainValue + (DezimalValue / Factor)
  
EndProcedure

Bernd

[infratec]

Step 2

But as usual the improvements are smaller

Code: Select all

Procedure.d CustomValD(String$)
  
  Protected MainValue.i, DezimalValue.i, Factor.i, *pString.Character

  
  *pString = @String$
  
  Factor = 1
  
  While *pString\c
    
    Debug *pString\c
    
    If *pString\c = '.'
      *pString + 2
      Break
    Else
      MainValue * 10 + (*pString\c - '0')
    EndIf
    
    *pString + 2
    
  Wend
  
  
  While *pString\c
    DezimalValue * 10 + (*pString\c - '0')
    Factor * 10
    
    *pString + 2
  Wend
  
  Debug "----"
  
  ProcedureReturn MainValue + (DezimalValue / Factor)
  
EndProcedure

Bernd

[wilbert]

@Bernd,
You used the integer format. This means on x86 you can't have numbers with more than 9 digits.
If you want to support both unicode and ascii, add the character size instead of 2.
*pString + SizeOf(Character)

I could try something asm based as well if someone would be interested.
If so, I need to know if ascii still needs to be supported and if it should use x87 or SSE for floats.

[infratec]

Hi, hi ,

I'm always up to date.
And in PB 5.50 you don't have to decide: a character is always 2 bytes long.

If he needs larger stuff he have to use .q

It always depends on the needs.

Btw. I tried also
<< 2
+
<< 1

Instead of * 10 but in PB it took longer.

Bernd

[wilbert]

It always depends on the needs.

I couldn't agree with you more

[infratec]

What Wilbert mean is:

you have to replace my definition line with:

Code: Select all

Protected MainValue.q, DezimalValue.q, Factor.q, *pString.Character

to get the correct(er) values.

Which slowes it down, of course.

Bernd

[Helle]

This is an old code from me, changed now for ASCII and unicode:

Code: Select all

;ONLY for test, not optimal! Don´t use the debugger! No check for string-correctness! For 64-bit-Windows! Make your own tests!
;ASCII and Unicode

Procedure StringToDouble(PointerToString.q, PointerToDouble.q)  ;= ATOF(); Parameters: PointerToString = RCX, PointerToDouble = RDX
  ;!mov rcx,[p.v_PointerToString]       ;for Debug
  ;!mov rdx,[p.v_PointerToDouble]

  !PUSH r12
  !PUSH r13
  !PUSH r14

  CompilerIf #PB_Compiler_Unicode
    !MOV r14,2 
   CompilerElse 
    !MOV r14,1 
  CompilerEndIf

  !XOR rax,rax
  !MOV r8,rax
  !MOV r9,rax
  !MOV r11,rax               ;signum_mantissa
  !MOV r12,rax               ;signum_exponent
  !MOV r13,rax               ;decimal_point
  !MOV al,[rcx]
  !CMP al,'-'
 !JE .Signum_Neg
  !CMP al,'+'
 !JE .Signum_Pos
 !JMP .Signum_End
!.Signum_Neg:
  !INC r11
!.Signum_Pos:
  !ADD rcx,r14
  !MOV al,byte[rcx]
!.Signum_End:
  !FLDZ
!.Read_Mantissa:
  !CMP eax,'E'
 !JE .Exponent
  !CMP eax,'e'
 !JE .Exponent
  !CMP eax,'.'
 !JE .Decimal_Point
  !XOR eax,'0'
  !CMP eax,9
 !JA .Digits_End
  !MOV [rdx],rax             ;temp
  !FMUL qword[Zehner]
  !FIADD word[rdx]
  !INC r8
 !JMP .No_Decimal_Point
!.Decimal_Point:
  !CMP r13,0                 ;decimal_point
 !JNE .Digits_End
  !MOV r13,r8                ;R13 = decimal_point
!.No_Decimal_Point:
  !ADD rcx,r14
  !MOVZX rax,byte[rcx]
 !JMP .Read_Mantissa
!.Exponent:
  !ADD rcx,r14
  !MOVZX rax,byte[rcx]
  !CMP al,'-'
 !JE .Signum_Exponent_Neg
  !CMP al,'+'
 !JE .Signum_Exponent_Pos
 !JMP .Read_Exponent
!.Signum_Exponent_Neg:
  !INC r12                   ;signum_exponent
!.Signum_Exponent_Pos:
  !ADD rcx,r14
  !MOVZX rax,byte[rcx]
!.Read_Exponent:
  !XOR rax,'0'
  !CMP rax,9
 !JA .Digits_End
  !LEA r9,[r9*4+r9]          ;R9 = Mul 5
  !LEA r9,[r9*2+rax]         ;R9 = Mul 10
  !ADD rcx,r14
  !MOVZX rax,byte[rcx]
 !JMP .Read_Exponent
!.Digits_End:
  !CMP r12,0                 ;signum_exponent
 !JE .Exponent_Ready
  !NEG r9
!.Exponent_Ready:
  !MOV rax,r13               ;R13 = decimal_point
  !OR rax,rax
 !JE .No_Decimal_Point2
  !SUB r8,rax
  !SUB r9,r8
!.No_Decimal_Point2:
  !Or r9,r9
 !JE .No_Exponent
  !MOV rax,r9
  !CMP rax,0
 !JGE .Signum_Exponent_OK
  !NEG rax
!.Signum_Exponent_OK:
  !FLD1
  !MOV r10b,al
  !AND r10,0Fh
 !JE .Big_Exponent
  !LEA r10,[r10+r10*4]
  !LEA r8,[Zehner_1]
  !FLD tword[r10*2+r8-10]
  !FMULP st1,st0
!.Big_Exponent:
  !MOV r10b,al
  !SHR r10b,4
  !AND r10,0Fh
 !JE .Bigger_Exponent
  !LEA r10,[r10+r10*4]
  !LEA r8,[Zehner_16]
  !FLD tword[r10*2+r8-10]
  !FMULP st1,st0
!.Bigger_Exponent:
  !SHR rax,8
  !AND rax,1Fh
 !JE .Signum_Exponent
  !LEA rax,[rax+rax*4]
  !LEA r8,[Zehner_256]
  !FLD tword[rax*2+r8-10]
  !FMULP st1,st0
!.Signum_Exponent:
  !CMP r9,0
  !JGE .Exponent_Pos
  !FDIVP st1,st0
 !JMP .No_Exponent
!.Exponent_Pos:
  !FMULP st1,st0
!.No_Exponent:
  !CMP r11,0                 ;signum_mantissa
 !JE .Ready
  !FCHS
!.Ready:
  !FSTP qword[rdx]           ;dword for Float

  !POP r14
  !POP r13
  !POP r12

 ProcedureReturn

  !Zehner     dq 10.0
  !Zehner_1   dt 1.0e1
  !           dt 1.0e2
  !           dt 1.0e3
  !           dt 1.0e4
  !           dt 1.0e5
  !           dt 1.0e6
  !           dt 1.0e7
  !           dt 1.0e8
  !           dt 1.0e9
  !           dt 1.0e10
  !           dt 1.0e11
  !           dt 1.0e12
  !           dt 1.0e13
  !           dt 1.0e14
  !           dt 1.0e15
  !Zehner_16  dt 1.0e16
  !           dt 1.0e32
  !           dt 1.0e48
  !           dt 1.0e64
  !           dt 1.0e80
  !           dt 1.0e96
  !           dt 1.0e112
  !           dt 1.0e128
  !           dt 1.0e144
  !           dt 1.0e160
  !           dt 1.0e176
  !           dt 1.0e192
  !           dt 1.0e208
  !           dt 1.0e224
  !           dt 1.0e240
  !Zehner_256 dt 1.0e256
  !           dt 1.0e512     ;.... for extended double, for this test not used

EndProcedure           

Double.d

StartTime = ElapsedMilliseconds()
For CTR = 1 To 1000000
  StringToDouble$ = "13215.33414554664"
  StringToDouble(@StringToDouble$, @Double)
Next
ElapsedTime = ElapsedMilliseconds() - StartTime
MessageRequester("Time!", "Elapsed Milliseconds : " + Str(ElapsedTime) + #LFCR$ + StrD(Double, 15))

Please make a test!

[Samuel]

Thank you everyone for the replies!

@infratec
Your procedure gives a nice speed boost. In my example above the loop completes in about 560 milliseconds instead of the original 1600 milliseconds. I am using quads and as you said it's a little slower then integers (350 milliseconds), but it's still a nice boost compared to what I had before.

I did need to add support for negative values. I believe what I added to your example should be good enough to handle the negative values unless someone can spot a problem with it.

Code: Select all

Procedure.d UnicodeValD(String$)
 
  Protected MainValue.q, DezimalValue.q, Factor.q, ValueSign.q, *pString.Character
  
  *pString = @String$
  
  ValueSign = 1
  Factor    = 1
  
  If *pString\c = '-'
    Debug "-"
    *pString + 2
    ValueSign = -1
  EndIf
  
  While *pString\c
   
    Debug *pString\c
   
    If *pString\c = '.'
      *pString + 2
      Break
    Else
      MainValue * 10 + (*pString\c - '0')
    EndIf
   
    *pString + 2
    
  Wend
 
 
  While *pString\c
    DezimalValue * 10 + (*pString\c - '0')
    Factor * 10
   
    *pString + 2
  Wend
 
  Debug "----"
 
  ProcedureReturn (MainValue + (DezimalValue / Factor)) * ValueSign
 
EndProcedure

@wilbert and @Helle
Asm is definitely fast, but I can barely understand any of it. I have a hard time using code when I can't follow it.
I do plan on learning asm, but at the moment my plate is pretty full. Anyways, thanks for the offer/example.

[wilbert]

Asm is definitely fast, but I can barely understand any of it. I have a hard time using code when I can't follow it.
I do plan on learning asm, but at the moment my plate is pretty full. Anyways, thanks for the offer/example.

There are still some things you can do to improve the speed without the use of asm.

For user defined procedures that take a string as an argument, PureBasic always makes a temporary copy of the string and passes the copy.
If you use a pointer as procedure argument and pass the address of the string instead, that will increase the performance.
Another thing is that division is very slow so instead of multiply Factor each time by 10 after the decimail dot has occurred, I would suggest to simply use a counter and use a small lookup table with values (0.1, 0.01, 0.001 etc.) to multiply with instead of divide.

[skywalk]

Infratec's ValDcustom() ~6x faster than ValD() but does not support scientific notation.