Klammerung mathematischer Ausdrücke verbindlich für Compiler?

[Belli]

Bashar schrieb:

Belli schrieb:

Also da finde ich sowas wie:

temp = b * c;
result = a * temp;

ein klein wenig übersichtlicher, um eine bestimmte Ausführungsreihenfolge zu erzwingen ...

Hm, in deinem ersten Post in diesem Thread hast du noch geschrieben, bei solchen Konstrukten müsste man hoffen, dass der Compiler das nicht wegoptimiert.

Jo, stimmt, ich habe keine Ahnung, wie intelligent so ein Compiler ist. Trotzdem würde ich das zunächst so probieren, bevor ich derart wilde Rekursionen entwickeln würde.

[namespace invader]

Warum denn nicht einfach a * (b * c) ? Wenn die Reihenfolge _nicht_ egal ist, und der Compiler es trotzdem umdreht, ist der Compiler kaputt.

Wenn a, b, und c z.B. unsigned ints sind, darf der Compiler sie natürlich in der Reihenfolge zusammenmultiplizieren, die ihm am meisten Spaß macht. Und braucht sich auch nicht durch überflüssige, wegoptimierbare Zusatzvariablen und Rekursionen daran hindern lassen.

[Belli]

namespace invader schrieb:

Warum denn nicht einfach a * (b * c) ? Wenn die Reihenfolge _nicht_ egal ist, und der Compiler es trotzdem umdreht, ist der Compiler kaputt.

Wenn a, b, und c z.B. unsigned ints sind, darf der Compiler sie natürlich in der Reihenfolge zusammenmultiplizieren, die ihm am meisten Spaß macht.

Meine These ist, daß er das unabhängig vom Datentyp darf, einfach weil die Multiplikation kommutativ ist.
Ich habe ehrlich gesagt das Problem 'skalierte Integerarithmetik' nicht verstanden, bin aber unabhängig davon der Meinung, daß der Compiler die Klammern dann nicht zu beachten braucht, wenn das Ergebnis (rein mathematisch betrachtet) davon nicht beeinträchtigt wird.

[knivil]

Belli schrieb:

Meine These ist, daß er das unabhängig vom Datentyp darf, einfach weil die Multiplikation kommutativ ist.
Ich habe ehrlich gesagt das Problem 'skalierte Integerarithmetik' nicht verstanden, bin aber unabhängig davon der Meinung, daß der Compiler die Klammern dann nicht zu beachten braucht, wenn das Ergebnis (rein mathematisch betrachtet) davon nicht beeinträchtigt wird.

Jaja, Thesen, Vermutungen, ...

1.) Hat sich jemand mal den Standard angesehen oder Assembler Code angeschaut?
2.) Welche Rolle spielt es fuer den Compiler, nicht die Reihenfolge des Nutzer zu beachten? (a*b)*c benoetigt 3 Multiplikationen genau wie a*(b*c).
3.) Rein mathematisch ist schoen und gut, aber wir rechnen im Computer immer mit diskreten Werten. Problematisch wird es wenn sehr grosse reelle Zahlen mit sehr kleinen reellen Zahlen multipliziert/addiert werden. Dort kann das Ergebnis stark von der Reihenfolge der Operationen abhaengen.

[Bashar]

Der Standard sagt dazu nicht viel explizit, man kann aber das Verhalten ableiten. Ein Ausdruck wie a*(b*c) besteht aus zwei Multiplikationsausdrücken. Der eine ist b*c, der andere besteht aus a und dem Ergebnis von b*c. Folglich würde die abstrakte Maschine zuerst b*c berechnen, dann a damit multiplizieren.
Falls a,b,c komplexe Ausdrücke sind, ist die Auswertungsreihenfolge nicht festgelegt, bei a()*(b()*c()) dürfte also durchaus erst a() aufgerufen werden, dann b()*c() ausgerechnet und zum Schluss multipliziert werden.
Der Compiler darf jetzt jeglichen Code generieren, dessen Semantik mit der der abstrakten Maschine übereinstimmt. Das ist der Freibrief für den Optimierer. (BTW, die Semantik der abstrakten Maschine ist nicht über mathematische Idealisierungen definiert, sondern über Bits und Bytes) Ausnahmen von dieser Regel müssen explizit definiert sein. Sowas gibt es für floating-point-Ausdrücke, bei denen der Compiler gewisse Ausdrücke zusammenfassen darf, wobei eventuell sich ein anderes Rundungsverhalten ergibt. Für normale Ganzzahlausdrücke hab ich sowas nicht gefunden.

[Belli]

knivil schrieb:

Belli schrieb:

Meine These ist, daß er das unabhängig vom Datentyp darf, einfach weil die Multiplikation kommutativ ist.
Ich habe ehrlich gesagt das Problem 'skalierte Integerarithmetik' nicht verstanden, bin aber unabhängig davon der Meinung, daß der Compiler die Klammern dann nicht zu beachten braucht, wenn das Ergebnis (rein mathematisch betrachtet) davon nicht beeinträchtigt wird.

