Manche objektorientierte Sprachen, z.B. Java oder X10, unterstützen nur Einfachvererbung zwischen Klassen, erlauben aber Mehrfachimplementierung von Interfaces. Interfaces enthalten keine Felder und definieren keine Methodenimplementierungen. Für den Compiler stellt sich hierbei die Frage, wie dynamisch gebundene Interface-Aufrufe implementiert werden.

Zur Implementierung von dynamisch gebundenen Methoden werden üblicherweise vtables benutzt. Prinzipiell ist es möglich, Interfaces genauso zu behandeln wie zusätzliche Oberklassen und die Techniken für Mehrfachvererbung anzuwenden. Dies würde bedeuten, dass ein Objekt mehrere vptrs enthalten kann und unter Umständen auch der this-Zeiger verschoben werden muss. Da es in Java und X10 üblich ist, viele Interfaces zu verwenden, würde dies häufig größere Objekte und deutlich erhöhte Komplexität bedeuten.

Daher werden in Java und X10 Klassenvererbung und Interfacevererbung unterschiedlich implementiert (siehe z.B. auch unterschiedliche Java-Bytecodes invokevirtual und invokeinterface). Durch Einfachvererbung zwischen Klassen reicht dann ein vptr pro Objekt aus und eine Verschiebung des this-Zeigers ist nicht nötig. Für Interface-Aufrufe wird ein anderer Mechanismus verwendet. Das einfachste Verfahren (Class Object Search) durchsucht bei jedem Interface-Aufruf zur Laufzeit die Klassenhierarchie, bis die gewünschte Methode gefunden wurde. Die Suche arbeitet auf der Laufzeit-Typinformation (Runtime Type Information, RTTI). Dieser Ansatz ist momentan in liboo, einer Hilfsbibliothek für objektorientierte Sprachkonstrukte, implementiert.

Es existieren schnellere, tabellenbasierte Implementierungsarten, welche sich vom vtable-Mechanismus dadurch unterscheiden, dass keine klassenhierarchieweit eindeutigen Methodenindizes benötigt werden. Ein tabellenbasierter Ansatz sind Searched ITables. Annahme ist, dass man alle Interfaces zur Compilezeit kennt und durchnummerieren kann. Nun wird für jedes Paar (K, I) von Klasse K und Interface I eine itable genannte Tabelle erzeugt, die Funktionszeiger auf die K-Implementierungen der Methoden von I enthält. Alle itables einer Klasse K werden in einem Array von itables gespeichert, das zur Laufzeit ausgehend von einer K-Objektreferenz zugänglich ist. Bei einem Interface-Aufruf wird nun zur Laufzeit die zum Interface passende itable ausgewählt und daraus die richtige Methodenimplementierung aufgerufen.

Ziel der Arbeit ist es, einen geeigneten tabellenbasierten Ansatz für Interface-Aufrufe, z.B. Searched ITables, zu implementieren. Die Implementierung soll mittels des Java-Bytecode-Frontends bytecode2firm und des X10-Frontends X10i getestet und evaluiert werden.

Aufgabe:

• Sie implementieren einen tabellenbasierten Ansatz, etwa Searched ITables, für Interface-Aufrufe.
• Sie testen und evaluieren Ihre Implementierung mit Hilfe von bytecode2firm und X10i.

Voraussetzungen

• Kenntnisse in Implementierungstechniken für objektorientierte Sprachen (z.B. aus Fortgeschrittene Objektorientierung)
• Erfahrung mit libFIRM (z.B. aus Compilerpraktikum) vorteilhaft

Literatur

• Efficient Implementation of Java Interfaces: Invokeinterface Considered Harmless, Bowen Alpern et al., besonders Abschnitt 7.1
• FIRM
• libFIRM
• libOO
• Bytecode2firm
• X10i



Veröffentlichungen

Veröffentlichung

Verbesserte Implementierung von Interface-Aufrufen

Betreuer

Ehemalige Mitarbeiter
Dr.-Ing. Manuel Mohr

Studenten

Ehemalige Studenten
Philipp Serrer