TSortableHashList und ShortString-Compare-Funktionen

Zur Vorstellung von Komponenten und Units für Lazarus
Antworten
ruewa
Beiträge: 153
Registriert: Sa 12. Apr 2014, 14:43

TSortableHashList und ShortString-Compare-Funktionen

Beitrag von ruewa »

Hallo!

Ausgehend von der Diskussion über TDictionary (http://www.lazarusforum.de/viewtopic.php?p=71940#p71940) habe ich mich mit der Möglichkeit beschäftigt, eine TFPHashList zu sortieren, und die Performance dieses Sortiervorgangs zu optimieren. Das ist jetzt soweit gediehen, daß ich es in guter Zuversicht, daß es nun einigermaßen produktionstauglich sein dürfte, denke veröffentlichen zu können.

Das Projekt besteht aus drei Teilen:

1) Einem Abkömmling von TFPHashList namens TSortableHashList (Unit SortableHashList).

An sich sind Hashlisten aus ihrer inneren Funktionsweise heraus nicht sortierbar, und eine eventuelle Sortierung würde auch keinen Sinn machen in Bezug auf Zugriffsgeschwindigkeit. Wohl aber benötigt man eine sortierte Reihenfolge oftmals an der Schnittstelle zum Benutzer, z.B. wenn der Inhalt der Hashliste etwa in einer TListBox auf den Bildschirm gebracht werden soll. TSortableHashList greift deshalb nicht in die interne Funktionsweise der Hashliste ein (tatsächlich bleiben deren Daten völlig unangetastet), sondern bedient sich eines einfachen Tricks: Die Hashliste erhält ein zusätzliches Array of PShortString (Property SortArray), das Zeiger auf alle Keys der Hashliste enthält. Nach Durchführen des Sortiervorgangs sind diese Zeiger in sortierter Reihenfolge abgelegt und können seriell ausgelesen werden. Das Sortieren selbst erfolgt wahlweise Case-Sensitiv (unter Berücksichtigung der Groß-/Kleinschreibung) oder Case-Insensitiv. Darüberhinaus enthält TSortableHashList auch eine Prozedur "SortToStrings", die die Ergebnisse des Sortiervorgangs direkt in eine Stringliste schreibt.

Entsprechend der Abstammung von der TFPHashList sind zwei Einschränkungen zu beachten: Erstens müssen die Keys ShortStrings sein - wer auf AnsiStrings (oder WideStrings etc.) angewiesen ist, muß auf Abkömmlinge der TCustomHashTable zurückgreifen. Und zweitens gibt es, anders als etwa bei einer TStringList, keinen Automatismus, der das SortArray auf aktuellem Stand hält, wenn sich der Inhalt der Hashliste ändert. In dem Fall muß der Sort-Vorgang von neuem durchgeführt werden.

Und, naja, man sollte natürlich auch wissen, was eine Hashliste eigentlich ist und warum man sie z.B. mit der Anweisung SortArray[25] := 'Ach ist das schön!' ratzfatz zerschießen kann...

2) Zwei ShortString-spezialisierte Compare-Funktionen CompareShortStringSensitive und CompareShortStringInsensitive (Unit SortableHashList).

Diese beiden Funktionen bilden das ShortString-Gegenstück zu den SysUtils-Funktionen CompareStr und CompareText. Das Problem der SysUtils-Routinen besteht darin, daß sie normale Strings als Parameter entgegen nehmen, und das heißt im Normalfall AnsiStrings. Die auf große Geschwindigkeit hin optimierte TFPHashList arbeitet hingegen mit den guten alten (Turbo-Pascal-) ShortStrings. Beim Sortieren einigermaßen umfangreicher Datensätze werden diese Compare-Funktionen größenordnungsmäßig 20-30 mal pro Datensatz aufgerufen, und wenn dann jedesmal beide zu vergleichenden ShortStrings erstmal in AnsiStrings umkopiert werden müssen, kostet das eine Unmenge Zeit. Ich habe die ShortString-Compare-Funktionen ausgiebig getestet und deren Performance während der Entwicklung ständig vermessen: Diese Routinen sind nunmehr um einen Faktor 3 - 6 schneller als ihre SysUtils-Kollegen (natürlich beschränkt auf ShortStrings).

