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