Vorteil von auf Primzahlen skalierten Hashmaps?

[himitsu]

Was soll denn der Hast so für Spezifikationen?

in meinem himXML steckt ein kleiner mutierter WideString-ELF-Hash (ich glaub das war mal einer ... hatte mir dafür mal eine AnsiHash-Funktion angepaßt, welche ich beim Hagen fand)

siehe (am Ende der himXML.pas)
Class Function TXHelper.CalcHash(Const S: TWideString): LongWord; allerdings hat diese ein paar spezielle Erweiterungen/Anpassungen, aber das läßt sich ja ändern
- einige bestimmte Steuerzeichen (*?\) schalten das Hashen ab
- es kann ein CaseInsensitiver Hash erstellt werden

PS: http://www.delphipraxis.net/137894-e...nicode-ok.html

[Namenloser]

Danke, ich werd's mir mal anschauen.

[idefix2]

Hallo, hab mir Dein Programm angeschaut, es schaut schon recht gut aus.

Die Hashfunktion kannst Du unverändert für Widestrings übernehmen, sie wird dort genausogut funktionieren.

Folgendes würde ich anders machen:

1. Die Suche nach Primzahlen ist beim verwendeten Algorithmus wirklich ganz überflüssig. Es sollte eine zum Wertebereich des Schlüssels teilerfremde Zahl sein. Im Fall des Stringkey ist der Wertebereich 2 hoch n, jede ungerade Zahl ist dazu teilerfremd. Im Fall eines Integerkeys hängt es vom Wertebereich des Integerkeys ab, der sollte besser kein Vielfaches der Feldgrösse sein - nicht umgekehrt. In fast allen Fällen in der Praxis wird das aber egal sein. Die hier eingesetzten Algorithmen gewinnen durch Primzahlen nichts.

2. Ein Rehash würde ich nicht davon abhängig machen, wie gefüllt die Tabelle schon ist, weil das ist eigentlich für die Performance ziemlich egal, sondern dann machen, wenn eine vorgegebene Anzahl von Kollisionen pro Hashentry überschritten wird: z.B: wenn bei irgend einem hashentry die angehängte Feldliste drei oder vier Elemente überschreitet.

[Namenloser]

Zitat von idefix2:

Hallo, hab mir Dein Programm angeschaut, es schaut schon recht gut aus.

Danke, dass du dir den Code angesehen hast und für dein Feedback.

Ich habe die Hashmap inzwischen noch etwas überarbeitet und unter anderem die Widestring-Map implementiert. Leider ist die ca. 4-5 mal so langsam wie die Ansi-Variante Ist es normal, dass Widestrings so viel langsamer sind? Wenn ich den Benchmark durch den SamplingProfiler laufen lasse, erzeugt ntdll.dll 57% der CPU-Last, was denke ich darauf zurückzuführen ist, dass WideStrings von Windows gemanaged werden. Die Exe selbst belegt nur ca 20%, wovon 50% die System.pas-Funktion mit WStrCmp und Co einnehmen.

Hat jemand eine Idee, wie man den Code vielleicht noch optimieren könnte?

Zitat von idefix2:

Folgendes würde ich anders machen:

1. Die Suche nach Primzahlen ist beim verwendeten Algorithmus wirklich ganz überflüssig. Es sollte eine zum Wertebereich des Schlüssels teilerfremde Zahl sein. Im Fall des Stringkey ist der Wertebereich 2 hoch n, jede ungerade Zahl ist dazu teilerfremd. Im Fall eines Integerkeys hängt es vom Wertebereich des Integerkeys ab, der sollte besser kein Vielfaches der Feldgrösse sein - nicht umgekehrt. In fast allen Fällen in der Praxis wird das aber egal sein. Die hier eingesetzten Algorithmen gewinnen durch Primzahlen nichts.

Primzahlen benutze ich in meiner Komponente ja auch nicht, nur die von alzaimar macht das. Meine Hashmap verdoppelt immer ihre Größe ab einer gewissen Schwelle und nutzt diesen Code um den Hash zu verlürzen:

Delphi-Quellcode:

function THashMap.GetShrunkHash(AKey: Pointer): cardinal;
var
  Tmp: Cardinal;
begin
  Tmp := CalculateHash(AKey);
  Result := (Tmp  
              xor (Tmp shr 8)
              xor (Tmp shr 16)
              xor (tmp shr 24))
            and
              FMask;
end;

Zitat von idefix2:

2. Ein Rehash würde ich nicht davon abhängig machen, wie gefüllt die Tabelle schon ist, weil das ist eigentlich für die Performance ziemlich egal, sondern dann machen, wenn eine vorgegebene Anzahl von Kollisionen pro Hashentry überschritten wird: z.B: wenn bei irgend einem hashentry die angehängte Feldliste drei oder vier Elemente überschreitet.

Die Methode habe ich von alzaimars Hashmap übernommen. Prinzipiell würde ich die Größe auch von der Anzahl an Kollisionen abhängig machen, das Problem ist nur, diese zu ermitteln, da die Kollisionen über eine verkettete Liste gehandhabt werden. Man müsste dann bei jeder Änderung die Liste komplett durchlaufen, um zu prüfen, wie viele Einträge dort abgelegt sind.

[himitsu]

Zitat von NamenLozer:

Ist es normal, dass Widestrings so viel langsamer sind?

ja

AnsiString und ab Delphi 2009 auch UnicodeString:
- delphieigener Typ
- Referenzzählung
- "optimierte" Speicherverwaltung über den Delphi-MemoryManager (neuerdings FastMM)

WideString:
- Umleitung auf WinAPI
- keine Referenzzählung
- (unbekannte) Speicherverwaltung über OleAuth32.dll

SysAllocStringLen
SysReAllocStringLen
SysFreeString
SysStringLen


Wozu Cardinal, wenn du am Ende alles quasi auf 1 Byte runterkürzt, bzw. den schönen Hash zerxorst?

würde es maximal so machen:

Delphi-Quellcode:

function THashMap.GetShrunkHash(AKey: Pointer): cardinal;
begin
  Result := CalculateHash(AKey) and FMask;
end;

[Namenloser]

Hallo himitsu,

Zitat von himitsu:

Wozu Cardinal, wenn du am Ende alles quasi auf 1 Byte runterkürzt, bzw. den schönen Hash zerxorst?

würde es maximal so machen:

Delphi-Quellcode:

function THashMap.GetShrunkHash(AKey: Pointer): cardinal;
begin
  Result := CalculateHash(AKey) and FMask;
end;

Das ist ab Post #6 erörtert.

[edit]
Habe mal eben schnell einen Test durchgeführt:
Ohne XOR:

Code:

---------------- Adding 100.000 items:
Namenlozer's hashmap:
Write: 0,218s
Read:  0,094s
Total: 111001
Hashmap size: 131072

---------------- Adding 1.000.000 items:
Namenlozer's hashmap:
Write: 2,511s
Read:  1,155s
Total: 1111001
Hashmap size: 1048576

---------------- Adding 10.000.000 items:
Namenlozer's hashmap:
Write: 30,997s
Read:  23,775s
Total: 11111001
Hashmap size: 8388608

Mit XOR:

Code:

---------------- Adding 100.000 items:
Namenlozer's hashmap:
Write: 0,218s
Read:  0,078s
Total: 111001
Hashmap size: 131072

---------------- Adding 1.000.000 items:
Namenlozer's hashmap:
Write: 2,294s
Read:  1,014s
Total: 1111001
Hashmap size: 1048576

---------------- Adding 10.000.000 items:
Namenlozer's hashmap:
Write: 27,768s
Read:  21,575s
Total: 11111001
Hashmap size: 8388608

Also wie du siehst, scheint das XOR keinen negativen, sondern eher einen positiven Effekt zu haben.
[/edit]
[edit]
Ich habe die Performance jetzt deutlich erhöht, indem ich den WideString stellenweise durch einen selbstimplementierten, etwas frickeligen (die verbuggte Implementierung von Record-Methoden in Turbo Delphi hat ihren Teil dazu beigetragen) Pseudo-Unicode-String ersetzt habe.

Code:

---------------- Adding 100.000 items:
Namenlozer's hashmap:
Write: 0,062s
Read:  0,063s
Total: 111000
Hashmap size: 131072

---------------- Adding 1.000.000 items:
Namenlozer's hashmap:
Write: 0,780s
Read:  0,608s
Total: 1111000
Hashmap size: 1048576

---------------- Adding 10.000.000 items:
Namenlozer's hashmap:
Write: 8,643s
Read:  6,755s
Total: 11111000
Hashmap size: 8388608

Wie man sieht, hat sich die Performance um mehr als das dreifache erhöht!
Zwar ist das ganze immer noch langsamer als die Ansi-Variante, aber ich denke, die Abweichung ist jetzt akzeptabel.
[/edit]