Delphi vs. Freepascal und THashedStringList

[Uwe Raabe]

Und die Delphi-Version ist 2007?

Zitat von DelTurbo:

Mache ich bei Delphi etwas falsch?

Etwas Code wäre vielleicht hilfreich.

Zitat von DelTurbo:

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 von Uwe Raabe:

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 von DelTurbo:

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 von himitsu:

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

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