Glossar

Aktivierung:

Der Speicherbereich innerhalb des $\rightarrow$Ausführungs-Stacks, der einem bestimmten Aufruf einer Funktion entspricht. Er enthält die Parameter und lokalen Variablen der Funktion, sowie einen Verweis auf die vorherige Aktivierung und sprachspezifische Daten.

Algebraische Vereinfachungen:

Klassischen Optimierung, bei der algebraische Ausdrücke durch Umformungen vereinfacht werden. Dabei werden beispielsweise Multiplikationen mit 2er-Pozentzen durch Verschiebe-Operationen ersetzt.

Alignment:

Die Ausrichtung einer Adresse im Speicher. Z.B. ist eine Adresse 32-bit-aligned, wenn sie sich ohne Rest durch 4 Teilen läßt (32 Bit entsprechen 4 Byte, Hauptspeicheradressen werden in Byte geführt).

Atomare Instruktion:

Komplexe Speicheroperation, die von der Architektur atomar ausgeführt wird. Beispiele sind ,,Test-and-Set`` oder ,,Compare-and-Swap``.

Ausführungs-Stack:

Speicherbereich, in dem Paramerter und lokale Variablen beim Aufruf einer Funktion im Falle der Stack-Allokation abgelegt werden.

Bytecode:

Serialisierte Instruktionsfolge für eine abstrakte Maschine in binärer Form.

CAS:

(,,Compare-and-Swap``) $\rightarrow$Atomare Instruktion, bei der ein Vergleich eines Registers mit einer Hauptspeicherzelle und bei Gleichheit ein Vertauschen der Inhalte atomar ausgeführt wird.

CHA:

$\rightarrow$Class Hierarchy Analysis

CSE:

$\rightarrow$Common Subexpression Elimination

Card Marking:

Methode um Zeiger zwischen Generationen zu protokollieren. Der Speicher wird in n Karten gleicher Größe unterteilt und ein Bit-Array cards der Größe n wird angelegt. Wird ein Zeiger geschrieben, so wird die entsprechende Karte markiert, indem cards[i] gesetzt wird. Alle Pointer auf der modifizierten Karten werden zu Wurzeln jeder Garbage Collection einer jüngeren Generation $\rightarrow$Remembered Sets.

Class Hierarchy Analysis:

Globale Programmanalyse des dynamischen Compilers bezüglich der Klassenhierarchie. So können Schlüsse über die möglichen Ziele eines dynamischen Methodenaufrufs gezogen werden.

Common Subexpression Elimination:

Klassische Optimierung, durch die die mehrfache Auswertung gleicher Ausdrücke oder Teilausdrücke vermieden wird. Wird beispielsweise an zwei Stellen in einer Prozedur der Ausdruck a + 1 berechnet und ist a an beiden Stellen gleich (durch Datenflußanlayse vom Optimierer zu beweisen), so kann einer Speicherung des Ergebnisses in einer Temporärvariablen erfolgen, um einen Wiederverwendung zu ermöglichen. Da eine Integer-Operation auf modernen Prozessoren scheller ist als ein Speichzugriff, lohnt sich die CSE nur wenn die erzeugte Teporärvariable einem Register zugewiesen werden kann. Andernfalls wäre eine erneute Berechnung meist schneller als der notwendige Speicherzugriff.

Constant Folding and Propagation:

Klassischen Optimierung, bei der Ausdrücke, deren Operanden zur Übersetzungszeit konstant sind, bereits vom Compiler ausgewertet werden. Dabei entstehen neue Konstanten, die im Code weiterpropagiert werden und ggf. wieder mit anderen Konstanten verknüpft werden. Der Compiler nimmt also einen Teil der Berechnung des laufenden Programmes voraus, indem er die Zielumgebung simuliert -- dies ist im Zusammenhang mit Fließkommazahlen nicht unproblematisch.

Control Path Dependency:

Begriff aus der Datenflußanalyse: Ist der Wert einer Datenflußvariablen an einem bestimmten Punkt von dem Weg abhängig, auf dem dieser Punkt erreicht wurde, so besteht eine control path dependency

Control Point Dependency:

Begriff aus der Datenflußanalyse: Ist der Wert einer Datenflußvariablen an einem bestimmten Punkt immer gleich, und ist die damit unabhängig vom Kontrollfluß, so besteht eine control point dependency

Deoptimierung:

Zurücknehmen bestimmter Optimierungen beim Übersetzen von Methoden; meist durch komplette Neuübersetzung. Notwendig, wenn zuvor getroffene Annahmen z.B. durch dynamisches Laden neuer Klassen nicht länger zutreffen. Erfordert u.U. $\rightarrow$On-Stack Replacement.

Dynamischer Compiler:

(dynamic compiler, just-in-time compiler) Compiler, der im laufenden Programm abstrakten Code in Maschinencode übersetzt und so das Programm erweitert oder verändert. Zur Portabilität oder späten Optimierung aufgrund von dynamischem Programmverhalten oder Maschinenspezifika.

Dynamischer Methodenaufruf:

(dynamic dispatch) Mechanismus objektorientierter Sprachen, die zu Empfängerklasse und Nachricht zugeordnete Methode zu ermitteln und aufzurufen. $\rightarrow$inline cache, polymorphic inline cache, vtable

Eden:

Begriff aus der $\rightarrow$generationalen Garbage Collection: Fester Bereich innerhalb der jüngsten Generation, in dem neue Objekte alloziert werden. Mit der nächsten Garbage Collection werden sie in den Hauptbereich der jüngsten Generation evakuiert.

Ereignisvariable:

(condition variable) Synchronisierungskonstrukt. Ereignisvariablen erlauben den Austausch anonymer Ereignisse zwischen $\rightarrow$Threads.

Exakter Garbage Collector:

Kann ein Garbage Collection für jede Speicherzelle im System zum Zeitpunkt der Garbage Collection bestimmen, ob sie einen Zeiger oder einen Skalar (z.B. eine Ganzzahl) enthält, so wird er als exakt bezeichet. Ein exakter Garbage Collector kann im Gegensatz zu einem $\rightarrow$konservativen Garbage Collector Objekte auf den Heap verschieben.

Fast Path:

Der schnellste ``Weg'', den eine Berechnung nehmen kann. Oftmals stellt dieser den Regelfall dar, so daß sich besondere Optimierung lohnt. Der fast path einer Allokation kann beispielsweise lediglich im Erhöhen eines Zeigers bestehen, während der slow path eine Garbage Collection ausführt.

GC Point:

(konsistenter Punkt) Programmpunkt, an dem eine Garbage Collection durchgeführt werden darf, weil hier $\rightarrow$Referenztabellen vorliegen. Alle Threads müssen zu ihrem nächsten ``GC Point'' vorgerollt werden, wenn eine Garbage Collection durchgeführt werden soll.

Generationale Garbage Collection:

Bei der generationalen Garbage Collection wird der Speicher logisch nach dem Alter der Objekte in mehrere Segmente unterteilt, die dann separat bereinigt werden können.

Gosling Property:

Eigenschaft des Java-Bytecodes, die besagt, daß der Typ einer Programmvariablen keine $\rightarrow$control path dependency aufweisen darf.

Header Word Displacement:

Implementierungstechnik zur Reduktion des Speicherbedarfs von Objekten. Zur Aufnahme nur temporär benötigter Objektmetadaten werden Teile des $\rightarrow$Objektkopfes durch Verweise auf zusätzliche Speicherbereiche ersetzt und dorthin verdrängt.

IC:

$\rightarrow$inline cache

Inkrementell Garbage Collection:

Garbage Collection, bei der bei jedem Aufruf nur ein kleiner Teil des Speichers bearbeitet wird.

Inline Cache:

(IC) Technik zum $\rightarrow$dynamischen Methodenaufruf. An der Aufrufstelle in den Code eingebetteter einelementiger Ergebniscache des letzten Aufrufs; dargestellt als direkter Sprung an die Zielmethode in Verbindung mit einem Klassentest des Empfängerobjektes. Diese Technik beschleunigt quasi-monomorphe Methodenaufrufe, da diese auf einen Vergleich und einen direkten Sprung reduziert werden. Bei einem cache miss wird der IC überschrieben. $\rightarrow$polymorphic inline cache, vtable

JIT:

$\rightarrow$Dynamischer Compiler

Kernel Space:

(kernel mode) Privilegiertes Ausführungsregime von Systemcode. Es besteht ungeschützter Zugriff auf Systemressourcen. $\rightarrow$user space

Konservativer Garbage Collector:

Ist ein Garbage Collector nicht in der Lage, für jede Speicherzelle zu bestimmen, ob sie einen Pointer oder einen Skalar (z.B. eine Ganzzahl) enthält, wird er als konservativ bezeichnet. Ein konservativer Garbage Collector muß (konservative) Annahmen über den Inhalt von Speicherzellen machen um eine Garbage Collection ausführen zu können.$\rightarrow$exakter Garbage Collector

LAB:

$\rightarrow$local allocation buffer

Liveness:

Um eine Speicherzelle wiederverwenden zu können, muß der Garbage Collector beweisen, daß diese vom laufenden Programm nicht mehr benötigt wird. Dieser Beweise wird i.d.R. aufgrund einer referenziellen Erreichbarkeit geführt. Kann eine Zelle vom Programm erreicht werden so wird sie als live bezeichnet

Local Allocation Buffer:

(LAB) Speicherbereich eines Threads, der zur Ausführung von Allokationen ohne jegliche Synchronisation mit anderen Threads dient. Ist der local allocation buffer erschöpft, so wird synchronisiert ein neuer Bereich angefordert.

Loop Invariant Code Motion:

Klassische Optimierung, bei der Schleifenkonstanten erkannt werden und ihre Auswertung vor die Schleife in den sogenannten preheader verlegt wird -- dies reduziert den Rechenaufwand oft erheblich. Ob ein Prozeduraufruf eine Schleifenkonstante darstellt, kann nur durch interprozedurale Analysen festgestellt werden.

Loop Unrolling:

Klassische Optimierung, bei der Schleifen ,,entrollt`` werden, indem der Schleifenkörper mehrfach hintereinander kopiert und dabei der Schleifenkontrollcode entsprechend angepaßt wird. Dies erlaubt wiederum eine bessere Verwendung von delay slots und vor allem eine optimalere Ausnutzung der Ausführungseinheiten superskalarer Prozessoren. Loop unrolling ist also eng mit $\rightarrow$software pipeling verknüpft.

Markierung:

(tagging) Methode zur Implementierung eines $\rightarrow$exakten Garbage Collectors, bei der jeder Wert seine Typinformation selbst enthält. Üblicherweise wird ein Bit der Repräsentation verwendet, um die Typinformation aufzunehmen - z.B. stellt ein Wert, bei dem das least significant bit gesetzt ist, einen verschobenen Integerwert dar, ein Wert, bei dem das least significant bit nicht gesetzt ist, einen Zeiger. $\rightarrow$alignment

Memory Barrier:

Instruktion, die Speicherinstruktionen vor Optimierungen schützt. Memory barriers sind zur Implementierung des $\rightarrow$Speichermodells notwendig.

Metasperre:

Primitive Sperrstruktur, die ein komplexes Synchronisationsobjekt seinerseits vor nebenläufigem Zugriff schützt. Zumeist durch $\rightarrow$atomare Instruktionen realisiert.

Methodenintegration:

(inlining) Klassische Optimierung, die den Aufruf einer Methode durch ihren Methodenkörper ersetzt. Wie bei der $\rightarrow$tail-call optimization werden zum eine die Kosten eines Aufrufes gespart und zum anderen weitere Optimierungen erst ermöglicht. Bei der Methodenintegration ist zu beachten, daß eine Vergößerung des Codes eine geringere Lokalität und damit cache misses im Instruktions-Cache bewirken kann.

Monitor:

Synchronisierungskonstrukt. Einheit von $\rightarrow$Sperre und $\rightarrow$Ereignisvariablen.

Nebenläufig:

Programmteile sind nebenläufig, wenn sie unabhängig voneinander und damit potentiell gleichzeitig ausgeführt werden können. Ein Programm ist nebenläufig, wenn es mehrere nebenläufige Programmteile enthält. $\rightarrow$parallel, Synchronisierung

Nebenläufiger Garbage Collector:

Garbage Collector, der $\rightarrow$nebenläufig mit dem ausgeführten Programm in einem eigenen Thread abläuft.

OSR:

$\rightarrow$on-stack replacement

Objektkopf:

Speicherbereich für Objektmetadaten wie z.B. Klasse oder Hashwert. Dieser liegt typischerweise direkt vor den ``Nutzdaten'' des Objekts im Speicher.

On-Stack Replacement:

(OSR). Austausch einer oder mehrerer $\rightarrow$Aktivierungen durch andere. Nötig, falls die aktive Methode durch den $\rightarrow$dynamischen Compiler auf unterschiedliche Art und Weise neu übersetzt wurde. $\rightarrow$Deoptimierung

PIC:

$\rightarrow$polymorphic inline cache

Parallel:

Programmteile sind parallel, wenn sie zur gleichen Zeit auf verschiedenen Prozessoren ausgeführt werden.$\rightarrow$nebenläufig

Paralleler Garbage Collector:

Ein Algorithmus zur parallelen Garbage Collection ist nebenläufig formuliert. Die Garbage Collection kann daher auf mehreren Prozessoren $\rightarrow$parallel ausgeführt werden.

Polymorphic Inline Cache:

(PIC). Technik zum $\rightarrow$dynamischen Methodenaufruf. Wie $\rightarrow$inline cache in den Code eingebetteter Cache, allerdings mit mehreren (üblicherweise bis zu 10) Einträgen; dargestellt als kaskadierter Klassentest mit direkten Sprüngen. Beschleunigt schwach-polymorphe Aufrufstellen, eignet sich zudem zur Profilerstellung. $\rightarrow$inline cache, vtable

Prozedurspezialisierung:

Klassischen Optimierung. Kann der Compiler feststellen, daß einen bestimmte Prozedur f(x) häufig mit dem Parameter x=3 aufgerufen wird, so kann einen Prozedur f(x)/x=3, erstellt werden. Durch $\rightarrow$constant folding kann diese Prozedur -- möglicherweise bis auf einen konstanten Wert -- weiter vereinfacht werden.

