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ß.
Baum2 schrieb: > Mich würde interessieren, welcher Rechenschritt auf dem µC schneller ist warum simulierst du es dann nicht einfach? 20 / 5; 20 >> 4; Da kommt eh nicht das gleiche Raus, was willst du das vergleichen? > Kann der µC mit den Schiebebefehlen schneller arbeiten? meist ja, genauere steht im Datenblatt
Peter II schrieb: > Baum2 schrieb: > Mich würde interessieren, welcher Rechenschritt auf dem µC schneller ist > > warum simulierst du es dann nicht einfach? > > 20 / 5; > 20 >> 4; > > Da kommt eh nicht das gleiche Raus, was willst du das vergleichen? Es geht mir um die Rechenschritte die er benötigt.
Schau doch im Prozessor-Handbuch, wieviel Cycles ein div braucht und wieviel Cycles ein shift braucht. Shift ist vermutl. schneller.
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.
Baum2 schrieb: >> Da kommt eh nicht das gleiche Raus, was willst du das vergleichen? > Es geht mir um die Rechenschritte die er benötigt. die Rechenschritte sind ja abhängig von den Werten in der Formel. Eine Division durch 1 geht z.b. sehr schnell.
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.
Baum2 schrieb: > Es geht mir um die Rechenschritte die er benötigt. Schreibe dir ein Mini-Programm das auf dem einen und dem anderen Weg die gleiche Rechnung durchführt. Compiliere es und schaue dir das vom Compiler erzeugte *.lss file an. Dort kannst du auf Asssembler-Ebene nachvollziehen was der Prozessor tun soll. Allerdings solltest du die Optimierung ausschalten da der Compiler eventuell für beide Rechenwege die gleiche Methode wählt.
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.“
:
Bearbeitet durch Moderator
Ich würde halt gerne wissen, ob es im Bezug auf die Optimierung sinnvoller ist, nur durch Zweierpotenzen zu dividieren.
Dirk_Geber schrieb: > Ich würde halt gerne wissen, ob es im Bezug auf die Optimierung > sinnvoller ist, nur durch Zweierpotenzen zu dividieren schaden tut es auf jeden Fall nicht. Damit es schneller ist, muss der Divisor aber zu Compilezeit konstant sein.
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.
> wahsaga schrieb zu vergleichbarem mal:
"
Forenposting mit Performancefrage Bewertungsfaustregel:
Wer Fragen nach der Performance solcher Kinkerlitzchen stellt, der
programmiert vermutlich noch nicht mal ansatzweise performant.
Andernfalls, wenn er wirklich und zu Recht an einer Applikation arbeiten
würde, bei der dieses Quentchen entscheidend ist, sollte er diese Frage
gar nicht mehr stellen müssen.
"
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.
Mark B. schrieb: > Zuerst einmal will man in aller Regel korrekte Ergebnisse haben. Ja, absolut korrekte Ergebnisse und die dann noch instantan berechnet, das ist natürlich das Ideal. Das Blöde ist halt nur: das geht nicht zu machen. Es wird immer eine gewisse Laufzeit erforderlich sein und oft werden auch gewisse Abweichungen vom absolut korrekten Ergebnis auftreten müssen. Der Trick in der Numerik ist, einen geeigneten Kompromiss zwischen Korrektheit und Laufzeit zu finden. Blöderweise ist aber wiederum von der Anwendung abhängig, welcher Kompromiss geeignet ist. Wer das nicht begriffen hat, hat vom Programmieren noch nicht viel verstanden.
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.
Volker B. schrieb: > Welche AVRs besitzen denn überhaupt einen Divisionsbefehl? Selbst ein BarrelShifter wird schmerzlich vermisst.
c-hater schrieb: > Ja, absolut korrekte Ergebnisse und die dann noch instantan berechnet, > das ist natürlich das Ideal. Ohne Laufzeit geht nur die wegoptimierte Division durch 1, aber warum sollte man da überhaupt dividieren, wenn es vorher bekannt ist. Alles andere hat was von Radio Eriwan...
Das Schieben ist schneller ABER eben nur zur entsprechenden Basis des Zahlensystemes. Bezogen auf binär heißt es du kannst nur durch 2 teilen auf die 10erBasis ist es eben nur /10. Somit ist die Aufgabe von dir die Dvision so abzubilden das du nicht nur durch die Basis des entsprechenden Zahlensystemes dividieren kannst sondern auch andere Teiler möglich sind. Dazu brauchst all den anderen Kram....
Also wenn rechnen müsste:
1 | uint8_t Wert = 20 / 5; |
Dann mach ich doch gleich so:
1 | uint8_t Wert = 4; |
;-) Ansonsten sehe ich das wie Arduino F. schrieb: >> wahsaga schrieb zu vergleichbarem mal: > " > Forenposting mit Performancefrage Bewertungsfaustregel: > Wer Fragen nach der Performance solcher Kinkerlitzchen stellt, der > programmiert vermutlich noch nicht mal ansatzweise performant. > Andernfalls, wenn er wirklich und zu Recht an einer Applikation arbeiten > würde, bei der dieses Quentchen entscheidend ist, sollte er diese Frage > gar nicht mehr stellen müssen. > "
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.
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.
:
Bearbeitet durch User
Es gab auf dem µCNet vor ein paar Jahren einen Thread mit einer schnellen Division, die in USA patentiert war. Der Thread stand vermutlich im Zusammenhang mit der Emulation des DIV-Befehls eines 8051 auf einem AVR-Controller. Vielleicht weiß noch jemand welcher Thread das war.
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 %= ?
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!
:
Bearbeitet durch User
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 | }
|
Zur Integer Division mit Konstanten gibts paar tricks: http://www.hackersdelight.org/divcMore.pdf Zur selbstprogrammierten Division von integern hatte ich hier mal was geschrieben. Beitrag "Integer division, Reciprocal of an integer value, Kehrwert eines integers" HTH Cheers Detlef
Hier ist das Patent, das ich gesucht habe (siehe oben): https://www.google.com/patents/US7007058 Der Algorithmus steht etwas tiefer und beginnt mit:
1 | #define uchar unsigned char
|
Der C-Quelltext selbst ist etwas putzig.
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.