Stack, Funktionsaufruf

blurry333

Wenn die funktion rekursiv 10 mal aufgerufen wird, dann sind es schon 5 * 10 also 50 Variablen auf dem stack !!

blurry333 schrieb:

Wenn die funktion rekursiv 10 mal aufgerufen wird, dann sind es schon 5 * 10 also 50 Variablen auf dem stack !!

Richtig.

Deshalb schreiben erfahrene Programmierer

void funk( int* zahl )
{

   int *a = new int(zahl+1 );
   int *b = new int(zahl +2 );
   int *c = new int(zahl +3 );
   int *d = new int(zahl -1 );

   if( zahl > 0 )
   {
      funk(new int(zahl - 2) );
   }

   delete a;
   delete b;
   delete c;
   delete d;
   delete zahl;
}

und schon sind nur noch 50 Pointer auf dem Stack.

Bashar

Du ignorierst wieder die Hälfte Naja nehm ich mal an, dass das eine void-Funktion sein soll.

Von vornherein ist auch nicht klar, auf welchem Abstraktionsniveau du fragst. Aber anscheinend hast du Angst vor einem Stacküberlauf, also befinden wir uns auf einer konkreten Maschine. Normalerweise ist natürlich klar, dass in der Regel alle Variablen auf dem Stack abgelegt werden müssten, aber dein Code benutzt die Variablen a, b, c und d nicht, also würde ein optimierender Compiler für sie keinen Code generieren. Außerdem ist deine Funktion endrekursiv, d.h. es kann sogar sein, dass die ganze Rekursion als Schleife realisiert wird und überhaupt kein Stack aufgebaut wird.

blurry333

So jetzt werden alle Variablen benutzt

int funk1( int zahl )
{

   int a = zahl+1;
   int b = zahl +2 ;
   int c = zahl +3;
   int d = zahl -1 ;

   if( zahl > 0 )
   {
      funk(zahl - 2 );
   }

   int e = a+b+c+d ;
   return e ;
}

blurry333

ohnein !! schrieb:

und schon sind nur noch 50 Pointer auf dem Stack.

Warum sollen 50 pointer besser sein als 50 int ? Kommt doch aufs selbe raus.

Nathan

blurry333 schrieb:

So jetzt werden alle Variablen benutzt

int funk1( int zahl )
{
 
   int a = zahl+1;
   int b = zahl +2 ;
   int c = zahl +3;
   int d = zahl -1 ;
 
   if( zahl > 0 )
   {
      funk(zahl - 2 );
   }

   int e = a+b+c+d ;
   return e ;
}

Aber der Rückgabewert von funk nicht.
Frage an alle anderen: Funktionsaufruf wegoptimiert, da keine Seiteneffekt?

Nathan

blurry333 schrieb:

ohnein !! schrieb:

und schon sind nur noch 50 Pointer auf dem Stack.

Warum sollen 50 pointer besser sein als 50 int ? Kommt doch aufs selbe raus.

Ist net garantiert.
Aber irgnorier diesen Post.

Bashar

blurry333 schrieb:

So jetzt werden alle Variablen benutzt

int funk1( int zahl )
{
 
   int a = zahl+1;
   int b = zahl +2 ;
   int c = zahl +3;
   int d = zahl -1 ;
 
   if( zahl > 0 )
   {
      funk(zahl - 2 );
   }

   int e = a+b+c+d ;
   return e ;
}

Und was soll das jetzt werden, eine Übung in "Wir spielen Optimierer"? Ein optimierender Compiler würde auch hier alles wegoptimieren und nur

return zahl+1+zahl+2+zahl+3+zahl-1;

stehen lassen (und das auch nochmal zusammenfassen, vermutlich.) Das ist aber eine ziemlich nutzlose Übung, deine Frage sollte doch wohl beantwortet sein?

SeppJ

Nathan schrieb:

Frage an alle anderen: Funktionsaufruf wegoptimiert, da keine Seiteneffekt?

Ich würde sagen nein und mein Compiler ebenfalls. Um zu beweisen, dass der Funktionsaufruf keine Seiteneffekte hat, müsste er beweisen, dass funk1, welches von funk1 aufgerufen wird, keine Seiteneffekte hat. Dazu wiederum, müsste er beweisen, dass funk1 keine Seiteneffekte hat, wozu er beweisen müsste, dass funk1 keine Seiteneffekte hat. Du siehst, worauf das hinaus läuft.

