Class Hierarchy Analysis

Abbildung 3.6: Beispiel einer Klassenhierarchie

Wie bereits in Abschnitt 2.1.2 beschrieben, stellt der dynamische Methodenaufruf ein großes Problem bei der Optimierung von Java-Programmen dar. Als Beispiel sei der folgende Aufruf auf der in Abbildung 3.6 dargestellten Klassenhierarchie angenommen. In Verlauf der Methode y in der Klasse X findet eine dynamischer Aufruf der Methode m an dem Empfängerobjekt c statt.

  public class X extends Object{
    public void y(C c){
      ...
      c.m();
      ...
    }
  }

Ohne globale Analysen kann der Aufruf von m nur mit einer Sicherungsinstruktion (guard) in einen statischen Aufruf gewandelt werden, da einen Subklasse von C die aus A geerbte Implementierung überschreiben könnte. Es könnte also lediglich der folgende Umstellung des Codes vorgenommen werden.

  public class X extends Object{
    public void y(C c){
      ...
      if(c.class == C)          // guard
        c.A::m();               // perform static call 
      else                      // if class test fails 
        c.class.dispatch(m);    // perform dynamic dispatch
                                // on receiver               
      ...
    }
  }

Die Auswirkung dieser Maßnahme auf die Performance hängt von der Aufrufhäufigkeit von y mit einer Instanz von C als Empfänger ab - vor einer solchen Optimierung sollte also eine Erhebung von Laufzeitprofilen erfolgt sein.

Hat der Optimierer jedoch Kenntnis von allen Subklassen von C, so kann der dynamische Aufruf von m direkt in einen statischen Aufruf von A::m ohne guard gewandelt werden, da keine der geladenen Klassen Subklassen von C (D und E) diese Methode überschreibt. Für jeden Aufruf von X::y muß also A::m aufgerufen werden. Der Optimierer kann demnach den folgenden Code produzieren:

  public class X extends Object{
    public void y(C c){
      ...
      c.A::m();                // perform static call w/o guard
      ...
    }
  }

Dieser Optimierung kann jetzt eine Integration der Methode A::m in den Methodenkörper von y folgen.

Die im Beispiel dargestellte Optimierung ist nur aufgrund der statischen, klassenbasierten Typisierung Javas möglich. Erst durch die Information über die Klassen des Parameters c wird klar, welche Methode gerufen werden soll. Sowohl in dynamisch typisierten Systemen (z.B. Smalltalk), als auch in statisch typisierten Systemen mit struktureller Subtypisierung (z.B. Tycoon-2 [Ernst, 1998]) ist die Möglichkeit der Optimierung durch globale Klassenanalysen stärker beschränkt.

Optimierung aufgrund von globalen Analysen der Klassenhierarchie findet - zumindest in moderater Form - in praktisch jeder Java-Maschine mit optimierendem Compiler statt. [Dean, 1996] hat diese Form der Analyse bereits 1996 als class hierarchy analysis formalisiert und eine Implementierung für den Vortex-Compiler beschrieben.