Klammerung mathematischer Ausdrücke verbindlich für Compiler?

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.

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.

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.

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.

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.

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.

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!

^^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.

pointercrash() schrieb:

+fricky schrieb:

^^welcher compiler ist das denn?

Crossworks für'n TI MSP430.

ok, danke für die warnung. für MSP430 hab' ich bisher IAR genommen. kann nicht klagen...

pointercrash**

+fricky schrieb:

ok, danke für die warnung. für MSP430 hab' ich bisher IAR genommen. kann nicht klagen...

Oh, ich auch nicht ... der Compiler war gestellt. Hab' gemotzt und sofort ein Feedback bekommen ... schaut er sich an, weil er sich wundert, daß er das beim MSP übersehen haben könnte.
In zwei, drei Tagen krieg' ich entweder nur einen neuen Freischalt- Key oder noch neue Binaries dazu - für lau.
IAR hat mir ca. '96 einen total unbrauchbaren C-Compiler geliefert und mich monatelang sitzen gelassen, bis die kostenlose Update- Frist abgelaufen war. Als ich dann endlich das "Upgrade- Angebot" für 2000 Mark bekam, war das Projekt in Assembler neu gemacht und ich habe von IAR (in dem Zug auch von C) die Finger gelassen. 7000 Mark in den Sand gesetzt waren mir genug.