AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Sprachen und Entwicklungsumgebungen Sonstige Fragen zu Delphi Delphi Delphi-Internals: Compilerverhalten bei Case statements

Delphi-Internals: Compilerverhalten bei Case statements

Ein Thema von Lemmy1 · begonnen am 7. Dez 2004 · letzter Beitrag vom 27. Aug 2005
Antwort Antwort
Seite 1 von 2  1 2   
Benutzerbild von Lemmy1
Lemmy1

Registriert seit: 28. Nov 2004
Ort: Ismaning
184 Beiträge
 
Delphi 2006 Professional
 
#1

Delphi-Internals: Compilerverhalten bei Case statements

  Alt 7. Dez 2004, 02:15
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
Daniel
www.nemu.com - The N64 Emulator
  Mit Zitat antworten Zitat
Benutzerbild von jim_raynor
jim_raynor

Registriert seit: 17. Okt 2004
Ort: Berlin
1.251 Beiträge
 
Delphi 5 Standard
 
#2

Re: Delphi-Internals: Compilerverhalten bei Case statements

  Alt 7. Dez 2004, 07:02
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.
Christian Reich
Schaut euch mein X-COM Remake X-Force: Fight For Destiny ( http://www.xforce-online.de ) an.
  Mit Zitat antworten Zitat
Benutzerbild von Lemmy1
Lemmy1

Registriert seit: 28. Nov 2004
Ort: Ismaning
184 Beiträge
 
Delphi 2006 Professional
 
#3

Re: Delphi-Internals: Compilerverhalten bei Case statements

  Alt 7. Dez 2004, 19:00
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ß
Daniel
www.nemu.com - The N64 Emulator
  Mit Zitat antworten Zitat
Benutzerbild von Pseudemys Nelsoni
Pseudemys Nelsoni

Registriert seit: 24. Dez 2002
Ort: Hamburg-Harburg
3.551 Beiträge
 
#4

Re: Delphi-Internals: Compilerverhalten bei Case statements

  Alt 7. Dez 2004, 19:06
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.
Mario
MSN: cyanide@ccode.de
  Mit Zitat antworten Zitat
roderich
(Gast)

n/a Beiträge
 
#5

Re: Delphi-Internals: Compilerverhalten bei Case statements

  Alt 7. Dez 2004, 19:16
@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
  Mit Zitat antworten Zitat
Benutzerbild von Lemmy1
Lemmy1

Registriert seit: 28. Nov 2004
Ort: Ismaning
184 Beiträge
 
Delphi 2006 Professional
 
#6

Re: Delphi-Internals: Compilerverhalten bei Case statements

  Alt 7. Dez 2004, 21:25
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
Daniel
www.nemu.com - The N64 Emulator
  Mit Zitat antworten Zitat
Benutzerbild von Lemmy1
Lemmy1

Registriert seit: 28. Nov 2004
Ort: Ismaning
184 Beiträge
 
Delphi 2006 Professional
 
#7

Re: Delphi-Internals: Compilerverhalten bei Case statements

  Alt 12. Dez 2004, 13:04
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ß
Daniel
www.nemu.com - The N64 Emulator
  Mit Zitat antworten Zitat
Benutzerbild von Kedariodakon
Kedariodakon

Registriert seit: 10. Sep 2004
Ort: Mönchengladbach
833 Beiträge
 
Delphi 7 Enterprise
 
#8

Re: Delphi-Internals: Compilerverhalten bei Case statements

  Alt 13. Jul 2005, 11:24
Mal so eine kleine dumme Frage dazu, woran erkenn ich überhaupt, das er eine Sprungtabelle anlegt, geschweige den 2 Sprungtabellen oder mehr

Bye
Christian
  Mit Zitat antworten Zitat
Benutzerbild von Jasocul
Jasocul

Registriert seit: 22. Sep 2004
Ort: Delmenhorst
1.354 Beiträge
 
Delphi 11 Alexandria
 
#9

Re: Delphi-Internals: Compilerverhalten bei Case statements

  Alt 13. Jul 2005, 11:33
Grundkenntnisse (mehr ist besser) in Assembler und das CPU-Fenster in der IDE helfen bei solchen Analysen sehr viel.
Peter
  Mit Zitat antworten Zitat
Robert Marquardt
(Gast)

n/a Beiträge
 
#10

Re: Delphi-Internals: Compilerverhalten bei Case statements

  Alt 13. Jul 2005, 11:42
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.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 12:58 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz