Effizienz des Speichermanagers
Hi,
ich arbeite an einer Implementierung von B+-Bäumen (oder sowas ähnlichem zumindest), in-memory. Ich habe da gestern mal mit Benchmarks angefangen, und während die Geschwindigkeit zwar in Ordnung war, ist mir aufgefallen, dass das Programm viel mehr RAM braucht als es eigentlich sollte. Theoretisch sollte es ungefähr 80MB brauchen, tatsächlich waren es hingegen über 230MB. Ein Speicherleck ist es aber nicht, es wird am Ende alles wieder ordentlich freigegeben. Der Verdacht lag auf Heap-Fragmentierung, da jeder Endknoten des Baumes in einer verketteten Liste gespeichert ist. Ich wollte das mal mit der HeapTrc-Unit überprüfen, allerdings gibt die mir pro Sekunde ungefähr eine Zeile aus und ist damit bei einer großen Anzahl Objekte leider überhaupt nicht zu gebrauchen. Ich konnte da also keine genaueren Erkenntnisse gewinnen. Dann habe ich auf StackOverflow den Tipp gefunden, den FPC-eigenen Speichermanager durch den C-Speichermanager auszutauschen, indem man die Unit "cmem" einbindet, eigentlich mit dem Ziel, mit Valgrind debuggen zu können. Allerdings hat sich bei mir das Problem überraschenderweise schon allein durch das Einbinden der Unit erübrigt: Auf einmal braucht das Programm nur noch 90MB, was nahezu perfekt ist (Das Programm braucht nach dem Start ja schon 8MB). Aber nicht nur das: Das Einfügen in den Baum dauert nun nur noch halb so lange wie vorher (~400ms statt vorher ~800ms). Warum schneidet der FPC-Speichermanager hier im Vergleich zu C so schlecht ab? Was macht C anders? |
AW: Effizienz des Speichermanagers
Wenn Du sehr viele kleine Fragmente hast, ist der Overhead vielleicht relativ gesehen zu groß. Ich würde nicht immer und überall Klassen verwenden, die guten alten Arrays tun es in vielen Fällen auch: Und die haben fast kein Overhead.
Ich habe als Knotenspeicher nämlich ein Array verwendet. Bei mir sind die Seiten konstant 8k groß, bzw. entsprechen der 'System Page Size', sodaß ich eine Klasse habe, die exakt diese Pagegröße liest und schreibt. Im Umkehrschluss ergibt sich daraus -abzüglich einiger Bytes for Bookkeeping- ca. 8160 Bytes Nutzdaten pro B+-Knoten (bei 8k System Page größe). Je nach länge des Schlüssels passen dann eben mehr oder weniger Daten in das Array. rein. Schneller geht es imho nicht. Beim laden und persistieren lese ich alles in einem Abwasch ein bzw. flushe es entsprechend performant. An dieser einen Stelle im Code habe ich dann -gut dokumentiert- etwas Adressarithmetik, die aber gekapselt ist. Ich weiss nicht, ob wir über exakt das gleiche Modell reden, fällt mir gerade ein: Ich habe B-Bäume umgesetzt, keine B+ Bäume. Trotzdem könnte das als Denkanstoß reichen, um den Speicherverbrauch zu optimieren. |
AW: Effizienz des Speichermanagers
Hast du die Exe mit Debug-Infos und/oder Stack-Frames erstellt?
|
AW: Effizienz des Speichermanagers
Zitat:
Zitat:
(Ich weiß nicht, ob das ein grundlegender Unterschied zwischen (a,b)-Bäumen und B+-Bäumen ist, oder ob unser Prof das einfach nur anders gemacht hat. Im Internet findet man zu (a,b)-Bäumen sehr wenig Informationen) Ursprünglich stand das schon länger auf meiner To-Do-Liste, diesen untersten Layer loszuwerden, allerdings ist mir dann aufgefallen, dass das so einen entscheidenden Vorteil hat: Wenn man sich einen Zeiger (Iterator) auf einen Datensatz holt, bleibt der – solange der Datensatz nicht gelöscht wird, natürlich – für immer gültig, egal was sich am Baum verändert. Man kann beliebig Knoten einfügen oder löschen, der Zeiger zeigt trotzdem noch auf den richtigen Knoten. Das ist bei der speichereffizienteren Variante nicht gegeben: Es könnte sein, dass der zugehörige Knoten in der Zwischenzeit aufgespalten oder mit einem anderen Knoten zusammengelegt wurde, wodurch er nicht mehr an der richtigen Stelle im Speicher liegt. Für meinen Anwendungsfall ist diese Persistenz sogar tatsächlich ein Vorteil. Deshalb wollte ich erst mal in Kauf nehmen, dass meine Lösung nicht die aller speichereffizienteste ist. Dass das allerdings zu so viel Fragmentierung führt, hätte ich nicht erwartet. Ich werde jetzt wahrscheinlich versuchen, mir nur für diese Records einen eigenen kleinen Speichermanager zu schreiben. @Bernhard Geyer: Ich hatte mal testweise alle Debug-Informationen rausgenommen, das hat aber nichts verändert. |
AW: Effizienz des Speichermanagers
Blöde Idee: Erzeuge 1 Mio deiner 48-Byte Blöcke in einem separaten Projekt. Wie hoch ist der Speicherverbrauch?
Jetzt erzeuge 2 Mio Blöcke. Und nun? Erzeuge 2 Mio, gib die Häfte wieder frei. Und nun? |
AW: Effizienz des Speichermanagers
Zitat:
@Namenloser: Ich nehme mal an, das Prinzip ist dir bekannt? Für deinen Anwendungsfall brauchst du nur eine direkte Freiblockliste implementieren :wink: |
AW: Effizienz des Speichermanagers
Zitat:
Delphi-Quellcode:
Und jetzt?
var
i: integer; begin // 7 MB for i := 0 to 1000000 - 1 do New(recs[i]); // 77 MB for i := 1000000 to 2000000 - 1 do New(recs[i]); // 144 MB for i := 0 to 1000000 - 1 do Dispose(recs[i]); // 83 MB end; @BUG: Freiblockliste? Nein, sagt mir nichts. |
AW: Effizienz des Speichermanagers
Zitat:
Was ein Speichermanager wie FastMM macht ist das er nicht jedes kleines Byte das freigegeben wird wieder ans OS zurück gibt sondern effektiver und schneller als das OS kleine Speicheranforderungen und Freigaben verwaltet. |
AW: Effizienz des Speichermanagers
Zitat:
Zitat:
|
AW: Effizienz des Speichermanagers
Also hier unter Linux gibt der FPC-Speichermanager auch den Speicher zurück. Der C-Manager hingegen behält ihn. Finde ich aber nicht so toll, ich finde, der Speicher sollte schon zurückgegeben werden, es laufen schließlich noch andere Programme auf dem Rechner.
|
Alle Zeitangaben in WEZ +1. Es ist jetzt 16:30 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz