StringBuilder [Include]

[cxAlex]

Servus.

Es kommt häufig zu der Situation das man einem String immer wieder vergrößert, meist in einer Schleife, zum Erzeugen von Datei-Inhalten, Logs, sonstiges (zeilenweises) Erstellen einer Text - Datei, .... .

Also ca. diese Form von Code:

Code: Alles auswählen

Define Log$ = ""
For i = 1 To LogEinträge
  ; Einträge laden...
  Log$ + LogZeile$
Next
; .....

Nur ist das extrem langsam, die interne Stringverwaltung von PB legt den LogString jedesmal neu an. Bei einigen 1000 LogZeilen kann das schonmal ein paar Sekunden dauern. Darum habe ich einen kleinen StringBuilder programmiert der auf den wohl wenig bekannten CopyMemoryString() Befehl basiert. Verpackt ist das Ganze in ein einfaches Interface, es sollte wirklich selbsterklärend sein.

Ein kleiner Demo-Code ist am Ende des Codes der die "normale" PB - Variante und den String-Builder gegenüberstellen. Bei mir benötigt PB ~35.000 ms, Der StringBuilder 0 ms!

StringBuilder.pbi :

Code: Alles auswählen

; ------------------------------------------------------------------------------------
; StringBuilder
; PB 4.5+ OS: Windows/Linux/MacOS Architecture: x86/x64
; Author: Alexander Aigner, cxAlex @ purebasic.fr/german
; ------------------------------------------------------------------------------------

; EnableExplicit

Structure _StringBuilder_Data
  *VTable
  *StringBuffer
  *StringBufferPointer
  *StringBufferPointerPointer
  StringSize.i
  BlockSize.i
  BlockCount.i
EndStructure

Interface StringBuilder ; StringBuilder Interface
  Add(*String) ; String hinzufügen (Pointer auf String)
  GetString.s() ; Totalen String laden
  Free() ; StringBuilder freigeben
EndInterface

; Neuer StringBuilder.
; BlockSize: mit welcher Blockgröße soll der Speicher erweitert werden?
Procedure StringBuilder_New(BlockSize = 1024*1024)
  Protected *SB._StringBuilder_Data = AllocateMemory(SizeOf(_StringBuilder_Data))
  With *SB
    \VTable = ?_StringBuilder_VTable
    \StringSize = #Null
    ; Speicher anlegen
    \BlockSize = BlockSize
    \BlockCount = #Null
    \StringBuffer = #Null
    \StringBufferPointer = #Null
    \StringBufferPointerPointer = @\StringBufferPointer ; Zeiger auf StringBufferPointer
  EndWith
  
  ProcedureReturn *SB
EndProcedure

Procedure _StringBuilder_Add(*SB._StringBuilder_Data, *String)
  Protected StringSize = MemoryStringLength(*String)

  With *SB
    ; Muss resizen
    While (\BlockCount*\BlockSize) < (\StringSize+StringSize+SizeOf(Character))
      \BlockCount + 1
      \StringBuffer = ReAllocateMemory(\StringBuffer, \BlockCount*\BlockSize)
      \StringBufferPointer = \StringBuffer + \StringSize
    Wend
    
    ; Kopieren
    ; CopyMemoryString Erhöht den \StringBufferPointer auf den \StringBufferPointerPointer zeigt selbst um StringSize,
    ; Deshabl müssen wir das nicht selbst machen.
    CopyMemoryString(*String, \StringBufferPointerPointer)
    
    ; Stringgröße erhöhen
    \StringSize+StringSize
  EndWith
EndProcedure

Procedure.s _StringBuilder_GetString(*SB._StringBuilder_Data)
  With *SB 
    If \StringBuffer
      ; Zurückgeben
      ProcedureReturn PeekS(\StringBuffer, \StringSize)
    EndIf
  EndWith
EndProcedure

Procedure _StringBuilder_Free(*SB._StringBuilder_Data)
  With *SB
    ; Freigeben
    If \StringBuffer
      FreeMemory(\StringBuffer)
    EndIf
    FreeMemory(*SB)
  EndWith
EndProcedure