Jaja, Thesen, Vermutungen, ...

Jaja ... schön, daß Du hier endlich mal mit handfesten Aussagen Licht ins Dunkel bringst ...

knivil schrieb:

1.) Hat sich jemand mal den Standard angesehen oder Assembler Code angeschaut?

Im Eingangsposting steht zu lesen, daß sich der Threadersteller den ASM-Code angesehen hat.

knivil schrieb:

2.) Welche Rolle spielt es fuer den Compiler, nicht die Reihenfolge des Nutzer zu beachten? (a*b)*c benoetigt 3 Multiplikationen genau wie a*(b*c).

Ähhh ..., ist das jetzt neu, oder waren wir nicht schon lange so weit?

knivil schrieb:

3.) Rein mathematisch ist schoen und gut, aber wir rechnen im Computer immer mit diskreten Werten. Problematisch wird es wenn sehr grosse reelle Zahlen mit sehr kleinen reellen Zahlen multipliziert/addiert werden. Dort kann das Ergebnis stark von der Reihenfolge der Operationen abhaengen.

Hier könnte das Problem des Threaderstellers liegen ... das hat er aber selbst schon erkannt, aber super, daß Du das noch mal erwähnst.

[Belli]

Bashar schrieb:

bei a()*(b()*c()) dürfte also durchaus erst a() aufgerufen werden, dann b()*c() ausgerechnet und zum Schluss multipliziert werden.

Das Problem (und die Frage nach der Zulässigkeit) hier ist laut TE aber, ob auch erst a() * b() ausgerechnet werden darf, um dann erst mit c() zu multiplizieren.

[Belli]

Ich habe keine Ahnung, ob es in diesem Zusammenhang von Belang ist:
Ich habe gerade mal in C++ eine Testklasse mit überladenem + - Operator erstellt und getestet, dort werden - auch mit Optimierungsschalter beim Compile-Vorgang - die Klammern beachtet. Es ist dort leicht zu testen, da man in der Überladenen Funktion einen Text ausgeben kann.

[Bashar]

Belli schrieb:

Das Problem (und die Frage nach der Zulässigkeit) hier ist laut TE aber, ob auch erst a() * b() ausgerechnet werden darf, um dann erst mit c() zu multiplizieren.

Darauf bin ich eingegangen. Halte mir doch nicht vor, dass ich noch etwas umfassender antworte.

Ich habe gerade mal in C++ eine Testklasse mit überladenem + - Operator erstellt und getestet, dort werden - auch mit Optimierungsschalter beim Compile-Vorgang - die Klammern beachtet. Es ist dort leicht zu testen, da man in der Überladenen Funktion einen Text ausgeben kann.

Das ist nicht relevant, da der +-Operator als Funktionsaufruf erkannt wird, so dass die späteren Compilerstufen gar keine Addition mehr zu Gesicht bekommen.

[Belli]

Bashar schrieb:

Belli schrieb:

Das Problem (und die Frage nach der Zulässigkeit) hier ist laut TE aber, ob auch erst a() * b() ausgerechnet werden darf, um dann erst mit c() zu multiplizieren.

Darauf bin ich eingegangen.

Das habe ich nicht erkannt.

Bashar schrieb:

Ich habe gerade mal in C++ eine Testklasse mit überladenem + - Operator erstellt und getestet, dort werden - auch mit Optimierungsschalter beim Compile-Vorgang - die Klammern beachtet. Es ist dort leicht zu testen, da man in der Überladenen Funktion einen Text ausgeben kann.

Das ist nicht relevant, da der +-Operator als Funktionsaufruf erkannt wird, so dass die späteren Compilerstufen gar keine Addition mehr zu Gesicht bekommen.

Ja, das macht Sinn. Ist wohl nicht vergleichbar mit dem Problem des TE.

[pointercrash**]

Bashar schrieb:

... Der Compiler darf jetzt jeglichen Code generieren, dessen Semantik mit der der abstrakten Maschine übereinstimmt. Das ist der Freibrief für den Optimierer. (BTW, die Semantik der abstrakten Maschine ist nicht über mathematische Idealisierungen definiert, sondern über Bits und Bytes) Ausnahmen von dieser Regel müssen explizit definiert sein. Sowas gibt es für floating-point-Ausdrücke, bei denen der Compiler gewisse Ausdrücke zusammenfassen darf, wobei eventuell sich ein anderes Rundungsverhalten ergibt. Für normale Ganzzahlausdrücke hab ich sowas nicht gefunden.

Du dürftest richtig liegen. Konnte wegen Probs an anderen Fronten das noch nicht 100%ig dingfest machen, aber die Geschichte betrifft zumindest einmal doubles, Integerzeugs schichtet er nicht um, das wär' nämlich wirklich schlimm.
Schon irre, da ist was so wohldefiniert und trotzdem touchiert man immer wieder Grenzbereiche ...

[Bashar]

Du hattest was von skalierten Integern, also Fixpunktarithmetik, erwähnt, deshalb hätte ich jetzt nicht gedacht, dass das relevant für dein Problem ist.