Einem Menschen ist natürlich klar, dass die Kette zahl -2 irgendwann kleiner wird als 0, aber der Compiler müsste das allgemein für jede vorstellbare Eingabe beweisen, was dann doch eine recht heftige mathematische Leistung wäre für ein Computerprogramm. Zumal viele Sonderfälle von Nebenbedingungen abhängen, wie MAX_INT oder dem Unterlaufverhalten, die dem Compiler zwar prinzipiell bekannt wären, aber nicht unbedingt offensichtlich in ihrer Anwendung sind.

Wenn da if(false) stünde, könnte das natürlich ohne Probleme wegoptimiert werden.

Nathan

SeppJ schrieb:

Nathan schrieb:

Frage an alle anderen: Funktionsaufruf wegoptimiert, da keine Seiteneffekt?

Ich würde sagen nein und mein Compiler ebenfalls. Um zu beweisen, dass der Funktionsaufruf keine Seiteneffekte hat, müsste er beweisen, dass funk1, welches von funk1 aufgerufen wird, keine Seiteneffekte hat. Dazu wiederum, müsste er beweisen, dass funk1 keine Seiteneffekte hat, wozu er beweisen müsste, dass funk1 keine Seiteneffekte hat. Du siehst, worauf das hinaus läuft.

Ja, Kompilierung könnte sich dann etwas in die Länge ziehen.

hustbaer

SeppJ schrieb:

Nathan schrieb:

Frage an alle anderen: Funktionsaufruf wegoptimiert, da keine Seiteneffekt?

Ich würde sagen nein und mein Compiler ebenfalls. Um zu beweisen, dass der Funktionsaufruf keine Seiteneffekte hat, müsste er beweisen, dass funk1, welches von funk1 aufgerufen wird, keine Seiteneffekte hat. Dazu wiederum, müsste er beweisen, dass funk1 keine Seiteneffekte hat, wozu er beweisen müsste, dass funk1 keine Seiteneffekte hat. Du siehst, worauf das hinaus läuft.

Ach nö, man kann das ganz einfach beweisen.
Wenn der Returnwert ignoriert wird, was ja hier der Fall ist, dann tut func1 nichts ausser sich selbst aufzurufen.
Da ein Aufruf einer Funktion kein beobachtbarer Seiteneffekt ist, tut func1 also nichts.
Beweis fertig. Ich sehe da kein Problem.

Liesse sich auch ganz einfach in einem Compiler implementieren - man guckt ob eine Funktion auf irgend einem Ausführungspfad beobachtbare Seiteneffekte hat, und verfolgt rekursive Pfade einfach nicht weiter.

Ob aktuelle Compiler das können oder nicht ist eine andere Frage.

SeppJ

hustbaer schrieb:

Ach nö, man kann das ganz einfach beweisen.
Wenn der Returnwert ignoriert wird, was ja hier der Fall ist, dann tut func1 nichts ausser sich selbst aufzurufen.
Da ein Aufruf einer Funktion kein beobachtbarer Seiteneffekt ist, tut func1 also nichts.
Beweis fertig. Ich sehe da kein Problem.

Ich schon: Endlosrekursion. Es gibt zwar die komische Klausel, dass in C++ angenommen werden darf, dass jede Schleife irgendwann einmal abbricht, aber wenn wir diese unintuitive Ausrede mal nicht zulassen, dann muss hier bewiesen werden, dass die Funktion überhaupt jemals zurück kehrt. Und das führt zu oben genannten Problemen.

hustbaer

Aber genau dafür gibt es diese "unintuitive(n)" Klausel(n) ja.

Wobei ich nichmal sicher bin dass man die Progress-Klausel braucht.

Man muss nur sagen dass ein korrektes Programm keinen Stack-Overflow produzieren darf.
Unter der Annahme dass das Programm korrekt ist, gibt es dann nur mehr die Möglichkeit dass func1 irgendwann zurückkehrt.
Und damit können wir es wegoptimieren.

Finde ich auch nicht sehr unintuitiv.

SeppJ schrieb:

Ich sehe da kein Problem.

Ich schon:

Ich nicht.
Clang (sorry für tinyurl, der Link* ist für das Forum zu lang) macht daraus

funk(int):                               # @funk(int)
	leal	5(,%rdi,4), %eax
	ret

