Marcus Denker Studienarbeit 
  
Entwurf von Optimierungen für Squeak

 

Einleitung

Das Squeak-System möchte eine flexible Programmierumgebung und ein mächtiges multimediales Autorensystem für Kinder bereitstellen. Die besonderen Eigenschaften eines solchen Systems stellen besondere Anforderungen an die Implementierung.

Die Studienarbeit zeigt die Probleme der bestehenden Implementierungen auf und stellt einen verbesserten Entwurf vor.

Gliederung

Das Kapitel 2 gibt einen Überblick über das existierende Squeak-System. Nach einer kurzen Vorstellung des Squeak-Projektes gehe ich insbesondere auf die Anforderungen ein, die Squeak an die Implementierung des Systems stellt.

Das Kapitel 3 zeigt, wie das aktuelle System diese Anforderungen durch Verwendung einer virtuellen Maschine erfüllt und stellt die Zielkriterien auf, die ein verbessertes System erfüllen muß.

Den ersten Versuch einer Verbesserung stelle ich in Kapitel 4 vor. Das Kapitel stellt den Squeak-Laufzeitübersetzer J3 vor, erläutert die Ergebnisse des J3 Projektes und stellt dar, inwieweit sie die Kriterien aus Kapitel 3 erfüllen.

Die Erfahrungen aus dem J3-Projekt bilden die Grundlage meines neuen Entwurfes. Dieser soll die Vorteile des ursprünglichen interpretativen Systems mit denen des Laufzeitübersetzers verbinden. Dazu definiert er eine neue virtuelle Maschine in Kapitel 5. Dieses Kapitel gibt außerdem einen Ausblick über zukünftige Entwicklungen. Die heterogene Umgebung erfordert ein portables System: Squeak selber muß auf allen Systemen lauffähig sein, aber auch die von den Schülern geschaffenen Inhalte sollen sowohl Zuhause als auch auf dem Schulrechner benutzbar sein.

Erwartetes Verhalten

Das Verhalten eines Squeak-Programmes sollte dem entsprechen, was der Benutzer erwartet. Ein System zeigt erwartetes Verhalten (engl. expected behaviour, siehe [START_REF] Zellweger | Interactive Source-Level Debugging of Optimized Programs[END_REF]), wenn es sich so verhält, wie es im Quellcode vorgegeben wurde.

Ein Interpreter, der den Quellcode direkt interpretiert, zeigt ein solches Verhalten. Falls man optimierende Transformationen zur Leistungssteigerung einsetzen möchte, müssen diese semantikerhaltend sein. Kapitel 3 zeigt, daß dies in der aktuellen Implementierung nicht der Fall ist.

Performanz

Die bis jetzt genannten Anforderungen an die Squeak-Implementierung (dynamische Metaprogrammierung, erwartetes Verhalten und Portabilität) haben alle einen entscheidenden Nachteil: Jede naive Implementierung ist sehr ineffizient.

Praktisch einsatzfähig ist das System nur, wenn es trotz weitgehender Verwirklichung dieser Anforderungen eine ausreichende Gesamtperformanz liefert.

Gerade für Multimediasysteme wird in vielen Bereichen (etwa Grafik oder Musik) ein sehr effizientes System benötigt. Dies ist besonders dann der Fall, wenn man das System auch auf portablen Endgeräten einsetzen möchte, bei denen die Leistungsfähigkeit durch einen geringen Stromverbrauch begrenzt wird. 

Zusammenfassung

Die Implementierung von Squeak

Squeak versucht, möglichst wenige der von dem Betriebsystem angebotenen Dienste zu nutzen. Dadurch vereinfacht sich die Portierung und Squeak bleibt über alle Systeme kompatibel.

