Hi, wollte mal wissen was von diesen Ausdrücken am schnellsten ist: x << 2 x * 4 x+x+x+x ?
Kommt drauf an, welcher Prozessor und ggf. Compiler.
Der Shift ist auf heutigen PCs am schnellsten (Sprich 386 aufwärts). Aber jeder gute Compiler setzt die anderen Anweisungen in den Shift um.
Es ist vollkommen egal, welchen Ausdruck du verwendest. Jeder halbwegs vernünftige Optimizer verwendet automatisch die schnellste Variante. Ausnahme: du benutzt einen Uralten oder aus sonstigen Gründen mieserablen Compiler.
Klaus schrieb: > Es ist vollkommen egal, welchen Ausdruck du verwendest. Jeder halbwegs > vernünftige Optimizer verwendet automatisch die schnellste Variante. Interessant sind allerdings Fälle, wo die entsprechende Optimierung dem Compiler verboten ist. Beispiel: Multiplikation mit 7
1 | x = (x<<3)-x; |
Da in diesem Fall das Ergebnis für einen Teil des möglichen Wertebereichs anders ausfällt als bei einer echten Multiplikation mit 7 (nämlich dann, wenn x*8 nicht mehr passt, x*7 aber schon), kann der Compiler die Optimierung selbst nicht durchführen. Der Programmierer kann dies aber tun, wenn er weiß, dass Werte aus dem fraglichen Bereich nicht auftreten können. In anderen Sprachen (Ada z.B.) ist es wiederum möglich, bei Variablen den exakten Wertebereich zu definieren, hier kann der Compiler dann wieder selbst optimieren. Andreas
Andreas Ferber schrieb: > Compiler die Optimierung selbst nicht durchführen. Bei welchen Werten treten denn verschiedene Ergebnisse auf? Immerhin führt GCC genau diese Optimierung durch, in beiden Vorzeichenvarianten (x86 und avr). Weder Shift noch Subtraktion fliegen beim Überlauf aus dem Fenster, sondern haben normales Modulo-Verhalten, weshalb das Ergebnis wieder stimmt. Ein besseres Beispiel ist x = x / 8; was bei Typen mit Vorzeichen aufgrund anderer Rundung bei negativen Werten nicht direkt durch Shift ersetzbar ist.
Umgekehrt wird ein Schuh draus: Der Compiler, der die Eigenschaften seiner Zielmaschine exakt kennt, darf die Ausdrücke x = x * 7; x = (x << 3) - x; ggf. als exakt äquivalent ansehen. Der Programmierer jedoch, der nur den C Standard als Basis hat, der darf dies nur bei vorzeichenloser Rechnung.
A. K. schrieb: >> Compiler die Optimierung selbst nicht durchführen. > Bei welchen Werten treten denn verschiedene Ergebnisse auf? Zum Beispiel auf AVR mit int8_t x = -17 oder x=-18. Bei x*7 ist in beiden Fällen alles im grünen Bereich, es kommt -119 bzw. -126 heraus. Bei (x<<3)-x hat man dagegen undefined behaviour, und auch real kommt hier dann -127 (nach dem Shiften, vom GCC implementiert durch wiederholtes addieren, ist binär 01110000 im Register, dazu 00010001 (17) addiert ergibt 10000001) bzw. +122 heraus. > Immerhin > führt GCC genau diese Optimierung durch, in beiden Vorzeichenvarianten > (x86 und avr). Prinzipiell schon, aber er erweitert dazu den Wert auf 16 Bit (x ist jeweils int8_t, kompiliert mit avr-gcc -O6 für einen AVR ohne Hardware-Multiplikation, GCC Version 4.3.4):
1 | x = x*7; |
2 | 0: 20 91 00 00 lds r18, 0x0000 |
3 | 4: 33 27 eor r19, r19 |
4 | 6: 27 fd sbrc r18, 7 |
5 | 8: 30 95 com r19 |
6 | a: c9 01 movw r24, r18 |
7 | c: 88 0f add r24, r24 |
8 | e: 99 1f adc r25, r25 |
9 | 10: 88 0f add r24, r24 |
10 | 12: 99 1f adc r25, r25 |
11 | 14: 88 0f add r24, r24 |
12 | 16: 99 1f adc r25, r25 |
13 | 18: 82 1b sub r24, r18 |
14 | 1a: 93 0b sbc r25, r19 |
15 | 1c: 80 93 00 00 sts 0x0000, r24 |
vs.
1 | x = (x<<3)-x; |
2 | 0: 90 91 00 00 lds r25, 0x0000 |
3 | 4: 89 2f mov r24, r25 |
4 | 6: 88 0f add r24, r24 |
5 | 8: 88 0f add r24, r24 |
6 | a: 88 0f add r24, r24 |
7 | c: 89 1b sub r24, r25 |
8 | e: 80 93 00 00 sts 0x0000, r24 |
Durch die Erweiterung wird die Overflow-Problematik umgangen. > Der Programmierer jedoch, der nur den > C Standard als Basis hat, der darf dies nur bei vorzeichenloser > Rechnung. Oder wenn er weiß, dass (im Beispiel mit int8_t) die Werte -17 und -18 niemals vorkommen können. Der Compiler kann das nicht wissen (zumindest nicht bei C). Andreas
Andreas Ferber schrieb: > Zum Beispiel auf AVR mit int8_t x = -17 oder x=-18. Bei x*7 ist in > beiden Fällen alles im grünen Bereich, es kommt -119 bzw. -126 heraus. > Bei (x<<3)-x hat man dagegen undefined behaviour, und auch real kommt > hier dann -127 (nach dem Shiften, vom GCC implementiert durch > wiederholtes addieren, ist binär 01110000 im Register, dazu 00010001 > (17) addiert ergibt 10000001) bzw. +122 heraus. Argh, um 1 Bit vertan. OK, passt real doch alles (für C bleibt es aber undefined). Trotzdem bleibt (warum auch immer): >> Immerhin >> führt GCC genau diese Optimierung durch, in beiden Vorzeichenvarianten >> (x86 und avr). > Prinzipiell schon, aber er erweitert dazu den Wert auf 16 Bit (x ist > jeweils int8_t, kompiliert mit avr-gcc -O6 für einen AVR ohne > Hardware-Multiplikation, GCC Version 4.3.4): [...] Andreas
Andreas Ferber schrieb: > Durch die Erweiterung wird die Overflow-Problematik umgangen. Auch bei int f(int x) { return x * 7; } erzeugt GCC die (x<<3)-x Variante.
Andreas Ferber schrieb: >> Bei (x<<3)-x hat man dagegen undefined behaviour Nur wenn der Programmierer das so hinschreibt. Dem Compiler ist das Verhalten der Maschine bei Überlauf hingegen bekannt, daher darf er das im Zwischencode sehr wohl verwenden wenn er weiss dass das gleiche rauskommt.
A. K. schrieb: > int f(int x) > { > return x * 7; > } > erzeugt GCC die (x<<3)-x Variante. Interessanterweise bekommt er es in diesem Fall auch mit int8_t hin:
1 | int8_t f(int8_t x) |
2 | {
|
3 | 0: 98 2f mov r25, r24 |
4 | 2: 99 0f add r25, r25 |
5 | 4: 99 0f add r25, r25 |
6 | 6: 99 0f add r25, r25 |
7 | return x*7; |
8 | } |
9 | 8: 98 1b sub r25, r24 |
10 | a: 89 2f mov r24, r25 |
11 | c: 08 95 ret |
Umso schleierhafter, warum er bei "x = x*7;" mit int8_t x auf der Erweiterung zu 16 Bit besteht. Andreas
Andreas Ferber schrieb: ... > > Umso schleierhafter, warum er bei "x = x*7;" mit int8_t x auf der > Erweiterung zu 16 Bit besteht. Weil "7" den Datentyp integer hat. Und das ist beim AVR-GCC 16 Bit breit. Es muss vor einer Multiplikation der kürzere Typ erweitert werden (sagt der C Standard).
Werner B. schrieb: > Weil "7" den Datentyp integer hat. > Also muss vor einer Multiplikation der kürzere Typ erweitert werden. Nein, er muss nicht. Wenn im Ergebnis das Gleiche rauskommt darf der Compiler auch ohne Erweiterung rechnen. Tut er auch ziemlich oft. Er muss nur so handeln als ob eine Erweiterung stattfinden würde. Ausserdem ist es völlig schnuppe, ob du x * 7 oder x * (int8_t)7 schreibst, denn jeder Ausdruck < "int" ist automatisch ein Ausdruck mit Rechnung und Ergebnis in "int". Dem Prinzip nach.
Andreas Ferber schrieb: > Umso schleierhafter, warum er bei "x = x*7;" mit int8_t x auf der > Erweiterung zu 16 Bit besteht. Der GCC 4.4.3 macht auch in diesem Fall die Shifts und die Subtraktion in 8 Bit.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.