Hallo zusammen,
Ich optimiere grade meinen Code bezüglich Geschwindigkeit. Da Divisionen
durch 2er Potenzen am schnellsten gehen, habe ich solche Werte gewählt.
Ich verwende AVR Studio4 mit der Optimierungsstufe Os.
folgende Rechenschritte benötigen zusammen etwa 400µs (Die Variablen in
diesem Beispiel sind vom Typ "int32_t"):
Yx = ( (KPx * winkel_gyro_e_p_x) / 65536 ) + ( (KIx*Ta*(
winkel_gyro_e_i_x / 1024 ) ) ) - ( (KDx*l3g_erg_x) / (1024) );
Yy = ( (KPy * winkel_gyro_e_p_y) / 65536 ) + ( (KIy*Ta*(
winkel_gyro_e_i_y / 1024 ) ) ) - ( (KDy*l3g_erg_y) / (1024) );
Yz = ( (KPz * winkel_gyro_e_p_z) / 65536 ) + ( (KIz*Ta*(
winkel_gyro_e_i_z / 1024 ) ) ) - ( (KDz*l3g_erg_z) / (1024) );
Wenn ich nun die Nenner durch zb. "10000" ersetze (keine 2er Potenz), so
bleibt die benötigte Zeit ebenso bei 400µs. Da sich Divisionen durch 2er
Potenzen durch Bitshift-Operationen realisieren lassen, müsste der
Compiler das doch wesentlich schneller hinbekommen oder nicht?
Danke und Gruß!
tip
Wenn hier dem Kompiler gesagt wird, er soll dividieren, dann verwendet
er den zeitraubenden Divisionsmechanismus auch beim Divisor 1024. Er
prüft sicher nicht die Zahl 1024, ob sie eine Binärzahl mit führender 1
ist.
Man muss schon das shiften um 10 Binärstellen nach rechts explizit
eingeben, dass der Compiler diesen wesentlich schnelleren Vorgang
bildet.
Peter R. schrieb:> Man muss schon das shiften um 10 Binärstellen nach rechts explizit> eingeben, dass der Compiler diesen wesentlich schnelleren Vorgang> bildet.
So ein Quatsch... also wenn der Compiler nicht mal diesen simplen Trick
beherrscht sollte man ihn wegwerfen. Was der Compiler aber nicht macht
ist das blind umzuwandeln, sondern nur wenn auch Mathematisch das selbe
rauskommt, und das geht bei Signed zahlen nicht.
Der Compiler macht schon so viel fpr uns (auf dem weg von C zum
Hex-Code),
da fände ich es nur fair, wenn man ihn ab und zu mal unterstützt. Int32
ist ja nicht gerade AVR's Leibspeise und wenn man die Division durch 2er
Potenzen per shift schreibt, dann ist auch klar dokumentiert, daß man
NUR 2er Potenzen benutzen wollte.
> Man muss schon das shiften um 10 Binärstellen nach rechts explizit> eingeben, dass der Compiler diesen wesentlich schnelleren Vorgang> bildet.
-------------------------
sowas hatte ich geahnt. Mir ist jedoch nicht verständlich, warum der
Compiler das nicht von sich aus tut. Ich teile doch durch eine
Konstante. wirklich seltsam.
Dann werde ich es wohl per Hand einfügen müssen.
>Aber nur für unsigned typen...
------------------------------
Für signed Typen nicht? Ich muss mir doch lediglich das Vorzeichenbit
merken, verschieben und nachträglich das Vorzeichen wieder
berücksichtigen oder liege ich da falsch?
Danke und Gruß!
tip
Bei negativen Zahlen nach dem Schieben entsprechend die oberen Bits zu
setzen, ist doch kein Hexenwerk.
Ein Blick in den List-File verrät, was der Compiler für Code erzeugt.
> Läubi, nicht so schnell schiessen. "Arithmetical Shift Right" macht> genau das. Rechtsschieben und Vorzeichen behalten.
Heißt das, der Compiler berücksichtigt bei dieser Operation das
Vorzeichenbit? Ich hätte jetzt gedacht, dass ich mit einer
Shiftoperation (x << y) auch das Vorzeichenbit verschiebe und daher
darauf achten muss.
gruß
tip
von wegen "geht nicht bei signed"
-4: 11111100
ASR arithmetic shift right
-2: 11111110
Wenn der Compilerbauer den Unterschied zum LSR "logical shift right"
nicht kennt, dann wäre das wirklich bedenklich.
Aber ist 10*32Bit schieben auf 'ner 8Bit CPU wirklich (sehr viel)
schneller?
Bisher ist auch ausser "läuft lang" noch kein Beweis angetreten, daß da
wirklich dividiert wird. Was hat der Compiler denn als Output geliefert?
Falls GCC: was steht denn im .LSS File?
Micha schrieb:> Läubi, nicht so schnell schiessen. "Arithmetical Shift Right" macht> genau das. Rechtsschieben und Vorzeichen behalten.http://www.plunk.org/~grantham/public/divshift.html rechtsschift auf
signed typen ist zudem "implementation-defined" in C...
gcc schrieb:> von wegen "geht nicht bei signed"
Du kennst den Beweis das alle ungeraden Zahlen außer 1 Primzahlen sind
oder?
Läubi .. schrieb:> gcc schrieb:>> von wegen "geht nicht bei signed">> Du kennst den Beweis das alle ungeraden Zahlen außer 1 Primzahlen sind> oder?
wenn drum geht spitzfindig zu sein:
"geht nicht" und "geht nicht oft, aber nicht immer" sind nicht das
selbe.
Μαtthias W. schrieb:> gcc schrieb:>> von wegen "geht nicht bei signed">>>> -4: 11111100>> ASR arithmetic shift right>> -2: 11111110>> Bitte mal mit -1 vorführen. Danke.>> Matthias
-1 / 2 zu rechnen als GANZZAHL macht keinen rechten Sinn. Kommt halt
wieder -1 raus.
das ist aber beim positiven Bereich genauso schlecht:
1 / 2 ergibt durchs shiften 0.
In beiden Fällen ist die Abweichung 0.5
Problem ist aber unter anderem auch in C: Es unterscheidet nicht
zwischen LSR/LSL und ASR/ASL, es gibt nur diesen << und >> Operator.
Division mit Vorzeichen und arithmetischer Shift führen zu
unterschiedlichen Ergebnissen wenn ein Rest bleibt. Der Compiler kann
das nutzen, aber es braucht beim AVR recht viel Platz, daher kann es
sein, dass der bei Optimierung auf Platz den viel langsameren aber
kürzeren Aufruf der Laufzeitfunktion für die Division erzeugt.
Johannes O. schrieb:> Problem ist aber unter anderem auch in C: Es unterscheidet nicht> zwischen LSR/LSL und ASR/ASL, es gibt nur diesen << und >> Operator.
Falsch!
Der Compiler weiss doch ob er signed oder unsigned shiften soll. Er
kennt den Typ der Variablen.
-1 / 2 ergibt 0
-1 >> 1 ergibt -1
Das sind unterschiedliche Ergebnisse.
Darum kann der Compiler bei signed die Divison nicht durch shift
ersetzen.
Johannes O. schrieb:> Μαtthias W. schrieb:>> gcc schrieb:>>> von wegen "geht nicht bei signed">>>>>> -4: 11111100>>> ASR arithmetic shift right>>> -2: 11111110>>>> Bitte mal mit -1 vorführen. Danke.>>>> Matthias>> -1 / 2 zu rechnen als GANZZAHL macht keinen rechten Sinn. Kommt halt> wieder -1 raus.
Wirklich? Zumindest die Ganzzahlarithmetik wie sie in C implementiert
wird rundet nicht sondern "schneidet ab". -1 / 2 = 0 Und da man den
Divident ja nicht kennt ist das Ergebnis von / 2 eben nicht identisch
mit >> 1
> das ist aber beim positiven Bereich genauso schlecht:> 1 / 2 ergibt durchs schiften 0.
Das ist korrekt im Sinne der Ganzzahlarithmetik in C.
> Problem ist aber unter anderem auch in C: Es unterscheidet nicht> zwischen LSR/LSL und ASR/ASL, es gibt nur diesen << und >> Operator.
ASR 1 ist aber nicht identisch mit DIV 2 für Zahlen im Zweierkomplement.
DirkB schrieb:> Darum kann der Compiler bei signed die Divison nicht durch shift> ersetzen.
Nicht unmittelbar. Er muss vorher entsprechend korrigieren.
tip schrieb:> mit der Optimierungsstufe Os.
Stand das nicht für möglichst kompakten Code??
Wenn sich da mein Halbwissen bestätigt gilt eine goldene Regel der
Informatik: Speicherplatz wird mit Rechenleistung/dauer erkauft
>Ich verwende AVR Studio4 mit der Optimierungsstufe Os.
Ich vermute mal, dass Du dich auf avr-gcc beziehst -- dann wäre der
Bereich gcc das richtige Unter-Forum, da gibt es eher Experten...
Und Option 0s, das ist doch bei gcc wohl Optimierung auf kompakten Code,
wenn ich mich recht erinnere. Du sagst doch damit, dass es Dir auf
Geschwindigkeit weniger ankommt.
DirkB schrieb:> Falsch!> Der Compiler weiss doch ob er signed oder unsigned shiften soll. Er> kennt den Typ der Variablen.
ich hatte damit GENAU DAS angedeutet: Es gibt keine 2 unterschiedliche
Befehle dafür. D.h. wenn ich explizit ein ASR oder ein LSR ausführen
will, dann kann ich das nur über die Variablentypen steuern. Aber NICHT
über einen Befehl.
Μαtthias W. schrieb:> Wirklich? Zumindest die Ganzzahlarithmetik wie sie in C implementiert> wird rundet nicht sondern "schneidet ab". -1 / 2 = 0 Und da man den> Divident ja nicht kennt ist das Ergebnis von / 2 eben nicht identisch> mit >> 1
Wenns dich stört, dann musst halt danach wieder +1 machen, falls du eine
1 im Carry hast. Aber oftmals ist es so, dass man lieber schneller
rechnet als dass man ganz genau rechnet. Denn insbesondere beim OP
seinem Regler ist eine hohe Regelfrequenz wichtig!
Johannes O. schrieb:> Μαtthias W. schrieb:>> gcc schrieb:>>> von wegen "geht nicht bei signed">>>>>> -4: 11111100>>> ASR arithmetic shift right>>> -2: 11111110>>>> Bitte mal mit -1 vorführen. Danke.>>>> Matthias>> -1 / 2 zu rechnen als GANZZAHL macht keinen rechten Sinn. Kommt halt> wieder -1 raus.> das ist aber beim positiven Bereich genauso schlecht:> 1 / 2 ergibt durchs shiften 0.> In beiden Fällen ist die Abweichung 0.5
Das ist doch nur eine Frage der Rundung. Wenn man natürlich vermutet,
das Rundung immer Symmetrisch (und vielleicht soger noch kaufmännisch,
"0,5") sein muß, der liegt falsch. Denn das ist alles eine Frage der
Definition.
Oder des sich Köpfe-Einschlagens, je nachdem.
Ich könnte mir denken, die Entwickler des GCC AVR Backends legen ihren
Haupeigenmerk nicht auf das Optimieren von 32bit Arithmetic, sondern
haben genug mit dem Haupanwendungsgebiet dieser Architektur zu tun, den
8 Bit.
Wenn der AVR nicht bringt: So ein kleiner ARM hat das selbe Gehäuse und
kann den Heli vielleicht schneller stabilisieren.
Wenn das Verhalten des Compilers bei -Os stört und -O1 oder -O2 in den
Speicher reinpasst, dann kann man das auch verwenden.
Mit
#pragma GCC optimize ("O2")
...
#pragma GCC reset_options
lässt sich das ab GCC 4.4 auch innerhalb vom Code umstellen.
Nochmals Danke!
Auf Genauigkeit kommt es nicht so sehr an. Mit der Optimierungsstufe
habe ich schon herumgespielt, aber keinen nennenswerten Unterschied
festgestellt.
Mir ist grade aufgefallen, dass dieses Thema schon besprochen wurde
(sorry für meinen zusätzlichen Thread - ich weiß, dass dies in Foren
ungern gesehen wird).
Beitrag "Optimiert der Compiler Division durch 2^n wirklich?"
Nochmals Danke!
