mikrocontroller.net

Forum: Compiler & IDEs Ausdruck optimieren auf Laufzeit


Autor: Udo (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi,

wollte mal wissen was von diesen Ausdrücken am schnellsten ist:

x << 2
x * 4
x+x+x+x



?

Autor: Lasse S. (cowz) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kommt drauf an, welcher Prozessor und ggf. Compiler.

Autor: Sebastian Hepp (sebihepp)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Der Shift ist auf heutigen PCs am schnellsten (Sprich 386 aufwärts). 
Aber jeder gute Compiler setzt die anderen Anweisungen in den Shift um.

Autor: Udo (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Diabdata Compiler
keine PC Programmierung

Autor: Klaus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Andreas Ferber (aferber)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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
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

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Andreas Ferber (aferber)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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):
        x = x*7;
   0:   20 91 00 00     lds     r18, 0x0000
   4:   33 27           eor     r19, r19
   6:   27 fd           sbrc    r18, 7
   8:   30 95           com     r19
   a:   c9 01           movw    r24, r18
   c:   88 0f           add     r24, r24
   e:   99 1f           adc     r25, r25
  10:   88 0f           add     r24, r24
  12:   99 1f           adc     r25, r25
  14:   88 0f           add     r24, r24
  16:   99 1f           adc     r25, r25
  18:   82 1b           sub     r24, r18
  1a:   93 0b           sbc     r25, r19
  1c:   80 93 00 00     sts     0x0000, r24

vs.
        x = (x<<3)-x;
   0:   90 91 00 00     lds     r25, 0x0000
   4:   89 2f           mov     r24, r25
   6:   88 0f           add     r24, r24
   8:   88 0f           add     r24, r24
   a:   88 0f           add     r24, r24
   c:   89 1b           sub     r24, r25
   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

Autor: Andreas Ferber (aferber)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Andreas Ferber (aferber)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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:
int8_t f(int8_t x)
{
   0:   98 2f           mov     r25, r24
   2:   99 0f           add     r25, r25
   4:   99 0f           add     r25, r25
   6:   99 0f           add     r25, r25
        return x*7;
}
   8:   98 1b           sub     r25, r24
   a:   89 2f           mov     r24, r25
   c:   08 95           ret

Umso schleierhafter, warum er bei "x = x*7;" mit int8_t x auf der 
Erweiterung zu 16 Bit besteht.

Andreas

Autor: Werner B. (werner-b)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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).

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.