Delphi-Internals: Compilerverhalten bei Case statements

[Lemmy1]

Hi Zusammen

ich habe mal ein paar empirische Tests gemacht zu dem Thema, wie Delphi Case statements umsetzt. Verwendet hierzu hab ich Delphi 2005 Professional Win32. Unter .NET sieht die Sache sicher anders aus. Zu erst aber ein Bisschen Theorie, warum ich das ganze gemacht hab.

Generelles vorweg: Prinzipiell gibt es ja zwei Methoden, wie ein Compiler ein Case statement kompilieren kann:

• Prüfen des Wertes gegen jeden Wert der Liste (entspricht if i=c1 then else if i=c2 then else if i=c3...)
• Erstellung einer Sprungtabelle zur Compilierzeit, aus der direkt die Zieladresse ersichtlich ist.

Was muss der Prozessor dabei tun? Die erste besteht aus Vergleichen und Sprüngen während die zweite aus Speicheroperation und EINEM Sprung erfolgt (dieser ist jedoch langsamer als die Einzelsprünge vorher, da die Zieladresse unbekannt ist).

Unmittelbar klar ist, dass die zweite Variante mehr Speicher benötigt, da für jeden potentiell auftretenden Wert ein Eintrag in der Tabelle von Nöten ist. Folgender Code beispielsweise würde als Tabelle keinen Sinn machen:

Delphi-Quellcode:

Case SomeValue of
  0 : dosomething;
  1000000: dosomethingelse;
end;

Die Tabelle hierfür wäre gigantisch müsste intern 1000000 Elemente speichern, das wären 1000000*4 Bytes = 4.000.000 Bytes = circa 4MB nur für diese 2 Zeilen

Im Gegensatz dazu würde ein Case über ein Byte b gegen alle Werte von 0 bis 255 sehr wohl sinn machen als Tabelle, da dann nicht im schlimmsten Fall 254 Vergleiche nötig wären. Typische Anwendung für so etwas wäre übrigens ein Emulator Jaja da komm ich eben her...

Welche Variante wählt also der Delphi Compiler? Gute Nachricht: Er kann beides und versucht zu ermitteln, welche ihm sinnvoller erscheint.

Getestet habe ich Code in der Art:

Delphi-Quellcode:

var
  i : Integer;
begin
  i := Random(1000);
  case i of
    0 : begin
      i := i div 40;
    end;
    3 : begin
      i := i div 60;
    end;
    // hier noch mehr Prüfungen...
  end;
  Caption := IntToStr(i);  // wichtig, da sonst ALLES wegoptimiert wird :)
end;

Wovon hängt es nun also ab, welche Variante der Compiler verwendet? Ich habe folgende Größen ausmachen können:
a: Differenz zwischen dem Größten und dem Kleinsten Wert (bei den beiden Prüfungen oben wäre das 3)
b: Anzahl der Prüf-Werte ohne "else" Teil

Zu erst die Messwerte (wir wollen das ganze ja streng wissenschaftlich angehen)

b | a | Ergebnis
---+----+-------------
4 | 20 | Einzelbedingungen
5 | 24 | Sprungtabelle
5 | 25 | Einzelbedingungen
8 | 39 | Sprungtabelle
8 | 40 | Einzelbedingungen
9 | 44 | Sprungtabelle
9 | 45 | Einzelbedingungen

Ablesen kann man also folgendes:
Für 4 und weniger Bedingungen:
Immer Prüfung mit Einzelabfragen
Ab 5 gilt:
Wenn a<4*b dann Sprungtabelle sonst Einzelbedingungen


Scheint ja bisher recht einfach, aber der Compiler ist noch ein Stück schlauer. Anscheinend kann er sogar Partitionen von Zahlen erkennen. Ein Beispiel:

Delphi-Quellcode:

  case i of
    0 : begin
      i := i div 2;
    end;
    1 : begin
      i := i div 2;
    end;
    2 : begin
      i := i div 2;
    end;
    3 : begin
      i := i div 2;
    end;
    4 : begin
      i := i div 2;
    end;
    5 : begin
      i := i div 2;
    end;
    100000 : begin
      i := i div 3;
    end;
    100001 : begin
      i := i div 3;
    end;
    100002 : begin
      i := i div 3;
    end;
    100003 : begin
      i := i div 3;
    end;
    100004 : begin
      i := i div 3;
    end;
    100005 : begin
      i := i div 3;
    end;
  end;

Hier erkennt der Compiler in der Tat, dass er 2 seperate Sprungtabellen anlegen kann. Welche davon nötig ist, prüft ein voriges CMP. Innerhalb dieser Partitionen scheint oben beschriebene a<4*b Regel weiterhin zu gelten.

Also mein Fazit des ganzen. Hut ab für Borland. Solche Optimierungen hatte ich gar nicht erwartet Nun ist aber Zeit für

Trotzdem wäre case über strings schön