DataSection
  _StringBuilder_VTable:
  Data.i @_StringBuilder_Add()
  Data.i @_StringBuilder_GetString()
  Data.i @_StringBuilder_Free()
EndDataSection








; TEST

#NB = 20000

Define ResultString$, ResultString2$

Define String$ = "####################################### Hallo!! #######################################" + #LFCR$
Define i, t1, t2

; Normal zusammenfügen:
t1 = ElapsedMilliseconds()
For i = 1 To #NB
  ResultString$ + String$
Next
t1 = ElapsedMilliseconds() - t1


; StringBuilder:
t2 = ElapsedMilliseconds()
Define mSB.StringBuilder = StringBuilder_New()
For i = 1 To #NB
  mSB\Add(@String$)
Next
ResultString2$ = mSB\GetString()
mSB\Free()
t2 = ElapsedMilliseconds() - t2

; Checksummen berechnen zum Vergleich:
Define CRC1 = CRC32Fingerprint(@ResultString$, StringByteLength(ResultString$))
Define CRC2 = CRC32Fingerprint(@ResultString2$, StringByteLength(ResultString2$))

MessageRequester("","PB Stringzusammenfügen:" + Chr(9) +Str(t1) + " ms, CRC:" + Chr(9)+ Str(CRC1) + Chr(13) + "Stringbuilder:" + Chr(9) + Chr(9) + Str(t2) + " ms, CRC:" + Chr(9) + Str(CRC2))

Gruß, Alex

[NicTheQuick]

Sieht gut aus. Hier auch das Ergebnis auf meinem System:

PB: 11151 ms
Stringbuilder: 10 ms

[STARGÅTE]

Irgendwas stimmt mit dem Code nicht:
Wenn ich den Buffer bei StringBuilder_New() auf 1000 setzen (als Beispiel)
bekomme ich folgende Meldung bei mSB\Free():

Ungültiger Speicherzugriff. (Lesefehler an der Adresse 0)

Code: Alles auswählen

If *SB\StringBuffer
  FreeMemory(*SB\StringBuffer) ; << Hier
EndIf

Daraus schlussfolgere ich, das FreeMemory eine MemoryAdresse bekommt, die nicht gültig ist, bzw. ein header zerstört wurde!

Das heißt an eigend einer Stelle gibt es n Speicherverletzung.

Schalte ich den Purifier an, bekomme ich folgende Meldung:
Overflow in a dynamically allocated memory block!

Code: Alles auswählen

    Else
      CopyMemoryString(*String) ; << Hier
    EndIf

Ich vermute es liegt daran, dass CopyMemoryString() ebenfalls die NULL am ende mit kopiert und deine Länge mit MemoryStringLength somit 1 Character zu wenig hat.
Dadurch wurde ein Byte eines falschen Speichers überschreiben!

Bitte korrigiere das!
ansonsten ist auf jedenfall schneller.

EDIT: Bitte nicht oben das +SizeOf(Character) hinzufügen, da du ja unten \StringSize+StringSize die echte Länge haben willst.
Also entweder unten wieder abziehen, oder es nur in den IF-Abfragen berücksichtigen.

[cxAlex]

Danke Stargâte, das hätte ich jetzt glatt übersehen! Mit 1000 hatte ich den Fehler auch. Ich habs jetzt in der IF-Abfrage mit drinnen, einfach ein +SizeOf(Character), jetzt läuft es rund.

Die Doku zum CopyMemoryString() Befehl ist leider nicht sehr ausführlich, da stand nichts davon drinnen ob es das/die Termination-Byte(s) mitkopiert. Auch über die Threadsicherheit kann ich leider noch nichts sagen, ich verlasse mich da gerade mal drauf das der Befehl den Speicher-Pointer für jeden Thread lokal im TSL speichert wenn Threadsafe aktiviert ist. Ansonsten kann man immer nur einen StringBuilder auf einmal verwenden, sollte der Pointer global gespeichert werden.

Gruß, Alex

[cxAlex]

Kleines Update.

Habe die Add-Procedure aufgeräumt und sie nebenbei auch Threadsicher gemacht

Gruß, Alex

[Kiffi]

