View
22
Download
1
Category
Preview:
DESCRIPTION
Mark – Compact GC & Performancemessungen. Bernhard Prügl, 0156212. Inhalt. Motivation für Mark – Compact Algorithmenüberblick 4 Algorithmen im Detail Zusammenfassung Algorithmen Performance der verschieden Garbage Collection Strategien. Motivation für Mark – Compact. - PowerPoint PPT Presentation
Citation preview
Mark – Compact GC & Performancemessungen
Bernhard Prügl, 0156212
2/18
Inhalt
Motivation für Mark – Compact Algorithmenüberblick 4 Algorithmen im Detail Zusammenfassung Algorithmen Performance der verschieden Garbage
Collection Strategien
3/18
Motivation für Mark – Compact
Lange Programmlaufzeit führt zu Fragmentierung, welche folgende Probleme verursacht:
Aufwand zum Anlegen neuer Objekte steigt Speicher wird nicht optimal ausgenützt Nacheinander angelegte Objekte oft nicht
nebeneinander Mark-Compact reduziert diese Probleme
4/18
AlgorithmenüberblickGrundsätzliche 3 Phasen:1. Markieren der lebendigen Knoten.2. Kompaktierung des Speichers (Knoten verschieben).3. Aktualisieren der Zeiger auf verschobene Knoten.
Kriterien anhand derer eine Einteilung möglich ist: Einteilung nach Art wie verschobene Knoten
angeordnet werden. 2 oder 3 Durchläufe zum Kompaktieren. Einteilung nach zusätzlich benötigten Speicher Weitere Anforderungen, z.B. nur Knoten gleicher
Größe
5/18
Zwei Finger Algorithmus
2 Zeiger "free" sucht freien
Speicher "live" sucht lebendige
Knoten "live" wird auf "free"
verschoben Neue Adresse wird in
"live" hinterlassen
6/18
Lisp 2 Algorithmus (1/2)
Adressenweiterleitend Zusätztliche
Speicherzelle im Header jedes Knoten
"free" läuft von Anfang bis Ende
Neue Adresse wird in Header jedes Knoten geschrieben
7/18
Lisp 2 Algorithmus (2/2)
2.Durchlauf: interne Zeiger aktualisieren anhand der Adresseinträge in den Headern
3.Durchlauf: Knoten tatsächlich verschieben
8/18
Haddon-Waite Algorithmus (1/2)
Tabellenbasiert Zeiger durchläuft
Speicher von Anfang bis Ende
Knoten werden sofort verschoben
Information über Verschiebung in Tabelle eintragen
9/18
Haddon-Waite Algorithmus (2/2)
Tabelle am Ende des bearbeiteten Bereichs wird bei Bedarf verschoben
Am Ende muss Tabelle sortiert werden
2. Durchlauf: interne Zeiger mit Hilfe der Tabelle aktualisieren
10/18
Threading
Zeiger werden verbogen durch tauschen der Inhalte
P enthält eine Liste mit allen Zeigern die auf P zeigen
Info im letzten Knoten
11/18
Jonkers Algorithmus (1/2)
Threaded Zuerst
vorwärtszeigende Zeiger threaden
Wird P erreicht werden alle schon gethreadeden Knoten aktualisiert
12/18
Jonkers Algorithmus (2/2)
Vorwärtszeigende Zeiger zeigen jetzt auf zukünftiges P
Rückwärtszeigende Zeiger werden gethreaded
2. Durchlauf: Knoten verschieben
Alle rückwärtszeigenden Zeiger aktualisieren
13/18
Überblick
Geeigneter Algorithmus muss entsprechend Vorgaben gewählt werden.
14/18
Performance
Performancemessungen in GC Bereich Messungen auf AMD Athlon XP 2600+, ausgeführt
von Stephen M Blackburn, 2004
3 Graphiken: Laufzeitmessungen des gesamten Programms und
der Garbage Collection allein Cache Misses bei verschiedenen GC Strategien Performance in Generationensystemen
15/18
Laufzeitmessungen
X-Achse: Heap Größe Y-Achse: Zeit
16/18
Cache Misses
X-Achse: Heap Größe Y-Achse: Zeit (a) / Cache Misses (b - d)
17/18
Performance in Generationensystemen
X-Achse: Speichergröße für neue Objekte
Y-Achse: Zeit (a-c) / Cache Misses (d-f)
18/18
Danke für eure Aufmerksamkeit
Recommended