Computed Goto's in C/C++

[Bernd (Gast)]

Hallo,

ich überlege gerade, wie man am schnellsten in Abhängigkeit von einer 
Variable in einer Funktion verzweigen kann.

Standardmäßig wäre ja:

switch(x){
  case 43: break;
  case 78: break;
  ...
}

Intern macht der Compiler da ja wohl so etwas wie

if (43) ...
else if (78) ...
else if .....

draus.

Wenn ich jetzt mal davon ausgehe, dass x nur Werte von 0 bis 255 
annehmen kann, und ich genug Speicher habe, wäre doch eine Sprungtabelle 
eine feine Sache.
Nun könnte man ja ein Array mit Function Pointern verwenden, aber 
letztlich will ich ja keine Funktionen aufrufen, die auch noch einen 
Hin- und einen Rücksprung nach sich ziehen, sondern nur innerhalb eines 
Funktionsabschnitts (ähnlich 'switch') in Unterbereiche verzweigen, dass 
aber möglichst schnell.
Macht es eigentlich Geschwindigkeitstechnisch einen Unterschied, ob die 
Programmausführung nur zweimal Spring (wie es bei switch der Fall sein 
dürfte; Anspringen der case Position und mit break dann zum Ende des 
switch Blocks) oder ob ich ein Unterprogramm mit Hin- und Rücksprung + 
Stackmanipulation ausgeführt wird (ohne Parameter)?

In Assembler würde man hier warscheinlich computed gotos verweden. Das 
ginge dann auch immer mit relativen Sprüngen.

Vielleicht so etwas wie:

int function(x) {
  unsigned long address[]={label1, &label2, &label3,....}; // 256 Werte
 
  goto address[x];
  
  return 0;

lable1: 
  ......
  goto end:
label2:
  ......
  goto end;
label3:
  ....
  goto end;

end:
  return 1;
}

Danke,
Bernd

[Karl H. (kbuchegg)]

> Vielleicht so etwas wie:

Die Chancen stehen nicht schlecht, dass der Compiler genau
so etwas bei einem switch-case implementiert.
Einfach mal ausprobieren und den Assembler Code anschauen.

[Rolf Magnus (Gast)]

> Intern macht der Compiler da ja wohl so etwas wie
> if (43) ...
> else if (78) ...
>else if .....
>
> draus.

Bei wenigen Werten in der Regel ja.

> Wenn ich jetzt mal davon ausgehe, dass x nur Werte von 0 bis 255
> annehmen kann, und ich genug Speicher habe, wäre doch eine
> Sprungtabelle eine feine Sache.

Deshalb machen Compiler das auch so, sofern die Anzahl an case-Labels so 
hoch ist, daß es sich lohnt.

[blub (Gast)]

array mit functions pointern ?

[Bernd (Gast)]

Nun ja, dann scheint der Compiler im Visual Studio (ok kein GCC)

00587CDA  mov         eax,dword ptr [nCtlColor]
00587CDD  mov         dword ptr [ebp-0DCh],eax
00587CE3  cmp         dword ptr [ebp-0DCh],1
00587CEA  je          CBaseView::OnCtlColor+0EFh (587D8Fh)
00587CF0  cmp         dword ptr [ebp-0DCh],3
00587CF7  je          CBaseView::OnCtlColor+67h (587D07h)
00587CF9  cmp         dword ptr [ebp-0DCh],6
00587D00  je          CBaseView::OnCtlColor+67h (587D07h)
00587D02  jmp         CBaseView::OnCtlColor+0F4h (587D94h)

entwerder nicht sehr gut zu sein, oder er benutzt die Sprungtabelle nur 
wenn nicht im Debug Modus compilert wird, nur weiß ich da nicht, wie ich 
die Stelle im Objectcode finden soll, da ja eine Debugging Informationen 
mehr drin stecken.

Oben wird aber mit #1, #3 und #6 verglichen und entsprchend gesprungen 
(je) und wenn nichts zutrifft mit jmp in den default-Zweig der 
switch-Anweisung.

Das Problem mit Function-Pointern ist, dass da ja Funktionen aufgerufen 
werden, die ihren eigenen Scope haben, also ich nicht lokale Variabeln 
der aufrufenden Funktion weiter verwenden kann, ohne sie irgendie 
weiterzureichen, was, wie auch immer man es macht, in jedem Fall auch 
Rechenzeit kostet.

