SQLite-StringBuilder

Beitrag von **Kiffi** » 14.03.2016 17:20

PB ist bekanntermaßen nicht so performant, wenn es darum geht, Zeichenketten zu verknüpfen.

In diesem und im englischen Forum gibt es bereits einige Codes, die Stringverknüpfungen beschleunigen.

Hier mal eine etwas andere Art eines Stringbuilders, welcher SQLite-Funktionalitäten verwendet.

Je höher die Anzahl der Durchläufe (bei ab einer Anzahl > 500) und je länger die zu verknüpfenden Zeichenketten, desto größer ist der Geschwindigkeits-Gewinn.

Code: Alles auswählen

EnableExplicit

Procedure SbInit()
  UseSQLiteDatabase()
  Protected DB
  DB = OpenDatabase(#PB_Any, ":memory:", "", "", #PB_Database_SQLite)
  DatabaseUpdate(DB, "Create Table Strings (String TEXT)")
  ProcedureReturn DB
EndProcedure

Procedure SbAppend(DB, String.s)
  SetDatabaseString(DB, 0, String)  
  DatabaseUpdate(DB, "Insert Into Strings (String) Values (?)")
EndProcedure

Procedure.s SbToString(DB, Delimiter.s = "")
  Protected ReturnValue.s
  DatabaseQuery(DB, "Select Group_Concat(String, '" + Delimiter + "') From Strings")
  NextDatabaseRow(DB)
  ReturnValue = GetDatabaseString(DB, 0)
  FinishDatabaseQuery(DB)
  ProcedureReturn ReturnValue
EndProcedure

Procedure.s SbClear(DB)
  DatabaseUpdate(DB, "Delete From Strings")
EndProcedure

Procedure.s SbExit(DB)
  CloseDatabase(DB)
EndProcedure


; Test:

#Anzahl = 5000

Define SB, Counter
Define Z1, Z2, L1

Z1=ElapsedMilliseconds()
SB = SbInit()
For Counter = 1 To #Anzahl
  SbAppend(SB, "Hello PureBasic!")
Next
L1 = Len(SbToString(SB))
SbClear(SB)
SbExit(SB)
Z2=ElapsedMilliseconds()

; ------

Define Z3, Z4, L2
Define SBString.s

Z3=ElapsedMilliseconds()
SBString = ""
For Counter = 1 To #Anzahl
  SBString + "Hello PureBasic!"
Next
L2 = Len(SBString)
SBString = ""
Z4=ElapsedMilliseconds()

MessageRequester("Result", 
                 "DB: " + Str(Z2-Z1) + " (" + Str(L1) + ")" + #CRLF$ + 
                 "PB: " + Str(Z4-Z3) + " (" + Str(L2) + ")")

Wer also ohnehin SQLite in seinem Code verwendet, kann das ja gerne mal ausprobieren. Allen anderen weise ich darauf hin, dass die Größe der EXE durch die Verwendung von SQLite-Befehlen um knapp ein halbes MB anwächst.

Optimierungen, Modularisierungen, etc. könnt Ihr gerne selber durchführen.

Grüße ... Peter

Sicro · Beitrag von **Sicro** » 15.03.2016 15:24

Beeindruckend, was für eine hohe Zeitersparnis mit SQLite erreicht werden kann.

Ich hätte nicht gedacht, dass PB bei der Zeichenverkettung so langsam ist.

Beitrag von **NicTheQuick** » 15.03.2016 16:43

Es ist zwar interessant, aber irgendwie nicht effektiv genug. Mit einer simplen LinkedList, Space() und PokeS() geht das selbe bei mir nochmals um einiges schneller:

Code: Alles auswählen

EnableExplicit

Structure Sb
	List strings.s()
	length.i
EndStructure

Procedure Sb2Init()
	ProcedureReturn AllocateStructure(Sb)
EndProcedure
Procedure Sb2Append(*Sb.Sb, String.s)
	If AddElement(*Sb\strings())
		*Sb\strings() = String
		*Sb\length + Len(String)
		ProcedureReturn #True
	EndIf
	ProcedureReturn #False
EndProcedure
Procedure.s Sb2ToString(*Sb.Sb)
	Protected result.s = Space(*Sb\length)
	Protected i.i
	ForEach *Sb\strings()
		i + PokeS(@result + i, *Sb\strings()); / SizeOf(Character)
	Next
	ProcedureReturn result
EndProcedure
Procedure Sb2Clear(*Sb.Sb)
	*Sb\length = 0
	ClearList(*Sb\strings())
EndProcedure
Procedure Sb2Exit(*Sb.Sb)
	FreeStructure(*Sb)
EndProcedure


Procedure SbInit()
	UseSQLiteDatabase()
	Protected DB
	DB = OpenDatabase(#PB_Any, ":memory:", "", "", #PB_Database_SQLite)
	DatabaseUpdate(DB, "Create Table Strings (String TEXT)")
	ProcedureReturn DB
EndProcedure

Procedure SbAppend(DB, String.s)
	SetDatabaseString(DB, 0, String) 
	DatabaseUpdate(DB, "Insert Into Strings (String) Values (?)")
EndProcedure

Procedure.s SbToString(DB, Delimiter.s = "")
	Protected ReturnValue.s
	DatabaseQuery(DB, "Select Group_Concat(String, '" + Delimiter + "') From Strings")
	NextDatabaseRow(DB)
	ReturnValue = GetDatabaseString(DB, 0)
	FinishDatabaseQuery(DB)
	ProcedureReturn ReturnValue
EndProcedure

Procedure.s SbClear(DB)
	DatabaseUpdate(DB, "Delete From Strings")
EndProcedure

Procedure.s SbExit(DB)
	CloseDatabase(DB)
EndProcedure


; Test:

#Anzahl = 50000

Define SB, Counter
Define T1, L1

T1 = ElapsedMilliseconds()
SB = SbInit()
For Counter = 1 To #Anzahl
	SbAppend(SB, "Hello PureBasic!")
Next
L1 = Len(SbToString(SB))
SbClear(SB)
SbExit(SB)
T1 = ElapsedMilliseconds() - T1

; ------

Define SB, Counter
Define T3, L3

T3 = ElapsedMilliseconds()
SB = Sb2Init()
For Counter = 1 To #Anzahl
	Sb2Append(SB, "Hello PureBasic!")
Next
L3 = Len(Sb2ToString(SB))
Sb2Clear(SB)
Sb2Exit(SB)
T3 = ElapsedMilliseconds() - T3


; ------

Define T2, L2
Define SBString.s

T2 = ElapsedMilliseconds()
SBString = ""
For Counter = 1 To #Anzahl
	SBString + "Hello PureBasic!"
Next
L2 = Len(SBString)
SBString = ""
T2 = ElapsedMilliseconds() - T2

MessageRequester("Result",
                 "DB: " + Str(T1) + " (" + Str(L1) + ")" + #CRLF$ +
                 "PB: " + Str(T2) + " (" + Str(L2) + ")" + #CRLF$ +
                 "LL: " + Str(T3) + " (" + Str(L3) + ")")

Ergebnis auf Linux:

Code: Alles auswählen

DB: 322 ms
PB: 19076 ms
LL: 12 ms (2683% schneller als DB)

Ergebnis auf Windows:

Code: Alles auswählen

DB: 476 ms
PB: 80489 ms
LL: 34 ms (1400% schneller als DB)

Sicro · Beitrag von **Sicro** » 16.03.2016 01:59

Per Memory geht es noch schneller:

Code: Alles auswählen

EnableExplicit

Structure Sb
  List strings.s()
  length.i
EndStructure
Procedure Sb2Init()
  ProcedureReturn AllocateStructure(Sb)
EndProcedure
Procedure Sb2Append(*Sb.Sb, String.s)
  If AddElement(*Sb\strings())
    *Sb\strings() = String
    *Sb\length + Len(String)
    ProcedureReturn #True
  EndIf
  ProcedureReturn #False
EndProcedure
Procedure.s Sb2ToString(*Sb.Sb)
  Protected result.s = Space(*Sb\length)
  Protected i.i
  ForEach *Sb\strings()
    i + PokeS(@result + i, *Sb\strings()); / SizeOf(Character)
  Next
  ProcedureReturn result
EndProcedure
Procedure Sb2Clear(*Sb.Sb)
  *Sb\length = 0
  ClearList(*Sb\strings())
EndProcedure
Procedure Sb2Exit(*Sb.Sb)
  FreeStructure(*Sb)
EndProcedure


Procedure SbInit()
  UseSQLiteDatabase()
  Protected DB
  DB = OpenDatabase(#PB_Any, ":memory:", "", "", #PB_Database_SQLite)
  DatabaseUpdate(DB, "Create Table Strings (String TEXT)")
  ProcedureReturn DB
EndProcedure
Procedure SbAppend(DB, String.s)
  SetDatabaseString(DB, 0, String)
  DatabaseUpdate(DB, "Insert Into Strings (String) Values (?)")
EndProcedure
Procedure.s SbToString(DB, Delimiter.s = "")
  Protected ReturnValue.s
  DatabaseQuery(DB, "Select Group_Concat(String, '" + Delimiter + "') From Strings")
  NextDatabaseRow(DB)
  ReturnValue = GetDatabaseString(DB, 0)
  FinishDatabaseQuery(DB)
  ProcedureReturn ReturnValue
EndProcedure
Procedure SbClear(DB)
  DatabaseUpdate(DB, "Delete From Strings")
EndProcedure
Procedure SbExit(DB)
  CloseDatabase(DB)
EndProcedure


Procedure Sb3Init()
EndProcedure
Procedure Sb3Append(*SBString, String.s)
  Protected Size, *Offset
  If *SBString <> 0
    Size = MemorySize(*SBString)
    *Offset = Size
  EndIf
  Size + StringByteLength(String)
  *SBString = ReAllocateMemory(*SBString, Size, #PB_Memory_NoClear)
  PokeS(*SBString + *Offset, String, -1, #PB_String_NoZero)
  ProcedureReturn *SBString
EndProcedure
Procedure.s Sb3ToString(*SBString)
  ProcedureReturn PeekS(*SBString, MemorySize(*SBString)/SizeOf(Character))
EndProcedure
Procedure Sb3Clear(*SBString)
  FreeMemory(*SBString)
EndProcedure
Procedure Sb3Exit()
EndProcedure



; Test:

#Anzahl = 50000

Define SB, Counter

Define T1, L1

T1 = ElapsedMilliseconds()
SB = SbInit()
For Counter = 1 To #Anzahl
  SbAppend(SB, "Hello PureBasic!")
Next
L1 = Len(SbToString(SB))
SbClear(SB)
SbExit(SB)
T1 = ElapsedMilliseconds() - T1

; ------

Define T3, L3

T3 = ElapsedMilliseconds()
SB = Sb2Init()
For Counter = 1 To #Anzahl
  Sb2Append(SB, "Hello PureBasic!")
Next
L3 = Len(Sb2ToString(SB))
Sb2Clear(SB)
Sb2Exit(SB)
T3 = ElapsedMilliseconds() - T3

; ------

Define T2, L2
Define SBString.s

T2 = ElapsedMilliseconds()
SBString = ""
For Counter = 1 To #Anzahl
  SBString + "Hello PureBasic!"
Next
L2 = Len(SBString)
SBString = ""
T2 = ElapsedMilliseconds() - T2

; ------

Define T4, L4
SB = 0

T4 = ElapsedMilliseconds()
Sb3Init()
For Counter = 1 To #Anzahl
  SB = Sb3Append(SB, "Hello PureBasic!")
Next
L4 = Len(Sb3ToString(SB))
Sb3Clear(SB)
Sb3Exit()
T4 = ElapsedMilliseconds() - T4

MessageRequester("Result",
                 "DB:  " + Str(T1) + " (" + Str(L1) + ")" + #CRLF$ +
                 "PB:  " + Str(T2) + " (" + Str(L2) + ")" + #CRLF$ +
                 "LL:  " + Str(T3) + " (" + Str(L3) + ")" + #CRLF$ +
                 "MEM: " + Str(T4) + " (" + Str(L4) + ")")

Linux:

Code: Alles auswählen

DB:  387 (800000)
PB:  28589 (800000)
LL:  17 (800000)
MEM: 9 (800000)

Da frage ich mich nun, was PB bei [String.s + "String"] macht, dass es so langsam ist.

matbal · Beitrag von **matbal** » 16.03.2016 10:25

Sicro hat geschrieben:Da frage ich mich nun, was PB bei [String.s + "String"] macht, dass es so langsam ist.

Eigentlich ist es klar. PB merkt sich nichts über einen String, außer wo er im Speicher beginnt. Hängt man mehrere Strings aneinander, muß PB jedesmal das Stringende suchen. Das dauert um so länger, je größer der String wird.

Und wenn der Speicherplatz nicht reicht, muß PB den String auch noch umkopieren, was auch mit steigende Stringlänge immer langsamer wird.

Das Suchen des Stringendes macht auch viele Stringfunktionen bei längeren Strings langsam.

p.s. übrigens ist deine Version bei mir langsamer.
---------------------------
Result - Windows
---------------------------
DB: 341 (800000)
PB: 30007 (800000)
LL: 18 (800000)
MEM: 28 (800000)
---------------------------

Sicro · Beitrag von **Sicro** » 03.04.2016 16:36

matbal hat geschrieben:PB merkt sich nichts über einen String, außer wo er im Speicher beginnt.

Da hast du anscheinend recht. Das erklärt den Geschwindigkeitsvorteil, den ich unter meinem Linux feststellen konnte, weil bei meinem Code die Länge des bereits zusammengesetzten Strings nicht erst berechnet werden muss, sondern zwischengespeichert ist und per MemorySize() nur noch ausgelesen werden muss. Nur die Länge des neuen Strings, der zum zusammengesetzten String hinzugefügt wird, muss berechnet werden (Size + StringByteLength(String)).

matbal hat geschrieben:Hängt man mehrere Strings aneinander, muß PB jedesmal das Stringende suchen.

Wie gesagt: Bei meinem ist das auch der Fall. Nur ist die Länge des bereits zusammengesetzten Strings schon bekannt und muss nicht mehr berechnet werden.

matbal hat geschrieben:Und wenn der Speicherplatz nicht reicht, muß PB den String auch noch umkopieren

Soweit ich weiß ist das nicht der Fall. Daten im RAM sind oft fragmentiert. Der RAM-Manager vom OS regelt das und lässt den allozierten Speicher zusammenhängend aussehen.

matbal hat geschrieben:p.s. übrigens ist deine Version bei mir langsamer.

Ok, dann ist der Geschwindigkeitsvorteil nur ein Sonderfall und nicht allgemeingültig.

PureBoard

SQLite-StringBuilder

SQLite-StringBuilder

Re: SQLite-StringBuilder

Re: SQLite-StringBuilder

Re: SQLite-StringBuilder

Re: SQLite-StringBuilder

Re: SQLite-StringBuilder