Das Modell

Das folgende Modell betrachtet Laufzeit als maßgebliche Größe für Optimierungsentscheidungen. Es lehnt sich an das in [Arnold et al., 2000b] dargestellte Modell an, und ergänzt einige zusätzliche Betrachtungen.

Es seien zwei vereinfachende Annahmen gemacht: erstens ist die Einheit der Übersetzung eine Methode m ohne Betrachtung von inlining, zweitens wird sequentielle Verarbeitung angenommen, d.h. die Möglichkeit paralleler Übersetzung wird nicht in Betracht gezogen. Wegen dieser und folgender Vereinfachungen eignet sich das Modell nur für qualitative Aussagen.

Es werden drei Komponenten betrachtet:

• Erwartete Restlaufzeit bei Interpretation t_int: Wieviel Zeit wird das Programm erwartungsgemäß durch Interpretation der betrachteten Methode in Anspruch nehmen?
• Erwartete Restlaufzeit mit optimierender Übersetzung t_opt: Wieviel Zeit wird das Programm erwartungsgemäß in Ausführung der übersetzten Methode verbringen?
• Übersetzungszeit t_comp: Wie lange dauert die Übersetzung der Methode?

Die Übersetzung der Methode ist nur lohnenswert, wenn Übersetzungszeit plus erwartete Restlaufzeit der optimierten Methode kleiner sind als der Interpretationsaufwand:

t_comp + t_opt < t_int (3.1)

Die drei Komponenten lassen sich weiter aufschlüsseln:

• Die Übersetzungszeit hängt vor allem von der Komplexität der verwendeten Optimierungsalgorithmen ab, und damit von der zu übersetzenden Methode. Relevante Größen sind hier die reine Methodengröße (Anzahl der Instruktionen), die Schleifen- und Sprungstruktur und damit die Struktur des Kontrollflußgraphen sowie die Zahl der verwendeten Variablen (z.B. für die Registerallokation). Da die beiden letzen Größen erst während eines Übersetzungsvorgangs offenbar werden, verwenden [Arnold et al., 2000b] ein lineares Modell der Methodengröße^3.1, welches durch entsprechende Messungen erarbeitet wurde. Es folgt:
  

  t_comp = c * |m| (3.2)

  
  
  c drückt die Zeitkomplexität der Optimierungsalgorithmen aus.
• Die Laufzeit der optimierten Methode variiert ebenfalls mit der Struktur des Programmcodes. Es kann also nur eine ungenaue Vorhersage über die Effektivität der Optimierungen gemacht werden. Entsprechend der Vorlage wird hier ebenfalls von einem konstanten Faktor ausgegangen:
  

  $$t_{opt} = \frac{t_{int}}{s}$$ (3.3)

  
  
  s > 1 drückt hier die Beschleunigung (speedup) der Methode aus und ist ebenfalls aus Erfahrungswerten abzuleiten.
• Man geht bei einem laufenden, nicht-interaktiven System von einer relativ stabilen Verteilung der Laufzeit auf einzelne Programmteile aus, so daß die Laufzeit einer Methode ein bestimmter Bruchteil der Gesamtrestlaufzeit ist.
  

  t_int = p * t_rest (3.4)

  
  
  Der Anteil p der betrachteten Methode an der Gesamtlaufzeit kann aufgrund der Stabilitätsannahme aus dem Laufzeitprofil des laufenden Programms gewonnen werden.

Setzt man obige Gleichungen ineinander ein, so ergibt sich, daß eine Übersetzung lohnenswert ist, wenn gilt:

$$c * \vert m\vert + \frac{p * t_{rest}}{s} < p * t_{rest}$$ (3.5)

resp.

$$\frac{\vert m\vert}{p * t_{rest}} < \frac{1}{c} * \left( 1 - \frac{1}{s} \right)$$ (3.6)

Die einfließenden Größen noch einmal zusammengefasst:

|m|	Methodengröße
p	Anteil der interpretierten Methode an der Programmlaufzeit
s	Maß für die Effektivität des Compilers
c	Maß für die Zeitkomplexität des Compilers
trest	Erwartete Restlaufzeit des Programms

Das vorgestellte Modell kann leicht auf ein System mit mehreren, unterschiedlich stark optimierenden Compilern erweitert werden.