Grüße,
Bernd

[... (Gast)]

Der Compiler von Visual Studio ist im allgemeinen sehr gut, was die 
Optimierungen betrifft. Im Debug-Modus wird natürlich nicht optimiert. 
Also compilier es im Realease-Modus und mach dir erst Gedanken üder 
solche Probleme, wenn das Programm wirklich zu langsam geworden ist. Die 
C/C++ Compiler sind heutzutage so gut, dass du als mittelmäßiger 
Assemblerprogrammierer mit Sicherheit keinen besseren Code programmieren 
kannst. Der wichtigste Ansatzpunkt für Optimierungen ist natürlich immer 
noch der Algorithmus.

[Karl H. (kbuchegg)]

Bernd wrote:

Das was ... (Gast) bereits sagte.

Plus

> 00587CDA  mov         eax,dword ptr [nCtlColor]
> 00587CDD  mov         dword ptr [ebp-0DCh],eax
> 00587CE3  cmp         dword ptr [ebp-0DCh],1
> 00587CEA  je          CBaseView::OnCtlColor+0EFh (587D8Fh)
> 00587CF0  cmp         dword ptr [ebp-0DCh],3
> 00587CF7  je          CBaseView::OnCtlColor+67h (587D07h)
> 00587CF9  cmp         dword ptr [ebp-0DCh],6
> 00587D00  je          CBaseView::OnCtlColor+67h (587D07h)
> 00587D02  jmp         CBaseView::OnCtlColor+0F4h (587D94h)
>
> entwerder nicht sehr gut zu sein, oder er benutzt die Sprungtabelle nur
> wenn nicht im Debug Modus compilert wird, nur weiß ich da nicht, wie ich
> die Stelle im Objectcode finden soll, da ja eine Debugging Informationen
> mehr drin stecken.
>
> Oben wird aber mit #1, #3 und #6 verglichen und entsprchend gesprungen
> (je) und wenn nichts zutrifft mit jmp in den default-Zweig der
> switch-Anweisung.

Ja. Aber eine Sprungtabelle ist in diesem Beispiel auch keine
wirklich gute Lösung.
Zum einen sind deine Werte nicht durchgehend, d.h. die Tabelle
hat Lücken. Ein Compiler muss ja auch darauf achten, dass er
ökonomisch mit dem Speicher umgeht. Wenn in einer Sprungtabelle
von 6 Einträgen nur 3 interessant sind, dann ist das nicht wirklich
ökonomisch. 6 Pointer + Auswertelogik verbrauchen mit ziemlicher
Sicherheit (ich habs jetzt nicht nachgerechnet) schon mehr Speicher
und auch Rechenzeit als obige Verzweigungsleiste.

Diese Sequenz

> 00587CE3  cmp         dword ptr [ebp-0DCh],1
> 00587CEA  je          CBaseView::OnCtlColor+0EFh (587D8Fh)
> 00587CF0  cmp         dword ptr [ebp-0DCh],3
> 00587CF7  je          CBaseView::OnCtlColor+67h (587D07h)
> 00587CF9  cmp         dword ptr [ebp-0DCh],6
> 00587D00  je          CBaseView::OnCtlColor+67h (587D07h)
> 00587D02  jmp         CBaseView::OnCtlColor+0F4h (587D94h)

durch etwas funktional gleichwertiges mit Tabelle zu ersetzen,
das auch noch schneller ist, wird dir nicht gelingen.
Was müsste gemacht werden

* Es muss getestet werden, ob der Wert > 6 oder < 1 ist
  wenn ja -> default anspringen
* Startadresse der Tabelle holen (das sind 6 Adressen im Speicher)
* den Indexwert mit sizeof(Pointer) multiplizieren und zur
  Startadresse addieren
* mit der jetzt bekannten Speicheradresse die Sprungadresse aus
  der Tabelle holen
* den indirekten Sprung ausführen