Der Absatz 6.5§8 lautet jedenfalls:
"A floating expression may be contracted, that is, evaluated as though it were an atomic
operation, thereby omitting rounding errors implied by the source code and the
expression evaluation method.64) The FP_CONTRACT pragma in <math.h> provides a
way to disallow contracted expressions. Otherwise, whether and how expressions are
contracted is implementation-defined."

[Ben04]

pointercrash() schrieb:

Integerzeugs schichtet er nicht um, das wär' nämlich wirklich schlimm.

Da ist es aber egal. Bei ints spielt die Reihenfolge nämlich keine Rolle, das Ergebnis ist selbst bei Overflows das selbe.

Ich glaube schon, dass er es bei a*(b*c) darf, da da kein Sequencepoint dazwischen ist. ; ist unter anderem ein Sequencepoint und deswegen dürfte t = b*c; a*t nicht umgeklammert werden. Ich bin mir da aber nicht sicher.

[Gast]

Ben04 schrieb:

Ich glaube schon, dass er es bei a*(b*c) darf, da da kein Sequencepoint dazwischen ist. ; ist unter anderem ein Sequencepoint und deswegen dürfte t = b*c; a*t nicht umgeklammert werden. Ich bin mir da aber nicht sicher.

Würde diese Argumentation nicht auch bedeuten, dass ein Compiler z.B. nicht Funktionen inlinen darf?

[Bashar]

Nochmal, es gibt überhaupt keine Regel, wie der Code genau auszusehen hat. Der Compiler darf überflüssige Rechnungen machen, der darf exakt das machen was dasteht, der darf auch alles bis zur Unkenntlichkeit verquirlen. Hauptsache, es kommt, sofern wir uns nicht im undefinierten bewegen, das gleiche beobachtbare Verhalten raus, das die abstrakte Maschine liefern würde. (Ausnahmen wie dieses 'contracting' bestätigen die Regel.)
Sequenzpunkte haben ja mit Seiteneffekten zu tun. Wenn die Zuweisungen aber jetzt nicht gerade an volatile ist, und der Compiler seinen Datenfluss so organisiert hat, dass das Verhalten passt, dann kann er auch die zeitliche Reihenfolge verdrehen, wenn es ihm passt. Der Unterschied wäre ja nicht legal wahrnehmbar.

[pointercrash**]

Der Vollständigkeit halber noch das Spielzeug:

double a = .123, b = 45.6, c = -32.767;
	double result, result1;

	while(1)
	{
		a += 0.1;
		a /= 3;
		b += 0.01;
		b /= 5;
		c += 10;
		c /= 7;
		result = a * b * c;
		result1 = a * (b * c);
		if (result != result1)
		{
			printf("%25.20f\n", result);
			printf("%25.20f\n", result1);
		}
	}

Ein Compiler, der die Klammerung rausschmeißt, schweigt in Ewigkeit, amen. Compiler die die Klammerung beachten, stolpern irgendwann mal über Rundungsfehler und geben Laut.

Ben04 schrieb:

Da ist es aber egal. Bei ints spielt die Reihenfolge nämlich keine Rolle, das Ergebnis ist selbst bei Overflows das selbe.

Jetzt hast Du mich verunsichert ... ich schau' mir noch die Sache mit dem Integerzeugs genauer an, ob das wirklich folgenlos bliebe.

[+fricky]

pointercrash() schrieb:

Ben04 schrieb:

Da ist es aber egal. Bei ints spielt die Reihenfolge nämlich keine Rolle, das Ergebnis ist selbst bei Overflows das selbe.

Jetzt hast Du mich verunsichert ... ich schau' mir noch die Sache mit dem Integerzeugs genauer an, ob das wirklich folgenlos bliebe.

naja, beim teilen musste auf die reihenfolge achten, falls a/b 'nen rest lassen würde. aber das ist wohl allen kar, schätze ich mal.

[pointercrash**]

+fricky schrieb:

naja, beim teilen musste auf die reihenfolge achten, falls a/b 'nen rest lassen würde. aber das ist wohl allen kar, schätze ich mal.

Du Optimist!
Nee, ich meinte schon die Kommutativität der Multiplikation mit Ergebnis-Reskalierung - und da hat Ben04 recht, das bleibt immer gleich samt Overflow und Underflow.
Der Compiler macht das anscheinend genau verkehrt herum, denn bei Integern wird die Klammerung beachtet. Ich werd' mich wohl mit dem Autor in Verbindung setzen - das wollte ich aber erst nach eurem Feedback, weil ich mir nicht sicher war, was erlaubt ist und was nicht.

In diesem Sinne:
Ein "Danke" an die Runde!

[+fricky]

^^welcher compiler ist das denn?

[pointercrash**]

+fricky schrieb:

^^welcher compiler ist das denn?

Crossworks für'n TI MSP430. Eigentlich ganz nett gemacht, aber für meinen Geschmack zu sehr VS- Klon.