Schnellere Division

Baum2 schrieb:
> Hallo
>
> Ich programmiere einen ATmega mit Hilfe des AVR Studios.
> Mich würde interessieren, welcher Rechenschritt auf dem µC schneller ist
> und warum.
>
> 20 / 5;
>
> oder
>
> 20 >> 4;
>
> Kann der µC mit den Schiebebefehlen schneller arbeiten? Und wie genau
> würde er die Division ausführen?
> Gruß.

Entscheidend ist, was der Compiler aus Deinem Code macht. Sehr 
wahrscheinlich wird er es so umsetzen, dass es keinen Vorteil bringt im 
Code einen Shift-Befehl hinzuschreiben anstatt einer Division.

Peter II schrieb:
> Eine Division durch 1 geht z.b. sehr schnell.

… gefolgt von einer Division durch ganze Zweierpotenzen.

Konstante Divisionen taugen natürlich sowieso nicht für den Vergleich,
denn die werden vom Compiler rausoptimiert.  Divisionen durch konstante
Zweierpotenzen werden typisch ebenfalls ohne Bibliotheksaufruf durch
passende Schiebeoperationen bereits vom Compiler ersetzt.

Assem-Blär schrieb:
> Allerdings solltest du die Optimierung ausschalten

Schlechter Ratschlag.

Dann kommt ja völlig praxisfremdes Zeugs raus.

„Wie schnell kann dieses Auto dort fahren?“

„Keine Ahnung, probier's aus, aber lass lieber die Handbremse
angezogen dabei.“

Dirk_Geber schrieb:
> Ich würde halt gerne wissen, ob es im Bezug auf die Optimierung
> sinnvoller ist, nur durch Zweierpotenzen zu dividieren.

Zuerst einmal will man in aller Regel korrekte Ergebnisse haben. Also 
führt man eben die Berechnungen aus, die notwendig sind um das 
gewünschte Ergebnis zu bekommen.

Ich habe noch von keiner realen Anwendung gehört, in der man sich das 
korrekte Dividieren aus Performance-Gründen komplett verkneifen musste.

Peter II schrieb:
> Damit es schneller ist, muss der Divisor aber zu Compilezeit konstant
> sein.

Nein.  Auch zur Laufzeit ist eine Division durch 2^N immer noch
schneller als andere Divisionen.  Der Algorithmus ist dann schneller
fertig.  (Zur Compilezeit kann es nur der Compiler gleich optimieren.)

Da geht's den Computern wie den Menschen.  Ins Dezimalsystem
übertragen: wenn du 37568 durch 100 dividieren sollst, bist du mit
dem Ergebnis auch viel schneller fertig, als wenn du es durch 101
teilen sollst.

Alex schrieb:
> Schau doch im Prozessor-Handbuch, wieviel Cycles ein div braucht
> und wieviel Cycles ein shift braucht.

Welche AVRs besitzen denn überhaupt einen Divisionsbefehl?

Grüßle,
Volker.

Draco schrieb:
> Also wenn rechnen müsste:
>
> uint8_t Wert = 20 / 5;

das dürfte schon der Präprozessor machen und 4 einsetzen vermute ich 
mal.

Mark B. schrieb:
> Entscheidend ist, was der Compiler aus Deinem Code macht. Sehr
> wahrscheinlich wird er es so umsetzen, dass es keinen Vorteil bringt im
> Code einen Shift-Befehl hinzuschreiben anstatt einer Division.

Sag das mal dem Keil C51 Compiler.

Bernd K. schrieb:
> Mark B. schrieb:
>> Entscheidend ist, was der Compiler aus Deinem Code macht. Sehr
>> wahrscheinlich wird er es so umsetzen, dass es keinen Vorteil bringt im
>> Code einen Shift-Befehl hinzuschreiben anstatt einer Division.
>
> Sag das mal dem Keil C51 Compiler.

Okay, also: Ein vernünftiger Compiler wird es so umsetzen, dass es 
keinen Vorteil bringt einen Shift-Befehl hinzuschreiben anstatt einer 
Division. ;-)

Joachim B. schrieb:
> das dürfte schon der Präprozessor machen und 4 einsetzen vermute ich
> mal.

Präprozessor, Subst.:

Mystischer Teil eines C-Compilers, dessen Möglichkeiten weithin
gefühlsmäßig dramatisch überschätzt werden.  Der P. erledigt einfache
Textersetzungen, bevor der Quelltext einer Übersetzungseinheit zum
eigentlichen Compiler weitergereicht wird.

Spannungsteiler schrieb:
> --->
> http://www.matuschek.net/avr-codeoptimierung2/

Mikrooptimierung.

Solche Hacks wird man sich nur antun, wenn's auf die paar Takte
wirklich ankommt.  Portiert man den ganzen Salat mal irgendwann
auf einen anderen Prozessor, dann kann einem solcherart
Optimierung ganz schnell auf die Füße fallen, weil sie sich dort
dann plötzlich als Pessimierung entpuppt, ganz davon abgesehen,
dass sie eine bestimmte Byteorder benötigt.

Bei ARM und GCC hat man übrigens Glück: der erkennt, dass all die
vielen Umständlichkeiten von "version2" letztlich zum gleichen
Code führen wie "version1", und schreibt in beiden Fällen den
passenden LSRS-Befehl (mit 22 Bit Schiebeweite) hin. ;-)

Jörg W. schrieb:
> Mystischer Teil eines C-Compilers, dessen Möglichkeiten weithin
> gefühlsmäßig dramatisch überschätzt werden.  Der P. erledigt einfache
> Textersetzungen,

OK dann macht die Ersetzung 20/5 der Compiler, ich hoffe ich liege nicht 
ganz falsch das er gleich 4 in die Konstante einsetzt.

Joachim B. schrieb:
> OK dann macht die Ersetzung 20/5 der Compiler

So ist es.

Jörg W. schrieb:
> Joachim B. schrieb:
>> das dürfte schon der Präprozessor machen und 4 einsetzen vermute ich
>> mal.
>
> Präprozessor, Subst.:
>
> Mystischer Teil eines C-Compilers, dessen Möglichkeiten weithin
> gefühlsmäßig dramatisch überschätzt werden.  Der P. erledigt einfache
> Textersetzungen, bevor der Quelltext einer Übersetzungseinheit zum
> eigentlichen Compiler weitergereicht wird.

Er kann aber rechnen, muss es sgoar, und zwar wenn es berechenbare Terme 
in #if Statements gibt.

Cyblord -. schrieb:
> Er kann aber rechnen

Hab' ich ja auch nicht bestritten.  Wird aber (abgesehen von einfachen
Booleschen Ausdrücken) nur selten benutzt, und insbesondere eben nur
dafür, um die Bedingung eines #if zu evaluieren.

Jörg W. schrieb:
> Cyblord -. schrieb:
>> Er kann aber rechnen
>
> Hab' ich ja auch nicht bestritten.

Doch irgendwie schon. Dein Beitrag suggeriert er mache ausschließlich 
einfache Textersetzungen. Was rechnen dann doch ausschließt.

Mark B. schrieb:
> Okay, also: Ein vernünftiger Compiler wird es so umsetzen, dass es
> keinen Vorteil bringt einen Shift-Befehl hinzuschreiben anstatt einer
> Division. ;-)

Wobei zu beachten wäre, dass
  int i = a;
  i %= 8;
und
  i >>= 3;
nicht äquivalent sind, weil auch bei Verwendung eines Schiebebefehls mit 
Vorzeichen bei negativen Werten unterschiedlich gerundet wird. Eine 
Divisionoperation, die durch Shift ersetzt wird, kann also komplizierter 
ausfallen als ein Shift allein. Und bei Optimierung auf Grösse kann die 
Division dann u.U. sparsamer ausfallen als dieser Ersatz.

A. K. schrieb:
> Wobei zu beachten wäre, dass
>   int i = a;
>   i %= 8;
> und
>   i >>= 3;
> nicht äquivalent sind

sind sie doch niemals, oder? Außer für den Sonderfall dass a zwischen 8 
und 16 ist.

aber du meintest wohl /= statt %= ?

Christopher B. schrieb:
> aber du meintest wohl /= statt %= ?

Ja. Oder "%=" und & statt Shift.

Jörg W. schrieb:
> Der P. erledigt einfache
> Textersetzungen,
Cyblord -. schrieb:
> Er kann aber rechnen, muss es sgoar, und zwar wenn es berechenbare Terme
> in #if Statements gibt.
Cyblord -. schrieb:
> Dein Beitrag suggeriert er mache ausschließlich
> einfache Textersetzungen. Was rechnen dann doch ausschließt.

danke, wusste ich doch das der Prä rechnen kann, aber irgendeiner muss 
ja immer widersprechen!

Joachim B. schrieb:
> wusste ich doch das der Prä rechnen kann

Macht er schon, nur nicht da, wo viele Leute vermuten, dass er es
täte …

1

#define FOO 42

2

#define BAR 21

3

4

int gimmevalue(void)

5

{

6

#if FOO - BAR  // hier rechnet er

7

   return FOO - BAR;  // hier nicht, hier ersetzt er nur Text

8

#else

9

   return 42;

10

#endif

11

}