Delphi vs. Freepascal und THashedStringList

[DelTurbo]

Hi,
ich habe mal eine Frage. Ich nutze gerne THashedStringList wenn ich viel vergleichen muss. Nun hatte ich eine liste mit ca. 2 Mio. Einträgen und eine liste mit ca. 500.000 Einträgen.
Die habe ich mit IndexOf verglichen. Unter Delphi Dauerte es ca. 5 Minuten. Dann habe ich das mal mit Freepascal übersetzt weil ich es auch für Unix brauche.
Es ist nichts geändert. Der Quellcode ist wirklich der gleiche. Aber unter FreePascal dauert das 1,5 Sekunden. Egal ob Windows oder Unix.

Mache ich bei Delphi etwas falsch? Ich mache nur ein Create. Muss man bei Delphi noch etwas andere setzen?

Was ist allerdings festgestellt habe, unter FreePascal kann man nicht mit mehreren Threads lesend auf THashedStringList zugreifen.

Oder ist das unter Delphi so langsam weil es Threadfest ist?

Vielen dank im Voraus

[himitsu]

Ein IndexOf dauert 5 Minuten? (würde aber nicht erwarten, dass Delphi da wirklich sooooo schlecht wäre)


Tja, beide werden bestimmt eigene/unterschiedliche Implementationen verwenden, die auch unterschlich gut implementiert wurden-

Ist deine Liste sortiert?
Ich weiß jetzt nicht wie es bei der THashedStringList aussieht, aber TStrings/TStringList hat unterschlieliche Suchfunktionen für Sortiert oder nicht. (ich hoffe mal das hat die THashedStringList auch)


PS: per se ist da in Delphi garnichts threadsafe gebaut, aber beim Lesen (solange dabei intern kein Schreibzugriff passiert, wie z.B. bei einem TStream), ist paralleles Lesen möglich.

[DelTurbo]

Nein, die liste ist nicht Sortiert. Also ein Unterschied von sagen wir mal 1-2 Minuten hätte ich noch verstanden. Aber soooo krass... Das hat mich wirklich erstaunt.

Die Freepascal Version hatte ich vergessen.
Free Pascal Compiler version 3.1.1 [2017/05/24] for x86_64

[Uwe Raabe]

Und die Delphi-Version ist 2007?

Zitat:

Zitat von DelTurbo (Beitrag 1455592)

Mache ich bei Delphi etwas falsch?

Etwas Code wäre vielleicht hilfreich.

Zitat:

Zitat von DelTurbo (Beitrag 1455592)

Oder ist das unter Delphi so langsam weil es Threadfest ist?

Wo wird das denn behauptet?

[DelTurbo]

Ja Delphi 2007.
Das mit dem Threadfest hatte ich mir einfach überlegt. Weil das auf den 1. Blick der einzige unterschied ist.

Und dann etwas Code. Ich habe eine Hauptschleife die sooft durchlaufen wie Daten da sind. Im moment ca. 500.000.

Delphi-Quellcode:

function IsInSubListID(list_id:String):Boolean; inline;
begin
    Result:=False;
    if ( GblListID.IndexOf(list_id)<>-1 ) then begin
      Result:=True;
    end;
end;

In der schleife wird dann hier nachgesehen ob die ID schon vorhanden ist. GblListID hat ca. 2,3Mio einträge.

Es liegt mir ferne Delphi "schlecht" zu machen. Mich hat das nur total gewundert das der gleiche Code plötzlich so schnell ist.

[himitsu]

Vielleicht ist die Liste, bzw. sind zumindestens die Hashs in FP standardmäßig soritert und in Delphi eben nicht standardmäßig.

Als Erklärung, auf eine Datenbank bezogen:
TStringList.IndexOf ohne Sortierung ist ein FullTableScan
und mit Sortierung ist es ein IndexScan.

[add]
In Delphi XE ist es immer ein "teilweiser" FullScan.
Und in Delphi2007 wird das nicht anders gewesen sein.

Delphi-Quellcode:

unit IniFiles;

//THashedStringList = class(TStringList)

function TStringHash.Find(const Key: string): PPHashItem;
var
  Hash: Integer;
begin
  Hash := HashOf(Key) mod Cardinal(Length(Buckets));
  Result := @Buckets[Hash];
  while Result^ <> nil do
  begin
    if Result^.Key = Key then
      Exit
    else
      Result := @Result^.Next;
  end;
end;

Für Delphi würde ich dann eher ein TDictionary<T> empfehlen.

[Uwe Raabe]

Ich würde das vielleicht nochmal mit einer aktuellen Delphi-Version probieren. In D2007 wird eine verkettete Liste für die Hash-Buckets verwendet. Neuere Versionen nehmen da ein Array.

Es ist aber vermutlich eher so, daß FP einen anderen Hash-Algorithmus verwendet, der für die aktuell verwendeten Strings weniger Kollisionen verursacht.

[DelTurbo]

Zitat:

Zitat von Uwe Raabe (Beitrag 1455600)

Es ist aber vermutlich eher so, daß FP einen anderen Hash-Algorithmus verwendet, der für die aktuell verwendeten Strings weniger Kollisionen verursacht.

Danke für die Antwort. Das kann natürlich sein. Obwohl FP Quelloffen ist, habe ich da nicht reingeschaut. Ich wollte den einfachen gehen und einfach mal fragen. :)

Und das ich mit einer 14 Jahre alten Delphi Version arbeite macht es nicht besser, das kann ich mir auch denken. Ich wollte auch nicht das dieser Thread "lang" wird.

Nochmal vielen dank an alle.....

[DelTurbo]

Richtig stellung:
Ich hatte mit mit den Zeiten vertan. Hier nun einmal die richtigen Daten.

Einträge in der THashedStringList: 2,313,748
Einträge die gegen getestet werden: 685,158

Zeiten:
Delphi 2007: 16:37 Minuten
FreePascal: 2:23 Minuten

So, das war es aber nun. Was ich im Kopf hatte als ich oben die Zeiten geschrieben weiß ich nicht mehr. :(

[Stevie]

THashedStringList steht nicht umsonst in der Unit IniFiles. Die ist nicht dafür ausgelegt mit vielen Einträgen performant zu funktionieren sondern nur im Kontext der TMemIniFile (die das inzwischen auch nicht mehr benutzt, sondern ein TDictionary aus System.Generics.Collections).

Die zugrundeliegende Hashtable wird mit einer festen Anzahl von 256 Buckets erstellt - d.h. bei 2mio Elementen wird aus einem theoretischen O(1) ein O(n).

Vergiss einfach, dass du jemals von THashedStringList gehört hast und benutz ein TDictionary aus System.Generics.Collections.

P.S. Ähh, Delphi 2007 - musst du dir was eigenes bauen, oder du modifizierst THashedStringList, dass sie mehr Buckets baut. Allerdings wirst du da auch nicht wirklich auf einen grünen Zweig kommen, da das intern ein bisschen verwurschtelt ist (hab hier grad nur XE als ältesten Sourcestand).

[jaenicke]

Zitat:

Zitat von DelTurbo (Beitrag 1455597)

Ja Delphi 2007.

Es wurde an einigen Stellen massiv an der Geschwindigkeit gearbeitet seit Delphi 2007 (unter anderem bei Threads), von den vielen anderen Verbesserungen ganz zu schweigen...

[himitsu]

Wurde FastStrings 2009 oder schon 2006 teilweise in Delphi übernommen?
(finde nicht mehr wann es war, aber 2007 hatte der originale Entwickler die Entwicklung eingestellt)

Mit 3% (div 33) der Daten dauert es nicht so lang.
Das mit dem "Selbsbau"-Hash findet manchmal mehr, wegen Hash-Kollisionen, zu kleinem Hash und da nicht nochmal der String verglichen wird.
Und das mit den Generics geht erst nach D2007, bzw. im FPC vermutlich etwas anders.

Code:

// 685.158 in 2.313.748
TArray.BinarySearch       342579  0,97
TArray.BinarySearch.Hash  342708  0,39
TStringList               nach über 3 Stunden abgebrochen und mit weniger versucht
TStringList.Sorted        342579  3,05
THashedStringList         342579  448,36
THashedStringList.Sorted  342579  334,23
TList<>                   ...

Code:

// mit DIV 30 = 22.838 in 77.124
TArray.BinarySearch       11419  0,01
TArray.BinarySearch.Hash  11419  0,01
TStringList               11419  153,13 (3min)
TStringList.Sorted        11419  0,05
THashedStringList         11419  0,11
THashedStringList.Sorted  11419  0,11
TList<>                   11419  9,30
TList<>.Sorted**          11419  9,31
TDictionary<>             11419  0,00

Fazit:
Für normale Mengen an INI-Einträgen ist die Delphi-THashedStringList absolut schwachsinnig.
Sortiert ist eine normale StringListe wesenlich schneller und selbst unsortiert ist sie in normalem Umfang immernoch schnell genug.

[Stevie]

Zitat:

Zitat von himitsu (Beitrag 1455792)

Für normale Mengen an INI-Einträgen ist die Delphi-THashedStringList absolut schwachsinnig.
Sortiert ist eine normale StringListe wesenlich schneller und selbst unsortiert ist sie in normalem Umfang immernoch schnell genug.

Ne sortierte StringListe kannste aber nicht modifizieren und wieder in eine Datei schreiben, so dass nur die geänderten Stellen unterschiedlich sind :roll:

Das Problem ist, dass schon damals viele der RTL Entwickler von Datenstrukturen und Algorithmen und schon gar nicht von Hardware Effekten (Cache Verhalten und Co) nen Plan hatten. Nativ kompiliert, da wird das schon schnell sein, woll :stupid:

[himitsu]

[doppelpost deleted] :oops:

[himitsu]

Och, es muß ja nur die Suchliste sortiert sein.

Was auch so manche Komponente so implementiert.
Die originale Liste und zusäzlich ein sortierter Index, mit den Suchmustern und ihren Indizes zur eigentlichen Liste.
Pssst: Wozu man wohl das Objects der TStringList missbrauchen können würde? :stupid: (oder gleich ein TDictionary<Key,Index>)

[p80286]

Zitat:

Zitat von Stevie (Beitrag 1455794)

Das Problem ist, dass schon damals viele der RTL Entwickler von Datenstrukturen und Algorithmen und schon gar nicht von Hardware Effekten (Cache Verhalten und Co) nen Plan hatten. Nativ kompiliert, da wird das schon schnell sein, woll :stupid:

Hmmm ist das jetzt so unter uns bei nem Bierchen gebrummelt oder hast Du konrete Informationen?

Gruß
K-H

[himitsu]

Zitat:

Zitat von p80286 (Beitrag 1455801)

Hmmm ist das jetzt so unter uns bei nem Bierchen gebrummelt oder hast Du konrete Informationen?

Wenn du dir StringReplace ansiehst, was da passiert, wenn mehr als Einwas ersetzt wird,
oder Format, wo mit einem statischen Puffer auf dem Stack gearbeitet wird, da wird dir schlecht.

Oder nimm dir mal den originalen DelphiMM vor. Ein bissl mehr hätte man da schon machen können, ohne gleich so weit zu gehn, wie der FastMM.
Gut, der ist "optimaler" für kleine Speicherblöcke, als das was Windows dort nativ (VirtualAlloc) anbietet und wesentlich schon flotter als der MM der OLE32.

Und auch viele andere StringFunktionen waren nicht grade "optimal".
Auch wenn nur Bruchteile der FastStrings übernommen wurden, war das Ergebnis schon um welten Besser, als die Originale, an denen man Jahrzehnte praktisch nie etwas geändert hatte .... es lief ja, also warum was tun.^

Den StringHelper hat man sich von anderen Programmiersprachen abgeguckt und dabei nur das Interface grob kopiert, aber natülich nichts davon an Pascal und dessen Verhalten angepasst, womit dort nun auch Einiges echt grausam aussieht, obwohl es nagelneu ist, außerdem dachte man nicht weiter und hat somit vieles vergessen, wo man sich fragt wieso gibt es das nichts, obwohl es einem sofort in den Kopf kommt.

[Luckie]

Bitte beim Thema bleiben.

[p80286]

Zitat:

Zitat von Luckie (Beitrag 1455807)

Bitte beim Thema bleiben.

MM nach ist das das Thema "Hat die RTL noch Optimierungsbedarf?".
Für mich hat sich das jetzt bestätigt, also weiterhin nicht alles als gegeben hinnehmen.

Gruß
K-H

P.S.
Make it run, make it reliable, make it fast.

[Stevie]

Zitat:

Zitat von p80286 (Beitrag 1455801)

Hmmm ist das jetzt so unter uns bei nem Bierchen gebrummelt oder hast Du konrete Informationen?

Einfach mal RTL Source Code studieren und ein bisschen (mehr maß ich mir gar nicht an von mir zu behaupten) Wissen über asymptotisches Verhalten, konstante Faktoren (vor allem von der Hardware beeinflusste) haben und ggf in den generierten Assembly Code zu schauen, um zu merken, dass man z.B. öffzig unnötige temporäre Strings gebastelt hat mit ner naiven Implementierung.

Zitat:

Zitat von p80286 (Beitrag 1455827)

Make it run, make it reliable, make it fast.

Für Standard Bibliotheken sollte allerdings zwischen 1 und 2 kein Release erfolgen, sondern erst nach 3. Nur leider stoppt nach 1 oft jegliche Entwicklung und fast alle Anmerkungen bzgl 2 und 3 werden als "new feature" abgetan.

[p80286]

Zitat:

Zitat von Stevie (Beitrag 1455829)

Einfach mal RTL Source Code studieren und ein bisschen (mehr maß ich mir gar nicht an von mir zu behaupten) Wissen über asymptotisches Verhalten, konstante Faktoren (vor allem von der Hardware beeinflusste) haben und ggf in den generierten Assembly Code zu schauen, um zu merken, dass man z.B. öffzig unnötige temporäre Strings gebastelt hat mit ner naiven Implementierung.

Is ja gut, Bahnhof hab ich noch verstanden, die Sache mit den Koffern muß ich mir dann irgendwann einmal erarbeiten.

Gruß
K-H