Wie du das mit weniger Speicherverbrauch (vergiss die Pointer Tabelle
nicht) und weniger Rechenzeitverbrauch als 3 cmp und 3 je hinkriegen
willst (2 cmp und 2 bedingte Sprünge brauchst du schon mal für
die Überprüfung ob die Eingangszahl sich überhaupt als Tabellen-
index eignet), ist mir ehrlich gesagt ein Rätsel.

Von wegen:
> entwerder nicht sehr gut zu sein

das Gegenteil ist eher der Fall.
Der Compiler kann wesentlich besser optimieren als du.
Du versuchst etwas zu optimieren, was so nicht mehr zu optimieren ist.

[Rolf Magnus (Gast)]

> nun ja, dann scheint der Compiler im Visual Studio (ok kein GCC)
> entwerder nicht sehr gut zu sein, oder er benutzt die Sprungtabelle nur
> wenn nicht im Debug Modus compilert wird,

Oder er hat, wie ich schon geschrieben habe, erkannt, daß es bei so 
wenig Werten sinnlos ist. Eine Sprungtabelle besitzt auch einen gewissen 
Overhead, und bei gerade einmal drei Werten lohnt sie sich nicht.

@...:

> Im Debug-Modus wird natürlich nicht optimiert.

So natürlich finde ich das nicht. Wie sinnvoll es ist, einen Code zu 
debuggen, der anders ist als der Release-Code, darüber kann man 
streiten. Vor allem bei Optimierungen, die oft noch so manchen vorher 
unbemerkten Fehler zutage fördern.

[... (Gast)]

Das "natürlich" bezog sich darauf, dass die Standardenistellungen so 
eingestellt sind, dass im debug build nicht optimiert wird.

[Bernd (Gast)]

OK, da war ich wohl zu voreilig. Habe mir mal ein Programm geschrieben, 
dass das Ganze noch einmal testet. Scheint wirklich so, als ob der 
Compiler bei zusammenhängenden Blöcken tatsächlich eine Sprungtabelle 
verwendet.

Grüße,
Bernd


int main(){
004132D0  push        ebp
004132D1  mov         ebp,esp
004132D3  sub         esp,0DCh
004132D9  push        ebx
004132DA  push        esi
004132DB  push        edi
004132DC  lea         edi,[ebp-0DCh]
004132E2  mov         ecx,37h
004132E7  mov         eax,0CCCCCCCCh
004132EC  rep stos    dword ptr es:[edi]
  int i;
  unsigned char select=8;
004132EE  mov         byte ptr [select],8

  switch(select) {
004132F2  movzx       eax,byte ptr [select]
004132F6  mov         dword ptr [ebp-0DCh],eax
004132FC  cmp         dword ptr [ebp-0DCh],0C8h
00413306  ja          $LN2+9 (413376h)
00413308  mov         ecx,dword ptr [ebp-0DCh]
0041330E  movzx       edx,byte ptr  (4133B4h)[ecx]
00413315  jmp         dword ptr  (413388h)[edx*4]
  case 0: i=0; break;
0041331C  mov         dword ptr [i],0
00413323  jmp         $LN2+10h (41337Dh)
  case 8: i=1; break;
00413325  mov         dword ptr [i],1
0041332C  jmp         $LN2+10h (41337Dh)
  case 9: i=1; break;
0041332E  mov         dword ptr [i],1
00413335  jmp         $LN2+10h (41337Dh)
  case 12: i=1; break;
00413337  mov         dword ptr [i],1
0041333E  jmp         $LN2+10h (41337Dh)
  case 13: i=1; break;
00413340  mov         dword ptr [i],1
00413347  jmp         $LN2+10h (41337Dh)
  case 14: i=1; break;
00413349  mov         dword ptr [i],1
00413350  jmp         $LN2+10h (41337Dh)
  case 15: i=1; break;
00413352  mov         dword ptr [i],1
00413359  jmp         $LN2+10h (41337Dh)
  case 16: i=1; break;
0041335B  mov         dword ptr [i],1
00413362  jmp         $LN2+10h (41337Dh)
  case 17: i=1; break;
00413364  mov         dword ptr [i],1
0041336B  jmp         $LN2+10h (41337Dh)
  case 200: i=1; break;
0041336D  mov         dword ptr [i],1
00413374  jmp         $LN2+10h (41337Dh)
  default: i=1000; break;
00413376  mov         dword ptr [i],3E8h
  }

};