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 :duck:

Trotzdem wäre case über strings schön :)

[jim_raynor]

Hast du jetzt fragen dazu? Oder möchtest du deine Ergebnisse bestätigt haben?

Ich kann sagen, dass der Compiler sich auch ausnutzt, dass ein Vergleich auf 0 schneller ist als auf einen beliebigen Wert.

Wenn du also so etwas hat:

Delphi-Quellcode:

case a of
  $1234656 : ...
  $1434534 : ...
  $2122312 : ...
end;

Dann sortiert er sich die Werte aufsteigend und zieht immer die Differenz vom vorherigen Wert von der Variablen a ab.

Also sortiert sähe es so aus.

$1234656
$1434534
$2122312

Jetzt zieht er von a $1234656 ab vergleicht es mit 0 ist es wahr, stimmt der Wert über ein ist es falsch, wird widerrum $1FFEDE (Differenz $1434534 und $1234656) von von a abgezogen. Ist es jetzt 0 hat er den entsprechenden Wert gefunden. Wenn nicht, verfährt er so mit dem nächsten Wert im Case-Statement weiter.

Also der Compiler optimiert schon ziemlich gut. Und das ist nicht nur bei Case so. Auch For Schleifen können sehr gut optimiert werden, in dem zum Beispiel Rückwärtsgezählt wird, oder Schleifen aufgebrochen werden. Deshalb ist es heutzutage fast unnütz zu versuchen mit Assembler bessere Ergebnisse zu erzielen.

[Lemmy1]

Zitat:

Zitat von jim_raynor

Hast du jetzt fragen dazu? Oder möchtest du deine Ergebnisse bestätigt haben?

Nein ich hab keine Fragen dazu, wollte nur die Allgemeinheit an meinen Erkenntnissen teilhaben lassen :) ich war überrascht, da ich nicht erwartet hatte, dass Delphi überhaupt Jumptables aufbaut :)

Gruß

[Pseudemys Nelsoni]

btw man kann wenn man für mehrere zahlen das gleiche machen möchte auch:

Delphi-Quellcode:

case bla of
  1,2,3,4,5: begin
               //irgendwas
             end;

bzw

Delphi-Quellcode:

case bla of
  1..5: begin
               //irgendwas
             end;

schreiben.

[roderich]

@Pseudemys Nelsoni:
ist dem Lemmy1 sicher klar, aber es ging ja gar nicht um die Codierung, sondern um die Intelligenz des Compilers, der 2 getrennte Sprungtabellen bildet.

@Lemmy1:
Dein Posting find ich klasse, informativ und gut recherchiert.
echt ne Wohltat unter x anderen Postings hier nach dem Motto "ich hab nen Button1 und will mit der Maus draufklicken, wie mach ich das nur......"


Roderich

[Lemmy1]

Zitat:

Zitat von roderich

@Pseudemys Nelsoni:
ist dem Lemmy1 sicher klar, aber es ging ja gar nicht um die Codierung, sondern um die Intelligenz des Compilers, der 2 getrennte Sprungtabellen bildet.

@Lemmy1:
Dein Posting find ich klasse, informativ und gut recherchiert.
echt ne Wohltat unter x anderen Postings hier nach dem Motto "ich hab nen Button1 und will mit der Maus draufklicken, wie mach ich das nur......"


Roderich

Dankeschön :)

[Lemmy1]

Dazu ein Frage an die Admins: Ist das das richte Board für solche Beiträge oder gibts da ein besseres für? Zugegeben ist ein keine "Frage" aber ich könnt mir vorstellen, das sowas auch andere interesiert...

Gruß

[Kedariodakon]

Mal so eine kleine dumme Frage dazu, woran erkenn ich überhaupt, das er eine Sprungtabelle anlegt, geschweige den 2 Sprungtabellen oder mehr :gruebel:

Bye

[Jasocul]

Grundkenntnisse (mehr ist besser) in Assembler und das CPU-Fenster in der IDE helfen bei solchen Analysen sehr viel.

[Robert Marquardt]

Ein guter Compiler koennte da noch viel interessantere Implementierungen machen.
Beispielsweise die einzelnen Cases umsortieren und eine sortierte Sprungtabelle anlegen, die per binaerer Suche ausgewertet wird.