Read Barrier:

Codeabschnitt, der bei jedem Lesen aus einem Speicherbereich ausgeführt wird.

Referenzlokalität:

Das Maß, in dem Zugriffe auf benachbarte Speicherzellen auch zeitlich dicht beieinander liegen.

Referenztabelle:

Eine Beschreibung der Prozessorregister und des Stacks, die es dem Garbage Collector erlaubt, zu bestimmen, in welchen Registern und Stack-Zellen sich Zeiger befinden.

Registerallokation:

Diese Optimierung ordnet den verwendeten symbolischen Registen physische Maschinenregister zu. Stehen diese nicht nicht in ausreichender Zahl zur Verfügung, so muß spill code eingefügt werden, der symbolische Register in den Hauptspeicher auslagert. Die Registerallokation stellt eine wichtige Optimierung dar, da die Zugriffe auf den Hauptspeicher durch die Ausnutzung der vorhandenen Maschinenregister minimiert werden.

Remembered Sets:

Methode um Zeiger zwischen Generationen zu protokollieren. Bei jeder Zeigerzuweisung wird das Ziel der Zuweisung in eine Menge aufgenommen, die den Wurzeln jeder Garbage Collection einer jüngeren Generation zugefügt werden. $\rightarrow$Card Marking

Sequential Store Buffer:

Methode zur effizienten Implementierung von $\rightarrow$Remembered Sets.

Skalare Ersetzung von Aggregaten:

Klassische Optimierung bei der Aggregate durch die enthaltenen Skalare ersetzt werden. Beispielsweise wird bei einer Struktur komplexeZahl anstatt z.real direkt eine float-Variable verwendet, wenn dies möglich ist. Dies vermeidet zum einen eine Indirektion und ermöglicht zum anderen weitere Optimierungen, bei denen Aggregate unberücksichtigt blieben.

Software Pipelining:

Klassische Optimierung. Hier wird die Architektur moderner Prozessoren mit pipelines unterstützt, indem der Code derart umstrukturiert wird, daß delay slots von Verzweigungen ausgenutzt und die Latenzzeiten einzelner Operationen berücksichtigt werden. Außerdem werden bei superskalaren Prozessoren abhängige Operationen derart versetzt, daß mehrere Ausführungseinheiten ausgenutzt werden können.

Speichermodell:

(memory model). Spezifikation der Operationen load und store auf dem globalen Speicher. Relevant für Multiprozessorarchitekturen und nebenläufige Programmiersprachen.

Sperre:

(mutex, lock) Synchronisierungskonstrukt. Eine Sperre kann nur von einem $\rightarrow$Thread zur Zeit erworben werden und realisiert so gegenseitigen Ausschluß.

Static Allocation Arena:

Methode der optimierten Allokation, bei der der gesamte innerhalb eines basic blocks benötigte Speicher in einer Allokation am Anfang des Blocks angefordert wird.

Tail-Call Optimizations:

Klassische Optimierung. Endet eine Prozedur mit dem Aufruf einer anderen oder mit einer Rekursion, so kann die tail-call optimization diese Aufrufe in Verzweigungen umwandeln. Es wird also zum Auswerten der gerufenen Prozedur die Aktivierung der aktuellen Methode verwendet. Dadurch werden zum einen die Kosten eines Aufrufes gespart, zum anderen werden Rekursionen zu Schleifen, die dann mittels Schleifenoptimierung weiter optimiert werden können.

Thread:

Kontrollflußabstraktion. Ein Thread ist ein unabhängiger Ausführungskontext mit eigenem Aufrufstack, Instruktionszeiger und lokalem Speicher. Threads kommunizieren durch Synchronisierungskonstrukte und tauschen Daten über einen geteilten, globalen Speicher aus.

Tricolor Marking:

Von Dijkstra formalisierte Abstraktion zur Betrachtung der Arbeit eines nebenläufigen Garbage Collectors.

User Space:

Geschütztes Ausführungsregime von Anwendungscode. Zugriff auf Systemressourcen ist nur durch Aufruf des Betriebssytems und Wechsel in $\rightarrow$kernel space möglich.

Vtable:

(virtual function table). Vom Compiler generierte Tabelle der virtuellen Methoden einer Klasse. Jeder Methodensignatur wird eine Zeile der Tabelle zugewiesen. Gleiche Methodensignaturen in durch Vererbung abhängigen Klassen werden der gleichen Zeile zugewiesen. Dadurch kann der virtuelle Methodenlookup durch einen einfachen Array-Zugriff implementiert werden. $\rightarrow$inline cache, polymorphic inline cache

Write Barrier:

Codeabschnitt, der bei jedem Schreiben in einen Speicherbereich ausgeführt wird.