[gelöst]tDictionary

[exc-jdbi]

Guten Morgen ruewa

Vielen dank für die Beispiele. Ich werde sie heute noch anschauen.

Freundliche Grüsse

exc-jdbi

[exc-jdbi]

Guten Abend ruewa

Habe mir das kurz angeschaut. Coole Sache.

Mit der QuickSortHashList 1 Mio. Daten

Code: Alles auswählen

 
Sortieren                      6645 ms
Überführung tStringList        1245 ms
 

Die anderen Zwei (CompareAsciiShortStrInsensitive, CompareAsciiShortStrSensitive) habe ich noch nicht getestet, werde ich aber noch machen. Leider kann es bei mir vorkommen, dass die Values (eventuell auch sporadisch bei den Key's) um einiges Länger sind als die 255 Bit.


Ich bin im Moment an etwas ganz Neuem. Eigenlich bin ich schon fertig, aber ich möchte es noch intensiver Testen. Ich verwende dazu eine Record, mit Rückzeiger und Vorzeiger und natürlich zwei Strings (Key+Values).

Das Ganze sieht bis jetzt gut aus. Nächste Woche, wenn es mir die Zeit erlaubt, kann ich mehr sagen.


Freundliche Grüsse

exc-jdbi

[ruewa]

Hallo exc-jdbi,

ist dieser Wert vergleichbar mit Deinen vorigen Tests? Dann würde das ja 3 x so lange brauchen wie TFPGMap.Sort. Wie gesagt, den Sortieralgorithmus habe ich von TFPGMap.Sort übernommen, meine Änderungen betrafen im Wesentlichen die spezielle Datenrepräsentanz TFPHashList / TSortArray. Deshalb müßte QuickSortHashList ähnlich schnell sein wie TFPGMap. Das bedeutet dann aber, daß sich der Laufzeitunterschied v.a. aus der verwendeten Comparemethode speist. Die ist der eigentliche Flaschenhals!

Die Ausgangsfrage ist: Mit welcher Sorte Strings (Shortstring, AnsiString, PChar) habe ich zu tun, und mit welcher Zeichenrepräsentation (Char/AnsiChar, WideChar, UTF-8)? Shortstrings sind ja die guten alten Turbo-Pascal-Stings, mit dem Längenbyte auf String[0] und 1-Byte-Zeichen auf String[1..Length]. Wenn Du normale Strings verwendest (und den Compilerschalter standardmäßig auf {$H+} läßt), sind Deine Daten als AnsiStrings abgelegt. Dann wirst Du mit einer auf ShortStrings basierenden Vergleichsmethode nicht viel Freude haben, denn selbst wenn Du den Compiler überzeigst, daß das in dem Fall schon in Ordnung ist, wirst Du bei jedem Compare-Aufruf eine ShortString-Kopie Deines AnsiStrings erzeugen müssen - und jede Typumwandlung (ob automatisch vom Compiler vorgenommen oder von Dir erzwungen) kostet an genau der Stelle Zeit, wo Du es nicht gebrauchen kannst.

Bevor ich die CompareAsciiShortStr(In)Sensitive-Funktionen geschrieben habe, habe ich mir die entsprechenden SysUtils-Routinen CompareStr und CompareText mal genauer angesehen und war erstaunt, daß die intern in eine ziemlich verschachtelte Aufrufstruktur hineinrutschen. Mag sein, daß ich bei meiner CompareText-Alternative noch irgendwelche Sonderregeln übersehen habe, aber zumindest beim einfacheren Fall des sensitiven Vergleichs kann ich nicht erkennen, was CompareStr kann, was das doch ziemlich einfach gestrickte CompareAsciiShortStrSensitive nicht kann - abgesehen vom handlicheren Stringtyp! Vor allem leuchtet mir überhaupt nicht ein, worin der Vorteil bestehen sollte, daß CompareStr in systemnahe Unterroutinen verzweigt (CompareByte) und da fürchterlich kompliziertes Zeug anstellt. Aber selbst dann erschließt sich mir immer noch nicht, warum eigentlich CompareStr 15-20 mal langsamer ist (meine Messung beinhaltet ja immer auch den konstanten Quicksort-Anteil) als die gute alte Einfachst-Handarbeit von CompareAsciiShortStrSensitive.

Wenn das bei AnsiString-/WideChar-Vergleichsoperationen aus dem FreePascal-Lego-Kasten auch nur halbwegs ähnlich ist, wirst Du nicht drumrum kommen, Dir eine an Deine Daten angepaßte Vergleichsmethode (die ohne Typumwandlung und Stringkopien auskommt) selbst zu schreiben.

Übrigens sind meine Teststrings für Vergleichs- und Sortieroperationen äußerst ungünstig verteilt. Mein Programm isoliert Bezeichner aus Header-Dateien kompletter C-Bibliotheken (dabei geht es mir um das Aufspüren undokumentierter API-Routinen). Ich teste es mit der WebKit2GTK-Bibliothek - da fangen allein 60 % aller Bezeichner mit "WEBKIT_DOM_..." an, d.h. die Compare-Funktion muß die Strings untypisch lange durchnudeln, bis sie zu einem Ergebnis kommt. Vielleicht ist das mit ein Grund, weshalb die Laufzeitunterschiede bei mir derart spektakulär ausfallen.

Fazit: Die Compare-Funktion ist der Dreh- und Angelpunkt für die Sortierlaufzeit, und man sollte sich offenbar nicht darauf verlassen, daß die entsprechenden FreePascal-Standardroutinen schon das Optimum herausgeholt haben würden.

Gruß Rüdiger

[BeniBela]

Normalerweise fügt man für sowas die Daten in eine Baumstruktur ein...

Dann sind sie immer in sortierter Reihenfolge auslesbar

[exc-jdbi]

Hallo ruewa und hallo BeniBela

Danke für die Antworten.

Ja es waren die gleichen Tests. Ich habe einfach deine Quicksort-Routine eingefügt.

Ich arbeite mit String also eigenlich Ansistring. Die Direktive {$B+} ist einbezogen. In diesem String kann es vorkommen, dass Sonderzeichen wie wir sie im Deutschen kennen drin sind. Also auch in der Key-Variable.

Warum das es gerade ca. 3x langsamer ist als in der TFPGMap möchte ich schon noch weiter suchen. Auch ich habe jetzt angefangen mehr in die entsprechenden uses-Dateien zu suchen. Ich finde immer wieder interessante Erkenntnisse.

Die von Dir dargestellten Sortier-Routinen finde ich sehr gut, und man erkennt schon, dass du dich mit dem befasst hast, und dich gut auskennst. Dafür möchte ich mich bedanken.. Ich habe mit dieser "tDctionary" schon viel neues gelernt in Bezug auf Lazarus, und es kommt immer wieder Neues dazu.

BeniBela wie meinst du das "die Daten in eine Baumstruktur" einzufügen? Parallel zur Hashliste?


Freundliche Grüsse

exc-jdbi

[BeniBela]

BeniBela wie meinst du das "die Daten in eine Baumstruktur" einzufügen? Parallel zur Hashliste?

Wie ich vorhin ruewa geschrieben habe:

Java hat z.B.: HashMap und TreeMap Klassen. (oder in c++ heißen sie std::map und std::unordered_map)

Für praktische Zwecke verhalten sich beide gleich, aber in der TreeMap lassen sich die Schlüssel sortiert durchlaufen...

[ruewa]

Hallo !

Ich habe mich noch etwas intensiver mit den Compare-Funktionen beschäftigt und konnte die Hashlisten-Sortierung noch einmal um ein Drittel beschleunigen. Der Sortiervorgang meiner TFPHashList (mit 4112 Elementen) läuft jetzt in 10 bzw. 12 Millisekunden (case-sensitiv / -insensitiv) durch. Derselbe Datensatz benötigt beim Sortieren in einer Stringliste 450 ms, das ist ist also ein Tuning um den Faktor 40! Und auch das Sortieren in der Hashliste hat sich gegenüber der Benutzung von Compare-Methoden aus der FreePascal-Bordapotheke um den Faktor 10-12 beschleunigt. Da kann man nicht meckern...

Um die Comparefunktionen weiter zu optimieren, habe ich ein Testprogramm geschrieben, das jeweils 100 Mio. Stringvergleiche unter verschiedenen Bedingungen durchführt. Damit konnte ich gut an meinen Funktionen feilen, bis ich schließlich mit deren Charakteristik zufrieden war. Es sind z.T. ziemlich kleine Dinge, die einen deutlichen Effekt ausmachen, z.B. das Ersetzen einer Break-Anweisung durch ein Goto-Label, oder das Deklarieren zweier lokaler Variablen als SmallInt anstatt Byte, während umgekehrt vier lokale Variable besser als Byte denn als SmallInt deklariert werden - soetwas kann man eigentlich nur durch viel Ausprobieren und Zeitmessen herausfinden. Apropos Zeitmessen: Es gibt eine neue Version des DebugTimers: http://www.lazarusforum.de/viewtopic.ph ... 571#p71571

Hier die Ergebnisse:

Dieselbe Messung mit Inline-Deklaration. Dies bringt v.a. bei den frühen Abbruchbedingungen noch einmal ein paar Prozente:

So spektakulär diese Verbesserung auch sein mag: Dies bedeutet nicht, daß die FP-Routinen lausig wären. Bei all meinen Versuchen, noch etwas mehr herauszukitzeln, ging es immer nur um ein Prozent hier und ein paar Prozente da, das Einsparen einer Result-Zuweisung und dergleichen. Der eigentliche, wirklich spektakuläre Effekt kommt durch die Parameterdefinition als ShortString zustande. Wenn ich meine Compare-Funktionen versuchshalber auf "String"-Parameter umstelle, ist der Effekt absolut grausam! Dann sind die schlagartig genauso langsam wie die SysUtils-Routinen CompareStr und CompareText (ein bißchen anders verteilt, aber im Schnitt), und zwar ganz unabhängig von den als Shortstring deklarierten Ausgangsdaten, auch unabhängig davon, daß die Compilerdirektive {$H-} sowohl bei der aufrufenden Unit wie in SysUtils wirksam ist, und ebenfalls unabhängig von der Tatsache, daß die Stringparameter als Konstanten übergeben werden!

Das ist für mich die eigentliche Erkenntnis: Die {$H-}-Direktive bietet in Free Pascal offenbar keine Gewähr dafür, daß die Strings konsistent als Shortstrings behandelt werde. Das zeigen auch meine Messungen: Die Compare-Funktion mag das Herzstück des Sortiervorgangs sein, aber eine Compare-Methode, die im Schnitt vielleicht 5 mal schneller ist, vermag das Sortieren als ganzes nicht um das 10-fache zu beschleunigen. Dennoch geschieht das, also muß es noch einen weiteren Flaschenhals geben. Meine starke Vermutung ist, daß der Compiler bei der Übergabe der Shortstring-Parameter aus der Hashliste an die String-deklarierte Compare-Funktion eine doppelte String-Umwandlung vornimmt, und zwar trotz const-Deklaration der Parameter: ShortString zu AnsiString und dann wieder zurück zu Shortstring, denn intern arbeiten die Sysutils-Funktionen dann doch wieder mit den guten alten Turbo-Pascal-Strings (etwa, wenn die lokalen Lesezeiger auf S1[1] und S2[1] gesetzt werden). Das heißt: Der Compiler geht im babylonischen String-Gewirr kurzerhand auf Nummer Sicher und opfert dafür ein Stück Sprach-Konsistenz.

Man bekommt das nur in den Griff, indem man darauf achtet, über die gesamte Aufrufkette explizit mit Shortstrings zu arbeiten. Das aber wird dann u.U. belohnt mit einem Geschwindigkeitszuwachs um den Faktor 10! Deshalb gab es zum Selberschreiben meiner Compare-Funktionen wohl auch keine Alternative.

Hier nun die optimierten Funktionen im Quelltext:

Code: Alles auswählen

{$GOTO+}
 
function CompareShortStringAnsiCharSensitive(const S1, S2 : ShortString): SmallInt;
var
  i, len : SmallInt;                     // SmallInt are faster than Byte
label L1;
begin
  if Length(S1) > Length(S2) then len := Length(S2) else len := Length(S1);
  i := 1;                                // Length(S1) is coded similar to Byte(S1[0])
  while i <= len do
  begin
    if (S1[i] = S2[i]) then inc(i)
    else begin
      result := Byte(S1[i]) - Byte(S2[i]);
      goto L1;                           // Label is faster than Break
    end;
  end;
  result := Length(S1) - Length(S2);     // only reached if all matched and i > len
  L1:
end;
 
function CompareShortStringAnsiCharInsensitive(const S1, S2 : ShortString) : SmallInt;
var
  i : SmallInt;                 // counter var must be SmallInt, thus result is used for len
  B1, B2 : Byte;                // otherwise match with len=255 causes endless-loop
label L2;
begin
  if Length(S1) > Length(S2) then result := Length(S2) else result := Length(S1);
  i := 1;                          // Length(S1) is coded similar to Byte(S1[0])
  while i <= result do
  begin
    B1 := Byte(S1[i]);             // must have copies to modify, because S1/S2 are consts
    B2 := Byte(S2[i]);             // doing it here accelerates first-char-mismatch
    if B1 = B2 then inc(i)         // and  different case matches
    else begin
      if B1 in [97..122] then dec(B1, 32);
      if B2 in [97..122] then dec(B2, 32);
      if B1 = B2 then inc(i)       // sensitivity match
      else begin
        result := B1 - B2;         // mismatch inside of the strings, "real" result now
        goto L2;                   // Label is faster than Break
      end;
    end;
  end;
  result := Length(S1) - Length(S2);   // only reached if all matched and i > len
  L2:
end;
 

(Edit: Bug beseitigt: Match bei Length=255 hat Endlosschleife verursacht.)

Gruß Rüdiger

[exc-jdbi]

Hallo ruewa

Interessant, Interessant.

Soviel ich weiss, besitzt jener String (Ansistring) von Delphi einen Referenz- und Längenzähler. Das macht den String dynamischer. Ist das nicht auch so in Lazarus.

Der Shortstring wirkt hingegen eher statisch. Ich kann mir gut vorstellen, dass genau darum der Shortstring um einiges "Pflegeleichter" ist, und die entsprechende Verarbeitung und Interpretation während der Laufzeit optimierter verlaufen. Sprich schnellere Laufzeiten.

Wahrscheinlich erreicht man diesen Effekt wenn es unbedingt ein Ansistring sein müsste auch mit der einfachen Angabe der Länge z.B. String[x], was jedoch ziemlich umständlich ist.

Die grössten Leistungseinbussen an Geschwindigkeit entsehen doch bei der Kopie eines Strings, da der Referenzzähler (also neuer Speicher etc.) komplett neu erstellt werden muss. Nicht jedoch bei einem Shortstring. Beim Shortstring wird einfach eine entsprechende aber "vorgegebene Grösse" an Speicher neu vergeben.

Stimmen meine Vermutungen?

Freundliche Grüsse

exc-jdbi

[ruewa]

Hallo exc-jdbi,

... besitzt jener String (Ansistring) von Delphi einen Referenz- und Längenzähler. Das macht den String dynamischer. Ist das nicht auch so in Lazarus.

Der Shortstring wirkt hingegen eher statisch. Ich kann mir gut vorstellen, dass genau darum der Shortstring um einiges "Pflegeleichter" ist, und die entsprechende Verarbeitung und Interpretation während der Laufzeit optimierter verlaufen. Sprich schnellere Laufzeiten.

Das ist in Free Pascal nicht anders. Der ShortString ist sozusagen ein Relikt aus der guten alten Turbo-Pascal-Zeit. Der hat auch einen Längenzähler, allerdings nur von 1 Byte Größe auf String[0], d.h., er kann maximal 255 Byte lang sein. Das war auch solange keine wirklich spürbare Einschränkung, solange man davon ausgehen konnte, daß ein Zeichen ein Zeichen und damit genau ein "Char" groß ist (zu Zeiten von ASCII und Codepages). "Z'erscht schlägt es siebene, a Stund drauf schlägt es achte, von aaner Stund zur nächstn woaß mer goar nix mehr", sang einst Georg Kreisler - heutzutage kannst Du nicht mehr eindeutig sagen, was ein "Zeichen" denn genau ist, der String kann Zeichen von 1, 2 oder 4 Byte Länge enthalten. Und selbst der Typbezeichner "Char" ist längst zum verwaschenen Begriff geworden. Erst das hat den Bedarf für die (schier) unbegrenzt langen Strings geschaffen.

Ein echtes Laufzeitproblem schaffen die langen Strings aber dennoch nicht. Ob der Deklarationskopf am Anfang des Strings nun 1 Byte oder 8 Bytes lang ist, macht nicht wirklich einen Unterschied - solange Du weißt, womit Du es zu tun hast. Aber genau das ist das Problem geworden.

Die grössten Leistungseinbussen an Geschwindigkeit entsehen doch bei der Kopie eines Strings, da der Referenzzähler (also neuer Speicher etc.) komplett neu erstellt werden muss. Nicht jedoch bei einem Shortstring. Beim Shortstring wird einfach eine entsprechende aber "vorgegebene Grösse" an Speicher neu vergeben.

Mit dem Referenzzähler hat das nichts zu tun, der wird ggfls. an Ort und Stelle einfach um eins erhöht und besagt lediglich "irgendjemand will grad was von mir". Ich weiß gar nicht, ob das innerhalb von Free Pascal irgendeine Bedeutung hat, da geht es wohl v.a. um Interoperabilität (Java z.B baut seinen Garbage Collector darauf auf - respektlos gesagt, sowas braucht man halt, wenn man den Überblick verloren hat...). Und auch der Shortstring ist "dynamisch" - dort ist eben alles nur eine Nummer kleiner.

Nein, das Problem sehe ich v.a. im Allerweltstyp "String", dem sozusagen die Rolle des Free-Pascal-Gemeindepfarrers zufällt, der für alle da sein soll, eine einfache Weltsicht vermittelt und sich insbesondere penetrant für diejenigen zuständig fühlt, die partout nichts von ihm wissen wollen... Vielleicht sollte man sich angewöhnen, den Mediatoren-Typ String ganz und gar aus seinen eigenen Programmen zu verbannen - nur nützt das nicht viel, weil die ganzen Bibliotheken ausgiebigen Gebrauch davon machen. Er ist ja auch solange superbequem, solange man nur Kinkerlitzchen damit anstellt, einer Form eine Überschrift zuweist etc. Der Compiler behandelt den "String" gewissermaßen als Oberbegriff: Der eine bekommt ihn dampfend frisch auf den Tisch, der andere als Tiefkühlpäckchen frei Haus, der dritte kriegt die Kinderportion... Auf dem Weg dorthin werden dann eben fleißig Kopien erstellt und Typumwandlungen vorgenommen - das kostet dann richtig Zeit, und zwar immer dort, wo man es am wenigsten gebrauchen kann, bei aufwendigen Operationen wie dem Sortieren etwa.

Die wichtigste Erkenntnis für mich ist dabei: Mit dem Compilerbefehl {$H-} ist nicht viel gewonnen, und wo "const" drauf steht, muß keineswegs auch wirklich "const" drin sein. Und solange irgendwo im Unterholz der Pfarrer rumlungert, ist man angeschmiert...

Gruß Rüdiger

[mse]

Kannst du den kompletten Code inklusive Testdaten und Sortierroutine posten? So schlecht sollte AnsiString nicht abschneiden.

[ruewa]

Kannst du den kompletten Code inklusive Testdaten und Sortierroutine posten?

Das Testprogramm liegt bei inclusive DbgTimer & EpikTimer (darauf basiert die Messung). Mein Hauptprojekt ist noch zusehr Baustelle, als daß ich es veröffentlicht sehen möchte. Das ist aber auch nicht unbedingt nötig, der Effekt ist auch im Testprogramm sichtbar. Ansonsten nimm einfach eine TFPHashList, füttere sie mit ein paar tausend Shortstrings aus einer Textdatei, dann kannst Du die Sortierung von außen mit FPHashListSort.QuickSortHashList durchführen (ich habe das Zeug inzwischen auch in eine abgeleitete TFPHashList-Klasse integriert, das ist aber noch nicht vollständig).

So schlecht sollte AnsiString nicht abschneiden.

Nein, tut er ja auch nicht! Das Problem ist nicht der AnsiString an sich, sondern das überbordende Ausmaß der Typkonversion während der Laufzeit. Um das nochmal ganz klar zu sagen: Ich habe nicht "bessere" Funktionen geschrieben als SysUtils.CompareStr/-Text, sondern besser geeignete! Also auf Shortstrings spezialisierte, zulasten der Flexibilität: Wenn ich meine Routinen probehalber auf "Strings" umstelle und {$H+} einschalte, werden die genauso langsam (bzw. sogar noch langsamer) als die entsprechenden SysUtils-Routinen.

Der Ausgangspunkt ist eben, daß die TFPHashList aus Gründen der Performance auf ShortStrings limitiert ist (damit kann ich gut leben, exc-jdbi weniger gut). Um die schnell sortieren zu können, muß sichergestellt sein, daß die ShortStrings nicht bei jeder Vergleichsoperation auf's neue in AnsiStrings umkopiert werden müssen, sondern einfach so, wie sie sind, durchgereicht werden. Das ist mit den String-basierten SysUtils-Routinen nicht möglich, während meine gerade darauf abzielen. Ich schätze mal, 85 % des Geschwindigkeitsunterschieds kommt schlicht durch die unterschiedliche Deklaration zustande, nur 15 % durch Feintuning. Und weshalb meine Funktionen im Umgang mit AnsiStrings langsamer sind, liegt offensichtlich daran, daß der für Shortstrings am besten geeignete indizierte Zugriff auf die einzelnen Speicherstellen bei AnsiStrings weniger effizient arbeitet, die wiederum mit inkrementierten Zeigern schneller zurechtkommen.

An einigen Stellen habe ich mich in meinem vorigen Posting übrigens geirrt: SysUtils ist (anders als alle anderen RTL-Units) doch mit {$H+} kompiliert (das ist etwas schwer zu erkennen, weil sowohl die Deklaration als auch die Implementierung der Routinen in verschachtelte Include-Dateien ausgelagert ist). Und CompareStr/-Text arbeiten doch auf der Grundlage von AnsiStrings (ich hatte die Programmzeile P1 := @S1[1]; als Indiz interpretiert, daß sie intern mit Shortstrings arbeiten; tatsächlich aber ist diese Indizierung auf AnsiStrings bezogen zwar ebenso gültig, aber ein reines Kunstprodukt und hat nichts mit dem tatsächlichen Speicherabbild zu tun, welches dieselbe Anweisung bei ShortStrings ja so gut begreifbar macht...).

Und weiter: {$H-} würde schon funktionieren, wenn... Bzw. die Dokumentation des $H-Schalters, die da behauptet "By default, the use of ansistrings is off, corresponding to {$H-}", würde schon stimmen, wenn... Wenn es da nicht ein ganz verstecktes Häkchen unter Projekteinstellungen/Compilereinstellungen/Parsen/AnsiStrings_verwenden gäbe, das "by default" auf ON gestellt ist... Das muß man erstmal finden!

Gruß Rüdiger

[mse]

Ich habe zum Vergleich die MSEgui Array-Sortierungsfunktion herangezogen, welche mit mergesort und AnsiString arbeitet. Ein zweiter Test verwendet pchar auf die für den fp-sort verwendeten shortstring um die gleichen Verhältnisse für die Speicherfragmentierung zu haben. Es wurden jeweils zwei Läufe gestartet, der Zweite mit den bereites sortierten Daten. Die Ergebnisse:

Code: Alles auswählen

 
           MSEgui first MSEgui second MSEgui first MSEgui second fp first    fp second
           ansistring   ansistring    pchar        pchar         shortstring shortstring
Mode: sms_upiascii Runs: 10
N:       5 0.000008s    0.000003s     0.000003s    0.000003s     0.000005s   0.000003s
N:      50 0.000023s    0.000011s     0.000023s    0.000011s     0.000042s   0.000040s
N:     500 0.000270s    0.000109s     0.000262s    0.000116s     0.000586s   0.000336s
N:    5000 0.004756s    0.002102s     0.004571s    0.002119s     0.008154s   0.004980s
N:   50000 0.090484s    0.055410s     0.055909s    0.051191s     0.061625s   0.048359s
N:  500000 1.009370s    1.399610s     0.785799s    0.670823s     0.923275s   0.762513s
Mode: sms_upiascii Runs: 5
N: 1000000 2.319368s    3.096984s     1.809602s    2.053424s     3.016536s   2.501383s
Mode: sms_upiascii Runs: 2
N: 5000000 15.954516s  18.836129s    12.667220s  13.815845s     22.516577s  18.154619s
 

Dies bestätigt deine Aussage, dass auch mit AnsiString gute Performance erreicht werden kann.
Das Projekt ist hier
https://gitorious.org/mseuniverse/mseun ... rk/sorting
und benötigt MSEide+MSEgui git master.
@exc-jdbi: in der erwähnten hashlist Implementation gibt es auch Versionen für AnsiString.

[exc-jdbi]

Danke euch beiden

Mit verlaub werde ich mir morgen die Codes anschauen.

Freundliche Grüsse

exc-jdbi

[exc-jdbi]

Guten Abend Comunity

Hier mein Testverlauf von meinem eigen erstellten tDictionary<String><String>

Freundliche Grüsse

exc-jdbi

[ruewa]

Ich habe zum Vergleich die MSEgui Array-Sortierungsfunktion herangezogen, welche mit mergesort und AnsiString arbeitet. Ein zweiter Test verwendet pchar auf die für den fp-sort verwendeten shortstring um die gleichen Verhältnisse für die Speicherfragmentierung zu haben. Es wurden jeweils zwei Läufe gestartet, der Zweite mit den bereites sortierten Daten. Die Ergebnisse: ...

Hallo Martin,

(ein verspätetes) Danke für Deine Bemühungen, das gegenzuzuchecken. Deine Meßergebnisse haben mich damals motiviert, das ganze noch einmal von vorne aufzurollen und ein weiteres Testprogramm zu schreiben (das Ergebnis habe ich nun hier veröffentlicht: http://www.lazarusforum.de/viewtopic.php?f=29&t=8233). Ich hatte schon damals vermutet, daß es über die Compare-Funktionen hinaus einen weiteren, sogar heftigeren Flaschenhals geben müsse, und tatsächlich haben sich die damals gemessenen Laufzeitunterschiede von bis zu 1:40 als Artefakt herausgestellt - nur konnte ich ewig die Ursache dafür nicht finden...

Was meine Ergebnisse damals massiv verfälscht hat, war das Unterlegen meiner Testprogramme mit HeapTrc (LeakView): Dies hat den Aufruf von Bibliotheksroutinen (wie SysUtils.CompareStr/-Text) um den Faktor 6-8 verlangsamt, während es die Laufzeit meiner eigenen Compare-Funktionen anscheinend kaum beeinträchtigt hat. Ich habe keine Ahnung und auch keine Idee, warum das so ist, aber das war die Ursache. Einerseits hat mich das zwar ordentlich in die Wüste geschickt, aber das hatte insofern auch sein Gutes, als mich die vermeintlich spektakulären Erfolge mächtig motiviert haben, weiterzubohren...

Inzwischen bin ich mir einigermaßen sicher, daß die jetzigen Ergebnisse (Laufzeitunterschiede der ShortString-Compare-Funktionen gegenüber den SysUtils-Funktionen im Bereich von 1:3 - 1:6) einigermaßen realistisch und frei von Artefakten sind. Nachdem ich ewig um klein-klein-Verbesserungen im Pascal-Quelltext gerungen hatte, kam ich dann an den Punkt, diese Funktionen für i386 und x86_64 in Assembler aufzusetzen. Ich denke, damit ist das Ende der Fahnenstange nun annähernd erreicht.

Eine wesentliche Erkenntnis während der Entwicklung bestand darin, ein realistischeres Bild der Lauflängen-Verteilung innerhalb der Compare-Funktionen zu gewinnen. Nur rund ein Viertel aller Stringvergleiche entscheiden sich beim Sortieren nämlich schon beim ersten Byte - das ist erheblich weniger, als man intuitiv erwarten würde. Das liegt daran, daß die Strings mit zunehmender Rekursionstiefe von Quicksort einander immer ähnlicher werden und daher immer weiter durchlaufen werden müssen, um eine Entscheidung zu fällen.

Nähere Informationen und auch die Quelltexte sind wie schon erwähnt unter http://www.lazarusforum.de/viewtopic.php?f=29&t=8233 zu finden.

Gruß Rüdiger