Laufzeitverhalten und Portierungsaspekte der Java Virtual Machine (JVM) und ausgewa"hlter Java-Bibliotheken Marc Schanne Eine Studienarbeit am Institut fu"r Programmstrukturen und Datenorganisation Betreuer: Dr. Michael Philippsen (IPD), Ralf J. Sch"afer (Siemens AG, Mu"nchen) Universit"at Karlsruhe 26. Februar 1997 Zusammenfassung Die Programmiersprache Java von Sun Microsystems hat innerhalb ku"rzester Zeit die sch"on geordnete Welt der Softwareentwicklung durcheinander geworfen. Objektorientiert, sicher, robust und portabel, soll das Java-System die Entwicklungsplattform der Zukunft sein. Eine Komponente des Java-Systems ist die Java Virtual Machine (JVM), die Spezifikation fu"r eine abstrakte stack-basierte Maschinenstruktur. Diese Arbeit stellt das Modell der JVM vor und untersucht und vergleicht die M"oglichkei- ten und Grenzen von JVM auf verschieden Plattformen. Das Laufzeitverhalten unterschied- licher JVM-Implementierungen wird anhand einer Sammlung von Testprogrammen gemes- sen und verglichen. Zus"atzlich sind Konzepte wie Just-in-Time-U"bersetzung oder die Ver- wendung von Native-Routinen zur beschleunigten Ausfu"hrung von Programmen Inhalt der "Uberlegungen. In einem zweiten Teil wird das Abstract Window Toolkit (der JDK 1.0.2) als gr"osste Java Bibliothek betrachtet und M"oglichkeiten der Portierung auf andere Hardwareplattform und Betriebssystem untersucht. Quem in ipsa re trepidare nolueris, ante rem exercas - Seneca Inhaltsverzeichnis 1 Einleitung 3 1.1 Java-Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Beispiele im WWW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 M"oglichkeiten und Grenzen . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Just in Time-Compiler (JITC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Laufzeitintensive Anwendungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Das Java-System 5 2.1 Die Programmiersprache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Die Java Virtual Maschine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 Die Kernbibliotheken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.4 Die Implementierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.5 JDK 1.0.x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Laufzeitverhalten verschiedener JVM 10 3.1 Allgemeine "Uberlegungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2 Benchmark-Programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.3 U"berlegungen zur Programmiersprache Java . . . . . . . . . . . . . . . . . . . . 13 3.4 Test-Bedingungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.4.1 Die drei Testplattformen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.4.2 Sonstige Festlegungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.5 Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.6 Ergebnisse von CaffeineMark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4 Laufzeitverbesserungen 27 4.1 Natives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2 JIT/ Ahead-of-Time-(Re)Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3 Andere Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.3.1 Teilauslagerung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.3.2 Vollimplementierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5 Portierung von Bibliotheken 35 5.1 Abstract Window Toolkit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.1.1 java.awt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 1 5.1.2 java.awt.peer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.1.3 sun.awt.win32 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.1.4 Alternativen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.2 Weiterfu"hrendes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6 Zusammenfassung und Ausblick 42 A Programme 43 B Messwerte der Benchmarks 66 C Verwendete Abk "urzungen 70 2 Abbildungsverzeichnis 2.1 Komponeten des Java-Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Verzeichnisstruktur JDK 1.0.2 fu"r Windows: share-Zweig . . . . . . . . . . . . 8 2.3 Verzeichnisstruktur JDK 1.0.2 fu"r Windows: win32-Zweig . . . . . . . . . . . . 9 3.1 Abstrakte Ebenen bei Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2 OMT-Diagramm: PrimeBenchmark . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.3 Berechnungsbeispiel der Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.4 Ergebnisse SPARCstation 4 - Solaris, alle Benchmarks . . . . . . . . . . . . . . . 19 3.5 Ergebnisse Pentium 90 - Windows 95, alle Benchmarks . . . . . . . . . . . . . . 20 3.6 Ergebnisse Pentium 90 - Linux, alle Benchmarks . . . . . . . . . . . . . . . . . . 23 3.7 Ergebnisse mit Netscape auf allen Plattformen, alle Benchmarks . . . . . . . . . 24 3.8 Ergebnisse mit JDK 1.0.2 auf allen Plattformen, alle Benchmarks . . . . . . . . . 24 3.9 Ergebnisse von CaffeineMark 2.5: JVM ohne JITC . . . . . . . . . . . . . . . . . 25 3.10Ergebnisse von CaffeineMark 2.5: JITC . . . . . . . . . . . . . . . . . . . . . . . . 26 4.1 Abstrakte Ebenen von Java: Java Bytecode . . . . . . . . . . . . . . . . . . . . . 27 4.2 Abstrakte Ebenen von Java: Java Virtual Machine (JVM) . . . . . . . . . . . . . 31 4.3 Interpretation vs JITC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.4 Abstrakte Ebenen von Java: Hardware, Betriebssystem . . . . . . . . . . . . . . 33 5.1 OMT-Diagramm: java.awt.* . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.2 Struktur der java.awt.peer-Interfaces . . . . . . . . . . . . . . . . . . . . . . 37 5.3 OMT-Diagramm: sun.awt.*.MToolkit . . . . . . . . . . . . . . . . . . . . . 38 5.4 Baumstruktur der BISS-AWT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3 Kapitel 1 Einleitung 1.1 Java-Benchmarks Der Siegeszug der Programmiersprache Java steht in engem Zusammenhang mit der M"oglichkeit mit ihr plattformunabh"angige Programme fu"r das Internet zu entwickeln. Die- se sind als Applets im Fenster eines World Wide Web-Browsers ausfu"hrbar. Mit Applets lassen sich nicht nur Web-Seiten interaktiver gestalten, sondern es ist m"oglich beliebige Programme auszufu"hren. In Folge einer richtigen Java-Euphorie sind deshalb auch in Java geschriebene Benchmark-Applets entstanden. Es genu"gt der Abruf einer URL (Uniform Resource Locator) und schon kann man die Leistungsf"ahigkeit seines eigenen Systems testen. 1.1.1 Beispiele im WWW Im Folgenden sind die drei derzeit wichtigsten Java-Benchmarks aufgelistet: fflLinpack1, von Jack Dongarra und Reed Wade, ist schon lange als Fortran oder C/C++-Benchmark zu haben [Dong96], und die Java-Version ist deshalb besonders ausgereift. Auch wenn der direkte Vergleich mit den Leistungszahlen herk"ommlicher Compiler schwierig ist, erm"oglichen die numerischen Tests den Performance-Vergleich verschiedener JVM. fflCaffeineMark2 und der Java Performance Report ist der derzeit wohl am h"aufigsten zitierte Test, wenn es um Java und die JVM geht. Auf die Ergebnisse von CaffeineMark 2.5 geht der Abschnitt 3.6 ein. fflBenchBeans3 _ von Holger Reckter _ ist ein weiterer Benchmark, der versucht, alle Aspekte der Java-Performance, einschliesslich Grafik zu behandeln. 13 Einzeltests ermitteln Vergleichswerte fu"r Arithmetik, Grafik, Speicher-Allozierung, Methoden und Text. ________________________________1 http://www.netlib.org/benchmark/linpackjava/ 2http://www.webfayre.com/pendragon/cm2/caffainemark2.html 3http://user.cs.tu-berlin.de/"mondraig/english/benchbeans.html 4 Eine gute "Ubersicht aller WWW-Ressourcen zum Thema gibt es bei Jonathan Hard- wick4. 1.1.2 M"oglichkeiten und Grenzen Durch das Sammeln m"oglichst vieler Ergebnisse versuchen s"amtliche Web-Java-Benchmarks eine Vergleichsm"oglichkeit verschiedener Rechnerplattformen und Interpreter zu erreichen. Die Testbedingungen sind bei dieser Vorgehensweise natu"rlich nicht immer klar festgelegt, und deshalb sind die Ergebnisse auch nur eingeschr"ankt brauchbar. Zumindest l"asst sich so aber die Leistung einer JVM einordnen. 1.2 Just in Time-Compiler (JITC) Um die Maschinenunabh"angigkeit eines Java-Programms zu gew"ahrleisten, erzeugt der Compiler ein architekturneutrales Objektdateiformat. Dieser Bytecode wird dann vom Java- Laufzeitsystem ausgefu"hrt (vgl. Abschnitt 2). Er wird interpretiert, und dies bedingt, dass die Ausfu"hrgeschwindigkeit langsamer ist, als die eines in C geschriebenen, "ubersetzten und gebundenen Programms. Ein Versuch diesen Nachteil auszugleichen sind sogenannte Just in Time-U"bersetzer (JITC), die den zu interpretierenden Java-Bytecode direkt vor der Ausfu"hrung in nativen Code "ubersetzen und so auch Hardware- oder systembedingte Vorteile nutzen k"onnen (vgl. dazu Abschnitt 4.2). Diese Studienarbeit untersucht in Kapitel 3, die so zu erreichende Leistungs- steigerung gegenu"ber der einfachen Interpretation zu ermitteln. 1.3 Laufzeitintensive Anwendungen Trotz st"andiger Ver"anderungen beruht die Existenzberechtigung vieler Computersysteme darauf, dass sie in der Lage sind, schnelle und genaue numerische Berechnungen zu realisieren. Auch die in dieser Studienarbeit ausgewerteten Benchmarks (vgl. Abschnitt 3.2) gehen deshalb von mathematischen Objekten aus: Matrizen, Polynome und Listen und bewerten die Rechenzeit fu"r verschiedene Routinen, wie Matrixmultiplikation oder Sortieren von Listen. ________________________________4 http://www.cs.cmu.edu/"jch/java/optimization.html 5 Kapitel 2 Das Java-System Java ist mehr als nur eine Programmiersprache, sie ist vielmehr ein "Technologiekonzept" [Dahl97]. Das Java-System beinhaltet ebenfalls ein Konzept fu"r ein abstraktes Maschinen- modell und eine Spezifikation der Kernbibliotheken. Die folgenden Abschnitte stellen diese Konzepte kurz vor und zeigen anhand des Java Development Kits 1.0.x (JDK) von JavaSoft wie diese Modelle real implementiert werden k"onnen. 2.1 Die Programmiersprache Die Sprache Java wurde seit 1990 bei Sun Microsystems entwickelt. In ihrer Syntax "ahnelt sie sehr C und C++ und ist vollst"andig objektorientiert. Fu"r weitergehende Informationen gibt es von Sun The Java Language Specification [Sun95a] und The Java Language: A White Paper [Sun94]. Fu"r eine Einfu"hrung mit Referenz ist [Flan96] gut geeignet. 2.2 Die Java Virtual Maschine Zus"atzlich zur Spezifikation der Sprache hat Sun Microsystems auch The Java Virtual Maschine Specification [Sun95b] festgelegt. Die JVM ist eine abstrakte stack-basierte Maschine und besteht aus folgenden Komponen- ten: fflMaschienenbefehlssatz fflRegister fflLaufzeitumgebung fflDatenspeicher (Stack, Heap) Zur Implementierung sagt Sun folgendes: All of these are logical, abstract components of the virtual machine. They do not presuppose any particular implementation technology or organization, but their functionality must be supplied in some fashion in every Java system based on this virtual machine [Sun95b]. 6 In der Spezifikation wird deshalb auch nur die Funktionalit"at und Begrenzung der Systemkomponenten beschrieben. Eine erweiterte Darstellung wird in [TiYe96] und [Dahl97] gegeben. Die einzige Festlegung, die fu"r einen konkreten Interpreter von Java-Bytecode getroffen wird, ist folgender Pseudo-Code-Abschnitt: do f fetch a byte execute an action depending on the value of the byte g while (there is more to do); Der Interpreter erh"alt eine Folge von "ubersetztem Java-Code und fu"hrt byteweise die Befehle der virtuellen Maschine aus. Teil der JVM-Spezifikation ist auch die Festlegung des Class File Format, in dem der Bytecode abgelegt ist. Es erm"oglicht den Austausch von u"bersetztem Code mit jeder beliebigen Plattform. 2.3 Die Kernbibliotheken Mit der Entwicklung von Kernbibliotheken1 und der Schnittstellen-Spezifikation versucht JavaSoft eine auf allen Plattformen gleiche Java-Umgebung (vgl. auch [Sun95c]) festzulegen. Das in Abschnitt 5.1 n"aher beschriebene Abtract Window Toolkit (AWT) ist eine der ersten Bibliotheken und schon in der JDK 1.0.x enthalten. Ab der Version 1.1 sollen noch andere in die Standard-Distribution aufgenommen werden. 2.4 Die Implementierung Abbildung 2.1 skizziert die Zusammenh"ange der einzelnen Komponeten des Java-Systems. Der Java-Compiler "ubersetzt Java-Code in Bytecode, entsprechend der JVM-Spezifikation. Um diesen auszufu"hren, werden dann ein Java-Interpreter und die Kernbibliotheken ge- braucht. Um auf einer beliebigen Plattform eine vollst"andige Java-Laufzeit-Umgebung zu unterstu"tzen, mu"ssen die gestrichelt gezeichneten Teile implementiert werden. Am Beispiel des Java Development Kits (JDK) von JavaSoft wird im n"achsten Abschnitt eine Implementierung der JVM vorgestellt. Die JVM-Spezifikation l"asst sich aber auch als Hardware realisieren; ein Beispiel dafu"r ist der Pico-Chip von Sun Microsystems.2 Im Folgenden wird der Begriff Java Virtual Maschine (JVM), wie im allgemeinen Sprach- gebrauch "ublich, fu"r die Implementation der Spezifikation verwendet. ________________________________1 http://www.javasoft.com/products/apiOverview.html 2http://www.sun.com/sparc/java/ 7 Abbildung 2.1: Komponeten des Java-Systems 8 Abbildung 2.2: Verzeichnisstruktur JDK 1.0.2 fu"r Windows: share-Zweig 2.5 JDK 1.0.x Die JDK 1.0.x von JavaSoft wurde gem"ass der JVM-Spezifikation entwickelt. Sie ist fu"r Windows 32 Bit Plattformen und fu"r Solaris erh"altlich.3 Der Quellcode ist in einen plattformunabh"angigen (vgl. Abbildung 2.2) und in einen -abh"angigen Teil (vgl Abbildung 2.3) gegliedert. Beide besitzen ein java- und ein sun- Unterverzeichnis. In den beiden java-Verzeichnissen sind alle Funktionen der Sprache und des Interpreters gesammelt. In javanruntime, javanutil und javanjang sind die Hauptteile der JVM implementiert. Die Verzeichnisse javanjava enthalten nur Java-Code; aufbauend auf Funktionen in C (z. B. in javanruntime) werden hier die Klassen der Kernbibliotheken implementiert oder Schnittstellen definiert. Der sun-Zweig in beiden Abbildungen ist "ahnlich aufgebaut. In den direkten Unterver- ________________________________3 Die Executeables sind bei JavaSoft (http://www.javasoft.com) frei erh"altlich. Aber auch der Source-Code ist unter bestimmten Bedingungen (http://java.sun.com/nav/business/license_dl.html) frei erh"altlich. JavaSoft f"ordert so die Portierung auf andere Systemplattformen. Nach einer Funktions-Kontrolle kann von jeder Portierung die "Ubersetzung frei zur Verf"ugung gestellt werden. F"ur Firmen gibt es die M"oglichkeit der kommerziellen Lizensierung. 9 Abbildung 2.3: Verzeichnisstruktur JDK 1.0.2 fu"r Windows: win32-Zweig zeichnissen von sun (debug, gif, images, ... und awt_common, mfc, ...) wird in C/C++ Funktionalit"at implementiert, auf die in den Java-Klassen in sunnsunn* zugegriffen wird. Sun/Javasoft bietet hier neben der Implementierung fu"r das AWT auch noch zus"atzliche Tools, wie einen Debugger und Compiler. Der Java-Compiler ist direkt in Java geschrieben (sun.tools.javac.Main) und kann deshalb mit jeder JVM-Implementierung verwendet werden. Die in Abbildung 2.3 zus"atzlich markierten Verzeichnisse beinhalten den plattform- abh"angigen Programmcode fu"r das AWT, dessen Struktur und Portierung in Abschnitt 5.1 n"aher betrachtet wird. Die hier beschriebene Struktur der JDK 1.0.x stellt nur eine Implementierung der JVM- Spezifikation dar, aber viele Software-Hersteller haben ihre Produkte auf diese aufgebaut. 10 Kapitel 3 Laufzeitverhalten verschiedener JVM Die Java Virtual Machine (JVM) spielt eine zentrale Rolle bei der Portabilit"at von Java. Sie stellt eine Abstraktionsschicht zwischen "ubersetztem Java-Programm (Bytecode) und der zugrundeliegenden Hardwareplattform mit Betriebssystem zur Verfu"gung. Die Abbildung 3.1 stellt diese Modell vereinfacht dar. 3.1 Allgemeine "Uberlegungen Ziel der Testprogramme ist es, die Leistungsf"ahigkeit von JVM-Implementierungen auf verschiedener Hardware und Betriebssystemen zu vergleichen. Die Benchmark Sammlung (Anhang A) beinhaltet mathematische Problemstellungen, wie das Primzahlensieb des Erathostenes oder die Multiplikation von Matrizen und Polyno- men. Die Performance des Benutzerinterfaces oder auch die grafische Leistungsf"ahigkeit wer- den nicht betrachtet. Hier h"angen bessere Testergebnisse meist mehr vom zugrundeliegenden System als von der JVM-Implementierung ab. X-Window und andere Client/Server-Grafik- Subsystemen geben anders, wie zum Beispiel die Grafikoberfl"ache von Windows 95, schon vor der kompletten Anzeige grafischer Elemente die Kontrolle an das Programm zuru"ck. Dies verhindert eine genaue Zeitmessung und auch der Vergleich dieser beiden grundlegend ver- schiedenen Systeme ist schwer m"oglich. Bei den einzelnen Benchmarks wurde Wert darauf gelegt, unterschiedliche Programmier- techniken (Rekursion, grosse Arrays, etc.) zu verwenden. Abbildung 3.1: Abstrakte Ebenen bei Java 11 Abbildung 3.2: OMT-Diagramm: PrimeBenchmark 3.2 Benchmark-Programme Das Diagramm1in Abbildung 3.2 zeigt beispielhaft am Primzahlen-Benchmark (PrimeBench mark) die objektorientierte Struktur der Benchmark-Klassen. Benchmark ist eine abstrakte Klasse, von der alle konkreten Testprogramme erben. Sie stellt Methoden zur systemunabh"angigen Ausgabe und Zeitmessung zur Verfu"gung. printBenchmark() leitet die Ausgabedaten bei einem Applet in ein Textfeld (java.awt. TextArea), bei einer Applikation an die Standardausgabe um. Die beiden Methoden begin Benchmark() und endBenchmark() sind eine Zeitklammer um den Benchmark, stoppen Start- und Endzeit, und geben die Laufzeit aus. Die abstrakt definierten Routinen runBenchmark() und infoBenchmark() mu"ssen von jedem Benchmark selbst implementiert werden. infoBenchmark() gibt den Name und die Versionsnummer des Tests aus, und in runBenchmark() wird der Test ausgefu"hrt. ________________________________1 Die Klassendiagramme in dieser Studienarbeit basieren auf OMT, der Object Modeling Technique, wie sie in Ausz"ugen in [GAMM96] beschrieben wird. 12 MatrixBenchmark implementiert eine einfache Matrizenmultiplikation: Xn cij= aikbkj k=1 und den Gauss-Algorithmus zum L"osen von Linearen Gleichungssystemen (LGS): A(n;n)x = b Der Algorithmus fu"r die Multiplikation berechnet durch einfaches Aufsummieren in drei verschachtelten Schleifen die L"osungsmatrix. Bei einer quadratischen (n,n)-Matrix bedeutet dies einen Aufwand von O(n3). Fu"r den Benchmark wird ein Produkt zweier (200,200)- Matrizen, mit zuf"allig gesetzten double-Werten, berechnet. Das LGS wird mit dem Gaussschen Eliminationsverfahren, wie es beispielsweise in [Sedg91.1] beschrieben wird, gel"ost. Der Test fu"hrt dies fu"r ein Gleichungssystem mit 400 Gleichungen und 400 Unbekannten _ in double _ durch. PolyBenchmark multipiziert zwei Polynome (Instanzen der Klasse Poly) nach dem Algorithmus von Kara- zuba. Dieser Algorithmus (vgl. [Sedg91.2]) l"ost nach dem Prinzip Teile und Herrsche rekursiv das Problem fu"r Polynome (Objekte der Klasse Poly) der L"ange n mit einem Aufwand in O(n1;58). In PolyBenchmark ist n = 4000 gew"ahlt. PrimeBenchmark ist der im obigen Diagramm dargestellte Test. Als Datenstruktur verwendet er eine boolean- Flag-Liste fu"r alle Zahlen. Der verwendete Algorithmus nach Eratosthenes filtert Nicht- primzahlen aus, indem er fu"r alle Primzahlen von 2 beginnendpdie_Vielfachen aus der Li- ste streicht (auf false setzt). Wenn er alle Zahlen bis n(mit n als L"ange der Liste, hier 9.000.000) getestet hat, sind nur noch Primzahlen true. Der Primzahlentest ist zweigeteilt, einmal wird die Zeit zur Erzeugung des PrimeList- Objekts, das im wesentlichen ein boolean-Array der L"ange 9.000.000 ist, gemessen und zum zweiten die Ausfu"hrungszeit des eigentlichen Primzahlensieb-Algorithmus. SortBenchmark erzeugt ein SortList-Objekt, eine Liste von Zahlen des Typs Integer mit Sortieralgorithmen. Die Liste wird mit Zufallszahlen gefu"llt und anschliessend mit Shell-Sort sortiert. Shell-Sort (vgl. [Sedg91.3]) ist eine Verbesserung des Sortierens durch Einf"ugen, indem es Teillisten vorsortiert. Inhalt des Tests ist einmal der h"aufige Zugriff auf die 1000 Array-Elemente w"ahrend des Sortiervorgangs und zweitens die 1000fache Wiederholung dieses Vorgangs. 13 InitBenchmark, RecBenchmark sind nur als Erg"anzung zu PolyBenchmark gedacht (vgl. die Auswertung in Abschnitt 3.5). Sie berechnen keinen Algorithmus, sondern testen nur das Verhalten der JVM beim Erzeugen von Objekten (InitBenchmark) und dem rekursiven Abstieg in einer Funktion (RecBenchmark). 3.3 "Uberlegungen zur Programmiersprache Java Bei den Testprogrammen wurde Wert darauf gelegt, die von Java und der JVM vorgegebenen Optimierungsm"oglichkeiten weitm"oglichst auszusch"opfen. Im Folgenden werden die wich- tigsten "Uberlegungen kurz beschrieben: Verwendung von final Damit der Compiler einen besseren Code erzeugen kann, sollte der Programmierer m"oglichst immer Methoden, die nicht mehr "uberschrieben werden, mit dem Modifikator final verse- hen. Z.B.: public final Poly mult(Poly b) f /* */ g aus der Klasse Matrix. private und static Methoden sind implizit final. Vermeidung von synchronized Ein grosser Vorteil Javas bei nebenl"aufiger Programmierung (d.h. bei Verwendung mehre- rer Threads) ist ein einfaches Synchronisierungs-Konzept. Kritische Stellen in parallelen Pro- grammteilen, wie gemeinsame Datenstrukturen und deren Methoden k"onnen synchronisiert werden. Dies bringt aber auch einen grossen Interpretations-Overhead mit sich. Beispielsweise werden so die java.io Klassen fu"r zeitkritische Anwendungen schlecht brauchbar. Derzeit sind alle JVM bei Ein/Ausgaben langsam. Garbage Collection In Java gibt es keine explizite Speicherfreigabe durch den Programmierer. Diese Aufgabe "ubernimmt ein System-Thread im Hintergrund. Wenn ein Objekt nicht mehr referenziert wird, gibt er dessen Speicher auf dem Heap wieder frei. Um Inkonsistenzen in der Zeitmessung zu vermeiden wird in den Benchmarks System. gc() verwendet. Dies veranlasst den Java Interpreter die Garbage Collection gleichzeitig, und nicht nur bei Speicher-Bedarf, durchzufu"hren. Um den zus"atzlichen Aufwand der Garbage Collection zu vermeiden, kann es sinnvoll sein, h"aufig erzeugte und verworfene Objekte mit einer eigenen Speicherverwaltung zu versehen. Der Programmierer kann bei Freigabe die Objekte in eine Freiliste aufnehmen, und wenn ein Objekt entsprechender Gr"osse neu angefordert wird, kann so die Erzeugungszeit gespart werden. 14 In der JVM-Spezifikation ist nicht festgelegt, welchen Algorithmus die Garbage Collection verwendet. Einen ersten "Uberblick der verschiedenen Techniken bietet der Onlineartikel Java's garbage-collected heap [Venn96]. St"arkereduktion Eine "ubliche Unterstu"tzung fu"r den Compiler ist die Verwendung von schw"acheren "aquiva- lenten Ausdru"cken. Der langsame Zugriff auf Felder in Java kann bei zweidimensionalen Feldern dadurch ab- geschw"acht werden, dass eine zus"atzliche eindimensionale Referenz eingefu"hrt wird. Im fol- genden Programmbeispiel aus MatrixBenchmark werden die variablen elem_i, elem_max, elem_j statt elem[i], elem[max] und elem[j] immer genau dann verwendet, wenn in einer Zeile der Matrix mehrere Elemente angesprochen werden. public final void eleminate() f double[] elem_i, elem_max, elem_j; double dummy; int i, j, k, max; for (i = 0; i < rows; i++) f max = i; for (j = i+1; j < rows; j++) if (Math.abs(elem[j][i]) > Math.abs(elem[max][i])) max = j; elem_i = elem[i]; elem_max = elem[max]; for (k = i; k < cols; k++) f dummy = elem_i[k]; elem_i[k] = elem_max[k]; elem_max[k] = dummy; g for (j = i+1; j < rows; j++) f elem_j = elem[j]; for (k = cols-1; k >= i; k--) elem_j[k] -= elem_i[k] * elem_j[i] / elem_i[i]; g g g Zweidimensionale Felder werden in Java wie eindimesionale Felder von Feld-Objekten behandelt. Jeder Zugriff elem[i][k] bedeutet also, dass erst die Referenz auf a[i] mit einem getfield-Befehl der JVM (vgl. [Sun95b]) auf den Stack geholt wird, und anschliessend mit dieser Adresse und einem weiteren getfield der Wert der Zelle. Durch Einfu"hren einer zus"atzlichen Referenz elem_i wird dies umgangen. 15 Es wird bei jeder Referenz ein iload- und ein aaload-Befehl im Java-Bytecode einge- spart.2 "Ahnliche Code-Verbesserungen, wie sie in vielen Hochsprachen "ublich sind (die Ent- fernung von invarianten Ausdru"cken in Schleifen, die Vorausberechnung von Abbruchbe- dingungen (rows statt elem.length) oder die Verwendung der x += y Operation statt x = x + y) wurden ebenfalls beachtet. Bei einfachen Integer-Variablen optimiert zwar auch der Compiler der JDK (javac, mit Parameter -O), aber sp"atestens bei Array-Zugriffen wie elem_j[k] = elem_j[k] - y geschieht dies nicht mehr. So verbesserter Code erm"oglicht auch JITC weitergehende Optimierungen. System.arraycopy() Eine weitere M"oglichkeit der Performancesteigerung im Java-Code ist die Verwendung der richtigen Java-Methode. Zum Beispiel bietet Java eine schnelle System-Funktion fu"r das (vollst"andige oder teilweise) Kopieren von Arrays an. Mit java.lang.System.array copy() im folgenden Code-Abschnitt: Poly al = new Poly(len2); Poly bl = new Poly(len2); try f System.arraycopy(elem, 0, al.elem, 0, len2); System.arraycopy(b.elem, 0, bl.elem, 0, len2); g catch(ArrayIndexOutOfBoundsException e) f g catch(ArrayStoreException e) f g statt einer einfachen Schleife: for (int i = 0; i < len2; i++) f al.elem[i] = elem[i]; bl.elem[i] = b.elem[i]; g kann so Ausfu"hrungszeit in kritischen Bereichen eingespart werden. Profiling Um diese zeitkritischen Bereiche zu finden, stellt der Interpreter (der JDK) die M"oglichkeit des Profiling zur Verfu"gung. Profiler sind Hilfprogramme, die messen, wieviel Laufzeit die einzelnen Teile eines Programms verbrauchen und wie oft Methoden aufgerufen werden. Den Java-Profiler wird mit dem Befehl java -prof aufgerufen und anhand der in ./java.prof abgelegten Statistik, k"onnen laufzeitfintensive Programmteile erkannt werden. Die in Anhang A angefu"gten Benchmark-Programme sind so auf ihre Zuverl"assigkeit getestet. ________________________________2 http://www.cs.cmu.edu/"jch/java/compilers.html 16 3.4 Test-Bedingungen 3.4.1 Die drei Testplattformen Im Folgenden sind die wichtigsten technischen Daten der drei Tesplattformen tabellarisch aufgelistet: SPARCstation 4 Modell: SPARCstation 4 Hersteller: Sun Microsystems RAM: 48 MB Virtueller Speicher: 141 MB CPU Anzahl: 1 CPU Typ: 85 MHz microSPARC II Kernel Architektur: sun4m Betriebssystem: SunOS 5.4 (Solaris) Virtueller Adress Cache:16384 Software: JDK 1.0.23 JDK 1.0.2dp11/13/96-15:42 (neuere Version) Netscape Navigator 3.014 kaffe 0.7.05 PC - Windows 95 CPU: Pentium 90 RAM: 48 MB Cache: 256 KB Betriebsystem: Microsoft Windows 95 Software: JDK 1.0.2ss:08/12/96-14:32:12 (neuere Version6) Symantec Visual Cafe prebeta II7 Asymetrix SuperCede 1.0 beta8 ________________________________3 http://www.javasoft.com/ 4http://www.netscape.com/ 5http://www.sarc.city.ac.uk/"tim/kaffe/index.html 6Teil des Java Workshops f"ur Windows von Sun Microsystems 7http://www.symantec.com/ 8http://www.asymetrix.com/ 17 Abbildung 3.3: Berechnungsbeispiel der Ergebnisse Microsoft Internet Explorer 3.019 Netscape Navigator 3.02 (mit JIT von Borland) PC - Linux 2.0.x Hardware: vgl. PC - Windows 95 Betriebssystem: Linux 2.0.x mit XFree86 3.1.2 Software: JDK 1.0.2chapman:10/12/12-23:1210 Netscape Navigator 3.01 Kaffe 0.7.0 3.4.2 Sonstige Festlegungen Alle Quelltexte wurden mit dem Java-Compiler javac von Sun Microsystems mit der Optimieroption -O in Bytecode "ubersetzt. Als Referenz-JVM ist auf jeder der Plattformen die JDK 1.0.2 von JavaSoft (bzw. bei Linux der Port von Randy Chapman) installiert. Deren Ergebnisse werden mit 100.0% gewertet, und abh"angig davon der Prozentwert der anderen Interpreter/JIT-U"bersetzer11berechnet. So ist ein plattformu"bergreifer Vergleich an Relativwerten m"oglich. Die Tests sind so dimensioniert, dass die Ausfu"hrungszeit mit dem Interpreter der JDK 1.0.2 zwischen einer und drei Minuten liegt. 3.5 Ergebnisse Im Anhang B sind die genauen Messwerte der Testl"aufe tabellarisch fu"r die einzelnen Platt- formen aufgefu"hrt. Abh"angig von Interpreter und Testprogramm sind je vier Zeitmessungen vorgenommen worden. Um den Einfluss von zuf"alligen Systemereignissen zu unterdru"cken, wurde der gr"osste und der kleinste Wert fu"r den weiteren Vergleich ignoriert. Die jeweils fu"nfte Zeile ist der Durchschnittswert der beiden gewerteten Zahlen. Fu"r ihn ist auch der Relativwert berechnet. Die Abbildung 3.3 zeigt ein Beispiel fu"r eine Messreihe. ________________________________9 http://www.microsoft.com/ie/ 10http://www.blackdown.org/ 11Das Konzept der Just in Time-Compiler wird in 4.2 n"aher beschreiben. 18 SPARCstation 4 - Solaris Neben Windows NT war Solaris (Abbildung 3.4) die erste Plattformen, fu"r die Sun seine Re- ferenzimplementierung einer JVM, die JDK, angeboten hat. Getestet wurden zwei verschie- dene Versionen, die normale Distribution und eine sp"atere Version: dp11/13/96-15:42. Au- sser bei den Benchmarks mit Matrix- und Polynommultiplikation (105%) bringt diese bessere Ergebnisse. Die verschiedene Versionen der JDK 1.0.2 ergeben sich aus verschieden Freiga- beterminen bei Sun/Javasoft. Mit neuen Entwicklungen wie dem Browser HotJava oder dem Java-Workshops, einer grafischen Entwicklungsumgebung fu"r Java-Programme, ist auch immer die entsprechend aktuellste Version des Interpreters erh"altlich. Insbesondere Fehler fru"herer Versionen12sind dort behoben. Kaffe ist eine frei erh"altliche JVM, die fu"r mehr als 20 Hardware/Betriebssystem-Varianten erh"altlich ist. Sie ist eine sogenannte Clean-Room-Implementierung, d.h. sie baut nicht auf den Code von Sun Microsystems auf. Auf der Intel Plattform und _ seit der hier getesteten Version 0.7.0 _ auch auf SPARC unterstu"tzt sie eine Just in Time-U"bersetzung in maschinenabh"angigen Code. Und obwohl sie immernoch ALPHA-Software ist, ist sie schon relativ stabil und sicher. Kaffe beinhaltet keine AWT, d.h. es wird keine Native-Library fu"r das Abtract Window Toolkit mitentwickelt. Fu"r Unix/X ist es aber m"oglich die in 5.1.4 beschriebenen AWT-Implementierungen einzubinden. Im Test zeigt kaffe 0.7.0 (ausgenommen von PolyBenchmark) eine Laufzeitverbesserung von im Schnitt Faktor 5. Bei Aufgaben wie dem Primzahlensieb oder dem mehrfachen Sortiern der Integerliste ist die Steigerungen deutlicher. Das L"osen der Gausselimination gelingt immerhin noch in 35.8% der Zeit, die der reine Interpretierer von Sun Microsystems ben"otigt. Negativ f"allt nur der Test mit der Polynommultiplikation auf, mit 235.3% ist kaffe hier mehr als doppelt so langsam. Gru"nde hierfu"r werden im n"achsten Abschnitt bei den JIT-Compilern fu"r Windows gesucht. Der Netscape Navigator 3.01 ist unter Solaris neben dem HotJava von Sun, der einzige WWW-Browser, der eine Java-Unterstu"tzung bietet. Da HotJava direkt auf die JDK aufsetzt wurde auf einen Test verzichtet. Der Browser von Netscape unterstu"tzt auf den Unix- Plattformen keine JIT-Compilierung, deshalb sind seine Ergebnisse bei den Benchmarks auch nicht weiter verwunderlich. Nur der Polynomtest und das Erzeugen des Primzahlenobjekts ergaben Abweichungen nach oben von bis zu 30 Prozentpunkten. Die restlichen Werte lagen zwischen 101.0% und 117.0%. Pentium 90 - Windows 95 Besonders fu"r Windows13 bieten viele Softwarehersteller JIT-Compiler (JITC) an. Bis auf die JDK 1.0.2 besitzen alle unter Windows getestete JVM diese Option. Im "Uberblick (vgl. Abbildung 3.5) best"atigen dies auch die Zahlen der Benchmarks. Bis zu Faktor 20 kann hier der Unterschied betragen (Primzahlensieb). Bei der L"osung des Gleichungssystems mit 400 Unbekannten und 400 Gleichungen liegen die vier JITC-Ergebnisse alle in einem Bereich von ________________________________12 http://www.javasoft.com/products/jdk/1.0.2/KnownBugs.html 13Die Tests wurden unter Microsoft Windows 95 vorgenommen, da mit Microsoft Windows NT nur ein 486/33 zur Verf"ugung stand und besonders bei den JIT-Compilern die Leistung der Hardware wichtig wird. So ist auch ein besserer Vergleich mit den Ergebnissen unter Linux auf der gleichen Hardware m"oglich. 19 Abbildung 3.4: Ergebnisse SPARCstation 4 - Solaris, alle Benchmarks 20 Abbildung 3.5: Ergebnisse Pentium 90 - Windows 95, alle Benchmarks 21 ______________________________________________________________________ _ _JDK 1.0.2 _Super- _Visual CafeN_etscape _IExplorer _ _________________ss08/12/96C_ede________2.00b07______3.01_______3.01____ _ Erzeugen von _ (52.68) _ (158.41) _ 51.57 _ _ (72.78) _ _ Objekten _ (52.89) _ 151.65 _ (51.63) _l"anger _ 72.12 _ _ _ 52.73 _ 145.06 _ (51.36) _als 8 Min. _ 71.96 _ _ _ 52.73 _ (144.84) _ 51.61 _ _ (71.30) _ _ _ 52.73 _ 148.36 _ 51.59 _ _ 72.04 _ ___________________100.0%____281.3%________97.8%______________136.6%____ _ Rekursiver _ 12.25 _ 1.37 _ 0.88 _ 0.94 _ 0.99 _ __Abstieg__________100.0%_____11.2%_________7.2%______7.7%______8.1%___ Tabelle 3.1: Ergebnisse fu"r InitBenchmark und RecBenchmarks unter Windows 95 10.2-12.4% des JDK-Wertes. Diese gleichen Leistungswerte sind aber keineswegs "ublich, nur bei Berechnung des Primzahlensiebs haben die Werte eine "ahnlich kleine Streuung (5.2-7.7%). Grunds"atzlich liegt die Ausfu"hrzeit der JVM im Netscape Browser in einer Gr"ossenordnung von 0.5 bis 1 "uber denen des Browsers von Microsoft (Internet Explorer). Auch die beiden Stand-alone-Produkte von Asymetrix und Symantec zeigen deutliche Unterschiede. Bei Ma- trizenmultipikation, Polynommultiplikation und im Sortieren der Integerliste "ubertrifft Visual Cafe PreBeta II SuperCede von Asymetrix in einem Faktor zwischen 1.8 und 4.2. Bei den Benchmarks mit Gausselimination, Erzeugen des Objekts fu"r den Primzahlentest und dem Primzahlensieb-Algorithmus selbst sind die Zeitwerte von SuperCede besser. Bei Prozent- werten von 5 bis 10 liegen die Abweichungen hier aber nur bei 2 bis 3 Prozentpunkten. Auffallend aber sind besonders die Ergebnisse des Benchmarks mit der Multiplikation zweier Polynome der L"ange 4000. Der Netscape Navigator hat hier eine doppelt so langen Ausfu"hrungszeit (203.7%) wie das Referenzsystem, die JDK von Sun Microsystems. Auch die anderen JITC ergeben hier keine "ahnlichen Geschwindigkeitsverbesserungen wie bei den anderen Tests. SuperCede ist mit einem Wert von 130.2% langsamer, genau wie der Internet Explorer (IE) mit 108.1% und nur Symantec Visual Cafe ist mit 46.2% schneller als der reine Interpretierer, der JDK. PolyBenchmark implementiert wie in Abschnitt 3.2 beschrieben eine rekursive Poly- nommultiplikation, in der das Problem in drei Teilprobleme der halben Gr"osse geteilt wird und danach die Ergebnisse wieder zusammengesetzt werden. Hierfu"r werden in jedem Re- kursionsschritt sechs neue Poly-Objekte erzeugt. Dies stellt sich fu"r die JITC als grosses Problem dar. Um zu entscheiden, welche Programm- teile die Beschleunigung durch die Just in Time-Compiler behindern, wird der Test in zwei auf- geteilt: InitBenchmark und RecBenchmark. Die Ergebnisse von InitBenchmark und RecBenchmark (vgl. fu"r den Programmcode Anhang A) in Tabelle 3.1 zeigen, dass Super- Cede, der Netscape Navigator und der Internet Explorer signifikant mehr Zeit bei der Erzeu- gung von neuen Objekten brauchen, als die JVM von JavaSoft. Dass die schlechten Resultate bei PolyBenchmark nicht von der Rekursion im Teile-und-Herrsche-Algorithmus abh"angt zeigt auch RecBenchmark, ein Test, der eine einfachen rekursiven Abstieg in einem Objekt beinhaltet (vgl. Tabelle 3.1). Der Grossteil der Ausfu"hrungszeit wird deshalb fu"r das Erzeugen der Objekte aufgewendet. 22 Bei InitBenchmark braucht SuperCede ca. 2,8 mal l"anger (281.3%) als der Interpretierer der JDK von JavaSoft. Der nicht ebenfalls so schlechte Wert bei PolyBenchmark resultiert deshalb aus der guten Optimierung der restlichen Programmteile. Visual Cafe von Symantec ist in der Lage, bei InitBenchmark die Zeit der JDK zu erreichen und knapp zu unterbieten. Auch hier wird der Zeitvorteil in PolyBenchmark durch Optimierung der anderen Programmkonstrukte erreicht. Fu"r die Programmentwicklung hat dies konkrete Folgen: Um nicht Performanceeinbussen hinnehmen zu mu"ssen, ist das allzu h"aufige Erzeugen von Objekten zu vermeiden. In PolyBenchmark k"onnte dies zum Beispiel mit der Einfu"hrung einer Freiliste fu"r nicht mehr verwendete Poly-Objekte und deren Recycling bei n"achster Gelegenheit erreicht werden. Da die Rekursion einen Tiefensuchebaum erzeugt, d.h. einen Teilzweig immer erst bis zum letzten Blatt abarbeitet, k"onnten die auf diesem Weg erzeugten Objekte im n"achsten Teilzweig wiederverwendet werden. Damit wird die Zeit zur Erzeugung eingespart. Ein positiver Nebeneffekt w"are die Umgehung der Garbage Collection von Java. Laut Be- richten in Newsgroups14und verschiedener Benchmarks15ist sie bei den meisten Interpretern und JIT-U"bersetzern nur schlecht implementiert. Pentium 90 - Linux Unter Linux (vgl. Abbildung 3.6) standen genau wie bei Solaris nur die JDK 1.0.2 (nicht in einer offiziellen Portierung von Sun), der Netscape Navigator 3.02 (ohne JITC) und kaffe 0.7.0 als Testsysteme zur Verfu"gung. Die Ergebnisse des Netscape Navigators sind mit denen der anderen Unix-Plattform vergleichbar. Die Primzahlentests sind mit Prozentwerten von 81.2% und 83.2% besser als die Werte des Interpreters von JavaSoft; die Multiplikation der Polynome braucht 154.5% der Ausfu"hrungszeit der JDK. Auch kaffe ergibt fast die gleichen Werte wie bei der SPARC-Version. Da die JITC-Option hier schon l"anger eingebaut und getestet ist unterstreicht das die Leistung bei der Solaris- Version, die erst mit der Version 0.7.0 eine Just in Time-Compilierung erm"oglicht. Das Erzeugen des grossen Arrays fu"r das Primzahlensieb ist unter Linux genau wie der Primzahlensieb-Algorithmus selbst und SortBenchmark relativ zur JDK doppelt so schnell wie unter Solaris. Ebenfalls negativ fiel PolyBenchmark auf. Die Werte lagen "uber dem Doppeltem der Sun-Ergebnisse. W"arend der Testl"aufe wurde eine Ausfu"hrung mit einer java.lang.NullPointerException beendet. Dieser Fehler liess sich nicht wiederholen und deutet auf einen internen Fehler der kaffe JVM hin. Allgemein Die Tests fu"r Windows 95 und Linux/X wurden auf der gleichen Hardware ausgefu"hrt. Deshalb lassen sich hier bedingt auch die absoluten Zahlen vergleichen. Deutlich zu erkennen ist, dass der Netscape Navigator unter Windows "uber eine JITC verfu"gt (vgl. Abbildung 3.7). "Uber die Betriebssystemgrenzen bewirkt dies eine Steigerung bis zu einem Faktor von 20. Natu"rlich unterscheiden sich auch die Leistungswerte der JDK selbst. Hier schneidet die ________________________________14 de.comp.lang.java und comp.lang.java.* 15http://www.cs.cmu.edu/"jch/java/benchmarks.html 23 Abbildung 3.6: Ergebnisse Pentium 90 - Linux, alle Benchmarks 24 Abbildung 3.7: Ergebnisse mit Netscape auf allen Plattformen, alle Benchmarks Abbildung 3.8: Ergebnisse mit JDK 1.0.2 auf allen Plattformen, alle Benchmarks 25 Abbildung 3.9: Ergebnisse von CaffeineMark 2.5: JVM ohne JITC Windows-Version um durchschnittlich 30% besser ab (vgl. Abbildung 3.8). 3.6 Ergebnisse von CaffeineMark Fu"r den normalen Java-Benutzer geschieht die Benutzung derzeit oft nur als Applet in einem Browser. Pendragon Software16versucht mit einem Benchmark-Paket, dem CaffeineMark, die Leistungsf"ahigkeit der eingebauten JVM der Browser von Microsoft (IE), Netscape (Navigator) und Sun (HotJava, ohne JITC) zu vergleichen. Der CoffeinMark 2.5 besteht aus 9 Tests die alle Bereiche der Java-Programmierung ab- decken. Zus"atzlich zu numerischen Berechnungen, wie sie Grundlage der Benchmarks dieser Studienarbeit sind, werden auch Performace-Aspekte der Grafik und Zeichenkettenverarbei- tung beachtet. Der CoffeineMark ist ein Mittelwert aus den 9 Test-Ergebnissen und gibt relativ zu einem Referenzsystem (mit Cyrix 6x86 P150+, Windows 95 und dem Symantec Cafe app- letviewer im Debug-Modus) einen Leistungswert fu"r die getestete JVM. Die Abbildung 3.9 zeigt die Ergebnisse fu"r HotJava PreBeta 1, Internet Explorer 3.0B1 und Navigator 2.02. Diese Browser-Versionen verfu"gen noch nicht "uber eine JIT-Compilierung. Im Vergleich dazu zeigen die beiden Browser Internet Explorer 3.0B2 und Navigator 3.0B5A in Abbildung 3.10 deutliche Steigerungen der Ausfu"hrungsgeschwindigkeit. Beson- ders "sieve, loop, logic floating-point (fp) und der method Test", so Pendragon, "werden dramatisch bescheunigt". Dies kommt besonders "berechnungsintensive Animationen und ________________________________16 Battle of Browsers: http://www.webfayre.com/battle.html 26 Abbildung 3.10: Ergebnisse von CaffeineMark 2.5: JITC 3D-Modellierung" (Pendragon) zugute. 27 Kapitel 4 Laufzeitverbesserungen 4.1 Natives Nach der Untersuchung des wirklichen Laufzeitverhaltens von Java Programmen und JVM liegt es nahe, Konzepte der Laufzeitverbesserung zu behandeln. In Benchmark (vgl. Abschnitt 3.3) wird System.arraycopy() verwendet, eine fu"r das Kopieren von Arrays optimierte Routine der JVM. Was fu"r das Kopieren von Arrays schon vorgesehen ist, kann auch fu"r andere Probleme selbst implementiert werden. Java sieht native Methoden vor. D.h. es lassen sich aus dem Java-Code heraus direkt C (C++)-Routinen aufrufen. JavaSoft hat fu"r diesen Fall entsprechende Tools und C-Include-Files vorgesehen. Sie sind Teil der Standard-Distribution und erm"oglichen die Kommunikation zwischen C- und Java-Ebene. C++-Routinen k"onnen ebenfalls "uber diese Schnittstelle eingebunden werden [Foot96]. Durch diese "Anderung auf Ebene des Java-Bytecodes (vgl. Abbildung 4.1) geht zwar die Systemunabh"angigkeit verloren, es kann aber bei rechenintensiven Beispielen deutliche Geschwindigkeitsvorteile bringen. Ausserdem besteht die M"oglichkeit, zus"atzlich zu den systemabh"angigen Methoden langsamere "Aquivalente in Java zu schreiben, die ausgefu"hrt werden, wenn die dynamisch ladbare Bibliothek nicht zur Verfu"gung steht (vgl. das n"achste Beispiel), z.B. auf einer anderen Hardwareplattform. Die folgende Klasse UseNative stellt die Einbindung von native Methoden vor. Die Methoden displayHelloWorld(), add_ab1() und add_ab2() sind ausserhalb des Java Codes implementiert. Verwendet werden k"onnen sie aber genauso wie normale Methoden: UseNative use = new UseNative(); Abbildung 4.1: Abstrakte Ebenen von Java: Java Bytecode 28 use.displayHelloWorld(); Beispielsweise gibt use.displayHelloWorld() Hello World an der Standardausgabe aus. Die Methode displayHelloWorldFallBackCode() erfu"llt die gleiche Aufgabe, pru"ft aber vorher ob der Ladebefehl fu"r die Shared Library funktioniert hat und fu"hrt andernfalls eine entsprechende Java Routine aus. Auch Parameter k"onnen der native Methode mitu"bergeben werden. Die Funtionen use.add_ab1(use.a, use.b); use.add_ab2(use.b); geben beide den Additionswert der Variablen a und b zuru"ck. Im ersten Fall werden beide als Paramter an die native Routine "ubergeben, im zweiten nur b. Auf a greift die C- Routine "uber die von der JDK vorgesehene Schnittstelle zu. Im Folgenden wird der Beispiel-Code fu"r die Klass UseNative gegeben: 29 class UseNative f private static boolean nativeCode; public native void displayHelloWorld(); public native int add_ab1(int a, int b); public native int add_ab2(int b); public void displayHelloWorldFallBackCode() f if (nativeCode) displayHelloWorld(); else System.out.println("Hello World"); g static f try f System.loadLibrary("hello"); nativeCode = true; g catch (UnsatisfiedLinkError e) f System.out.println("Library not found."); nativeCode = false; g catch (Exception e) f System.out.println("Cannot load Library."); nativeCode = false; g g public int a; public int b; g Der dazugeh"orende C Code der Datei MyUseNative.c sieht so aus: #include #include "UseNative.h" #include /* Ausgabe an stdout */ void UseNative_displayHelloWorld(struct HUseNative *h) f printf("Hello World!nn"); return; 30 g /* Addition der beiden Parameter */ long UseNative_add_ab1(struct HUseNative *h, long x, long y) f return x + y; g /* Addition der int-Variable a des Java * Objekts mit dem "ubergebenen Paramter */ long UseNative_add_ab2(struct HUseNative *h, long y) f return unhand(h)->a + y; g Um dem Java Programm die C Funktionen zur Verfu"gung zu stellen, sind nur drei Arbeitschritte n"otig: 1. "Ubersetzen des Java Codes: javac UseNative.java 2. Erzeugen der C-Header und Source Dateien, die die Klasse UseNative beschreiben und eine Schnittstelle zwischen Java und C zur Verfu"gung stellen: javah UseNative javah -stubs UseNative 3. "Ubersetzen des eigenen C-Codes und Binden zu einer Library Unter Solaris geht dies zum Beispiel in einer Befehlszeile: gcc -G MyUseNative.c UseNative.c -o libhello.so -I/export/opt/java/include -I/export/opt/java/include/solaris -I/export/opt/GNU/lib/g++-include Nicht nur die Verwendung von Code in C oder C++ zum Geschwindigkeitsgewinn ist fu"r Softwareentwickler interessant. Auch die Wiederverwendbarkeit von altem Code ist so m"oglich. Mit der Beta-Release der JDK 1.1 hat JavaSoft ein neue genau spezifizierte Schnittstelle fu"r native Methoden eingefu"hrt, das Java Native Method Interface [Java96b]. 31 Abbildung 4.2: Abstrakte Ebenen von Java: Java Virtual Machine (JVM) 4.2 JIT/ Ahead-of-Time-(Re)Compiler Die Laufzeiteffizienz kann ebenfalls auf der abstrakten Ebene der JVM gesteigert werden (vgl Abbildung 4.2). Ein Konzept sind sogenannte Just In Time-U"bersetzer, die parallel zur Ausfu"hrung oder dem Laden der Klasse ausgefu"hrt werden. Sie generieren Native-Code on-the-fly1, der schneller ausgefu"hrt werden kann. Der JIT-Code kann dann auch plattformspezifische Hardwarevoraussetzungen, wie einen Coprozessor oder "ahnliches, nutzen. Die Abbildung 4.3 verdeutlicht den Unterschied zwischen Interpretation und Just in Time-U"bersetzung. Die JDK von Sun sieht fu"r die Einbindung eines JIT-Compilers die Klasse java.lang. Compiler vor [Java96a]. Sie ist sowohl zust"andig fu"r das Feststellen ob eine entsprechende Bibliothek mit JIT-Compiler existiert, als auch fu"r die Initialisierung; beides geschieht im static- initializer-Block beim Laden der Klasse: try f String library = System.getProperty("java.compiler"); if (library != null) f System.loadLibrary(library); initialize(); g g catch Throwable e) f g Mit der System-Routine getProperty() wird die Umgebungsvariable JAVA_COMPILER gelesen und die dort optional angegebene Bibliothek dynamisch geladen. Ausserdem enth"alt die Klasse verschiedene Methoden mit denen Applikationen Informa- tionen an den Compiler senden und empfangen k"onnen: public static void disable(); public static void enable(); public static boolean compileClass(Class clazz); public static boolean compileClasses(String string); public static Object command(Object any); Die genaue Beschreibung dieser Methoden und weiterer Strukturen findet sich in [Ja- va96a]. ________________________________1 d.h. w"ahrend der Ausf"uhrung, direkt bei Bedarf 32 Abbildung 4.3: Interpretation vs JITC 33 Abbildung 4.4: Abstrakte Ebenen von Java: Hardware, Betriebssystem Vor oder parallel zur Ausfu"hrung einer Klasse wird ihr Bytecode in maschinenabh"angigen Code "ubersetzt, der dann nicht mehr interpretiert werden muss, sondern wie ein normales Programm ausgefu"hrt werden kann. Besonders dann, wenn weiteru"bersetzter Code mehrfach verwendet wird, kann die JIT-U"bersetzung die Ausfu"hrungszeit reduzieren. Die oben getesteten JVM von Symantec, Asymetrix, Microsoft und auch die frei erh"altliche JVM kaffe verfu"gen "uber eine JIT-U"bersetzereinheit. In der Windows-Version des Navigators setzt Netscape derzeit noch die JIT-JVM von Borland ein. Das U"bersetzen des Bytecodes in Maschinenbefehle erm"oglicht auch die Ausnutzung spezifischer Hardware. Der erzeugte Code kann wesentlich weiter optimiert werden als dies fu"r die Stack-Maschine der JVM m"oglich ist. Besonders bei rechenintensiven Programmen sparen JIT-Compiler Zeit und hier ist dann auch mehr Aufwand bei der Optimierung durch ku"rzere Ausfu"hrzeiten leicht aufzuwie- gen. Derzeit sind die Produkte auf dem Markt sicher noch nicht am Ende ihrer Entwick- lungsm"oglichkeiten angelangt, schon der Performanceunterschied der einzelnen JIT-JVM deu- tet darauf hin. Was ein JIT-U"bersetzer on-the-fly durchfu"hrt (vgl. markierter Ablaufpfad in Abbildung 4.3), kann auch vorher von einem Ahead-of-Time-Compiler oder Recompiler berechnet und in einem fat Classfile abgelegt werden [Java96a]. Fat Classfiles enthalten neben dem normalen Java-Bytecode plattformabh"angigen Maschinencode fu"r die gesamte Klasse oder nur fu"r bestimmte Methoden. Es ist auch m"oglich den Code von mehreren Maschinenarchitekturen hier abzulegen. Auch in diesem Fall wird der Zugriff "uber die Klasse java.lang.Compiler geregelt. Die dynamisch ladbare Bibliothek muss dann Routinen zum Zugriff auf den entsprechenden "ubersetzten Code besitzen. 4.3 Andere Hardware Just in Time-U"bersetzer, Natives und Fat Classfiles sind natu"rlich abh"angig von der zugrun- deliegen Hardware und Software. Aber sie verfolgen Konzepte, die systemunabh"angig sind. Eine andere Herangehensweise an das Problem Performancesteigerung ist der Austausch der Hardware selbst (vgl. Abbildung 4.4). 4.3.1 Teilauslagerung Teile einer JVM lassen sich relativ einfach auf andere Hardwaresysteme oder Subsysteme ausgliedern. Dazu sind nur "ahnlich der in Abschnitt 4.1 besprochen native Methoden 34 die von der JVM verwendeten Routinen auf dem Hostsystem durch effizientere (z.B. einen Coprozessor benutzende) zu ersetzen. Beispielsweise liessen sich die Klassen-Methoden fu"r trigonometrische Funktionen in java.lang.Math so mit wenig Aufwand durch leistungsf"ahigere "Aquivalente ersetzen. 4.3.2 Vollimplementierung Aber auch die vollst"andige Implementierung der JVM ist denkbar. Die JVM stellt eine sehr kleine, robuste Menge von Befehlen auf einer sehr einfachen abstrakten Maschinenstruktur zur Verfu"gung Die Konzepte (vgl. Kapitel 2) lassen sich auf bestehende Hardware abbilden. Und durch Optimierung und Ausnutzung besonderer Hardwarebedingungen l"asst sich die Performance deutlich steigern. Weiter "Uberlegungen zur Portierung der Runtime der JDK 1.0.2 findet man in [Gu"nt97]. 35 Kapitel 5 Portierung von Bibliotheken Die meisten nativen Routinen sind im Bibliothekssystem der Java-API zu finden. Die Kernbibliotheken der JDK 1.0.x1 sind java.io, java.net und java.awt, das Abstract Window Toolkit (AWT). Diese beinhaltet Funktionen fu"r eine grafisches Benutzerinterface (GUI) und fu"r grafische Ausgaben. 5.1 Abstract Window Toolkit Das AWT ist eine portable GUI-Bibliothek fu"r Java. Diese kann man in einem Java Programm durch den Befehl import java.awt.* einbinden. Das AWT soll nachfolgend als Beispiel n"aher beschrieben werden, um Probleme und L"osungsm"oglichkeiten fu"r eine Portierung oder Implementierung bei schon laufendem Run- time zu zeigen. 5.1.1 java.awt Das AWT, im package java.awt, bietet Funktionen fu"r die Gestaltung von graphischen Benutzerinterfaces. Neben den reinen GUI-Komponenten enth"alt es aber auch grundlegende Klassen zur Grafikausgabe. Das OMT-Diagramm in Abbildung 5.1 zeigt einige der Klassen und ihre Beziehungen2. Als GUI-Klassen gibt es Komponenten und Layoutmanager. Komponenten sind entweder einzelne Objekte, wie Button, Label, List, etc., oder Container, die mehrerer Komponenten beinhalten. LayoutManager kontrollieren das Layout der Elemente innerhalb eines Contai- ners. Wichtigste Grafik-Klasse ist java.awt.Graphics, die ist als abstrakte Klasse definiert ist und eine systemunabh"angige Schnittstelle zur Grafik herstellt. Graphics-Objekte k"onnen nicht direkt erzeugt werden, aber sie k"onnen u"ber die getGraphics()-Routine einer Komponete angefordert werden. ________________________________1 Mit Einf"uhrung der JDK 1.1 beta hat JavaSoft diese wesentlich erweitert. 2F"ur eine Gesamt"ubersicht aller Klassen ist der Referenzteil von [Flan96] zu empfehlen. Eine Einf"uhrung in das AWT bietet [Yu95]. 36 Abbildung 5.1: OMT-Diagramm: java.awt.* 37 Abbildung 5.2: Struktur der java.awt.peer-Interfaces 5.1.2 java.awt.peer Das Package java.awt.peer besteht vollst"andig aus Interface-Definitionen (vgl. Abbil- dung 5.2). Die Hirachie entspricht fast vollst"andig der des Packages java.awt. Ziel der Peer-Spezifikationen ist es, eine abstrakte Schnittstelle fu"r die GUI-Implementierung auf ver- schiedenen Plattformen zu bieten (vgl. Abschnitt 2.3). 5.1.3 sun.awt.win32 Bei Implementierung des AWT gilt es, die in Abschnitt 5.1.1 beschriebene Klassenstruktur und Funktionalit"at zur Verfu"gung zu stellen. Sun hat fu"r die Einbindung des AWT eine abstrakte Klasse java.awt.Toolkit vorge- sehen. Eine AWT-Implementation muss diese erweitern und die entsprechenden Funktionen besitzen. Bei Benutzung von AWT-Objekten wird dieses Toolkit einmal instanziert und mit seinen Funktionen das entsprechende Objekt zuru"ckgeliefert. Im Diagramm in Abbildung 5.3 wird ein kleiner Ausschnitt der von Sun entwickelten Toolkits fu"r Windows und Motif darge- stellt. Wird in einem Java-Programm ein Button-Objekt der Klasse java.awt.Button ein- gebunden, erzeugt das Windows-Toolkit ein Objekt der Klasse sun.awt.win32.MButton Peer und gibt dies zuru"ck. Damit die tats"achliche Implementierung der Grafik und GUI- 38 Abbildung 5.3: OMT-Diagramm: sun.awt.*.MToolkit 39 Objekte mit denen der AWT-Spezifikation "ubereinstimmt, mu"ssen diese Klassen die Interfa- ces des java.awt.peer Paketes unterstu"tzen. Die Klasse sun.awt.win32.MButtonPeer implementiert zum Beispiel das Interface java.awt.peer.ButtonPeer. Ein grosser Teil der AWT ist somit in Java selbst geschrieben, nur um tats"achliche Objekte auf dem Bildschirm zu erzeugen, werden ca. 140 native Methoden ben"otigt. Die 1.0.x Implementierung von Sun baut unter Solaris auf das Motif-Framework3 und unter Windows auf die Microsoft Foundation Classes (MFC) auf. Eine Klasse MButtonPeer mit ihrer nativen Methode create() wird deshalb auf das entsprechende C++-A"quivalent der MFC mit den entsprechenden Routinen abgebildet. Das nachfolgende Programmsegment zeigt den C++-Code. /* C++-Klasse AwtButton erbt von MFC CButton */ class AwtButton : public CButton f public: AwtButton(); "AwtButton(); /* ... */ g Die im OMT-Diagramm (Abbildung 5.3) angedeutete C-Funktion sun_awt_win32_MButton Peer_create() fungiert sozusagen als Schnittstelle zwischen dem in Java und in C++ ge- schriebenen Code. Auf Grund dieser Struktur der sun.awt.win32 h"angt der Aufwand, die AWT-Bibliothek der JDK 1.0.x von Windows auf andere Systeme zu portieren, sehr von den dortigen Gegeben- heiten ab. Mit einem Fenster-Framework, dass in Struktur, Umfang und Leistungsf"ahigkeit den MFC entspricht, w"are es m"oglich, den Sun-Code 1:1 umzusetzen. Der in Java geschrie- bene Teil k"onnte ohne "Anderungen "ubernommen werden, und der C++-Code muss nur an die neuen GUI-Objekte angepasst werden. Da die AWT nur eine relativ kleine Standard-GUI- Menge darstellt, ist dies oft m"oglich. Wenn ein entsprechendes Framework nicht existiert, oder es eine andere Struktur besitzt, liegt der Hauptaufwand der Portierung in der Abbildung des AWT. Mit der Freigabe der 1.1-Beta-Release der JDK hat JavaSoft den AWT-Windows-Teil voll- kommen neu geschrieben4 und unabh"angig von den Microsoft Foundation Classes gestaltet. Derzeit ist diese Software aber noch im "offentlichen Beta-Test und noch nicht fehlerfrei5. ________________________________3 Motif ist eine Bibliothek zur Darstellung eines grafischen Benutzerinterfaces unter X. 4http://www.javasoft.com/products/jdk/1.1/ 5http://www.javasoft.com/products/jdk/1.1/README 40 Abbildung 5.4: Baumstruktur der BISS-AWT 5.1.4 Alternativen BISS-AWT Auf der Mailingliste fu"r die unter der GNU General Public License6 erh"altliche JVM kaffe hat Anfang 1997 eine fu"r Unix-Plattformen mit Source-Code frei erh"altliche AWT- Implementierung das Interesse auf sich gezogen, das BISS AWT7. Urspru"nglich nur als Erweiterung und Anpassung des AWT an eigene Zwecke gedacht, hat der Hersteller (BISS GmbH) das BISS Java Framework entworfen, das aufbauend auf die Basisklassen Graphics, Frame, Panel und Canvas in java.awt eine selbst"andige graphische Benutzerschnittstelle definiert [BISS97]. In Zusammenhang mit der "Anderung der Lizenzbedingungen bei Freigabe der JDK 1.0.2 und den U"berlegungen der Internetgemeinde zu einer frei erh"altlichen JVM8, haben die Entwickler aufbauend auf das Framework die java.awt.peer Interfaces, sowie die fu"r ein Stand-alone- System n"otigen Grundklassen implementiert. Als Referenzsystem wurde Linux/X mit kaffe und den Xlib-Funktionen gew"ahlt. Ein Vorteil, den diese AWT-Implementierung gegenu"ber dem Sun-Original besitzt ist die grosse Systemunabh"angigkeit (vgl. Abbildung 5.4): nur 1/3 der fu"r die Sun AWT zu imple- mentierenden Native-Methoden sind n"otig. Durch einen konsequent hirachischen Aufbau ________________________________6 http://www.gnu.org/copyleft/gpl.html 7http://www.biss-net.com/biss-awt.html 8JOLT, Java Open Language Toolkit: http://www.redhat.com/jolt/ 41 werden alle GUI-Komponenten in Java implementiert und eben nur wenige Basisklassen mit systemabh"angigen Aufrufen gebraucht. SAWT Ein anderer Ansatz ein freies Abtract Window Toolkit fu"r Unix/X zu entwickeln ist das SAWT-Projekt9. Hierbei werden ebenfalls alle Peer-Interfaces implementiert. Aber anders als das Sun-Entwicklerteam werden nicht das Motif-Framework, sondern direkt Xlib-Aufrufe verwendet. Interessant an diesem Projekt ist die Herangehensweise; in vier Schritten soll die volle Funktionalit"at zur Verfu"gung gestellt werden. A: API Gerippe B: minimale Funktionalit"at (Anzeige) C: ganze Funktionalit"at (Fonts, Farben, etc.) D: optimierte Funktionen SAWT befindet sich immer noch im ALPHA-Zustand, bei fast allen Komponeten ist erst Entwicklungsstand B (minimale Funktionalit"at) erreicht, und ist deshalb noch keine Alternative zur Sun-Implementation. 5.2 Weiterf "uhrendes Das Abtract Window Toolkit stellt derzeit die gr"osste zu portierende Bibliothek der JDK dar. Der Aufwand hierfu"r h"angt stark von den Gegebenheiten auf der Zielplattform ab. Weiter Bibliotheken sind java.net oder sun.audio die in der JDK 1.0.x gr"osstenteils in Java implementiert sind und deshalb weniger Portierungsaufwand erfordern. Neben Java-Compiler und Interpreter sind die Kernbibliotheken Teil des Java-Systems (vgl. dazu Abschnitt 2). Sie stehen auf jeder unterstu"tzten Plattform zur Verfu"gung, und JavaSoft allein ist fu"r die Definition der Schnittstellen zust"andig. Mit Einfu"hrung der JDK 1.1 hat JavaSoft diese unter anderem um die JDBC10und die Java Security API11erweitert. JDBC ist die Datenbankschnittstelle fu"r Java, die Java-Programme den Zugriff auf rationale Datenbanken erlaubt. Die neue Java Security API enth"alt Funktionen fu"r digitale Unterschriften, Verschlu"sselung und Authentisierung. Mit Implementierung dieser Kernbibliotheken besitzt Java eine auf allen Plattformen gleiche Umgebung und erm"oglicht eine Softwareentwicklung fu"r ein einheitliches System. ________________________________9 http://slhp1.epfl.ch/sawt.html 10http://www.javasoft.com/products/jdk/1.1/docs/guide/jdbc/index.html 11http://www.javasoft.com/products/jdk/1.1/docs/guide/JavaSecurityOverview.html 42 Kapitel 6 Zusammenfassung und Ausblick Die Programmiersprache Java ist innerhalb sehr kurzer Zeit zu einer festen Gr"osse in der Soft- wareentwicklung geworden, und besonders leistungsf"ahige JIT-U"bersetzer _ auf m"oglichst vielen Rechnerplattformen _ werden dies weiter unterstu"tzen. Die Benchmarks dieser Studienarbeit best"atigen eine durchschnittliche Leistungssteige- rung von einem Faktor 5. Einziger Schwachpunkt aller JITC-Implementierungen ist die Er- zeugung von Objekten. Im Vergleich mit dem Interpreter der JDK ergeben fast alle JVM mit JIT-U"bersetzung hier eine langsamere Ausfu"hrungszeit. Eine vollst"andige Implementierung der Java Virtual Machine besteht neben Java-Compiler und Bytecode-Interpreter auch aus den Kernbibliotheken des Java-Systems. Ein Teil ist das Abstract Window Toolkit (AWT). Der Aufwand zur Portierung des AWT der JDK 1.0.2 h"angt, durch die Struktur der Sun- Implementierung fu"r Windows bedingt, stark von den Voraussetzungen auf der Zielplattform ab. Nur bei "ahnlichen Grundbedingungen kann viel Code 1:1 "ubernommen werden. Zusammen mit der Implementierung weiterer API-Schnittstellen vervollst"andigt dies das Java-System, und ergibt eine auf allen Plattformen standardisierten Laufzeit- und Program- mierumgebung. 43 Anhang A Programme Benchmark /** SMall JVM-Benchmark-Collection * @version 1.1 * @author Marc Schanne */ import java.applet.*; import java.awt.*; import java.io.*; /** Benchmark ist eine abstrakte Klasse, die fuer konkrete * Benchmark-Programme Methoden zur Zeitmessung, systemunabh. * Ausgabe und Appletdarstellung zur Verfuegung stellt. * runBenchmark() und infoBenchmark() muessen vom konkreten * Testprogramm implementiert werden. */ public abstract class Benchmark extends Applet f // Variablen zur Zeitmessung und Ausgabe private long startTime, elapsedTime; private Button runButton; private TextArea textArea; // Applet oder Application? private boolean isApplet = false; 44 /** System- (d.h. von Applet oder Application) * unabhaengige Ausgabe-Routine */ public void printBenchmark(String str) f if (isApplet) textArea.appendText(str + "nn"); else System.out.println(str); g /** Zeitklammer oeffnen (d.h Startzeit speichern) */ public void beginBenchmark() f System.gc(); printBenchmark("Die Uhr laeuft ..."); startTime = System.currentTimeMillis(); g /** Zeitklammer schliessen und Laufzeit ausgeben */ public void endBenchmark() f elapsedTime = System.currentTimeMillis() - startTime; double seconds = elapsedTime / 1000.0; printBenchmarkf"... und stop. Laufzeit: " + seconds + " Sek."); g /** Der Test selbst; * Ausgaben ueber die printBenchmark()-Methode * Zeitmessung mit begin/endBenchmark() */ public abstract void runBenchmark(); /** Gibt Informationen ueber den Test aus */ public abstract void infoBenchmark(); /* Methoden fuer Appletdarstellung */ /** Einrichten des Start-Buttons und des Ausgabe-TextAreas * und Informationen ueber den Test ausgeben. */ public void init() f isApplet = true; // Ausgabe in Applet this.setLayout(new BorderLayout(0, 0)); runButton = new Button("Benchmark starten"); this.add("North", runButton); 45 textArea = new TextArea(15, 60); textArea.setFont(new Font("Helvetica", Font.PLAIN, 12)); textArea.setEditable(false); this.add("Center", textArea); this.show(); // alles anzeigen infoBenchmark(); g /** Bei Klick auf den Start-Button wird der Benchmark * ausfuehren, andere Events werden in der Event-Kette * weitergeben. * Es gibt keine Abfrage ob ein Test bereits laeuft! */ public boolean action(Event e, Object o) f if (e.target == runButton) f runBenchmark(); return true; g return super.action(e, o); g g 46 MatrixBenchmark /** SMall JVM-Benchmark-Collection: Matrizenrechnung * @version 1.1 * @author Marc Schanne */ import java.util.*; /** Matrizen(Zeilen x Spalten)-Klasse mit * Multiplikation und Gauss-Elimination */ class Matrix f public double elem[][]; // Matrix-Elemente public int rows; // Anzahl der Zeilen und public int cols; // Spalten /** Erzeugen der Matrix(rows x cols) */ public Matrix(int r, int c) f rows = r; cols = c; elem = new double[rows][cols]; g /** Konstruieren einer erweiterten Matrix fuer die Gauss- * Elimination aus einer quadradtischen Matrix A und einem * Vektor b. */ public Matrix(QMatrix a, VMatrix b) f rows = a.rows; cols = a.cols+1; elem = new double[a.rows][a.cols+1]; int i, j; /* Verwendung der schnellen System-Routine arraycopy(). * Vgl. dazu Abschnitt 3.3 */ try f for (i = 0; i < rows; i++) System.arraycopy(a.elem[i], 0, elem[i], 0, a.cols); g catch(ArrayIndexOutOfBoundsException e) f g catch(ArrayStoreException e) f g 47 for (i = 0; i < rows; i++) elem[i][a.cols] = b.elem[i][0]; g /** Matrix mit zufaelligen Double-Werten fuellen */ public final void randomFill() f Random random = new Random(); int i, j; for (i = 0; i < rows; i++) for (j = 0; j < cols; j++) elem[i][j] = random.nextDouble(); g /** Einfache Matrizenmultiplikation in O(n^3) */ public final Matrix mult(Matrix b) f int i, j, k; Matrix c = new Matrix(rows, b.cols); for (i = 0; i < rows; i++) f for (j = 0; j < b.cols; j++) f for (k = 0; k < cols; k++) f c.elem[i][j] += elem[i][k] * b.elem[k][j]; g g g return c; g /** Vorwaerts-Elimination nach Gauss mit Pivot-Suche */ public final void eleminate() f double[] elem_i, elem_max, elem_j; // Vgl. Abschnitt 3.3 double dummy; int i, j, k, max; for (i = 0; i < rows; i++) f max = i; for (j = i+1; j < rows; j++) if (Math.abs(elem[j][i]) > Math.abs(elem[max][i])) max = j; elem_i = elem[i]; elem_max = elem[max]; for (k = i; k < cols; k++) f dummy = elem_i[k]; elem_i[k] = elem_max[k]; elem_max[k] = dummy; g 48 for (j = i+1; j < rows; j++) f elem_j = elem[j]; for (k = cols-1; k >= i; k--) elem_j[k] -= elem_i[k] * elem_j[i] / elem_i[i]; g g g /** Rueckwaerts-Einsetzen (Gauss) * Der Loesungsvektor wird erzeugt und zureckgegeben. */ public final VMatrix substitute() f VMatrix x = new VMatrix(rows); double dummy; int i, k; for (i = rows-1; i >= 0; i--) f dummy = 0.0; for (k = i+1; k < cols-1; k++) dummy += elem[i][k] * x.elem[k][0]; x.elem[i][0] = (elem[i][cols-1]-dummy) / elem[i][i]; g return x; g /** Ueberschreibt Object.toString */ public String toString() f int i, j; StringBuffer dummy = new StringBuffer(""); for (i = 0; i < rows; i++) f for (j = 0; j < cols; j++) dummy.append(elem[i][j] + ", "); dummy.append("nn"); g String out = new String(dummy); return out; g g /** Klasse quadratischer Matrizen * (direkte Kindklasse normalerMatrizen) * F"ur quad. Matrizen kann der Gauss-Alg. aufgerufen werden. */ class QMatrix extends Matrix f 49 public QMatrix(int r) f super(r, r); g /** Gauss, verwendet eleminate(), substitute() */ public final VMatrix gauss(VMatrix y) f Matrix ay = new Matrix(this, y); ay.eleminate(); VMatrix x = ay.substitute(); return x; g g /** Vektoren sind ebenfalls als Kindklasse von Matrix * implemntiert. */ class VMatrix extends Matrix f public VMatrix(int r) f super(r, 1); g g /** Benchmark mit grossen Matrizen * Multiplikation und Gauss (keine optimierten Alg.) */ public class MatrixBenchmark extends Benchmark f public void runBenchmark() f printBenchmark("Matrixmutliplikation in O(n^3)"); QMatrix a = new QMatrix(200); QMatrix b = new QMatrix(200); a.randomFill(); b.randomFill(); Matrix c; beginBenchmark(); // Test-Start c = a.mult(b); // C = A * B endBenchmark(); // Test-Ende printBenchmark("Gauss-Elimination fuer LGS"); QMatrix m = new QMatrix(400); VMatrix y = new VMatrix(400); VMatrix x; m.randomFill(); y.randomFill(); beginBenchmark(); // Test-Start x = m.gauss(y); // A * x = y endBenchmark(); // Test-Ende g 50 public void infoBenchmark() f printBenchmark("SMall JVM-Benchmark-Collection: " + Matrizenrechnung"); printBenchmark("v1.1"); printBenchmark("Marc Schanne " + "nn"); g /** Application-Main * Benchmark-Objekt erzeugen und Test ausfuehren */ public static void main(String args[]) f MatrixBenchmark mb = new MatrixBenchmark(); mb.infoBenchmark(); mb.runBenchmark(); g g 51 PolyBenchmark /** SMall JVM-Benchmark-Collection: Polynome * @version 1.1 * @author Marc Schanne */ import java.util.*; /** Polynom n-ter Ordung mit Multiplikation */ class Poly f private double elem[]; // Koeffizentenfeld /** double-Feld f"ur Koeffizenten mit Laenge n erzeugen */ public Poly(int n) f elem = new double[n]; g /** Polynom der Laenge n erzeugen und die ersten Elemete aus * Polynom a kopieren. */ private Poly(Poly a, int n) f int i; elem = new double[n]; // Vgl. Abschnitt 3.3 try f System.arraycopy(a.elem, 0, elem, 0, a.elem.length); g catch(ArrayIndexOutOfBoundsException e) f g catch(ArrayStoreException e) f g for (i = a.elem.length; i < n; i++) elem[i] = 0; g /** Zufaelliges Fuellen mit Werten */ public final void randomFill() f int i, len; Random random = new Random(); len = elem.length; for (i = 0; i < len; i++) elem[i] = random.nextDouble(); g 52 /** Rekursive Funktion zum Multipizieren der Polynome this * und b. * Beschr.: Nach dem Prinzip "Teile und Herrsche" wird * das Problem der Multiplikation von Polynomen der * Groesse n durch Loesen von 3 Teilproblemen der * Groesse n/2 geloest. * Fuer n=1 ist das Produkt gleich dem Skalar- * produkt der beiden Konstanten-Koeffizienten. * Aufwand: O(n^lg3) * Randbed: this.elem.length == b.elem.length == 2^k * (wird deshalb aus mult() aufgerufen) */ private final Poly multRec(Poly b) f if (elem.length == 1) f Poly c = new Poly(1); c.elem[0] = elem[0] * b.elem[0]; return c; g else f int len; int len2 = elem.length / 2; // Zerlegung in 6 Polynome Poly al = new Poly(len2); // der Laenge n/2: Poly bl = new Poly(len2); // al, bl, ah, bh, t1, t2 try f System.arraycopy(elem, 0, al.elem, 0, len2); System.arraycopy(b.elem, 0, bl.elem, 0, len2); g catch(ArrayIndexOutOfBoundsException e) f g catch(ArrayStoreException e) f g Poly ah = new Poly(len2); Poly bh = new Poly(len2); try f System.arraycopy(elem, len2, ah.elem, 0, len2); System.arraycopy(b.elem, len2, bh.elem, 0, len2); g catch(ArrayIndexOutOfBoundsException e) f g catch(ArrayStoreException e) f g Poly t1 = new Poly(len2); Poly t2 = new Poly(len2); for (int i = 0; i < len2; i++) f t1.elem[i] = al.elem[i] + ah.elem[i]; t2.elem[i] = bl.elem[i] + bh.elem[i]; g Poly rm = new Poly(elem.length); // Teilberechnungen rm = t1.multRec(t2); 53 Poly rl = new Poly(elem.length); rl = al.multRec(bl); Poly rh = new Poly(elem.length); rh = ah.multRec(bh); Poly c = new Poly(2*elem.length-1); // Rekombination len = elem.length-1; try f System.arraycopy(rl.elem, 0, c.elem, 0, len); System.arraycopy(rh.elem, 0, c.elem, len+1, len); g catch(ArrayIndexOutOfBoundsException e) f g catch(ArrayStoreException e) f g c.elem[len] = 0; for (int i = 0; i < len; i++) c.elem[len2+i] += rm.elem[i] - (rl.elem[i] + rh.elem[i]); return c; g g /** Mult hat 2 Aufgaben: * 1) Aufruf des Multiplikations-Alg. (mutlRec()) mit * Polynomen richtiger Groesse: n = 2^(aufrunden(log_2(n)) * 2) Rueckgabe des Ergebnisses */ public final Poly mult(Poly b) f Poly a2 = new Poly(this, (int)Math.pow(2, (double)((int)( Math.log (Math.max(elem.length, b.elem.length)) / Math.log(2.0)) + 1))); Poly b2 = new Poly(b, (int)Math.pow(2, (double)((int)( Math.log(Math.max(elem.length, b.elem.length)) / Math.log(2.0)) + 1))); return a2.multRec(b2); g /** Ueberschreibt Object.toString() */ public String toString() f StringBuffer dummy = new StringBuffer("p(x) = "); for (int i = elem.length-1; i > 0; i--) if (elem[i] != 0.0) dummy.append(elem[i] + "*x^" + i + " + "); 54 dummy.append(elem[0]); String out = new String(dummy); return out; g g /** Benchmark: Polynom-Multiplikation */ public class PolyBenchmark extends Benchmark f /** der Test */ public void runBenchmark() f printBenchmark("c(x) = a(x) * b(x); a, b vom Grad 4000"); Poly a = new Poly(4000); Poly b = new Poly(4000); Poly c; a.randomFill(); b.randomFill(); beginBenchmark(); // Test-Start c = a.mult(b); // c(x) = a(x) * b(x) endBenchmark(); // Test-Ende g /** Versionsnummer und Name */ public void infoBenchmark() f printBenchmark("SMall JVM-Benchmark-Collection: " + "Polynom-Multiplikation"); printBenchmark("v1.1"); printBenchmark("Marc Schanne " + "nn"); g /** Main-Prog. fuer Application * Erzeugen des Benchmark-Objekts und Ausf"uhren des Tests */ public static void main(String argv[]) f PolyBenchmark pb = new PolyBenchmark(); pb.infoBenchmark(); pb.runBenchmark(); g g 55 PrimeBenchmark /** SMall JVM-Benchmark-Collection: Primzahlen * @version 1.1 * @author Marc Schanne */ import java.util.*; /** PrimeList stellt eine Prime-Flag-Liste fuer die Zahlen * von 2 bis len und eine Methode zur Primzahlenberechnung * mit dem Sieb des Eratosthenes zur Verfuegung. */ class PrimeList f private boolean flag[]; // Prime-Flag fuer 2 ... private int sqrtLen; // ... bis sqrtLen^2 /** @param sqrtLen Quadrat-Wurzel der gewuenschten * Array-Laenge */ public PrimeList(int sqrtLen) f this.sqrtLen = sqrtLen; flag = new boolean[sqrtLen*sqrtLen+1]; int i, len; len = flag.length; // Annahme: alle prim for(i = 0; i < len; i++) flag[i] = true; g /** Primzahlenberechnug mit Sieb der Eratosthenes * von 2 bis sqrtLen^2 * * Bsp. fuer sqrtLen=4: * Init. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 * i=2 2 3 - 5 - 7 - 9 - 11 - 13 - 15 - * i=3 2 3 - 5 - 7 - - - 11 - 13 - - - * i=4 keine Primzahl. Fertig. */ public final void runSieve() f int i, k, prime; for (i = 2; i <= sqrtLen; i++) f if(flag[i]) f prime = i; 56 for (k = i + prime; k < flag.length; k += prime) flag[k]=false; g g g /** zur einfachen Ausgabe, ueberschreibt Object.toString() */ public String toString() f int i, len; StringBuffer dummy = new StringBuffer("Primz. von 2 bis "); dummy.append((flag.length-1) + ": "); len = flag.length; for (i = 2; i < len; i++) if (flag[i]) dummy.append(i + " "); String out = new String(dummy); return out; g g /** Benchmark mit Primzahlenwaesche des Eratosthenes */ public class PrimeBenchmark extends Benchmark f /** Erzeugt ein PrimeList-Objekt und ruft das Primzahlensieb * dafuer auf. */ public void runBenchmark() f printBenchmark("1) Erzeugen des PrimeList-Objects (im " + "wesentlichen ein boolean-Array fuer die " + "Zahlen 2 bis 9.000.000)"); beginBenchmark(); // Test-Start PrimeList pl = new PrimeList(3000); // Objekt erzeugen endBenchmark(); //Test-Ende printBenchmark("2) Primzahlenberechnung selbst"); beginBenchmark(); // Test-Start pl.runSieve(); // Primzahlensieb endBenchmark(); // Tes-Ende g public void infoBenchmark() f printBenchmark("SMall JVM-Benchmark-Collection: " + "Primezahlensieb"); 57 printBenchmark("v1.1"); printBenchmark("Marc Schanne" + "nn"); g; /** Application-Main */ public static void main(String argv[]) f PrimeBenchmark pb = new PrimeBenchmark(); pb.infoBenchmark(); pb.runBenchmark(); g g 58 SortBenchmark /** SMall JVM-Benchmark-Collection: Integerfeld sortieren * @version 1.1 * @author Marc Schanne */ import java.util.*; /** Liste von Integern mit verschiedenen elementaren * Sortier-Algorithmen (Bubble-Sort, Insertion-Sort und * Shell-Sort) */ class SortList f private int elem[]; /** int-Feld der Laenge len erzeugen */ public SortList(int len) f elem = new int[len]; g /** Liste mit Zufallsintegerzahlen fuellen */ public final void randomFill() f int i, len; Random random = new Random(); len = elem.length; for (i = 0; i < len; i++) elem[i] = random.nextInt(); g /** Bubble-Sort (Sortieren durch Austauschen) * Beschr.: Durchlaufe immer wieder das feld und vertausche * jedesmal, wenn es notwendig ist, benachbarte * Elemente (wenn bei einem Durchlauf kein * Austausch mehr erforderlich ist, ist die Datei * sortiert). * Aufwand: quadratisch */ public final void sortBubbleSort() f int i, j, dummy; for (i = elem.length; i >= 0; i--) for (j = 1; j <= i; j++) 59 if (elem[j-1] > elem[j]) f dummy = elem[j-1]; elem[j-1] = elem[j]; elem[j] = dummy; g g /** Insertion-Sort (Sortieren durch Einfuegen) * Beschr.: Betrachte die Elemnte eines nach dem anderen und * fuege jedes an seinen richtigen Platz zwischen * den bereits betrachteten ein. Das gerade * betrachtete Element wird eingefuegt, indem die * groessten Elemente einfach um eine Position nach * rechts bewegt werden. * Aufwand: quadratisch, aber fuer "fast sortierte" Felder * linear */ public final void sortInsertionSort() f int i, j, dummy, len; len = elem.length; for (i = 1; i < len; i++) f dummy = elem[i]; j = i; while ((j > 0) && (elem[j-1] > dummy)) f elem[j] = elem[j-1]; j = j - 1; g elem[j] = dummy; g g /** Shell-Sort eine Verbesserung von Insertion-Sort * Beschr.: Die Zahlenliste wird in mehreren Durchgaengen * mit Insertion-Sort (vor-)sortiert. Dabei * werden Teilfolgen (mit bestimmtem Offset) * sortiert. */ public final void sortShellSort() f int h = 1; // h-sortiert mit Folge int i, j, dummy, len; len = elem.length; do f h = 3 * h + 1; // ..,1093,364,121,40,13,4,1 g while (h < len); 60 do f // Beginn Sortieralg. h = h / 3; for (i = h+1; i <= len; i++) f dummy = elem[i-1]; j = i; while (elem[j-h-1] > dummy) f elem[j-1] = elem[j-h-1]; j = j - h; if (j <= h) break; g elem[j-1] = dummy; g g while (h != 1); g /** Ueberschreibt Object.toString() */ public String toString() f int i, len; StringBuffer dummy = new StringBuffer(" "); len = elem.length; for (i = 0; i < len; i++) dummy.append(elem[i] + " "); String out = new String(dummy); return out; g g /** Haeufiges Sortieren eines Integer-Feldes mit Shell-Sort */ public class SortBenchmark extends Benchmark f public void runBenchmark() f printBenchmark("1000 mal Array der Groesse 1000 in einer " + "Methode mit Zufallszahlen fuellen und mit " + "einer 2. Methode sortieren"); SortList sl = new SortList(1000); beginBenchmark(); // Test-Start for (int i=0; i < 1000; i++) f // Schleife !!! sl.randomFill(); // Fuellen mit Zufallszahlen sl.sortShellSort(); // Sortieren g endBenchmark(); // Test-Ende g 61 public void infoBenchmark() f printBenchmark("SMall JVM-Benchmark-Collection: Sortieren " + "mit Shell-Sort"); printBenchmark("v1.1"); printBenchmark("Marc Schanne " + "nn"); g /** Main-Prog. fuer Application */ public static void main(String args[]) f SortBenchmark sb = new SortBenchmark(); sb.infoBenchmark(); sb.runBenchmark(); g g 62 InitBenchmark /** SMall JVM-Benchmark-Collection: Objekte erzeugen * @version 0.1 * @author Marc Schanne */ import java.util.*; /** Klasse mit Array-Objekt und einer Fuellmethode */ class Init f private double elem[]; /** double-Feld mit Laenge n erzeugen */ public Init(int n) f elem = new double[n]; g /** Zufaelliges Fuellen mit Werten */ public final void randomFill() f int i, len; Random random = new Random(); len = elem.length; for (i = 0; i < len; i++) elem[i] = random.nextDouble(); g g /** Benchmark: Erzeugen von Objekten */ public class InitBenchmark extends Benchmark f public void runBenchmark() f int i, j; Init a[] = new Init[1000]; printBenchmark("Init as init can"); beginBenchmark(); // Test-Start for (j = 0; j < 100; j++) // 100 x for (i = 0; i < 1000; i++) // 1000 Objekte a[i] = new Init(1000); // (= Arrays) erzeugen endBenchmark(); // Test-Ende g 63 public void infoBenchmark() f printBenchmark("SMall JVM-Benchmark-Collection: " + "Objekte erzeugen"); printBenchmark("v0.1"); printBenchmark("Marc Schanne " + "nn"); g /** Main-Prog. fuer Application */ public static void main(String argv[]) f InitBenchmark ib = new InitBenchmark(); ib.infoBenchmark(); ib.runBenchmark(); g g 64 RecBenchmark /** SMall JVM-Benchmark-Collection: rekursiver Abstieg * @version 0.1 * @author Marc Schanne */ import java.util.*; /** In einem grossen Array ermoeglicht diese Klasse einen * rekursive Abstieg */ class Rec f private double elem[]; /** double-Feld mit Laenge n erzeugen */ public Rec(int n) f elem = new double[n]; g /** Zufaelliges Fuellen mit Werten */ public final void randomFill() f int i, len; Random random = new Random(); len = elem.length; for (i = 0; i < len; i++) elem[i] = random.nextDouble(); g /* rekursiver Aufruf von doRec */ public final double doRec(int l, int r) f if (l == r) f // Abbruchbed. return elem[l]; g else f return doRec(l, l+(int)((r-l)/2)) * doRec(l+(int)((r-l)/2+1), r); g g g 65 /** Benchmark: 1 Objekt erzeugen und darin einen rekursive * Abstieg ausfuehren. */ public class RecBenchmark extends Benchmark f public void runBenchmark() f Rec a = new Rec(1000001); a.randomFill(); beginBenchmark(); // Test-Start double d = a.doRec(0, 1000000); // Rekursion aufrufen endBenchmark(); // Test-Ende g public void infoBenchmark() f printBenchmark("SMall JVM-Benchmark-Collection: " + "rekursiver Abstieg"); printBenchmark("v0.1"); printBenchmark("Marc Schanne " + nn"); g /** Main-Prog. fuer Application */ public static void main(String argv[]) f RecBenchmark pb = new RecBenchmark(); pb.infoBenchmark(); pb.runBenchmark(); g g 66 Anhang B Messwerte der Benchmarks SPARCStaion 4 - Solaris ___________________________________________________________ _ _JDK 1.0.2 _JDK 1.0.2 N_etscape _ Kaffe _ ___________________________dp11/13/96____3.01_______0.7.0____ _ Matrizen _ 95.206 _ (100.525) _ 95.751 _ (23.092) _ _ Multiplikation (_94.245) _ 98.993 _ (95.746) _(18.319) _ _ _ 94.919 _ (98.094) _ (97.013) _ 19.137 _ _ _(95.867) _ 99.311 _ 96.417 _ 18.481 _ _ _ 95.063 _ 99.152 _ 96.084 _ 18.809 _ __________________100.0%______104.3%____101.1%______19.8%___ _ Gauss _(163.736) _(157.122) _(199.187) _(75.009) _ _ Elimination _167.294 _ 158.525 _ 196.221 _ (59.765) _ _ _(167.607) _(159.879) _ 194.445 _ 59.855 _ _ _ 166.663 _ 159.528 _ (193.489) _ 59.804 _ _ _ 166.979 _ 159.027 _ 195.333 _ 59.830 _ __________________100.0%_______95.2%____117.0%______35.8%____ _ Polynom _(199.064) _ (202.198) _(229.672) _(438.695) _ _ Multiplikation(1_73.273) _(185.342) _ 234.463 _(414.036) _ _ _ 176.199 _ 187.126 _ (281.229) _415.763 _ _ _ 177.353 _ 186.543 _ 235.605 _ 416.213 _ _ _ 176.776 _ 186.835 _ 235.034 _ 415.988 _ __________________100.0%______105.7%____133.0%_____235.3%____ _ Primezahlen _(30.996) _ 24.872 _ (35.114) _ (8.058) _ _ Objekt _ 30.778 _ 24.454 _ (44.902) _ (6.388) _ _ erzeugen _ 29.710 _ (24.398) _ 38.746 _ 6.507 _ _ _(29.698) _ (25.531) _ 41.130 _ 6.393 _ _ _ 30.244 _ 24.663 _ 39.938 _ 6.450 _ __________________100.0%_______81.5%____132.1%______21.3%___ 67 Fortsetzung der Tabelle von Seite 66: _____________________________________________________________ _ _JDK 1.0.2 J_DK 1.0.2 _Netscape _ Kaffe _ ____________________________dp11/13/96____3.01_______0.7.0_____ _ Sieb _ 91.420 _ (83.746) _(95.369) _ (17.047) _ _ _ 91.643 _ (86.861) _(90.690) _ (11.026) _ _ _ (91.614) _ 86.170 _ 91.618 _ 11.086 _ _ _ (92.802) _ 84.835 _ 93.243 _ 11.112 _ _ _ 91.532 _ 85.503 _ 92.431 _ 11.099 _ ___________________100.0%_______93.4%_____101.0%______12.1%____ _ Sortieren _(200.743) _ (167.288) _201.472 _ (27.400) _ _ _ 182.615 _ 170.002 _(201.663) _ 27.317 _ _ _ 184.453 _ 170.292 _ 196.070 _ (26.065) _ _ _(181.285) _ (170.710) _(193.222) _ 26.325 _ _ _ 183.534 _ 170.147 _ 198.771 _ 26.821 _ ___________________100.0%_______92.7%_____108.3%______14.6%___ 68 PC - Windows 95 _______________________________________________________________________ _ _JDK 1.0.2 _Super- _Visual Cafe _Netscape _IExplorer _ ________________ss08/12/96__Cede_1.0b___2.00b07______3.01______3.02______ _ Matrizen _ (67.72) _ (13.78) _ (7.96) _ (11.37) _ (8.56) _ _ Multiplikation _ 67.78 _ 14.06 _ 7.86 _ 11.15 _ 8.07 _ _ _ 67.83 _ 13.90 _ 7.91 _ (10.99) _ (7.97) _ _ _ (68.94) _ (14.11) _ (7.90) _ 11.10 _ 8.08 _ _ _ 67.81 _ 13.98 _ 7.89 _ 11.13 _ 8.08 _ ___________________100.0%______20.6%_______11.6%______16.4%_____11.9%___ _ Gauss _ 145.72 _ 15.77 _ 17.79 _ 18.23 _ (14.88) _ _ Elimination _ (145.72) _ 15.87 _ 17.79 _ (18.34) _ 14.83 _ _ _ 146.08 _ (15.82) _ (17.79) _ (18.13) _ (14.83) _ _ _ (146.46) _ (15.60) _ (17.77) _ 18.24 _ 14.85 _ _ _ 145.90 _ 15.82 _ 17.79 _ 18.24 _ 14.84 _ ___________________100.0%______10.8%_______12.2%______12.4%_____10.2%____ _ Polynom _ 109.57 _ 142.42 _ (51.13) _ 223.49 _ 118.69 _ _ Multiplikation _(113.14) _ 143.30 _ 50.58 _ (221.62) _(118.48) _ _ _ (108.31) _ (142.09) _ 50.81 _ (223.66) _ 118.69 _ _ _ 109.92 _ (144.29) _ (50.47) _ 223.55 _ (118.86) _ _ _ 109.75 _ 142.86 _ 50.70 _ 223.52 _ 118.69 _ ___________________100.0%_____130.2%_______46.2%_____203.7%____108.1%____ _ Primzahlen _ (24.39) _ 2.03 _ 2.69 _ (4.91) _ (2.42) _ _ Objekt _ 23.89 _ (2.04) _ (2.47) _ 6.43 _ (3.35) _ _ erzeugen _ 23.84 _ 2.03 _ 2.64 _ 6.54 _ 2.88 _ _ _ (23.67) _ (2.03) _ (2.74) _ (8.51) _ 2.96 _ _ _ 23.87 _ 2.03 _ 2.67 _ 6.49 _ 2.92 _ ___________________100.0%_______8.5%_______11.2%______27.2%_____12.2%___ _ Sieb _ 79.97 _ (4.12) _ 6.20 _ 4.51 _ 4.12 _ _ _ 79.97 _ 4.17 _ 6.16 _ 4.51 _ 4.12 _ _ _ (79.98) _ 4.17 _ (6.20) _ (4.45) _ (4.06) _ _ _ (79.82) _ (4.17) _ (6.10) _ (4.51) _ (4.12) _ _ _ 79.97 _ 4.17 _ 6.18 _ 4.51 _ 4.12 _ ___________________100.0%_______5.2%________7.7%_______5.6%______5.2%____ _ Sortieren _ 147.59 _ 41.90 _ 9.94 _ (20.71) _ (10.82) _ _ _ (146.15) _ (41.96) _ (10.00) _ (20.21) _ 10.99 _ _ _ (148.96) _ (41.08) _ 9.77 _ 20.26 _ 10.88 _ _ _ 147.63 _ 41.91 _ (8.84) _ 20.27 _ (11.04) _ _ _ 147.61 _ 41.91 _ 9.86 _ 20.27 _ 10.94 _ ___________________100.0%______28.4%________6.7%______13.7%______7.4%___ 69 PC - Linux 2.0.x _______________________________________________ _ _JDK 1.0.2 _Netscape _ Kaffe _ ________________chapman______3.02_______0.7.0____ _ Matrizen _ 93.589 _ 99.401 _ 17.442 _ _ Multiplikation _(93.613) _(98.849) _ 17.402 _ _ _ 93.573 _ 100.250 _ (17.621) _ _ _ (93.446) _(101.384) _ (17.255) _ _ _ 93.581 _ 99.826 _ 17.422 _ __________________100.0%____106.7%_______18.6%__ _ Gauss _179.399 _ (201.751) _ (55.888) _ _ Elimination _(179.649) _201.451 _ 55.822 _ _ _(178.983) _(201.387) _ (55.681) _ _ _ 179.236 _ 201.445 _ 55.806 _ _ _ 179.318 _ 201.448 _ 55.814 _ __________________100.0%____112.3%_______31.1%___ _ Polynom _ 144.901 _ (218.059) _ 335.903 _ _ Multiplikation(_144.973) _223.024 _ (*) _ _ _(144.570) _ 224.670 _ 337.378 _ _ _ 144.800 _ (225.816) _(342.335) _ _ _ 144.851 _ 223.847 _ 336.641 _ __________________100.0%____154.5%______232.4%___ _ Primzahlen _ (35.012) _ 28.735 _ (3.463) _ _ Objekt _ 35.034 _ (29.706) _ 3.472 _ _ erzeugen _ 35.090 _ 28.182 _ 3.489 _ _ _ (39.381) _ (28.105) _ (3.544) _ _ _ 35.062 _ 28.459 _ 3.481 _ __________________100.0%_____81.2%________9.9%__ _ Sieb _ 128.143 _ (106.365) _ (7.620) _ _ _(128.090) _ 107.213 _ 7.625 _ _ _ 128.697 _ (108.195) _ 7.646 _ _ _(147.805) _ 106.467 _ (7.744) _ _ _ 128.420 _ 106.840 _ 7.636 _ __________________100.0%_____83.2%________5.9%___ _ Sortieren _202.869 _ (197.112) _ (13.921) _ _ _(202.852) _(196.913) _ 13.886 _ _ _(203.439) _ 197.066 _ (13.844) _ _ _ 203.239 _ 197.109 _ 13.872 _ _ _ 203.054 _ 197.088 _ 13.879 _ __________________100.0%_____97.1%________6.8%__ * java.lang.NullPointerException 70 Anhang C Verwendete Abku"rzungen API Application Programming Interface AWT Abtract Window(ing) Toolkit GNU GNU's Not Unix GUI Graphic User Interface IE Microsoft Internet Explorer JDK Java Development Kit JIT Just in Time JITC Just in Time-Compiler JVM Java Virtual Machine LGS Lineares Gleichungssystem MFC Microsoft Foundation Classes OMT Object Modeling Technique O( n3) Komplexit"atsmass fu"r kubische Laufzeit URL Uniform Resource Locator WWW World Wide Web X X-Window-System 71 Literaturverzeichnis [BISS97] The BISS AWT framework. Version 0.86. Wilhelmshaven: BISS GmbH, Januar 1997. [Dalh97] Matthias Kalle Dalheimer: Java Virtual Machine. Sprache, Konzept, Architek- tur. K"oln: O'Reilly Verlag, 1997. [Dong96] Jack J. Dongarra: Performace of Various Computers using Standard Linear Equa- tions Software. Computer Science department, University of Tennessee, November 1996. http://www.netlib.org/benchmark/performance.ps [Flan96] David Flanagan: Java in a Nutshell. A desktop Quick Reference for Java Programmers. Sebastopol: O'Reilly & Associates, Inc., 1996. [Foot96] Bill Foote: Integrating Java with C++. Learn how to use C++ code from within a Java application and how to call from C++ to a Java object. Oktober 1996. http://www.javaworld.com/javaworld/javatips/jw-javatip17.html [GHJV96] Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides: Entwurfs- muster. Elemente wiederverwendbarer objektorientierter Software. Bonn: Addison- Wesley, 1996. S. 401ff. [Gu"nt97] Edwin Gu"nthner: Portierung der JVM auf den Video- und Multimediaprozessor TMS320C80. Studienarbeit am Institut fu"r Programmstrukturen und Datenorganisation. Karlsruhe, 1997. [Java96a] The Java Native Code API. JavaSoft, 30.7.1996. http://www.javasoft.com/doc/jit_interface.html [Java96b] The Java Native Method Interface. JavaSoft, 1996. http://www.javasoft.com/products/jdk/1.1/docs/guide/jni/spec/jniTOC.doc.html [LiYe96] Tim Lindholm, Frank Yellin: The Java Virtual Machine Specifikation. Addison- Wesley, 1996. [Phil96] Michael Philippsen (Hg.): Java Seminarbeitr"age. Technical report 24/96. Univer- sit"at Karlsruhe, Juli 1996. [Sedg91.1] Robert Sedgwick: Algorithmen. Bonn: Addison-Wesley, 1991. S. 607ff. [Sedg91.2] ebd. S. 591ff. 72 [Sedg91.3] ebd. S. 136ff. [Sun94] The Java Language: A White Paper. Sun Microsystems, 1994. [Sun95a] The Java Language Specification. Version 1.0 Beta. Sun Microsystems, Oktober 1995. [Sun95b] The Java Virtual Machine Specification. Sun Microsystems, M"arz 1995. [Sun95c] The Java Language Environment. A White Paper. Sun Microsystems, Mai 1995. [Venn96] Bill Venners: Unter the Hood: Java's garbage-collected heap. An inroduction to the garbage-collected heap of the HJava virtual machine. Juli 1996. http://www.javaworld.com/javaworld/jw-08-1996/jw-08-gc.html [Yu95] Nelson Yu: Inroduction to the AWT. 1995. 73