Thread Speicherverbrauch Array-Cache vs Hash-Cache (8 answers)
Opened by Kuerbis at 2022-07-07 09:06

haj
 2022-07-08 00:22
#194405 #194405
User since
2015-01-07
521 Artikel
BenutzerIn

user image
2022-07-07T07:06:25 Kuerbis
Der Array-Cache kann im ungünstigsten Fall 9 MB mehr Speicher verbrauchen als ein Hash-Cache.
Sind es diese 9 MB wert zu überlegen, den Array-Cache durch einen Hash-Cache zu ersetzten?

Ich muss da auch ein bisschen raten. In Kürze: Im "typischen Fall" ist ein Array geringfügig besser, im "ungünstigen Fall" ist ein Array merklich schlechter.

Ausführlicher:

Was war die Welt noch einfach, als alles ASCII war... bei einem Array mit 255 Elementen hätte sich keiner was gedacht. Aber wir haben jetzt Unicode mit Millionen von Zeichen, und entsprechend hoch können auch die Rückgabewerte von ord werden.

Ich rate, dass in Deinen Ausgaben 99% aller Zeichen ASCII sind und weitere 0.99% sich im nicht-ASCII-Bereich der "Base Multilingual Plane" befinden (BMP). In der BMP sind alle europäischen Schriften, aber auch griechische, kyrillische, japanische und chinesische Zeichen drin. Bei einer japanischen Anwendung zum Beispiel gibt es vielleicht ein paar tausend Zeichen, die liegen alle noch in der BMP.

Dein Beispiel [0x10fffd] gehört in den "Rest", noch dazu in die Kategorie "Private Use", ich weiß also gar nicht, wie der aussieht. Sobald ein solches Zeichen (U+1F42A sollte für 16MB Mehrbedarf reichen) auftaucht, allokiert Perl bei einem Array alle Felder mit kleinerem Index.

Dein Array-Cache enthält also, sobald mal ein Emoji verwendet wird, so etwa 100000 von undefinierten Werten. Bei den ersten 128 ist (in Europa) was los, danach wird's dünner und danach extrem dünn.

Des weiteren vermute ich, dass Dein Cache beim Ablauf Deiner Anwendung gefüllt wird, das ist also eher eine interaktive Sache. Ich glaube nicht, dass jemand so lange vor dem Terminal sitzt, bis da eine Million verschiedener Zeichen zusammenkommen. Nicht mal bei Teens, die sich komplett in Emojis austauschen.

Ein Hash ist bei ähnlicher Größe um einiges ineffizienter als ein halbwegs gefülltes Array: Der Key beim Hash ist ein vollwertiger Skalar (ein String) und belegt damit mindestens 18 Byte, während ein Array-Index nirgends explizit gespeichert wird. Auch der Zugriff auf ein Element ist beim Hash um einiges langsamer, weil da jedes Mal einige Vergleiche gemacht werden anstatt nur etwas Pointer-Arithmetik.

Von halbwegs gefüllt bist Du aber um 5-6 Größenordnungen entfernt, sobald auch nur ein Zeichen außerhalb der BMP im Text auftaucht.

Also: Sowas würde ich in einen Hash schreiben. Im typischen Fall (nur ASCII) bist Du damit etwas schlechter bei Speicherverbrauch und Laufzeit als bei einem Array, aber die Werte sind winzig. Im asiatischen Fall bist Du schon sparsamer beim Speicherverbrauch und im Emoji-Fall viel effizienter beim Speicherverbrauch als beim Array. Den Unterschied in der Laufzeit wirst Du kaum messen können und bei einer interaktiven Anwendung ist das langsamste eh der Mensch am Terminal.

Die Beurteilung, ob 9MB viel sind, hängt ja wirklich von der Situation ab. Zu 640kb DOS-Zeiten war das erschreckend viel, heute haben schon die kleinsten Raspberry-Kisten ein GB. Andererseits.... Es gibt Speicherschweine wie Chromium, die schnell mal allen verfügbaren RAM für sich reklamieren. Wenn's dumm läuft, dann müssen für Deine 9MB genauso viele Daten in den Swap geschrieben werden. Wohl dem, der eine SSD hat.

View full thread Speicherverbrauch Array-Cache vs Hash-Cache