Eine kleine Hashtabelle (jetzt ohne Speicherlecks!)

[bluejoke]

ich bin Schwabe - und ich schließe mich an

[Ingo Platte]

Hallo, ich pflege die HT gerade in meiner Datenbank (sqlite) ein.
Dabei ist mir aufgefallen das ein simples GetS() den Speicher vollknallt.

Code: Alles auswählen

XIncludeFile "Hashtabelle.pbi"

Global *HT.HT

*HT = HT_Create()
If *HT = 0 : End : EndIf
*HT\SetMaxTreeSize(5)
*HT\SetVariant(#HT_CRC32)

For zzz= 0 To 10000000
*HT\GetS("dsfsdfsdf")
Next

ein Bug???

gruß Ingo

[NicTheQuick]

Hehe, das ist interessant.
Ich hab nur gerade gemerkt, dass mein Link zur Hashtable nicht mehr geht.
Dann kann ich sie mir wohl auch gerade nicht herunterladen. Wenn ich
morgen zu Hause bin, kann ich ja mal schauen. Aber hier auf dem Laptop
hab ich die Include nicht.

Ich kann mir aber auch schon vorstellen, mit was es zusammenhängt.

[Ingo Platte]

Dann kann ich sie mir wohl auch gerade nicht herunterladen

Ich habe die Include von hier: http://freakshow.gpfclan.de

Noch was, weil das leider nicht dokumentiert ist.

Was hat es mit der Funktion "*HT\SetMaxTreeSize(5)" aufsich?
Ich habe es laut deinem Beispiel auf 5 gelassen. Was wäre wenn ich diesen
Wert auf 10 oder auf 3 setzte. Ist das besser/schlechter od. langsamer/schneller? Wonach richtet sich die Baumhöhe ?

[NicTheQuick]

Hab eben auch gemerkt, dass ich Include noch auf meiner
Freakshow-Seite hab. Hab das Speicherleck auch schon gefunden.

Du kannst dir die Include auch wieder hier herunterladen.

Hier das Testprogramm für Speicherlecks. Falls du noch weitere findest,
sollte dir der folgende Code helfen:

Code: Alles auswählen

Global MemAlloc.l
Procedure AM(Size.l)
  Protected *mem
  *mem = AllocateMemory(size + 4)
  If *mem
    PokeL(*mem, size)
    MemAlloc + Size
    ProcedureReturn *mem + 4
  EndIf
  ProcedureReturn 0
EndProcedure
Procedure FM(*mem)
  
  MemAlloc - PeekL(*mem - 4)
  ProcedureReturn FreeMemory(*mem - 4)
EndProcedure

Macro AllocateMemory(Size)
  AM(Size)
EndMacro
Macro FreeMemory(mem)
  FM(mem)
EndMacro

XIncludeFile "HT.pbi"

Global *HT.HT

Debug MemAlloc

*HT = HT_Create()
If *HT = 0 : End : EndIf
*HT\SetMaxTreeSize(5)
*HT\SetVariant(#HT_CRC32)

Debug MemAlloc

For zzz= 0 To 100000
  *HT\GetL(123)
Next

Debug MemAlloc

*HT\Free()

Debug MemAlloc

Hier wird 'AllocateMemory()' und 'FreeMemory()' durch eigene Procedures
ersetzt und mitzuloggen, wieviel Speicher allokiert und wieder freigegeben
wird. Die globale Variable 'MemAlloc' enthält dann immer die aktuell
allokierten Bytes.

Die Baumhöhe gibt einfach nur an, wie oft sich der Baum verzweigen soll.
Dabei kommt es auf die Bytes an. Bei CRC32 nützt eine Baumhöhe größer
als 4 nichts, da CRC32 sowieso nur 4 Bytes zurückgibt. MD5 gibt allerdings
32 Zeichen (Bytes) zurück und deswegen kann man die Baumhöhe hier
auf maximal 32 setzen.
Im Endeffekt kommt es auf die Menge der Einträge an, die man in die
Hashtable reinsteckt. Je mehr Einträge, desto höher sollte die Baumhöhe
sein.

Die sinnvolle Baumhöhe würde ich so bestimmen:
Für CRC32
Für weniger als 65536 Einträge: Baumhöhe = 2.
Für weniger als 16777216 Enträge: Baumhöhe = 3 bis 4.
Alles darüber: Baumhöhe = 4.
Für MD5
Für weniger als 66536 Einträge: Baumhöhe = 4.
Für weniger als 16777216 Einträge: Baumhöhe = 7.
Für alles darüber: Baumhöhe = 10.
Für eigene Checksummen
Kommt auf die Anzahl der zurückgelieferten Bytes und deren
Werteverteilung an.

[Ingo Platte]

Danke, ging ja wirklich schnell.

Ich brauche diese HT um neue Einträge mit bereits vorhanden Einträge zu vergleichen. Vorher habe ich die vorhandende Einträge in einem Array
Binär durchsuchen lassen (das ging auch blitzschnell), aber die neuen Einträge gingen dann in eine LinkedList, die ich leider nur linaer vergleichen konnte. Da waren leider nicht mehr wie 400 -500 Einträge/sek drin. Jetzt, mit deiner HT komme ich immerhin auf 2000 - 2500 Einträge/sek.
Und das kann sich wirklich sehen lassen

[NicTheQuick]

Das freut mich zu hören!

Du kannst ja mal ein bisschen mit den Hashs und Baumgrößen
herumprobieren. Vielleicht bekommst du noch ein bisschen mehr Speed raus.

[NicTheQuick]

Ich habe gerade meine alte HashTable wieder gefunden. Ich habe sie noch nicht auf eine aktuelle PB-Version angepasst, aber vielleicht kann wieder jemand was damit anfangen. Immerhin unterstützt sie als Key nicht nur Strings.

Hier der neue Link: HT.pbi

[DarkDragon]

Nett, danke . Vielleicht wäre es jedoch sinnvoller ein Initialiserungsmakro zu schreiben, welches die Hashtabelle mit einem dynamischen Datentypen deklariert.

Sowas in der Art:

Code: Alles auswählen

Macro DeclareHashtable(KeyDatatype, ValueDatatype)
  Interface HT#KeyDatatype#To#ValueDatatype
    ...
    Set(*Key.KeyDatatype, *Value.ValueDatatype)
    Get.i(*Key.KeyDatatype)
    ...
  EndInterface
  ...
EndMacro

DeclareHastable(Integer, Double)

Define MyHT.HTIntegerToDouble
Define Key.i = 5
Define Value.d = 3.0
MyHT\Set(@Key, @Value)

Aber da es Makros ja noch nicht so lange gibt und deine HT wahrscheinlich älter ist kann ich verstehen dass es nicht so implementiert wurde .

[NicTheQuick]

Ja, heute würde ich das wahrscheinlich komplett anders machen. Aber wegen irgendeinem Thread bin ich wieder auf meine eigene HashTable gestoßen und habe gesehen, dass die Links alle nicht mehr gehen. Darum jetzt hier das Neu-Posting. Ich habe nur keine Zeit das ganze zu erneuern. Vielleicht ja mal demnächst, wenn ich's nicht wieder vergessen hab.