Die Routinen existieren in dreifacher Ausführung: Für i386- und x86-64-Prozessoren habe ich sie jeweils in Assembler geschrieben. Einen Vorbehalt muß ich machen: Während ich mir ziemlich sicher bin, daß die x86-64-Version unter allen Umständen klaglos funktioniert, bin ich mir bei der i-386-Version nicht ganz sicher, ob die gewählte flache 32-Bit-Speicheraddressierung (d.h. das Ignorieren der DS-/ES-Register) unter allen denkbaren Umständen zulässig ist. Selbstverständlich habe ich sie auch mit einem i386-Rechner getestet und sie funktionieren dort fehlerfrei, aber natürlich konnte ich nicht alle denkbaren Rechner-Konfigurationen erfassen. Vielleicht kann jemand, der in i-386-Assemblerprogrammierung und FPC-Speichermodellierung erfahren ist, das mal gegenchecken?

3) Das Testprogramm, mit dessen Hilfe ich die Unit SortableHashList entwickelt habe.

Eine interessante Erkenntnis bei der Entwicklung war, daß die Verteilung der Lauflängen beim Vergleich zweier Strings beim Sortieren doch deutlich anders ausfällt, als man sich das von vorne herein vorstellt. Nur rund 25 % aller Compare-Aufrufe werden schon im ersten Byte entschieden, während das bei normalverteilten Daten bei weit über 90 % der Vergleiche der Fall ist. Das liegt daran, daß die zu vergleichenden Strings mit zunehmender Rekursionstiefe sich immer ähnlicher werden, jedenfalls bei Divide-and-Conquer-Algorithmen wie Quicksort. Man kann Compare-Methoden also gut und gern auf ein falsches Ziel hin optimieren! Was bei normalverteilten Daten superschnell ist, kann beim Sortieren ziemlich im Weg sein. Ich habe diese Compare-Funktionen, nachdem ich das erstmal begriffen hatte, v.a. auf das Sortieren (sprich auf größere Lauflängen) hin optimiert.

Bei meinen Tests habe ich alle Pascal-Dateien, derer ich habhaft werden konnte (das ganze Lazarus-Verzeichnis), eingelesen und deren Zeilen in die Hashliste gepackt. Dadurch kamen Datensätze mit mehr als 1.000.000 Strings zustande. Das Ergebnis sieht so aus:

SortTest.jpeg


Die Buttons rechts führen jeweils Sortiervorgänge mit unterschiedlichen Compare-Funktionen durch. Ich denke, das ist soweit selbsterklärend.

Der Button Debugging führt sowohl eine case-sensitive als auch eine insensitive Sortierung durch und vergleicht jeweils das Ergebnis meiner Compare-Funktion mit dem Ergebnis der SysUtils-Routinen. Jede Differenz wird als Fehler gewertet und die Programmausführung in eine Schleife geschickt, wo ich dann während der Entwicklung entsprechende Haltepunkte gesetzt habe (selbstverständlich ist jetzt bei Veröffentlichung kein offenkundiger Fehler mehr vorhanden).

Der Button Perfomance führt - anders als beim Sortieren - zufallsverteilte Vergleiche durch. Hier sind also die durchnittlichen Lauflängen erheblich kürzer als im interessanteren Fall der Sortierung. Außerdem habe ich versucht, die Laufzeiten innerhalb der Compare-Funktion zu isolieren, indem ich zuvor einen Testlauf mit einer leeren Dummy-Funktion durchführe, und diesen konstanten (Verwaltungs-) Zeitanteil (Aufrufschleife, Parameterübergabe, Sprung, Rücksprung) vom Meßergebnis abziehe.

Die Buttons SortToStrings und ShowList machen im Grunde dasselbe, nämlich die (sortierten) Daten in die ListBox zu schreiben, mit dem Unterschied, daß ersteres explizit die TSortableHashList.SortToStings-Methode verwendet. Aber Vorsicht: Bei einer Million Zeilen dauert das ordentlich lange, dafür sind Listboxen eigentlich nicht gedacht (wobei ein TMemo nochmal um Dimensionen langsamer ist)...

Die Meßergebnisse werden in einem Logfile mitprotokolliert, mit ShowLog läßt sich diese Logdatei einsehen und resetten.

Ich bitte um Verständnis, daß mein Testprogramm nicht so ausgefeilt ist wie die Unit SortableHashList, das ist einfach als Werkzeug nebenher on the run entstanden und natürlich etliche Male aufgebohrt worden, wie das halt so ist. Aber zu Testzwecken erfüllt es seine Aufgabe denke ich hinreichend.

Mir selbst steht kein Windows-Rechner zur Verfügung (sowas kommt hier nicht ins Haus!), ich konnte das Programm bzw. die Unit also nur unter Linux testen. Insofern wäre es interessant, wenn der eine oder andere es mal unter Windows (oder Mac) laufen lassen könnte und entsprechende Rückmeldung gäbe.

Gruß Rüdiger
Dateianhänge
SortTest.zip
Version 0.4.2 mit DbgTimer 0.9.0-4
(98.64 KiB) 109-mal heruntergeladen
Zuletzt geändert von ruewa am Mo 10. Nov 2014, 00:34, insgesamt 2-mal geändert.

Michl
Beiträge: 2505
Registriert: Di 19. Jun 2012, 12:54

Re: TSortableHashList und ShortString-Compare-Funktionen

Beitrag von Michl »

Hallo Rüdiger,

kurzes Feedback für Windows:

Ich habe eben das Prog runtergeladen und gestartet, bis auf, dass die überladene "function DebugTimerStop(NumCycles: integer=0): Extended; overload;" als nicht mit der Deklaration überseinstimmend bemängelt wurde (habe aus beiden eine gemacht, da die Überladung sowieso nur den vordefinierten Wert aufruft), sieht das Ergebnis ähnlich Deiner Grafik aus (Win64 bit, Lazarus 1.3-Trunc 32bit).

Habe mich aber bisher nicht mit Hash-Listen beschäftigt und auch das Ergebnis nicht näher untersucht. Aber möglicherweise brauche ich sie ja mal in der Zukunft, so hätte ich dann ja jemanden, den ich mit meinen Fragen belästigen könnte :mrgreen:

Viele Grüße

Michael

Code: Alles auswählen

type
  TLiveSelection = (lsMoney, lsChilds, lsTime);
  TLive = Array[0..1] of TLiveSelection; 

ruewa
Beiträge: 153
Registriert: Sa 12. Apr 2014, 14:43

Re: TSortableHashList und ShortString-Compare-Funktionen

Beitrag von ruewa »

Hallo Michael,

danke für die Rückmeldung!

Michl hat geschrieben:... bis auf, dass die überladene "function DebugTimerStop(NumCycles: integer=0): Extended; overload;" als nicht mit der Deklaration überseinstimmend bemängelt wurde (habe aus beiden eine gemacht, da die Überladung sowieso nur den vordefinierten Wert aufruft)...