Leider wird die ganze Performance gefressen, wenn man durch eine äussere
Schleife gezwungen ist, den StringBuilder ständig freizugeben und neu zu
initialisieren:

Code: Alles auswählen

For Counter = 0 To GanzGanzViel
  MeinStringBuilder = StringBuilder_New() 
  For Counter2 = 0 To NochVielMehr
    MeinStringBuilder\Add(@IrgendEinenWert)
  Next
  TuWasMitDemStringBuilder(MeinStringBuilder)
  MeinStringBuilder\Free()
Next

@cxAlex: Kann man da was drehen?

Danke & Grüße ... Kiffi

[Kukulkan]

Hi,

since I program (starting c64) i use a simple trick on this. It produces good results and does not need any special techniques:

Code: Alles auswählen

Add.s = "01234567890123456789012345678901234567890123456789" ; 50 chars
Rounds.i = 20000

OpenConsole()

; TEST 1 (ordinary)
Test.s = ""
cStart.i = ElapsedMilliseconds()
For x.i = 1 To Rounds.i
  Test.s = Test.s + Add.s
Next
cEnd.i = ElapsedMilliseconds()

PrintN("1. Needed " + Str(cEnd.i - cStart.i) + "ms")


; TEST 2 (enhanced)
Test.s = ""
Dummy.s = ""
DummyLength.i = Len(Add.s) * 100
cStart.i = ElapsedMilliseconds()
For x.i = 1 To Rounds.i
  Dummy.s = Dummy.s + Add.s
  If Len(Dummy.s) >= DummyLength.i
    Test.s = Test.s + Dummy.s
    Dummy.s = ""
  EndIf
Next
Test.s = Test.s + Dummy.s; add the rest
cEnd.i = ElapsedMilliseconds()

PrintN("2. Needed " + Str(cEnd.i - cStart.i) + "ms")

PrintN("press enter")

Input()

CloseConsole()

1. Needed 29703ms
2. Needed 547ms
press enter

A simple technique and needs only 1.84% of the first run. It is not as fast as the StringBuilder, but it may be good enough in many cases.

[edit]Tschuldigung für's Englisch. War aus Gewohnheit...[/edit]

Kukulkan

[PMV]

CopyMemoryString() hab ich tatsächlich vergessen. Doch entweder
hat der Code noch einen signifikanten Fehler, oder der Befehl ist in
V4.51 verbuggt. Wenn ich den Code 1:1 übernehme, wird das
Programm von Windows selber abgebrochen. Ich bekomme keine
Messagebox und der Resource Monitor sagt "Programm abgebrochen".
Aktiviere ich den Purifier, wird in der Zeile mit CopyMemoryString()
ein Überlauf fest gestellt, wie Stargate es schon ansprach. Den
Fehler konnt ich aber leider nicht finden.

Und als Optimierungsvorschlag hätte ich noch: Die Blockanzahl
berechnen, und nicht in einer Schleife hoch zählen und jedes
mal ReallocateMemory() aufrufen.

Das Ergebnis ist aber schon krass, also < 16ms im vergleich zu
ner halben Minute ist heftig. Muss ich mir auf jeden fall merken.

MFG PMV

[Kiffi]

@Volker: Danke für Deinen Snippet! Ist schon erstaunlich,
wie gut man den Code mit diesem kleinen Trick beschleunigen
kann

Allerdings ist die Performance dann nicht mehr so gut, wenn
ich Deinen Code im mein Programm einbaue. Im Gegensatz zu
Dir baue ich unterschiedlich lange Strings (teilweise auch nur
ein Zeichen) zusammen. Muss noch schauen, woran es liegt...

Nochmals Danke & Grüße ... Kiffi

[Kukulkan]

Hallo Kiffi,

der Zauberparameter zur Optimierung ist DummyLength.i. Wenn Du viele kurze Werte anhängst, kann es Sinn machen hier einen kleineren Wert zu verwenden (zB 200 bis 600). Meistens lass ich den nicht (wie im Beispiel) berechnen sondern suche in drei oder vier Testläufen einen gut geeigneten Wert den ich dann fest kodiere. Dadurch lassen sich nochmal einige Prozent rausholen.

Grüße,

Kukulkan