Faster ways to convert strings to doubles?

[Samuel]

@wilbert
Thanks for the tip on the pointer. That alone shaved off another 100 milliseconds.

As for removing the division it doesn't seem to give a very noticeable speed boost. For a quick test I swapped out "/ Factor" to "* 0.00000000001" which is the value to use when Factor = 100000000000, but that only shaved of 10 milliseconds. If I add a counter and then look up the corresponding value I'd imagine I'd lose a couple of those milliseconds.
It may be minor, but a speed boost is a speed boost.

Procedure with the new string pointer and a commented out multiplication test.

Code: Select all

Procedure.d MATH_UnicodeValD(*StringToConvert.String)
 
  Protected MainValue.q, DezimalValue.q, Factor.q, ValueSign.q, *pString.Character
  
  *pString = *StringToConvert
  
  ValueSign = 1
  Factor    = 1
  
  If *pString\c = '-'
    *pString + 2
    ValueSign = -1
  EndIf
  
  While *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
  
  ;## For comparing division to multiplication.
  ;## When String = "-13215.33414554664" then Factor = 100000000000.
  ;ProcedureReturn (MainValue + (DezimalValue * 0.00000000001)) * ValueSign
  
  ProcedureReturn (MainValue + (DezimalValue / Factor)) * ValueSign
 
EndProcedure

[wilbert]

I couldn't resist trying an asm version

x86 and x64 using FPU

Code: Select all

Macro M_GetNextChar()
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
    CompilerIf #PB_Compiler_Unicode
      !movzx eax, word [rdx]  ; x64 Unicode
      !add rdx, 2
    CompilerElse
      !movzx eax, byte [rdx]  ; x64 Ascii
      !add rdx, 1
    CompilerEndIf
  CompilerElse
    CompilerIf #PB_Compiler_Unicode
      !movzx eax, word [edx]  ; x86 Unicode
      !add edx, 2
    CompilerElse
      !movzx eax, byte [edx]  ; x86 Ascii
      !add edx, 1
    CompilerEndIf
  CompilerEndIf
EndMacro

Macro M_AddInt32ToDouble()
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x64  
    !mov [rsp - 4], ebx
    !fiadd dword [rsp - 4]
  CompilerElse
    !mov [esp - 4], ebx
    !fiadd dword [esp - 4]
  CompilerEndIf
EndMacro

Macro M_MulFromTable(Offset)
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x64  
    !fmul qword [rdi + rax * 8 + Offset]
  CompilerElse
    !fmul qword [edi + eax * 8 + Offset]
  CompilerEndIf
EndMacro

Procedure.d ValueD(*ValueString)
  ; >> Initialize <<
  Protected Result.d
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
    !mov rdx, [p.p_ValueString]
    !push rbx
    !push rsi
    !push rdi
    !lea rdi, [.vald_lut]
  CompilerElse
    !mov edx, [p.p_ValueString]
    !push ebx
    !push esi
    !push edi
    !lea edi, [.vald_lut]
  CompilerEndIf
  !fld qword [.vald_lut + 64]   ; 100000000
  !fldz                         ; 0
  !mov esi, 0x00000001          ; counter add value
  !xor ebx, ebx                 ; integer value
  !xor ecx, ecx                 ; 2 x 16 bit counter
  ; >> Prescan <<
  !.l0:
  M_GetNextChar()
  !cmp eax, ' '                 ; skip leading spaces
  !je .l0
  !cmp eax, '+'                 ; '+' ==> .l1
  !je .l1
  !cmp eax, '-'                 ; not '-' ==> .l2 
  !jne .l2
  !or ecx, 0x00001000           ; set flag for negative value
  ; >> Main <<
  !.l1:
  M_GetNextChar()               ; get next character
  !.l2:
  !sub eax, '0'                 ; < '0'  ==> .l3
  !jc .l3
  !cmp eax, 9                   ; > '9'  ==> .l4              
  !ja .l4
  !imul ebx, 10                 ; ebx * 10
  !add ebx, eax                 ; ebx + digit
  !add ecx, esi                 ; update step counter
  !test ecx, 0x7                ; is step a multiple of 8 
  !jnz .l1                      ; no ==> .l1
  !fmul st0, st1                ; double * 100000000
  M_AddInt32ToDouble()          ; double + ebx
  !xor ebx, ebx                 ; clear ebx
  !jmp .l1                      ; ==> .l1
  !.l3:
  !test esi, 0x00010000         ; did a '.' already occur
  !jnz .l4                      ; yes ==> .l4
  !or esi, 0x00010000           ; update counter add value
  !cmp eax, '.' -48             ; '.' ==> .l1
  !je .l1
  ; >> Finalize <<
  !.l4:
  !mov eax, ecx                 ; add remaining value to ebx
  !and eax, 7
  M_MulFromTable(0)
  M_AddInt32ToDouble()
  !test ecx, 0x00001000         ; test negative value flag
  !jz .l5
  !fchs                         ; change sign when negative 
  !.l5:
  !shr ecx, 16                  ; shift so ecx is counter after '.'
  !jz .l7                       ; nothing behind a '.' ==> .l7
  !mov eax, ecx
  !and eax, 15
  M_MulFromTable(72)            ; correct for dot position
  !shr ecx, 4
  !jz .l7
  !.l6:
  !fmul qword [.vald_lut + 200] ; further correction if required
  !dec ecx
  !jnz .l6
  ; >> Done <<
  !.l7:
  !fstp st1
  ; >> Cleanup <<
  CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
    !pop rdi
    !pop rsi
    !pop rbx
  CompilerElse
    !pop edi
    !pop esi
    !pop ebx
  CompilerEndIf
  !fstp qword [p.v_Result]
  ProcedureReturn Result
  ; >> Lookup table <<
  !.vald_lut:
  !dq 1.0e0,  1.0e1,  1.0e2,  1.0e3,  1.0e4,  1.0e5,  1.0e6,  1.0e7,  1.0e8
  !dq 1.0e0, 1.0e-1, 1.0e-2, 1.0e-3, 1.0e-4, 1.0e-5, 1.0e-6, 1.0e-7, 1.0e-8
  !dq 1.0e-9, 1.0e-10, 1.0e-11, 1.0e-12, 1.0e-13, 1.0e-14, 1.0e-15, 1.0e-16