Hoppala! Danke für den Hinweis! Das "=0" muß weg, ansonsten sind die beiden überladenen Funktionen schon richtig so. Ich hatte zuerst versucht, ob es ohne Überladung geht (mit default 0), dabei aber festgestellt, daß der default-Mechanismus (bei mir jedenfalls) nur bei einem von mehreren Parametern funktioniert, nicht aber, wenn es der einzige Parameter ist. Das habe ich dann anscheinend nicht sauber entfernt - mein Compiler hat das (hab's gerade nochmal überprüft) nicht angemeckert. Kann sein, daß da eine Inkonsistenz zwischen den Linux- und Windows-Compilern besteht. Ich habe das jetzt im Zip-File ausgetauscht, ansonsten einfach das "=0" (Zeile 189 in DbgTimer.pas) löschen, dann paßt's.

Michl hat geschrieben:Habe mich aber bisher nicht mit Hash-Listen beschäftigt und auch das Ergebnis nicht näher untersucht. Aber möglicherweise brauche ich sie ja mal in der Zukunft, so hätte ich dann ja jemanden, den ich mit meinen Fragen belästigen könnte :mrgreen:


Gerne doch! Als ich anfing, mich mit Hashlisten zu beschäftigen, ist mein geistiger Knoten an der Stelle geplatzt, wo mir klar wurde, daß Hashlisten viel mit Stringlisten gemeinsam haben. Ich hatte das, damals noch fragend und unsicher, hier zur Diskussion gestellt: http://www.lazarusforum.de/viewtopic.php?p=71575#p71575. Heute würde ich sagen, daß das ein ganz guter Ansatz ist, sich Hashlisten gedanklich zu nähern. Nur an einer Stelle hatte ich mich geirrt: Die TFPHashList akzeptiert Duplikate, und wenn man die vermeiden möchte, stößt man auf einen (leicht zu umgehenden, wenn man's weiß) Bug: http://bugs.freepascal.org/view.php?id=26800. Und betont werden müßte noch, daß die TFPHashList nur ShortStrings (als Keys) gebrauchen kann.

Gruß Rüdiger

tazy
Beiträge: 1
Registriert: Mo 10. Nov 2014, 11:57

Re: TSortableHashList und ShortString-Compare-Funktionen

Beitrag von tazy »

Habe mich aber bisher nicht mit Hash-Listen beschäftigt und auch das Ergebnis nicht näher untersucht. Aber möglicherweise brauche ich sie ja mal in der Zukunft, so hätte ich dann ja jemanden, den ich mit meinen Fragen belästigen könnte...!!!
tZy

Michl
Beiträge: 2505
Registriert: Di 19. Jun 2012, 12:54

Re: TSortableHashList und ShortString-Compare-Funktionen

Beitrag von Michl »

ruewa hat geschrieben:Ich hatte zuerst versucht, ob es ohne Überladung geht (mit default 0), dabei aber festgestellt, daß der default-Mechanismus (bei mir jedenfalls) nur bei einem von mehreren Parametern funktioniert

Unter welchem System? Bei mir funktioniert statt

Code: Alles auswählen

function  DebugTimerStop: Extended; overload;
function  DebugTimerStop(NumCycles: integer): Extended; overload;   
genauso

Code: Alles auswählen

function  DebugTimerStop(NumCycles: integer = 0): Extended;
Win7 64bit, Lazarus 32bit Trunc, FPC 2.7.1 Trunc

In beiden Fällen sind die Aufrufe

Code: Alles auswählen

  Result := DebugTimerStop(1000);
  Result := DebugTimerStop(0);
  Result := DebugTimerStop;   
möglich.

Code: Alles auswählen

type
  TLiveSelection = (lsMoney, lsChilds, lsTime);
  TLive = Array[0..1] of TLiveSelection; 

ruewa
Beiträge: 153
Registriert: Sa 12. Apr 2014, 14:43

Re: TSortableHashList und ShortString-Compare-Funktionen

Beitrag von ruewa »

Michl hat geschrieben:Bei mir funktioniert statt

Code: Alles auswählen

function  DebugTimerStop: Extended; overload;
function  DebugTimerStop(NumCycles: integer): Extended; overload;   
genauso

Code: Alles auswählen

function  DebugTimerStop(NumCycles: integer = 0): Extended;
Win7 64bit, Lazarus 32bit Trunc, FPC 2.7.1 Trunc

In beiden Fällen sind die Aufrufe

Code: Alles auswählen

  Result := DebugTimerStop(1000);
  Result := DebugTimerStop(0);
  Result := DebugTimerStop;   
möglich.


Stimmt, Du hast recht! Jetzt funktioniert das bei mir auch. Aaaber...

... beim Versuch, zu rekonstruieren, warum ich damals (das ist jetzt schon ein paar Monate her, und ich glaube, es auch mit einer früheren Lazarus-Version geschrieben zu haben) meinte, das würde so nicht funktionieren, bin ich auf diesen Bugreport gestoßen: http://bugs.freepascal.org/view.php?id=24485 Der letzte Eintrag von Marco van de Voort erklärt, was da offenbar passiert ist: Sobald Du nämlich der Unit ein {$mode fpc} verpaßt, meckert der Compiler das Default-Konstrukt an und sagt

Code: Alles auswählen

dbgtimer.pas(141,64) Fatal: Syntax error, ")" expected but "=" found

Sowas muß da passiert sein. Ich kriege es jetzt nicht mehr zusammen, warum ich das damals nicht im objfpc-Mode laufen hatte, meine mich aber zu erinnern, im Zusammenhang mit ShortString-Sortier-Performance auch mit unterschiedlichen Modi experimentiert zu haben. Ich hatte mich damals auch nicht lange damit aufgehalten und dann stattdessen gleich die Overload-Variante geschrieben. Die andere Sache ist, daß bei mir der Compiler diesen "=0"-Müll nicht angemeckert hat, weiß der Himmel, warum.

Okay, wieder was gelernt, danke! Ich lasse es jetzt erstmal bei der Overload-Variante, die funktioniert jedenfalls auch im fpc-Mode. Ich vermute ohnehin, daß der Compiler beide Synthax-Varianten intern gleich behandelt. Und denk nochmal drüber nach, ob es besser wäre, die Unit explizit als objfpc-Mode zu definieren... Gibt es gute Argumente, eine der beiden Varianten zu bevorzugen?

Gruß Rüdiger

mschnell
Beiträge: 3444
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

Re: TSortableHashList und ShortString-Compare-Funktionen

Beitrag von mschnell »

ruewa hat geschrieben:anders als etwa bei einer TStringList, keinen Automatismus, der das SortArray auf aktuellem Stand hält, wenn sich der Inhalt der Hashliste ändert. In dem Fall muß der Sort-Vorgang von neuem durchgeführt werden.


Wenn man nach dem Einfügen eines Elementes in die Liste die komplette Sortierung durchführen müsste, wäre doch ziemlich ineffektiv. Da würde doch nach dem Hashen ein Insert in die sortierte Liste reichen, weil bei Einfügen (anders als beim Austauschen (löschen und dann einfügen) eines Elementes) im Hash die anderen Elemente ja an ihrem Platz bleiben.

-Michael

ruewa
Beiträge: 153
Registriert: Sa 12. Apr 2014, 14:43

Re: TSortableHashList und ShortString-Compare-Funktionen

Beitrag von ruewa »

mschnell hat geschrieben:Wenn man nach dem Einfügen eines Elementes in die Liste die komplette Sortierung durchführen müsste, wäre doch ziemlich ineffektiv. Da würde doch nach dem Hashen ein Insert in die sortierte Liste reichen, weil bei Einfügen (anders als beim Austauschen (löschen und dann einfügen) eines Elementes) im Hash die anderen Elemente ja an ihrem Platz bleiben.


Hallo Michael,

machen könnte man das natürlich schon, und ich hatte anfangs auch darüber nachgedacht, es dann aber verworfen. Um das SortArray effizient auf Stand zu halten, müßte man es statt als Array als verkettete Liste aufsetzen, der Rest wäre Folklore. Meine Überlegung war dann aber, daß man mit dieser Einschränkung insofern gut leben kann, als die Sortierung einer Hashliste ohnehin nur dann interessant ist, wenn der Inhalt in einer GUI-Komponente angezeigt werden muß. Bei großen Datenmengen wird man das so gut es geht vermeiden wollen (das Laden von 1 Mio. Strings in die Listbox dauert länger als eine volle Minute, dafür sind die Dinger einfach nicht gemacht). Bei kleineren, komponentengerechten, Datenmengen ist das Sortieren dann saumäßig schnell, und ggfls. kann man die Stringliste der Anzeigekomponente dann auch sortiert halten und die Keys, die man der Hashliste übergibt, direkt in die Stringliste einfügen.

Ich weiß einfach nicht, ob es einen realen Bedarf für eine ständig aktualisierte Hashlisten-Sortierung gibt. Der Grund, weshalb ich sie entwickelt habe, war, um im Rahmen einer Suchfunktion den Sonderfall der leeren Suche (mit der Anzeige aller Daten) aus Konsistenzgründen mit vertretbarem Zeitaufwand (schneller als die Tippgeschwindigkeit des Benutzers) hinzukriegen. Bei jedem Buchstaben, den der Benutzer in die Suchmaske eintippt, muß dann die Ergebnisliste ohnehin wieder komplett neu generiert werden (deshalb brauche ich ja eine hoch performante Hashliste anstelle einer lahmen Stringliste). D.h. für diesen Anwendungsfall fange ich mit einer stets aktualisierten Sortierung gar nichts an.

Sicher sind auch andere Anwendungsfälle denkbar, und ich will auch gar nicht ausschließen, daß das ein weiterer Entwicklungsschritt sein könnte. Es wäre halt ein beträchtlicher Mehraufwand, denn dann müßte man die Hälfte aller Hashlisten-Methoden (wie Add, Rename etc.) entsprechend anpassen, so ist's nur ein überschaubares Anhängsel. Wenn es in Zukunft ein entsprechendes Feedback gibt, bin ich gerne bereit, das in Angriff zu nehmen, im Moment sehe ich die Notwendigkeit noch nicht.

Gruß Rüdiger

Antworten