Das Squeak-System enthält eine umfangreiche Klassenbibliothek (ca. 1700 Klassen). Diese stellt neben Grundlegendem (etwa Datentypen wie Integer und Float oder einem mächtigen Behälterrahmenwerk (engl. collection hierarchy) auch Klassen für graphische Oberflächen, Netzwerkprotokolle und Multimedia zur Verfügung.

Die virtuelle Maschine

Die Implementierung der virtuellen Maschine hält sich weitgehend an die Referenzimplementierung der Smalltalk 80 VM in [START_REF] Goldberg | Smalltalk-80: The Language and Its Implementation[END_REF], die genauen Unterschiede diskutiert [START_REF] Ingalls | Back to the Future: The Story of Squeak, A Practical Smalltalk Written in Itself[END_REF].

Die virtuelle Maschine von Squeak gliedert sich in drei Teile (siehe Abbildung 5):

• Objektspeicher (ObjectMemory)

• Interpreter

• Primitive Funktionen für elementare Aufgaben Die folgenden Abschnitte stellen diese Teile kurz genauer vor. Eine ausführliche Beschreibung findet sich in [START_REF] Rowledge | Squeak, Open Personal Computing for Multimedia, chapter A Tour of the Squeak Object Engine[END_REF].

ObjectMemory

Der ObjectMemory ist das Speicherverwaltungssystem der virtuellen Maschine. Er implementiert das Objektmodell und stellt eine automatische Speicherbereinigung bereit.

Die Speicherbereinigung verwendet Generation Scavanging [START_REF] David | Generation Scavenging: A Non-disruptive High-Performance Storage Reclamation Algorithm[END_REF]. Das Verfahren macht Gebrauch von der Beobachtung, daß viele Objekte nur für eine sehr kurze Zeit nach ihrer Erzeugung benötigt werden.

Der Speicher der virtuellen Maschine wird in mindestens zwei Bereiche eingeteilt. Im Falle von Squeak existiert ein kleiner Bereich, in dem neue Objekte erzeugt werden (der sog. Newspace) und ein großer Speicherbereich für langlebige Objekte (Oldspace).

Da der Newspace nur wenige 100 Kilobyte umfaßt, dauert eine Speicherbereinigung nur eine kurze Zeit. Sie kann also sehr häufig durchgeführt werden. Da ein sehr großer Anteil der Objekte nur eine kurze Lebensdauer hat, überleben nur wenige Objekte die Bereinigung des Newspace.

Mit der Zeit werden aber auch langlebige Objekte erzeugt. Wenn die Anzahl der Objekte nach der Bereinigung des Newspace einen Schwellwert überschreitet, so werden alle diese Objekte dem Oldspace zugeordnet.

Der Oldspace wird nur sehr selten bereinigt. Solch ein Fall tritt z. B. auf, wenn nicht mehr genug Speicher für neue Objekte vorhanden ist.

Die Speicherverwaltung von Squeak wird in [START_REF] Ingalls | Back to the Future: The Story of Squeak, A Practical Smalltalk Written in Itself[END_REF] ausführlich beschrieben. Rücksprünge Rücksprung aus Methoden und Blöcken.

Der Bytecode kennt also keine primitive Typen. Es werden lediglich Nachrichten an Objekte gesendet.

Primitive Funktionen

Die primitiven Funktionen erlauben es, Code aufzurufen, der direkt in der virtuellen Maschine implementiert ist. Es gibt zwei Gründe, auf primitive Funktionen zurückzugreifen: Zum einen Operationen, die nicht in Squeak implementiert werden können (weil sie z. B. das Typsystem umgehen oder Betriebssystemroutinen aufrufen). Zum anderen werden primitive Funktionen zur Steigerung der Geschwindigkeit eingesetzt.

Die vorhandenen primitiven Funktionen lassen sich in folgende Klassen einteilen:

Ein-/Ausgabe: Tastatur, Maus, Bildschirm über plattformabhängige C-Funktionen

Arithmetik: Grundlegende arithmetische Operationen auf Integer/Float.

Erzeugen neuer Objekte: Aufrufe der Speicherverwaltung.

Prozeßmanipulation: Prozesse starten, anhalten und beenden.

Ausführungskontrolle: Erzeugung neuer Ausführungskontexte von Methoden und Blöcken.

Performanz: Primitive Funktionen zur Beschleunigung des Systems. 

Architektur

Der Squeak J3 ersetzt den Bytecode-Interpreter der normalen virtuellen Maschine. Viele andere Teile, etwa die primitiven Funktionen und die automatische Speicherbereinigung (den sog. ObjectMemory) kann J3 wiederverwenden.

Der Übersetzer besteht aus drei Teilen: Transformation in eine Zwischenrepräsentation, Optimierung und schließlich Codegenerierung (siehe Abbildung 6).

Squeak Abstract Machine (SAM)

Im ersten Schritt transformiert J3 die Bytecodes (siehe Kapitel 3.1.3) in eine Zwischenrepräsentation (siehe Abbildung 6).

Diese SAM genannten Operationen sind ein stark vereinfachter Bytecode, statt 248 verschiedenen Bytecodes gibt es nur 22 grundlegende SAM-Instruktionen, dazu kommen noch 12 Instruktionen (Add, Sub, etc), die einzig der besseren Lesbarkeit und dem Verständnis sowohl des generierten SAM-Codes, als auch der Implementierung des Optimierers dienen. 

Optimierung und

Bewertung

Das J3-Projekt hat gezeigt, daß auch ein relativ einfacher und leicht portierbarer Laufzeitübersetzer die Ausführungsgeschwindigkeit steigern kann.

Die erreichte Beschleunigung (ca. Faktor 5-7) wird es möglich machen, in einigen Fällen auf den Einsatz von primitiven Funktionen zu verzichten. Dazu müßte der Laufzeitübersetzer aber auf allen System verfügbar sein.

Hier zeigt sich ein Problem des Ansatzes: Die Portierung eines Übersetzers ist, auch im Fall von J3, doch immer noch viel aufwendiger als die des Interpreters (der einfach nur mit Hilfe eines C-Compilers übersetzt werden muß).

Daher wird der Laufzeitübersetzer den Interpreter nie ersetzen können: Es wird immer zwei virtuelle Maschinen geben, die fast vollständig getrennt voneinander gewartet und weiterentwickelt werden müssen.

Ein weiteres Problem ist die Implementierungssprache C++: Die Entwicklungsumgebung ist, besonders bei der Fehlersuche, bei weitem nicht so mächtig wie Squeak. Außerdem hat sich gezeigt, daß es sehr viel schwieriger für die anderen Squeak-Entwickler ist, mit dem J3-System zu experimentieren als mit dem Squeak-Interpreter. Dies liegt natürlich zum einen an der viel höheren Komplexität eines Übersetzers, darüberhinaus spielt aber auch die Implementierungssprache eine Rolle: Ein in Squeak implementiertes System ist für die Entwickler viel einfacher zu verstehen und zu verändern.

Zusammenfassung

Durch einen Laufzeitübersetzer kann, trotz einfacher Architektur, eine entscheidende Beschleunigung erreicht werden. Der J3-Laufzeitübersetzer hat aber einzig die Beschleunigung der Ausführung des existierenden Squeak-Bytecodes zum Ziel. Die Probleme, die dieser Bytecode mit sich bringt (siehe Kapitel 3.2.2), behebt er daher nicht.

Eine Architektur, die auch diese Probleme lösen möchte, muß daher einen anderen Weg gehen. Kapitel 5 stellt einen entsprechenden Entwurf für eine solche Architektur (SX Squeak eXtreme) vor.

Interpreterzielbytecode

SX

PowerPC

IntelX86

weitere

ByteCode

Zwischensprachen-Abbildung 8: Architektur SX 5 Entwurf SX (Squeak eXtreme)

Überblick

In diesem Kapitel stelle ich meinen neuen Entwurf für die Squeak virtuelle Maschine vor. Dieser versucht alle Anforderungen aus Kapitel 2.4 zu erfüllen.

Ziele

Die Ziele, an denen sich der neue Entwurf messen lassen muß, sind also

• Steigerung der Ausführungsgeschwindigkeit (mindestens so wie J3).

• Einfache Portierung.

• Einfacheres Experimentieren durch Implementierung in Smalltalk

• Verbesserung des erwarteten Verhaltens. Die drei zentralen Eigenschaften des SX-Entwurfs sind also:

Architekturüberlegungen

• Bytecode ist eine optionale Zielsprache, nicht Zwischensprache.

• Das System sollte in Squeak implementiert sein.

• Laufzeitübersetzung nicht Just in Time

Im folgenden werden diese Ideen weiter erläutert und gezeigt, welche weiteren Vorteile sich daraus ergeben.

Bytecode als Zielsprache

Der Ansatz von SX ist, die virtuelle Maschine genau wie auch die realen Maschinen als Zielsystem des Laufzeitübersetzers zu behandeln.

Daraus ergeben sich einige interessante Vorteile:

• Als Zwischensprache muß kein Bytecode mehr verwendet werden. 

Abbildung 5 :

 5 Abbildung 5: Struktur der virtuellen Maschine

3. 1 . 3 Interpreter

 13 Die virtuelle Maschine interpretiert einen kellerbasierten Bytecode, der im Hinblick auf Kompaktheit und eine relativ effiziente Interpretierbarkeit entwickelt wurde. Kompakt ist der Bytecode z. B. dadurch, daß die virtuelle Maschine extra Bytecodes für häufig vorkommende Folgen von einfachen Operationen bereitstellt. Effizient interpretierbar wird der Bytecode durch Sprungbefehle. Diese erlauben dem Smalltalk Übersetzer, die Methoden der Kontrollstrukturen wie ifTrue: oder whileTrue: offen einzubauen. Die insgesamt 248 verschiedenen Bytecodes lassen sich in folgende Gruppen gliedern: Keller Manipulation: Diese Bytecodes ändern den Keller der virtuellen Maschine: z. B. push bzw. pop von lokalen Variablen. Sprünge: Einige wenige Methoden werden offen eingebaut (z. B. ifTrue:). Dazu werden Sprungbefehle benötigt. Nachrichten versenden: Methodenaufrufe. Neben dem allgemeinen send Bytecode existieren einige extra Bytecodes für häufig vorkommende Aufrufe (z. B. sendAdd).

  

  

  

  Dieses Kapitel stellt das aktuelle Squeak-System kurz vor. Nach einem kurzen Überblick zeigt Abschnitt 2.4 die besonderen Anforderungen auf, die Squeak an die Implementierung der virtuellen Maschine stellt.Das Ziel des Smalltalk-Projektes, das Dynabook, wurde aber nie erreicht. Das Smalltalk-System wurde stattdessen in Richtung eines professionellen Entwicklungsystems weiterentwickelt und als solches 1983 kommerzialisiert.Squeak versteht sich als Fortführung des Smalltalk Projektes, es ist in gewisser Weise ein neuer Versuch, das Dynabook zu verwirklichen.2.3 Squeak im EinsatzDas Learning Research Institute entwickelt mit Squeak ein System, mit dem Kinder spielerisch mit neuen Ideen umgehen und diese lernen sollen. Das Squeak-System wird in Schulen (z. B. der Open Charter School in Los Angeles/USA) im Unterricht eingesetzt. Die Squeak-Umgebung erlaubt es den Kindern, spielerisch die im Mathematikunterricht gelernten Ideen kennen zu lernen. Dazu bietet Squeak eine graphische Skriptsprache, mit deren Hilfe sich sowohl einfache als auch komplexere Animationen und Simulationen erstellen lassen. Alle Änderungen an diesen Skripten sind sofort spürbar, man kann sehr einfach und mit wenig Aufwand verschiedene Möglichkeiten ausprobieren. Die Kinder können auch zur Laufzeit mit den erstellten Skripten experimentieren: Während das Programm läuft kann man Parameter ändern, neue Befehle hinzufügen oder ganze neue Skripte erstellen. Dadurch werden die Auswirkungen der einzelnen Änderungen sofort sichtbar. Man erkennt sehr schnell Zusammenhänge und Funktionsweisen der einzelnen Befehle. Das Ergebnis ist ein Auto, das programmgesteuert auf der Straße fährt. Wenn alle Kinder ihre Autos fertig entwickelt haben, veranstaltet die Klasse ein Autorennen: Die Autos werden zum Rechner des Lehrers gesendet, und schon kann das Rennen beginnen (siehe Abbildung 4). Unter dynamischer Metaprogrammierung versteht man die Änderung eines Programms durch ein zweites Programm (das Metaprogramm) zur Laufzeit. Ein Kind, das mit einem einfachen Squeak-Skript eine Animation erstellt, verwendet Squeak zur Metaprogrammierung: Mit Squeak wird ein Programm erstellt und ausgeführt. Die Metaprogrammierung ist dynamisch, da man das Programm nicht anhalten muß: Es lassen sich neue Methoden zu einem Objekt zur Laufzeit unter Beibehaltung des Zustandes hinzufügen. Natürlich ist auch die Änderung bestehender Methoden oder die Definition neuer Klassen zur Laufzeit möglich. Eine der Voraussetzungen für dynamische Metaprogrammierung ist, daß man die Ausführung eines Programms zu jeder Zeit anhalten, den Code verändern und dann das Programm weiterlaufen lassen kann.

	2 Das Squeak-System: 2.4 Technische Anforderungen
	Hintergrund und Anforderungen Als Konsequenz aus dem im vorigen Kapitel dargestellten Einsatz von
	Squeak als Lernmedium ergeben sich einige interessante technische Anfor-2.1 Überblick derungen, die das System erfüllen muß.
	2.4.1 Dynamische Metaprogrammierung
	2.2 Geschichte
	Abbildung 3: Ein programmiertes Auto in Squeak
	Dies hat sich gerade für ein Lernsystem als sehr wichtig erwiesen: Es erlaubt,
	sehr einfach den Ablauf eines Programms zu erforschen.
	Ein Edit-Compile-Run Zyklus, wie man ihn von vielen Programmierspra-
	Abbildung 1: Der Betrachter chen kennt, ist eher kontraproduktiv: Er macht jedes spielerisch-explorative
	Umgehen mit dem Entwicklungssystem unmöglich
	2.4.2 Portabilität
	Im Schulbetrieb kommen viele verschiedene Betriebsysteme zum Einsatz.
	Der Ausbildungsmarkt ist in den USA historisch bedingt immer noch sehr
	heterogen, da noch in weiten Teilen Apple-Systeme eingesetzt werden. In
	Deutschland finden langsam Linux-Systeme Verwendung in der Schule, da
	diese eindeutige Kostenvorteile bieten.
	Abbildung 2: Drehe das Auto um fünf Grad im Uhrzeigersinn
	Abbildung 4: Autorennen in Squeak

Das Squeak-Projekt wurde 1995 von einer kleinen Forschungsgruppe (geleitet von Alan Kay) bei Apple gestartet. Nach 5 Jahren bei Walt Disney Imagineering arbeitet die Gruppe nun selbständig als Viewpoints Research Institute 1 . Die Anfänge von Squeak lassen sich weiter bis ans Xerox PARC zurückverfolgen. Squeak basiert auf dem Smalltalk 80 System, das in den Jahren 1971 -1980 unter der Leitung von Alan Kay am Xerox PARC entwickelt wurde. Ziel des Smalltalk-Projektes war es, einen Computer für Kinder (das Dynabook) zu entwickeln, ein interaktives Buch. Das Smalltalk System war Prototyp für Betriebsystem, Benutzeroberfläche, Programmiersprache und Entwicklungssystem dieses Kindercomputers. Im Zuge des Smalltalk-Projektes wurde ein erstaunliches System geschaffen, das seiner Zeit weit voraus war: Es war das erste System mit einer modernen, fensterbasierten graphischen Benutzeroberfläche. Das System war mit der ersten modernen objektorientierten Programmiersprache nach Simula implementiert. Diese basierte, wie Java 20 Jahre später, auf einer bytecodebasierten virtuellen Maschine mit automatischer Speicherbereinigung. Als Beispiel dient im folgenden ein typisches Projekt für die fünfte oder sechste Klasse: Ein Auto soll von einem Programm gesteuert über eine Straße fahren. Nachdem das Kind ein Auto gemalt hat, kann es sich alle Befehle anzeigen lassen, die jedes Bildschirmobjekt beherrscht (mittels des Betrachters, siehe Abbildung 1). Wenn man einen dieser Befehle auf eine freie Stelle des Bildschirm zieht, entsteht ein neues Programm (siehe Abbildung 2). Abbildung 3 zeigt das Ergebnis des Projektes. Man erkennt drei Skripte: Eines bringt das Auto dazu, vorwärts zu fahren (Auto gehe vorwärts um 5), die beiden weiteren Skripte drehen das Auto in die richtige Richtung, um auf der Straße zu bleiben. Nach einem Klick auf den "

Go" Knopf werden die Skripte nun immer wieder, von einer globalen Uhr gesteuert, aufgerufen. Diese " tickende" Art der Methodenausführung erlaubt es, komplexe Kontrollstrukturen erst zu einem späteren Zeitpunkt einzuführen.

  Wie in Abschnitt 3.1.3 erläutert, verwendet Squeak einen relativ komplexen Satz von Bytecodes. Der Bytecode enthält z. B. Sprungbefehle für die offene Kodierung von Methoden. Außerdem gibt es eine Menge von Spezialbefehlen z. B. für arithmetische Operationen. Das aktuelle Squeak-System versucht die Anforderungen aus Kapitel 2.4 durch den Einsatz eines Bytecodeinterpreters zu erfüllen. Da ein Interpreter aber zu langsam ist, führt der Smalltalk-Übersetzer Optimierungen durch, die für den Benutzer nicht transparent sind. Diese Teile des Systems erfüllen die Anforderungen nicht. Das im folgenden Kapitel 4 beschriebene J3 Projekt implementiert einen Laufzeitübersetzer, der das Problem der schlechten Performanz des Interpreters angeht. Abschnitt 3.2.1 hat die schlechte Performanz der interpretierenden virtuellen Maschine als Problem identifiziert. Dieses Problem will der J3-Laufzeitübersetzer [19] durch Übersetzen des Bytecodes in Maschinencode zur Programmlaufzeit beheben. Die Arbeitweise und Eigenschaften von J3 beschreibt dieses Kapitel. Das Ziel des J3 Projektes ist, die Ausführungsgeschwindigkeit von Squeak durch Erzeugen von Maschinencode zur Laufzeit zu erhöhen. Der erzeugte Code soll eine hohe Qualität haben (d. h. er soll performant sein). Wichtig ist, daß sich der Compiler relativ einfach auf neue Architekturen portieren läßt. Der Squeak J3 wurde von Ian Piumarta (INRIA Rocquencourt) für PowerPC Systeme entwickelt und von mir im Zuge eines Praktikums bei Walt Disney Imagineering auf Intel x86 Systeme portiert.

	und realisiert dynamische Metaprogrammierung durch den Einsatz eines In-Änderung der Methode False>>ifTrue: (etwa zum Hinzufügen von Aus-
	terpreters. Auf den ersten Blick scheinen damit die Zielkriterien aus Kapitel 2.4 erfüllt, aber bei einer genaueren Betrachtung erkennt man viele Probleme. Das Per-Optimierung gaben zur Fehlersuche) niemals wirksam. Da die Optimierung nur für wenige, bereits existierende Spezialfälle erfolgt, können Kontrollstrukturen, die der Benutzer hinzufügt, nicht optimiert wer-SAM Codegenerierung code ByteCode und j3_interpret() Maschinen -
	formanzproblem des Interpreters diskutiert Abschnitt 3.2.1. Abschnitt 3.2.2 den.
	erläutert, warum das System durch nicht-transparente Optimierungen auch
	kein erwartetes Verhalten garantiert. 3.3 Zusammenfassung Abbildung 6: Architektur J3
	3.2.1 Performanz 4 J3: Ein Squeak-Laufzeitübersetzer
	4.1 Projektziele
	3.2.2 Erwartetes Verhalten
	3.2 Bewertung
	Schüler und Lehrer setzen die in diesem Kapitel vorgestelle virtuelle Ma-Das Problem ist, daß diese Optimierungen nicht transparent eingesetzt wer-schine auf verschiedenen Plattformen erfolgreich ein. Das System ist auf den: Der Smalltalk-nach-Bytecode Übersetzer (siehe [2]) implementiert of-aktueller (und damit schneller) Hardware ausreichend performant für den fenen Einbau von Methoden für wenige Spezialfälle (z. B. ifTrue:). Diese praktischen Einsatz. Die aktuelle virtuelle Maschine erfüllt die Kriterien aus Abschnitt 2 weitgehend: Das System ist hoch portabel, ausreichend schnell Spezialfälle sind hart im Übersetzer kodiert, daher wird beispielsweise jede

3.1.5 Portierung

Die virtuelle Maschine ist zu einem großen Teil in Slang implementiert, dies ist ein vereinfachter Smalltalk-Dialekt, der sehr einfach nach C übersetzt werden kann.

Neben dem so implementierten Interpreter, der automatischen Speicherbereinigung (Garbage Collector) und den primitiven Funktionen werden für eine vollständige virtuelle Maschine noch einige systemnahe Funktionen zur Ein-und Ausgabe (Netzwerk, Graphik, Maus, Tastatur) benötigt, insgesamt nur ca. 4000 Zeilen C-Code.

Einzig dieser überschaubare Teil der virtuellen Maschine ist spezifisch für das jeweils eingesetzte Betriebssystem, der weitaus größte Teil ist portabel. Da nur sehr wenig Code für ein neues System implementiert werden muß, ist Squeak mit sehr geringem Aufwand zu portieren (siehe [21]). Anfang 2001 lief Squeak auf ca. 20 Systemen, darunter alle Windows-Systeme, Unix und MacOS. Squeak wurde auch schon erfolgreich auf PDAs portiert, wie z. B. Sharp, Zaurus und PocketPC. Die Entscheidung, ein Multimedia-System mittels einer interpretierten Sprache zu implementieren, ist ungewöhnlich. Gerade bei Multimedia-Systemen wird eine hohe Leistung benötigt, da solche Systeme Graphik und Klang in Echtzeit verarbeiten müssen. Alle kritischen Teile des Systems wurden daher mittels primitiver Funktionen als Teil der virtuellen Maschine implementiert. Der Einsatz von primitiven Funktionen zur Geschwindigkeitssteigerung hat jedoch viele Nachteile. Primitive Funktionen liegen als Binärcode vor und sind damit nicht so einfach änderbar wie Smalltalk-Code: Die primitiven Funktionen sind Teil der virtuellen Maschine, nicht Teil der Klassenbibliothek. Für diese Teile gilt also keines der Zielkriterien außer einem: Sie sind schnell. Aber es ist keine Metaprogrammierung möglich, man kann den Code nicht anhalten und nicht modifizieren, ohne eine neue virtuelle Maschine zu erstellen. Das gesamte System ist dadurch wenig flexibel.

Codegenerierung

  Der Laufzeitübersetzer führt auf Basis des SAM-Zwischencodes einige einfache Optimierungen durch. Der Optimierer bringt die im Code vorkommenden Sprungbefehle in in eine Form, die es später dem Codegenerator ermöglichen, besseren Code zu erzeugen. Will man die Ausführungsgeschwindigkeit einer virtuellen Maschine beurteilen, so interessiert zum einen, wie schnell sie den Bytecode verarbeitet, also wieviele Bytecodes pro Sekunde eines realen, kleinen Programms sie ausführt. Dies der erste Meßwert des tinyBenchmarks (siehe erste Spalte in Tabelle 1). Programm verbringt einen großen Teil der Zeit mit der Ausführung dieser primitiven Funktionen, die der Übersetzer nicht beschleunigen kann. Die Beschleunigung des Gesamtsystems durch eine schnellere virtuelle Maschine reduziert sich daher um die Menge der primitiven Funktionen. Ein Ziel der Entwicklung des J3 war es, den Laufzeitübersetzer mit relativ geringem Aufwand auf neue Architekturen portieren zu können. Es wurde zuerst ein Backend für PowerPC Prozessoren implementiert. Zum Test der Portierbarkeit wurde das J3-System auf Intel x86 portiert. Das Ergebnis ist positiv: Der Aufwand betrug ca. 4 Monate für einen Entwickler, der weder mit Laufzeitübersetzern im allgemeinen noch J3 im besonderen vertraut war. Dabei ist aber zu beachten, daß der Laufzeitassembler CCG schon auf Intel Systemen eingesetzt wurde. Eine zusätzliche Portierung des Assembler, wie sie z. B. für Intel StrongARM nötig wäre, würde den Aufwand einer Portierung mindestens verdoppeln.

	Zur Generierung von Maschinenbefehlen werden dem Codegenerator Funk-Tabelle 1: Vergleich tinyBenchmarks PowerPC G4 (450Mhz) Tabelle 2: Vergleich macroBenchmarks PowerPC G4 (450Mhz) tionen bzw. Makros bereitgestellt, die von der Plattform abstrahieren und ei-ne prozessorunabhängige assemblernahe Sprache darstellen. Diese Routinen C Compiler Datei.ccg ccg Datei.c Datei.o Bytecodeausführung Methodenaufrufe müssen für jede Architektur implementiert werden. Als Laufzeitassembler Interpreter: Benchmark Decompile morphic tiles slang ctxstpSim 19393939 bytecodes/sec 880528 sends/sec wird CCG eingesetzt, der im nächsten Abschnitt näher beschrieben wird. Eine ausführlichere Beschreibung des J3-Übersetzers findet sich in [19]. J3-Übersetzer: Interpreter 44245 56616 71890 26059 52159739 bytecodes/sec 6575704 sends/sec Beschleunigungsfaktor: 2.7 7.47 Übersetzer 19835 34206 38587 12364
	Beschleunigungsfaktor 2.2	1.6	1.8	2.1
	ccg Header InterprSim browsers 4.2.3 Der Laufzeitassembler CCG Benchmark 4.3.1 Messung der Interpreterleistung Interpreter 6987 9402 Der Codegenerator muß den erzeugten Maschinencode direkt im Speicher FreeCel 7718 Abbildung 7: Der CCG Präprozessor Übersetzer 3740 6709 6930 erzeugen. Außerdem wird der Codegenerator bei der ersten Ausführung ei-ner Methode zur Laufzeit aufgerufen, die Codegenerierung muß daher auch Beschleunigungsfaktor 1.8 1.4 1.1
	sehr schnell geschehen. Der Laufzeitübersetzer kann also nicht, wie bei stati-Der Präprozessor CCG ersetzt diese innerhalb der eckigen Klammern durch
	schen Übersetzern üblich, den vom Betriebsystem bereitgestellten Assembler die entsprechenden Makrobefehle für den C Präprozessor:
	nutzen.			
	Ein Beispiel ist ein vom Smalltalk-Übersetzer erzeugter bedingter Rück-
	sprung:			
	label: ....			
			jumpTrue: label
	... *(char *)(someAdress)	= 0xB8; /* insn: move imm32 -> %eax */
	*(char *)(someAdress + 1) = 0x2A; /* constant: 42 */
	Dieser läßt sich umformen in einen bedingten Vorwärtssprung und einen
	unbedingten Rücksprung, die die Sprungvorhersage korrekt erkennen kann: Der C-Übersetzer kann den Code also so stark optimieren, daß er zur Erzeu-
	gung von Maschinenbefehlen zur Laufzeit nur Konstanten in den Speicher
	label: schreiben muß.	....		
			jumpFalse: label2
	label2: 4.3 Performanz ...	jumpTo: label
	Anschließend findet eine weitere einfache Optimierung während der Code-generierung statt. Verwendet wird eine Form der Codegenerierung mit Ma-Die erreichte Steigerung der Ausführungsgeschwindigkeit ist trotz des einfa-4.2.4 Beispiel chen Codegenerators schon sehr zufriedenstellend.
	schinensimulation (Delayed Code Generation (DCG) siehe [22]). Das folgende Beispiel verdeutlicht die Funktionsweise des CCG-Zur Messung der Leistungsteigerung der virtuellen Maschine enthält die
	Laufzeitassemblers. Squeak-Klassenbibliothek zwei verschiedene Benchmarks. Einer ermittelt die 4.3.2 Leistung des Gesamtsystems Die Maschinensimulation simuliert eine Kellermaschine, alle Operanden der Maschine werden mittels Deskriptoren beschrieben. Leistung der virtuellen Maschine, der zweite zeigt die Leistung des Gesamt-Gegeben sei die Assembleranweisung: Die Leistung des Gesamtsystems messen die sogenannten macroBenchmarks, systems. Mit Hilfe eines simulierten Kellers kann der Codegenerator so zur Überset-die eher die in realen Programmen zu erwartende Geschwindigkeitssteige-
	zungzeit konstante Ausdrücke berechnen. #[ movl $42, %eax ]# rung wiedergeben. Bei den macroBenchmarks werden Squeak-Programme

Der Squeak J3 verwendet als Laufzeitassembler den von Ian Piumarta entwickelten CCG (siehe

[START_REF] Piumarta | ccg: a Tool for Writing Dynamic Code Generators[END_REF]

). Dies ist ein Präprozessor, der es erlaubt, Assembleranweisungen direkt in C (bzw. C++) Code einzubetten. Die Assembleranweisungen werden dann mit Hilfe des CCG-Präprozessors durch ANSI-C Präprozessormakros ersetzt, die der C-Übersetzer als konstant erkennt und zu einfachen und effizienten Zuweisungen umformt. Abbildung 7 zeigt den Einsatz von CCG im Überblick: Ziel ist ein Programm, das seinen eigenen Code im Speicher manipuliert. Dazu wird ein C-Programm mit CCG-Anweisungen erstellt (Datei.ccg in Abbildung 7). Der CCG-Präprozessor erzeugt daraus ein C-Programm (Datei.c), das Makro-Definitionen des CCG-Systems verwendet. Der C-Präprozessor und C-Übersetzer erzeugen dann das Endprodukt: Ein ausführbares Programm, das selber zur Laufzeit neuen ausführbaren Maschinencode erzeugen kann (Datei.o). MOVLir(42,_EAX); Das Makro MOVLir wird in den vom CCG-System [20] bereitgestellten C-Header Dateien definiert. Nach Optimierung entspricht dies folgendem C-Code: Zum anderen ist aber auch die Geschwindigkeit von Methodenaufrufen entscheidend: Der Smalltalk-Übersetzer baut nur wenige Methoden offen ein: Einzig einige bestehende Sprachkonstrukte wie Schleifen und If-Abfragen optimiert er zu Sprüngen. Jeden anderen Methodenaufruf kann er nicht optimieren, ein effizienter Aufruf von Methoden (send) ist daher sehr wichtig. Der zweite Meßwert des tinyBenchmarks gibt daher die Anzahl von Methodenaufrufen pro Sekunde an (siehe zweite Spalte in Tabelle 1). Der Quellcode des Benchmarks findet sich in Anhang A. Der tinyBenchmark gibt die Leistungsfähigkeit der virtuellen Maschine wieder, aber er testet lediglich die Ausführungsgeschwindigkeit unter der Voraussetzung, daß ausschließlich Bytecode ausgeführt wird. Dies ist aber in einem realen Programm niemals der Fall: Alle zeitkritischen Teile des Systems sind als primitive Funktionen implementiert. Ein Squeak-als Benchmark verwendet, die auch im normalen Alltag auftreten. Dazu zählen unter anderem das Übersetzen von Smalltalk-Code, das Generieren von C-Code für den Interpreter und einige weitere alltägliche Aktivitäten, wie z. B. das Öffnen mehrerer Editoren. Tabelle 2 zeigt, daß die bei diesem Benchmark beobachtete Beschleunigung weit hinter den tinyBenchmarks zurückbleibt.

4.4 Portabilität

  Laufzeitübersetzer nur Maschinencode erzeugen kann, kann man ihn nur einsetzen, wenn die Zielmaschine unterstützt wird. In allen anderen Fällen muß man auf den Interpreter zurückgreifen. Aber ein Übersetzer kann ja nicht nur Code für existierende Maschinen, sondern auch für die virtuelle Maschine erzeugen (siehe Abbildung 8). In diesem Fall wären die Optimierungen des Smalltalk-nach-Bytecode-Übersetzers nicht mehr nötig. Die Optimierungen finden dann vollständig transparent im Optimierer des Laufzeitübersetzers statt. Der J3-Übersetzer war in C++ implementiert. Dies hat einige Nachteile gezeigt: Zur Entwicklung kann man die mächtige Squeak-Entwicklungsumgebung nicht verwenden, die Fehlersuche ist daher sehr schwierig. SX soll deshalb in Smalltalk, nicht C++, implementiert sein. Der Hauptgrund für die Entscheidung, C++ als Implementierungssprache für J3 zu verwenden, war die benötigte Geschwindigkeit des Laufzeitübersetzers. Der J3 generiert Code nur zur Laufzeit, direkt vor Ausführung einer Methode. Dagegen soll der SX-Entwurf prüfen, ob man nicht den einmal übersetzten Code speichern kann. Durch einen inkrementellen Ansatz könnte so der Einfluß der Geschwindigkeit des Laufzeitübersetzers auf die interaktiven Eigenschaften gemindert werden.

	durchführt. Wenn ein Laufzeitübersetzer vorhanden ist, kann man auf diese
	Optimierungen aber vollständig verzichten: Es existiert dann ja schon ei-
	ne Optimierung innerhalb des Laufzeitübersetzers. Für Optimierungen auf
	Bytecode-Ebene besteht daher kein Grund, sobald der Laufzeitübersetzer
	zur Anwendung kommt. Da der J3-
	Die grundlegende Idee der SX-Architektur ist, die Vorteile, die ein Lauf-
	zeitübersetzer bietet, für weitere Verbesserungen auszunutzen. Das J3-
	Projekt hat gezeigt, daß ein Laufzeitübersetzer sinnvoll ist. J3 war aber
	nicht vollständig ins System integriert: Das Ziel war, die Ausführung des
	bestehenden Bytecodes zu beschleunigen.
	Eine sehr problematische Eigenschaft des Squeak-Systems sind die Op-
	timierungen für Spezialfälle, die der Smalltalk-nach-Bytecode-Übersetzer

•

  Es wird möglich, den generierten Bytecode, wie auch den Binärcode, vom Laufzeitübersetzer optimieren zu lassen.Die Verwendung von Bytecode als Zwischensprache bei Smalltalk und Java ist für eine virtuelle Maschine mit Laufzeitübersetzer eher negativ: Kellerbasierter Bytecode ist denkbar schlecht geeignet als Zwischensprache für einen Übersetzer. Daher ist der erste Schritt aller Laufzeitübersetzer, aus dem Bytecode wieder eine für Optimierungen geeignete Zwischenrepräsentation zu gewinnen.Wenn der Laufzeitübersetzer auch Code für die virtuelle Maschine erzeugen kann (für den Fall, daß der Prozessor der Zielmaschine nicht unterstützt wird), dann gibt es keinen Grund, einen komplexen, einfach zu interpretierenden aber schwierig zu übersetzenden Bytecode als Zwischensprache zu verwenden. Daher verwendet das SX-System einen sehr stark vereinfachtem Bytecode, der möglichst nahe an der Sprache Smalltalk ist. Insbesondere enthält er keine Optimierungen. Alle Optimierungen führt der SX-Laufzeitübersetzer auf einer SSA-basierten Zwischendarstellung durch, die er aus dem Eingabebytecode erzeugt.Die Sprache Slang ist aber so stark vereinfacht (keine Polymorphie, keine Objekte), daß man viele der Vorteile von Smalltalk nicht nutzen kann.Eine sehr interessante Möglichkeit wäre, den Übersetzer direkt, sozusagen reflexiv in Squeak zu implementieren: Nach dem Start interpretiert ein einfacher Interpreter den Laufzeitübersetzer, während dieser sich selber übersetzt. Nach dieser ineffizienten Startphase würde der Interpreter nicht mehr eingesetzt, sondern jetzt kann der nun in Maschinensprache vorliegende Laufzeitübersetzer die Ausführung vollständig übernehmen.Wenn eine Methode das erste mal aufgerufen wird (oder wenn sie aus dem Cache gelöscht wurde), erzeugt ein schneller Übersetzer just in time den entsprechenden Code. Dabei wird die Ausführung des Programms angehalten.Das entscheidende Entwurfskriterium für Laufzeitübersetzer ist also einzig die Geschwindigkeit, mit der sie Code generieren können. Alles andere muß sich diesem Ziel unterordnen. Es ist klar, daß Geschwindigkeit bei der Übersetzung meist auf Kosten der Geschwindigkeit des erzeugten Codes erkauft wird: Ein Just-In-Time-Übersetzer kann nur triviale Optimierungen durchführen.Will man aufwendige Optimierungen durchführen, so muß man auf ein zweistufiges System zurückgreifen: Ein Compiler erzeugt schnell schlechten Code, chert.Ein solcher Entwurf erlaubt es, eine virtuelle Maschine zu implementieren, die alle Vorteile eines statischen Übersetzers mit denen eines Laufzeitübersetzers verbindet. Insbesondere kann man aufwendige Optimierungen durchführen.5.4 Weitere KonsequenzenDer in diesem Kapitel vorgestelle Entwurf eines Squeak-Laufzeitübersetzers könnte noch einige weitere interessante Vorteile haben, die nicht direkt mit der virtuellen Maschine in Zusammenhang stehen. Interessant dabei sind zwei Aspekte: Die Wiederverwendung des Übersetzerrahmenwerks für einen statischen Übersetzer und die Auswirkungen einer AST-basierten Zwischensprache auf die Entwicklungsumgebung.5.4.1 Ein statischer Smalltalk ÜbersetzerMit Hilfe des Übersetzerrahmenwerks kann man sehr einfach einen statischen Smalltalk-Übersetzer erstellen. Diesen kann man z. B. dazu einsetzen, einen einfachen Interpreter zu erstellen, der zum Bootstrapping des Systems benötigt wird.5.4.2 Anbindung von Werkzeugen über die ZwischenspracheDie Squeak-Kinder-Skriptsprache Etoys erlaubt es, jede Methode des Systems als graphisches Skript darzustellen und zu manipulieren. Für diese Funktionalität erstellt der Zerteiler des Smalltalk-nach-Bytecode-Übersetzers eine AST-Darstellung. Dieser Mechanismus kann durch eine ASTbasierte Zwischensprache stark vereinfacht und besser ins System integriert werden.Auch viele Werkzeuge wie z. B. der Refactoring Browser[START_REF] Bradley | Practical Analysis for Refactoring[END_REF] arbeiten auf Basis einer Baumdarstellung. Auch hier könnte die AST-Zwischendarstellung hilfreich sein.In dieser Studienarbeit habe ich die Anforderungen dargestellt, die bei der Implementierung des Kinderprogrammiersystems Squeak auftreten. Nach einem kurzen Überblick über die aktuelle interpreterbasierte Implementierung habe ich gezeigt, daß diese die Anforderungen nur bedingt erfüllt.Zwei Verbesserungen wurden diskutiert: Der Laufzeitübersetzer J3 und mein darauf aufbauender, verbesserter Entwurf (SX).Der von mir im Rahmen eines Auslandspraktikums auf Intel-Rechner portierte Laufzeitübersetzer J3 hat gezeigt, daß ein schwerwiegendes Problem des Squeak-Systems, die mangelnde Performanz des Interpreters, durch einen relativ einfachen und portablen Laufzeitübersetzer verbessert werden kann.Das J3-Experiment hat aber auch weitere Probleme aufgezeigt. Diese führen zu einem neuen Entwurf, der versucht, alle dargestellen Probleme zu lösen. Grundlage des SX Systems ist die Idee, daß der Laufzeitübersetzer nicht Maschinencode, sondern auch Bytecode generieren kann. Dies erlaubt eine Vereinfachung des verwendeten Zwischencodes im Squeak-System. Dadurch können die Probleme gelöst werden, die durch nicht transparente Optimierungen des Squeak-Bytecodes entstanden sind.

	5.3.2 Übersetzer in Smalltalk 6 Zusammenfassung
	Die aktuelle virtuelle Maschine ist in einer Teilmenge von Smalltalk (Slang)
	implementiert, die nach C übersetzt wird. Diese Lösung erlaubt es, die
	virtuelle Maschine mit der mächtigen Entwicklungsumgebung des Squeak-
	Systems zu entwickeln. Die hat sich besonders bei der Fehlerbehebung als
	sehr hilfreich herausgestellt.
	Alternativ kann man den abstrakten Syntaxbaum direkt als Zwischenspra-5.3.3 Laufzeitübersetzer ohne JIT
	che verwenden. Franz zeigt in [6], daß ein komprimierter AST sogar kom-
	pakter ist als typische bytecodebasierte Codierungen. Gegen die Verwendung Die meisten Laufzeitübersetzer speichern den generierten Code nicht dauer-
	eines AST als Zwischensprache spricht, daß man in diesem Fall die Werzeu-haft, sondern verwenden einen sehr kleinen Cache (meist weniger als 1MB),
	ge der Squeak-Entwicklungsumgebung wie z. B. den Debugger nicht mit in dem sie den Maschinencode nach einer LRU-Strategie verwalten. Dieser
	geringem Aufwand anpassen kann. Cache wird insbesondere nicht auf dem Hintergrundspeicher gesichert, der
	Neben einer besseren Zwischensprache erlaubt dieser Entwurf auch, den By-Code muß also mindestens bei jedem Programmstart neu generiert werden.
	tecode durch den Laufzeitübersetzer optimieren zu lassen. Fast alle typischen
	Optimierungen, die ein Übersetzer durchführt, sollten auch dann eine Ge-
	schwindigkeitsteigerung zur Folge haben, wenn Code für einen Interpreter
	generiert wird. Den Squeak-Bytecode und die virtuelle Maschine muß man
	in diesem Fall aber anpassen. Man kann beispielsweise vorkommende Auf-
	rufziele im Bytecodestrom direkt puffern, um diese statistische Information
	bei der Codegenerierung ausnutzen zu können.
	In einem solchen System besteht insbesondere kein Grund mehr für die in
	Kapitel 3.2.2 kritisierten Optimierungen des Bytecodes: Diese kann der Op-
	timierer des Laufzeitübersetzers transparent durchführen.

Der experimentelle Java JIT-Compiler OpenJIT hat gezeigt, das ein solcher Entwurf tatsächlich praktisch zu verwirklichen ist (siehe

[START_REF] Ogawa | OpenJIT: An Open-Ended, Reflective JIT Compiler Framework for Java[END_REF] 

und

[START_REF] Matsuoka | OpenJIT -A Reflective Java JIT Compiler[END_REF]

), daher wird das SX-System diesen Ansatz verfolgen.

www.viewpointsresearch.org

Diese Idee wurde vom Self-Projekt (siehe [START_REF] Chambers | An Efficient Implementation of SELF a Dynamically-Typed Object-Oriented Language Based on Prototypes[END_REF] und [START_REF] Ungar | Self: The power of simplicity[END_REF]) als erstes implementiert und wird heute bei einigen modernen Java-Systemen eingesetzt (z. B. Sun HotSpot [START_REF] Detlefs | The Case for Multiple Compilers[END_REF]).

Die IBM Jalapeno/Jikes Research VM (siehe [