EndProcedure

There's only a minor difference in accuracy with ValD.

Code: Select all

S.s = "-0.00000000000000000000005"
Debug ValD(S)
Debug ValueD(@S)
;Debug MATH_UnicodeValD(@S)

S.s = "12345678901234567890.12345678901234567890"
Debug ValD(S)
Debug ValueD(@S)
;Debug MATH_UnicodeValD(@S)

On x64, SSE seems to be a bit faster

Code: Select all

; 64 bit version using SSE instead of FPU

Macro M_GetNextChar()
  CompilerIf #PB_Compiler_Unicode
    !movzx eax, word [r9]  ; Unicode
    !add r9, 2
  CompilerElse
    !movzx eax, byte [r9]  ; Ascii
    !add r9, 1
  CompilerEndIf
EndMacro

Procedure.d ValueD(*ValueString)
  ; >> Initialize <<
  Protected Result.d
  !lea r8, [.vald_lut]
  !mov r9, [p.p_ValueString]
  !movsd xmm1, [r8 + 64]        ; 100000000
  !xorpd xmm0, xmm0
  !xorpd xmm3, xmm3             ; sign
  !mov r10d, 1                  ; counter add value
  !xor edx, edx                 ; integer value
  !xor ecx, ecx                 ; 2 x 16 bit counter
  ; >> Prescan <<
  !.l0:
  M_GetNextChar()
  !cmp eax, ' '                 ; skip leading spaces
  !je .l0
  !cmp eax, '+'                 ; '+' ==> .l1
  !je .l1
  !cmp eax, '-'                 ; not '-' ==> .l2 
  !jne .l2
  !movsd xmm3, [.vald_sgn]
  ; >> Main <<
  !.l1:
  M_GetNextChar()               ; get next character
  !.l2:
  !sub eax, '0'                 ; < '0'  ==> .l3
  !jc .l3
  !cmp eax, 9                   ; > '9'  ==> .l4              
  !ja .l4
  !imul edx, 10                 ; edx * 10
  !add edx, eax                 ; edx + digit
  !add ecx, r10d                ; update step counter
  !test ecx, 0x7                ; is step a multiple of 8 
  !jnz .l1                      ; no ==> .l1
  !cvtsi2sd xmm2, edx
  !mulsd xmm0, xmm1             ; double * 100000000
  !addsd xmm0, xmm2
  !xor edx, edx                 ; clear edx
  !jmp .l1                      ; ==> .l1
  !.l3:
  !test r10d, 0x00010000        ; did a '.' already occur
  !jnz .l4                      ; yes ==> .l4
  !or r10d, 0x00010000          ; update counter add value
  !cmp eax, '.' -48             ; '.' ==> .l1
  !je .l1
  ; >> Finalize <<
  !.l4:
  !cvtsi2sd xmm2, edx
  !mov eax, ecx                 ; add remaining value to edx
  !and eax, 7
  !mulsd xmm0, [r8 + rax*8]
  !addsd xmm0, xmm2
  !orpd xmm0, xmm3              ; set sign
  !shr ecx, 16                  ; shift so ecx is counter after '.'
  !jz .l7                       ; nothing behind a '.' ==> .l7
  !mov eax, ecx
  !and eax, 15
  !mulsd xmm0, [r8 + rax*8 + 72]; correct for dot position
  !shr ecx, 4
  !jz .l7
  !.l6:
  !mulsd xmm0, [r8 + 200]       ; further correction if required
  !dec ecx
  !jnz .l6
  ; >> Done <<
  !.l7:
  !movsd [p.v_Result], xmm0
  ProcedureReturn Result
  ; >> Lookup table <<
  !.vald_sgn: dq 0x8000000000000000
  !.vald_lut:
  !dq 1.0e0,  1.0e1,  1.0e2,  1.0e3,  1.0e4,  1.0e5,  1.0e6,  1.0e7,  1.0e8
  !dq 1.0e0, 1.0e-1, 1.0e-2, 1.0e-3, 1.0e-4, 1.0e-5, 1.0e-6, 1.0e-7, 1.0e-8
  !dq 1.0e-9, 1.0e-10, 1.0e-11, 1.0e-12, 1.0e-13, 1.0e-14, 1.0e-15, 1.0e-16
EndProcedure

[infratec]

As always ...

unfair



I squeeze my brain to find a fast way with PB commands and then wilbert presents his assembler solution.

Next time I also use directly assembler, be warned.

Bernd

Well done

PB 5.50 x86:
ValD 2655
My version 417
Wilbert 175

[wilbert]

I squeeze my brain to find a fast way with PB commands

That's often the best to start with.
It's just that I like to play a bit with assembler but in reality your PB code is fast enough and easier to read.
Even ValD has enough performance for most tasks.

[skywalk]

Using C lib directly supports scientific notation and is ~75% faster than ValD.

Code: Select all

; Count(n),             1000000
; ValD(ms),             2474
; ValDca(ms),           712
; ValDcu(ms),           572
; ValDca : ValD(%),     -71.22
; ValDcu : ValD(%),     -76.88
EnableExplicit
ImportC "";"msvcrt.lib"
  atof.d(*txt) As "_atof"
  wcstod.d(*txt, *endoftxt=#Null) As "_wcstod"
EndImport
Macro ValDca(txt)
  atof(Ascii(txt))
EndMacro
Macro ValDcu(txt)
  wcstod(@txt, #Null)
EndMacro
;-{ TEST SPEED
; There is a small bias where 1st procedure is always slower.
; Options: 
;   Ignore/Sacrifice results of Code1$ but repeat at end.
;   Or comment out each procedure to run only 1 at a time.
CompilerIf #PB_Compiler_Debugger = 0
  Macro ML_pcDif(y, Ynorm)
    ; Compute % difference of 2 numbers.
    (y - (Ynorm)) / (Ynorm + 1e-16) * 100
  EndMacro
  SetPriorityClass_(GetCurrentProcess_(), #REALTIME_PRIORITY_CLASS)
  #Tries = 1e6
  Define.q u,time,t1,t2,t3,tw = 24
  Define.s r$
  Define.s code1$ = "ValD"
  Define.s code2$ = "ValDca"
  Define.s code3$ = "ValDcu"
  
  Define.i COMMMONVARIABLES_HERE
  Define.d D
  Define.s S$ = "13215.33414554664e+3"
  U=0
  time = ElapsedMilliseconds()
  ;-> INSERT CODE 1 HERE...
  While U < #Tries
    D = ValD(S$)
    Debug StrD(D,6)
    U + 1
  Wend
  t1 = ElapsedMilliseconds()-time
  U=0
  time = ElapsedMilliseconds()
  ;-> INSERT CODE 2 HERE...
  While U < #Tries
    D = ValDca(S$)
    Debug StrD(D,6)
    U + 1
  Wend
  t2 = ElapsedMilliseconds()-time
  U=0
  time = ElapsedMilliseconds()
  ;-> INSERT CODE 3 HERE...
  While U < #Tries
    D = ValDcu(S$)
    Debug StrD(D,6)
    U + 1
  Wend
  t3 = ElapsedMilliseconds()-time
  
  r$ = LSet("; Count(n),",tw) + Str(#Tries) + #CRLF$
  r$ + LSet("; "+code1$+"(ms),",tw) + Str(t1) + #CRLF$
  r$ + LSet("; "+code2$+"(ms),",tw) + Str(t2) + #CRLF$
  r$ + LSet("; "+code3$+"(ms),",tw) + Str(t3) + #CRLF$
  r$ + LSet("; "+code2$+" : "+code1$+"(%),",tw) + StrD(ML_pcDif(t2,t1),2) + #CRLF$
  r$ + LSet("; "+code3$+" : "+code1$+"(%),",tw) + StrD(ML_pcDif(t3,t1),2) + #CRLF$
  If MessageRequester("Speed Test - Copy To Clipboard?",r$,#PB_MessageRequester_YesNo) = #PB_MessageRequester_Yes
    SetClipboardText(r$)
  EndIf
  SetPriorityClass_(GetCurrentProcess_(), #NORMAL_PRIORITY_CLASS)
CompilerEndIf
;-}