AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Vorteil von auf Primzahlen skalierten Hashmaps?

Ein Thema von Namenloser · begonnen am 9. Jul 2010 · letzter Beitrag vom 17. Jul 2010
Antwort Antwort
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
44.556 Beiträge
 
Delphi 12 Athens
 
#1

AW: Vorteil von auf Primzahlen skalierten Hashmaps?

  Alt 17. Jul 2010, 23:25
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

MSDN-Library durchsuchenSysAllocStringLen
MSDN-Library durchsuchenSysReAllocStringLen
MSDN-Library durchsuchenSysFreeString
MSDN-Library durchsuchenSysStringLen


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;
Ein Therapeut entspricht 1024 Gigapeut.

Geändert von himitsu (17. Jul 2010 um 23:34 Uhr)
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#2

AW: Vorteil von auf Primzahlen skalierten Hashmaps?

  Alt 17. Jul 2010, 23:42
Hallo 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]
Angehängte Dateien
Dateityp: zip Hashmap.zip (1,45 MB, 13x aufgerufen)

Geändert von Namenloser (18. Jul 2010 um 08:03 Uhr)
  Mit Zitat antworten Zitat
Antwort Antwort


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 09:43 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz