Suche Funktion um Charakter im Memory zu zählen

[Thorium]

Hm, tut mir leid aber offensichtlich habe ich mich geirrt, wobei das bei verschiedenen CPU's zu verschiedenen Zeiten kommen kann. Teste mal die neue Prozedur, die benötigt keinen Längenparameter und ein ein klein wenig schneller als die alte.

Code: Alles auswählen

Structure myFileInfo
name.s
laenge.i
StructureUnion
  inhalt.s
  zeiger.i
EndStructureUnion
EndStructure

Procedure.i DatenLesen(*dat.myFileInfo)

With *dat
   Protected dnr = ReadFile(#PB_Any, \name)
   If dnr
      \laenge = Lof(dnr)
      \inhalt = Space(\laenge)
      \laenge = ReadData(dnr, \zeiger, \laenge)
      CloseFile(dnr)
   Else
      MessageRequester(\name,"Konnte diese Datei nicht öffnen!")
      End
   EndIf
EndWith

EndProcedure

Procedure CountChar1(*Buffer.Character, BufferLength)
; von Thorium

  Protected.i i, Count
   
  For i = 1 To BufferLength   
    If *Buffer\c = 13
      Count + 1
    EndIf   
    *Buffer + SizeOf(Character)
  Next

  ProcedureReturn Count
EndProcedure

Procedure CountChar2(*pointer.Character)
; von Stargate

Protected anz

While *pointer\c
   If *pointer\c = 13 : anz + 1 : EndIf
   *pointer + SizeOf(Character)
Wend

ProcedureReturn anz
EndProcedure

Procedure CountChar3(pointer)
; von Bremer

Protected p = pointer - SizeOf(Character)
Protected anz

While p
   p = strchr_(p + SizeOf(Character), 13)
   If p: anz + 1: EndIf
Wend

ProcedureReturn anz
EndProcedure

Procedure.i CountCharAsm(*Buffer, BufferLength.i, Char.a)

  CompilerSelect #PB_Compiler_Processor

    CompilerCase #PB_Processor_x86
    
      !push edi
      !cld
      !xor edx,edx
      !mov ecx,[p.v_BufferLength+4]
      !mov edi,[p.p_Buffer+4]
      !mov al,[p.v_Char+4]
     
      !align 4
      !CountCharAsmLoop:
        !repne scasb
        !inc edx
        !test ecx,ecx
      !jne CountCharAsmLoop
     
      !mov bl,[edi]
      !cmp bl,al
      !je CountCharAsmEnd
        !dec edx 
      !CountCharAsmEnd:
     
      !mov eax, edx
      !pop edi

    CompilerCase #PB_Processor_x64
   
      !push rdi
      !cld
      !xor rdx,rdx
      !mov rcx,[p.v_BufferLength+8]
      !mov rdi,[p.p_Buffer+8]
      !mov al,[p.v_Char+8]
     
      !align 8
      !CountCharAsmLoop:
        !repne scasb
        !inc rdx
        !test rcx,rcx
      !jne CountCharAsmLoop
     
      !mov bl,[rdi]
      !cmp bl,al
      !je CountCharAsmEnd
        !dec rdx 
      !CountCharAsmEnd:
     
      !mov rax, rdx
      !pop rdi
      
  CompilerEndSelect

  ProcedureReturn

EndProcedure

Procedure.i CountCharAsm2(*Buffer, Char.a)

  CompilerSelect #PB_Compiler_Processor

    CompilerCase #PB_Processor_x86
    
      !push edi
      !push esi
      !xor edx,edx
      !xor ebx,ebx
      !xor esi,esi
      !mov edi,[p.p_Buffer+8]
      !mov al,[p.v_Char+8]
     
      !align 4
      !CountCharAsm2Loop:
      
        !mov bl,[edi]
        !cmp al,bl
        !sete dl
        !add esi,edx
        !inc edi
        
        !test bl,bl
      !jne CountCharAsm2Loop
     
      !mov eax,esi
      !pop esi
      !pop edi

    CompilerCase #PB_Processor_x64
   
      !push rdi
      !push rsi
      !xor rdx,rdx
      !xor rbx,rbx
      !xor rsi,rsi
      !mov rdi,[p.p_Buffer+16]
      !mov al,[p.v_Char+16]
     
      !align 8
      !CountCharAsm2Loop:
      
        !mov bl,[rdi]
        !cmp al,bl
        !sete dl
        !add rsi,rdx
        !inc rdi
        
        !test bl,bl
      !jne CountCharAsm2Loop
     
      !mov rax,rsi
      !pop rsi
      !pop rdi
      
  CompilerEndSelect

  ProcedureReturn

EndProcedure



datei.myFileInfo
datei\name = #PB_Compiler_Home + "Compilers\APIFunctionListing.txt"

DatenLesen(datei)

max = 500

a = GetTickCount_()
  For j = 1 To max: anz = CountChar1(datei\zeiger, datei\laenge): Next
thorium = GetTickCount_() - a
i$ = Str(anz) + " thorium  " + Str(thorium) + #LF$

a = GetTickCount_()
  For j = 1 To max: anz = CountChar2(datei\zeiger): Next
stargate = GetTickCount_() - a
i$ + Str(anz) + " stargate " + Str(stargate) + #LF$

a = GetTickCount_()
  For j = 1 To max: anz = CountChar3(datei\zeiger): Next
strchr = GetTickCount_() - a
i$ + Str(anz) + " strchr   " + Str(strchr) + #LF$

a = GetTickCount_()
  For j = 1 To max: anz = CountCharAsm(datei\zeiger, datei\laenge, 13): Next
SimpleAsm = GetTickCount_() - a
i$ + Str(anz) + " simples Assembler   " + Str(SimpleAsm) + #LF$

a = GetTickCount_()
  For j = 1 To max: anz = CountCharAsm2(datei\zeiger, 13): Next
SimpleAsm2 = GetTickCount_() - a
i$ + Str(anz) + " simples Assembler 2   " + Str(SimpleAsm2) + #LF$

MessageRequester("", i$)

[Thorium]

Ok, jetzt festhalten. ^^
Ich habs mit SSE4.2 genauergesagt SSE2 mit POPCNT Instruktion geschrieben und es ist 15x schneller als die einfache Assemblerprozedur! 1500%

Ich hab auch die Zeitmessung etwas verbessert nun ist auch ersichtlich, das meine erste Assemblerprozedur, welche die Bufferlänge benötigt, doch etwas schneller ist als die, welche die Pufferlänge selbst ermittelt.

Zu beachten sind 2 Dinge beim folgenden Code. Damit er überhaupt kompiliert werden kann muss FASM aktualisiert werden. Dazu die aktuelle Version von http://www.flatassembler.net runterladen und im Compilers Ordner des PureBasic Ordners ersetzen. Das ist deswegen nötig, weil die Version von FASM, die PureBasic mitliefert SSE4 nicht kennt und somit einen Assemblerfehler auswirft beim Kompilieren.

Zweitens ist darauf zu achten das eure CPU SSE4.2 unterstützt oder zumindest die POPCNT Instruktion. Das heisst der Code ist nur lauffähig mit einer recht aktuellen CPU. Tut mir leid aber mir hats einfach in den Fingern gejuckt zu schauen wie viel die POPCNT Instruktion bringt, ohne die wirds viel langsamer, vieleicht sogar langsamer als mit simplem Assembler.

Natürlich kann noch weiter ordentlich Geschwindigkeit erwirtschaftet werden. Hier ist noch nicht das Ende der Fahnenstange erreicht. Der nächste Schritt wäre den String zu zerteilen und von mehreren Cores paralel verarbeiten zu lassen, aber das kann gerne jemand anders schreiben.

Code: Alles auswählen

Structure myFileInfo
name.s
laenge.i
StructureUnion
  inhalt.s
  zeiger.i
EndStructureUnion
EndStructure

Procedure.i DatenLesen(*dat.myFileInfo)

With *dat
   Protected dnr = ReadFile(#PB_Any, \name)
   If dnr
      \laenge = Lof(dnr)
      \inhalt = Space(\laenge)
      \laenge = ReadData(dnr, \zeiger, \laenge)
      CloseFile(dnr)
   Else
      MessageRequester(\name,"Konnte diese Datei nicht öffnen!")
      End
   EndIf
EndWith

EndProcedure

Procedure CountChar1(*Buffer.Character, BufferLength)
; von Thorium

  Protected.i i, Count
   
  For i = 1 To BufferLength   
    If *Buffer\c = 13
      Count + 1
    EndIf   
    *Buffer + SizeOf(Character)
  Next

  ProcedureReturn Count
EndProcedure

Procedure CountChar2(*pointer.Character)
; von Stargate

Protected anz

While *pointer\c
   If *pointer\c = 13 : anz + 1 : EndIf
   *pointer + SizeOf(Character)
Wend

ProcedureReturn anz
EndProcedure

Procedure CountChar3(pointer)
; von Bremer

Protected p = pointer - SizeOf(Character)
Protected anz

While p
   p = strchr_(p + SizeOf(Character), 13)
   If p: anz + 1: EndIf
Wend

ProcedureReturn anz
EndProcedure

Procedure.i CountCharAsm(*Buffer, BufferLength.i, Char.a)

  CompilerSelect #PB_Compiler_Processor

    CompilerCase #PB_Processor_x86
    
      !push edi
      !cld
      !xor edx,edx
      !mov ecx,[p.v_BufferLength+4]
      !mov edi,[p.p_Buffer+4]
      !mov al,[p.v_Char+4]
     
      !align 4
      !CountCharAsmLoop:
        !repne scasb
        !inc edx
        !test ecx,ecx
      !jne CountCharAsmLoop
     
      !mov bl,[edi]
      !cmp bl,al
      !je CountCharAsmEnd
        !dec edx 
      !CountCharAsmEnd:
     
      !mov eax, edx
      !pop edi

    CompilerCase #PB_Processor_x64
   
      !push rdi
      !cld
      !xor rdx,rdx
      !mov rcx,[p.v_BufferLength+8]
      !mov rdi,[p.p_Buffer+8]
      !mov al,[p.v_Char+8]
     
      !align 8
      !CountCharAsmLoop:
        !repne scasb
        !inc rdx
        !test rcx,rcx
      !jne CountCharAsmLoop
     
      !mov bl,[rdi]
      !cmp bl,al
      !je CountCharAsmEnd
        !dec rdx 
      !CountCharAsmEnd:
     
      !mov rax, rdx
      !pop rdi
      
  CompilerEndSelect

  ProcedureReturn

EndProcedure

Procedure.i CountCharAsm2(*Buffer, Char.a)

  CompilerSelect #PB_Compiler_Processor

    CompilerCase #PB_Processor_x86
    
      !push edi
      !push esi
      !xor edx,edx
      !xor ebx,ebx
      !xor esi,esi
      !mov edi,[p.p_Buffer+8]
      !mov al,[p.v_Char+8]
     
      !align 4
      !CountCharAsm2Loop:
      
        !mov bl,[edi]
        !cmp al,bl
        !sete dl
        !add esi,edx
        !inc edi
        
        !test bl,bl
      !jne CountCharAsm2Loop
     
      !mov eax,esi
      !pop esi
      !pop edi

    CompilerCase #PB_Processor_x64
   
      !push rdi
      !push rsi
      !xor rdx,rdx
      !xor rbx,rbx
      !xor rsi,rsi
      !mov rdi,[p.p_Buffer+16]
      !mov al,[p.v_Char+16]
     
      !align 8
      !CountCharAsm2Loop:
      
        !mov bl,[rdi]
        !cmp al,bl
        !sete dl
        !add rsi,rdx
        !inc rdi
        
        !test bl,bl
      !jne CountCharAsm2Loop
     
      !mov rax,rsi
      !pop rsi
      !pop rdi
      
  CompilerEndSelect

  ProcedureReturn

EndProcedure

Procedure.i CountCharSSE42(*Buffer, BufferLength.i, Char.a)

  CompilerSelect #PB_Compiler_Processor

    CompilerCase #PB_Processor_x86
      
      !push ebx
      !push esi
      !push edi
      !push ebp

      !mov esi,[p.v_BufferLength+16]
      !mov edi,[p.p_Buffer+16]
      !mov al,[p.v_Char+16]
      !xor ebp,ebp
      
      ;process some bytes to get 16 byte alignment

      !mov ecx,edi
      !and ecx,15
      
      !test ecx,ecx
      !je CountCharSSE42_AlignEnd
      
      !sub esi,ecx
      
      !xor edx,edx
      
      !align 4
      !CountCharSSE42_AlignLoop:
      
        !mov bl,[edi]
        !cmp al,bl
        !sete dl
        !add ebp,edx
        !inc edi
        !dec ecx

      !jne CountCharSSE42_AlignLoop
      
      !CountCharSSE42_AlignEnd:
      
      ;cut length to a multiply of 16 and process it

      !mov cl,al
      !shl eax,8
      !mov al,cl
      !shl eax,8
      !mov al,cl
      !shl eax,8
      !mov al,cl
      !push eax
      !push eax
      !push eax
      !push eax
      !movdqu xmm0,[esp]
      !add esp,16

      !mov ecx,esi
      !shr ecx,4
      
      !test ecx,ecx
      !je CountCharSSE42_MainEnd
      
      !and esi,15

      !align 4
      !CountCharSSE42_Loop:
      
        !movdqa xmm1,[edi]
        !pcmpeqb xmm1,xmm0
        !pmovmskb eax,xmm1
        
        !popcnt eax,eax
        !add ebp,eax
        
        !add edi,16
        !dec ecx
        
      !jne CountCharSSE42_Loop
      
      !CountCharSSE42_MainEnd:
      
      ;process the rest of the string

      !test esi,esi
      !je CountCharSSE42_RestEnd

      !mov al,[p.v_Char+16]
      !mov ecx,esi
      !xor edx,edx
      
      !align 4
      !CountCharSSE42_RestLoop:
      
        !mov bl,[edi]
        !cmp al,bl
        !sete dl
        !add ebp,edx
        !inc edi
        !dec ecx

      !jne CountCharSSE42_RestLoop
      
      !CountCharSSE42_RestEnd:

      !mov eax,ebp
 
      !pop ebp
      !pop edi
      !pop esi
      !pop ebx

    CompilerCase #PB_Processor_x64

      !push rbx
      !push rsi
      !push rdi
      !push rbp

      !mov rsi,[p.v_BufferLength+32]
      !mov rdi,[p.p_Buffer+32]
      !mov al,[p.v_Char+32]
      !xor rbp,rbp
      
      ;process some bytes to get 16 byte alignment

      !mov rcx,rdi
      !and rcx,15
      
      !test rcx,rcx
      !je CountCharSSE42_AlignEnd
      
      !sub rsi,rcx
      
      !xor rdx,rdx
      
      !align 8
      !CountCharSSE42_AlignLoop:
      
        !mov bl,[rdi]
        !cmp al,bl
        !sete dl
        !add rbp,rdx
        !inc rdi
        !dec rcx

      !jne CountCharSSE42_AlignLoop
      
      !CountCharSSE42_AlignEnd:
      
      ;cut length to a multiply of 16 and process it

      !mov cl,al
      !shl rax,8
      !mov al,cl
      !shl rax,8
      !mov al,cl
      !shl rax,8
      !mov al,cl
      !shl rax,8
      !mov al,cl
      !shl rax,8
      !mov al,cl
      !shl rax,8
      !mov al,cl
      !shl rax,8
      !mov al,cl
      !push rax
      !push rax
      !movdqu xmm0,[rsp]
      !add rsp,16

      !mov rcx,rsi
      !shr rcx,4
      
      !test rcx,rcx
      !je CountCharSSE42_MainEnd
      
      !and rsi,15
      !xor rax,rax

      !align 8
      !CountCharSSE42_Loop:
      
        !movdqa xmm1,[rdi]
        !pcmpeqb xmm1,xmm0
        !pmovmskb eax,xmm1
        
        !popcnt eax,eax
        !add rbp,rax
        
        !add rdi,16
        !dec rcx
        
      !jne CountCharSSE42_Loop
      
      !CountCharSSE42_MainEnd:
      
      ;process the rest of the string

      !test rsi,rsi
      !je CountCharSSE42_RestEnd

      !mov al,[p.v_Char+32]
      !mov rcx,rsi
      !xor rdx,rdx
      
      !align 8
      !CountCharSSE42_RestLoop:
      
        !mov bl,[rdi]
        !cmp al,bl
        !sete dl
        !add rbp,rdx
        !inc rdi
        !dec rcx

      !jne CountCharSSE42_RestLoop
      
      !CountCharSSE42_RestEnd:

      !mov rax,rbp
 
      !pop rbp
      !pop rdi
      !pop rsi
      !pop rbx

  CompilerEndSelect

  ProcedureReturn

EndProcedure

datei.myFileInfo
datei\name = #PB_Compiler_Home + "Compilers\APIFunctionListing.txt"

DatenLesen(datei)

max = 5000

timeBeginPeriod_(1)

a = timeGetTime_()
  For j = 1 To max: anz = CountChar1(datei\zeiger, datei\laenge): Next
thorium = timeGetTime_() - a
i$ = Str(anz) + " thorium  " + Str(thorium) + #LF$

a = timeGetTime_()
  For j = 1 To max: anz = CountChar2(datei\zeiger): Next
stargate = timeGetTime_() - a
i$ + Str(anz) + " stargate " + Str(stargate) + #LF$

a = timeGetTime_()
  For j = 1 To max: anz = CountChar3(datei\zeiger): Next
strchr = timeGetTime_() - a
i$ + Str(anz) + " strchr   " + Str(strchr) + #LF$

a = timeGetTime_()
  For j = 1 To max: anz = CountCharAsm(datei\zeiger, datei\laenge, 13): Next
SimpleAsm = timeGetTime_() - a
i$ + Str(anz) + " simples Assembler   " + Str(SimpleAsm) + #LF$

a = timeGetTime_()
  For j = 1 To max: anz = CountCharAsm2(datei\zeiger, 13): Next
SimpleAsm2 = timeGetTime_() - a
i$ + Str(anz) + " simples Assembler 2   " + Str(SimpleAsm2) + #LF$

a = timeGetTime_()
  For j = 1 To max: anz = CountCharSSE42(datei\zeiger, datei\laenge, 13): Next
SSE42 = timeGetTime_() - a
i$ + Str(anz) + " SSE4.2   " + Str(SSE42) + #LF$

timeEndPeriod_(1)

MessageRequester("", i$)

[7x7]

und dann mit CountString den Chr 13 zählen. Aber wat fürn Unsinn.

Und was genau ist da der Unsinn? Für mich ist eine alternative 400(!)-Zeilen-Lösung der grössere Unsinn!

[Thorium]

und dann mit CountString den Chr 13 zählen. Aber wat fürn Unsinn.

Und was genau ist da der Unsinn? Für mich ist eine alternative 400(!)-Zeilen-Lösung der grössere Unsinn!

59 Zeilen ist die Assembler-Prozedur.
234 Zeilen die SSE4.2 Prozedur.

Was genau ist daran für dich unsinn? Wenn du mehrere 100MB oder gar GB durchackern musst, bist du froh über ne schnelle Prozedur.

[Thorium]

Trond hat im englischen Forum noch eine Variante mit traditionellem Assembler gepostet, er meint sie wäre 6 mal so schnell auf seinem Rechner, wie meine simple Assembler Variante. Auf meinem Rechner ist sie allerdings nur 5% schneller. Also SSE4.2 ist auf meinem Rechner auch im Vergleich zu seiner 15 mal schneller. Aber nützlich falls SSE4.2 nicht verfügbar ist.

Code: Alles auswählen

Procedure CountChars(*B.Ascii, L, Char.a)
  !mov  ecx, [p.v_L]
  !mov  dl, [p.v_Char]
  !mov  eax, [p.p_B]
 
  !push edi
  !push ebp
  !mov  ebp, eax
 
  !xor  edi, edi
  !lp:
    !xor eax, eax
    !cmp byte [ecx+ebp-1], dl
    !sete al
    !add edi, eax
    !add ecx, -1
    !jnz lp
  !mov eax, edi
 
  !pop ebp
  !pop edi
  ProcedureReturn
EndProcedure

[7x7]

Code: Alles auswählen

CreateFile(1,"5MBTest.txt")
For a=1 To 500000
	WriteStringN(1,"10_Zeichen")  
Next a
CloseFile(1)


OpenFile(1,"5MBTest.txt")
txt$=Space(Lof(1)+4)
ReadData(1,@txt$, Lof(1))
CloseFile(1)


TimeStart= ElapsedMilliseconds()
For a=1 To 100
	Count=CountString(txt$,Chr(13))
Next a
TimeEnd  = (ElapsedMilliseconds()-TimeStart)/100

Debug Str(count)+" Chr(13) gefunden in "+Str(TimeEnd)+"ms"

8ms für die Analyse sind nicht schnell genug ? Wenn man schon 15ms für das Einlesen der Textdatei benötigt ?

Da macht es natürlich Sinn, dass man noch etwas an der Performance dreht...

[a14xerus]

was genau soll mir dein code sagen, 7x7????
bei mir dauert die analyse um einiges länger als das einlesen

einlesen 0.2 sekunden, analyse: 12sekunden

(habe deinen code genommen, nochmal eine 0 mehr dangehängt und auch ne zeitabfrage fürs laden eingebaut, die fehlt bei dir nämlich -.-)

[7x7]

bei mir dauert die analyse um einiges länger als das einlesen

Mindestvoraussetzung für diesen Test ist ein 80486

[a14xerus]

bei mir dauert die analyse um einiges länger als das einlesen

Mindestvoraussetzung für diesen Test ist ein 80486

what??

[hjbremer]

Was genau ist daran für dich unsinn? Wenn du mehrere 100MB oder gar GB durchackern musst, bist du froh über ne schnelle Prozedur.

Ganz deiner Meinung !!! Wer große Datenbestände interpretieren muß, freut sich über jede Millisekunde. Da zählt jeder CPU-Takt. Besonders auf älteren Rechnern, so wie meiner.

Und da wären wir beim Thema, CountCharAsm2 ist bei mir ein drittel langsamer als die 1. ASM Routine. Also 265 zu 375.
Und auch Trond seine ist bei mir 282 zu 265 etwas langsamer. Aber das liegt wohl daran, das bei beiden repne scasb nicht benutzt wird und gerade dieser Befehl auf meinem Uralt AMD 2200+ 1500 MHz richtig was bringt. Leider kann ich deine SSE Variante darum wohl nicht testen.

Ich denke manch Anwender kann sich nun aus den hier gebotenen Codes das richtige für sich heraussuchen

Trotzdem nochmal vielen Dank für deine Mühe !!!