*: http://gcc.godbolt.org/#{%22version%22%3A3%2C%22filterAsm%22%3A{%22labels%22%3Atrue%2C%22directives%22%3Atrue%2C%22commentOnly%22%3Atrue}%2C%22compilers%22%3A[{%22source%22%3A%22int%20funk%28%20int%20zahl%20%29\n{\n\n%20%20int%20a%20%3D%20zahl%2B1%3B\n%20%20int%20b%20%3D%20zahl%20%2B2%20%3B\n%20%20int%20c%20%3D%20zahl%20%2B3%3B\n%20%20int%20d%20%3D%20zahl%20-1%20%3B\n\n%20%20if%28%20zahl%20%3E%200%20%29\n%20%20%20%20{\n%20%20%20%20%20%20funk%28zahl%20-%202%20%29%3B\n%20%20%20%20}\n\n%20%20int%20e%20%3D%20a%2Bb%2Bc%2Bd%20%3B\n%20%20return%20e%3B\n}%22%2C%22compiler%22%3A%22%2Fusr%2Fbin%2Fclang%2B%2B%22%2C%22options%22%3A%22-O3%20-march%3Dnative%20-std%3Dc%2B%2B11%22}]}

hustbaer

SeppJ schrieb:

Es gibt zwar die komische Klausel, dass in C++ angenommen werden darf, dass jede Schleife irgendwann einmal abbricht, aber wenn wir diese unintuitive Ausrede mal nicht zulassen

Nö.
Man darf davon ausgehen dass ein Programm nie in einen Zustand wechselt wo es nix mehr macht.
(In C++ 11 gilt das vermutlich für jeden Thread eines Programms einzeln.)

Wobei jeder beobachtbare Seiteneffekt als "was machen" gilt. Endlosschleifen sind dabei nicht verboten - sie müssen nur einen möglichen Ausführungspfad enthalten der einen beobachtbaren Seiteneffekt produziert.

Und damit wird das ganze auch weit weniger unintuitiv.

EDIT: @himmlischer klang: Danke für den Link, die Seite kannte ich noch nicht! ICC kann es übrigens auch wegoptimieren.
EDIT2: Man kann sogar das "if" wegmachen und Clang/ICC können es immer noch optimieren.

SeppJ

hustbaer schrieb:

SeppJ schrieb:

Es gibt zwar die komische Klausel, dass in C++ angenommen werden darf, dass jede Schleife irgendwann einmal abbricht, aber wenn wir diese unintuitive Ausrede mal nicht zulassen

Nö.
Man darf davon ausgehen dass ein Programm nie in einen Zustand wechselt wo es nix mehr macht.
(In C++ 11 gilt das vermutlich für jeden Thread eines Programms einzeln.)

Wobei jeder beobachtbare Seiteneffekt als "was machen" gilt. Endlosschleifen sind dabei nicht verboten - sie müssen nur einen möglichen Ausführungspfad enthalten der einen beobachtbaren Seiteneffekt produziert.

Und damit wird das ganze auch weit weniger unintuitiv.

Hast du dich neulich nicht selber mal beschwert, dass man hier immer Seitenlange Disclaimer schreiben muss, wenn man irgendeine Aussage tätigt? Natürlich reden wir hier von seiteneffektfreien Schleifen wie die, um die es hier schon über zwei Seiten hinweg geht.

EDIT2: Man kann sogar das "if" wegmachen und Clang/ICC können es immer noch optimieren.

Und genau das ist das unintuitive. Erwartetes Verhalten: Endlosschleife, theoretisch unterbrechbar mit Signal. Tatsächliches Verhalten: Ausgabe einer Zahl und Return aus der main!

hustbaer

@SeppJ
OK.

Nur finde ich es nicht sinnvoll damit zu antworten das deiner Meinung nach sein sollte, wenn Nathan fragt was aktuelle Compiler können bzw. dürfen.
Sie dürfen, und sie können.

Dein "nein" war nicht hilfreich (da falsch).
Die klassifizierung einer Klausel im Standard als "unintuitive Ausrede" ändert daran auch nix.

ps: Ja, auf den ersten Blick ist es unintuitiv. Man kann aber schnell verstehen was das ganze soll und auch ein gutes Verständnis dafür entwickeln was OK ist und was nicht - von daher finde ich es nicht sehr unintuitiv. Und was den Teil Ausrede angeht: nuja, es ermöglicht einige Dinge zu optimieren, die sonst nur mit viel mehr Aufwand zu optimieren wären. Und es tut nicht weh. Strict Aliasing tut viel mehr weh.