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
tip schrieb: > Da sich Divisionen durch 2er > Potenzen durch Bitshift-Operationen realisieren lassen Aber nur für unsigned typen...
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.
> 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.
gcc schrieb: > von wegen "geht nicht bei signed" > > -4: 11111100 > ASR arithmetic shift right > -2: 11111110 Bitte mal mit -1 vorführen. Danke. Matthias
sollte natürlich
>>"geht nicht" und "geht oft, aber nicht immer"<<
sein
Μα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.
Hier das entsprechende .LSS-File einmal mit 2er-Potenzen und einmal ohne:
1 | Yx = ( (KPx * winkel_gyro_e_p_x) / 65536 ) + ( (KIx*Ta*( winkel_gyro_e_i_x / 1024 ) ) ) - ( (KDx*l3g_erg_x) / (1024) ); |
2 | 8c0: 60 91 ac 01 lds r22, 0x01AC |
3 | 8c4: 70 91 ad 01 lds r23, 0x01AD |
4 | 8c8: 80 91 ae 01 lds r24, 0x01AE |
5 | 8cc: 90 91 af 01 lds r25, 0x01AF |
6 | 8d0: a0 90 be 01 lds r10, 0x01BE |
7 | 8d4: b0 90 bf 01 lds r11, 0x01BF |
8 | 8d8: 20 91 12 02 lds r18, 0x0212 |
9 | 8dc: 30 91 13 02 lds r19, 0x0213 |
10 | 8e0: 40 91 14 02 lds r20, 0x0214 |
11 | 8e4: 50 91 15 02 lds r21, 0x0215 |
12 | 8e8: 0e 94 4f 0b call 0x169e ; 0x169e <__mulsi3> |
13 | 8ec: 7b 01 movw r14, r22 |
14 | 8ee: 8c 01 movw r16, r24 |
15 | 8f0: 60 91 06 02 lds r22, 0x0206 |
16 | 8f4: 70 91 07 02 lds r23, 0x0207 |
17 | 8f8: 80 91 08 02 lds r24, 0x0208 |
18 | 8fc: 90 91 09 02 lds r25, 0x0209 |
19 | 900: 20 e0 ldi r18, 0x00 ; 0 |
20 | 902: 34 e0 ldi r19, 0x04 ; 4 |
21 | 904: 40 e0 ldi r20, 0x00 ; 0 |
22 | 906: 50 e0 ldi r21, 0x00 ; 0 |
23 | 908: 0e 94 a3 0b call 0x1746 ; 0x1746 <__divmodsi4> |
24 | 90c: c8 01 movw r24, r16 |
25 | 90e: b7 01 movw r22, r14 |
26 | 910: 0e 94 4f 0b call 0x169e ; 0x169e <__mulsi3> |
27 | 914: 7b 01 movw r14, r22 |
28 | 916: 8c 01 movw r16, r24 |
29 | 918: 60 91 fa 01 lds r22, 0x01FA |
30 | 91c: 70 91 fb 01 lds r23, 0x01FB |
31 | 920: 80 91 fc 01 lds r24, 0x01FC |
32 | 924: 90 91 fd 01 lds r25, 0x01FD |
33 | 928: 20 91 57 01 lds r18, 0x0157 |
34 | 92c: 30 91 58 01 lds r19, 0x0158 |
35 | 930: 40 91 59 01 lds r20, 0x0159 |
36 | 934: 50 91 5a 01 lds r21, 0x015A |
37 | 938: 0e 94 4f 0b call 0x169e ; 0x169e <__mulsi3> |
38 | 93c: 20 e0 ldi r18, 0x00 ; 0 |
39 | 93e: 30 e0 ldi r19, 0x00 ; 0 |
40 | 940: 41 e0 ldi r20, 0x01 ; 1 |
41 | 942: 50 e0 ldi r21, 0x00 ; 0 |
42 | 944: 0e 94 a3 0b call 0x1746 ; 0x1746 <__divmodsi4> |
43 | 948: e2 0e add r14, r18 |
44 | 94a: f3 1e adc r15, r19 |
45 | 94c: 04 1f adc r16, r20 |
46 | 94e: 15 1f adc r17, r21 |
47 | 950: cc 24 eor r12, r12 |
48 | 952: b7 fc sbrc r11, 7 |
49 | 954: c0 94 com r12 |
50 | 956: dc 2c mov r13, r12 |
51 | 958: 20 91 1e 02 lds r18, 0x021E |
52 | 95c: 30 91 1f 02 lds r19, 0x021F |
53 | 960: 40 91 20 02 lds r20, 0x0220 |
54 | 964: 50 91 21 02 lds r21, 0x0221 |
55 | 968: c6 01 movw r24, r12 |
56 | 96a: b5 01 movw r22, r10 |
57 | 96c: 0e 94 4f 0b call 0x169e ; 0x169e <__mulsi3> |
58 | 970: 20 e0 ldi r18, 0x00 ; 0 |
59 | 972: 34 e0 ldi r19, 0x04 ; 4 |
60 | 974: 40 e0 ldi r20, 0x00 ; 0 |
61 | 976: 50 e0 ldi r21, 0x00 ; 0 |
62 | 978: 0e 94 a3 0b call 0x1746 ; 0x1746 <__divmodsi4> |
63 | 97c: e2 1a sub r14, r18 |
64 | 97e: f3 0a sbc r15, r19 |
65 | 980: 04 0b sbc r16, r20 |
66 | 982: 15 0b sbc r17, r21 |
67 | 984: e0 92 4e 02 sts 0x024E, r14 |
68 | 988: f0 92 4f 02 sts 0x024F, r15 |
69 | 98c: 00 93 50 02 sts 0x0250, r16 |
70 | 990: 10 93 51 02 sts 0x0251, r17 |
71 | |
72 | |
73 | -------------------------------------------------------------------------- |
74 | |
75 | Yx = ( (KPx * winkel_gyro_e_p_x) / 10000 ) + ( (KIx*Ta*( winkel_gyro_e_i_x / 1000 ) ) ) - ( (KDx*l3g_erg_x) / (1000) ); |
76 | 8c0: 60 91 ac 01 lds r22, 0x01AC |
77 | 8c4: 70 91 ad 01 lds r23, 0x01AD |
78 | 8c8: 80 91 ae 01 lds r24, 0x01AE |
79 | 8cc: 90 91 af 01 lds r25, 0x01AF |
80 | 8d0: a0 90 be 01 lds r10, 0x01BE |
81 | 8d4: b0 90 bf 01 lds r11, 0x01BF |
82 | 8d8: 20 91 12 02 lds r18, 0x0212 |
83 | 8dc: 30 91 13 02 lds r19, 0x0213 |
84 | 8e0: 40 91 14 02 lds r20, 0x0214 |
85 | 8e4: 50 91 15 02 lds r21, 0x0215 |
86 | 8e8: 0e 94 4f 0b call 0x169e ; 0x169e <__mulsi3> |
87 | 8ec: 7b 01 movw r14, r22 |
88 | 8ee: 8c 01 movw r16, r24 |
89 | 8f0: 60 91 06 02 lds r22, 0x0206 |
90 | 8f4: 70 91 07 02 lds r23, 0x0207 |
91 | 8f8: 80 91 08 02 lds r24, 0x0208 |
92 | 8fc: 90 91 09 02 lds r25, 0x0209 |
93 | 900: 28 ee ldi r18, 0xE8 ; 232 |
94 | 902: 33 e0 ldi r19, 0x03 ; 3 |
95 | 904: 40 e0 ldi r20, 0x00 ; 0 |
96 | 906: 50 e0 ldi r21, 0x00 ; 0 |
97 | 908: 0e 94 a3 0b call 0x1746 ; 0x1746 <__divmodsi4> |
98 | 90c: c8 01 movw r24, r16 |
99 | 90e: b7 01 movw r22, r14 |
100 | 910: 0e 94 4f 0b call 0x169e ; 0x169e <__mulsi3> |
101 | 914: 7b 01 movw r14, r22 |
102 | 916: 8c 01 movw r16, r24 |
103 | 918: 60 91 fa 01 lds r22, 0x01FA |
104 | 91c: 70 91 fb 01 lds r23, 0x01FB |
105 | 920: 80 91 fc 01 lds r24, 0x01FC |
106 | 924: 90 91 fd 01 lds r25, 0x01FD |
107 | 928: 20 91 57 01 lds r18, 0x0157 |
108 | 92c: 30 91 58 01 lds r19, 0x0158 |
109 | 930: 40 91 59 01 lds r20, 0x0159 |
110 | 934: 50 91 5a 01 lds r21, 0x015A |
111 | 938: 0e 94 4f 0b call 0x169e ; 0x169e <__mulsi3> |
112 | 93c: 20 e1 ldi r18, 0x10 ; 16 |
113 | 93e: 37 e2 ldi r19, 0x27 ; 39 |
114 | 940: 40 e0 ldi r20, 0x00 ; 0 |
115 | 942: 50 e0 ldi r21, 0x00 ; 0 |
116 | 944: 0e 94 a3 0b call 0x1746 ; 0x1746 <__divmodsi4> |
117 | 948: e2 0e add r14, r18 |
118 | 94a: f3 1e adc r15, r19 |
119 | 94c: 04 1f adc r16, r20 |
120 | 94e: 15 1f adc r17, r21 |
121 | 950: cc 24 eor r12, r12 |
122 | 952: b7 fc sbrc r11, 7 |
123 | 954: c0 94 com r12 |
124 | 956: dc 2c mov r13, r12 |
125 | 958: 20 91 1e 02 lds r18, 0x021E |
126 | 95c: 30 91 1f 02 lds r19, 0x021F |
127 | 960: 40 91 20 02 lds r20, 0x0220 |
128 | 964: 50 91 21 02 lds r21, 0x0221 |
129 | 968: c6 01 movw r24, r12 |
130 | 96a: b5 01 movw r22, r10 |
131 | 96c: 0e 94 4f 0b call 0x169e ; 0x169e <__mulsi3> |
132 | 970: 28 e1 ldi r18, 0x18 ; 24 |
133 | 972: 3c ef ldi r19, 0xFC ; 252 |
134 | 974: 4f ef ldi r20, 0xFF ; 255 |
135 | 976: 5f ef ldi r21, 0xFF ; 255 |
136 | 978: 0e 94 a3 0b call 0x1746 ; 0x1746 <__divmodsi4> |
137 | 97c: e2 0e add r14, r18 |
138 | 97e: f3 1e adc r15, r19 |
139 | 980: 04 1f adc r16, r20 |
140 | 982: 15 1f adc r17, r21 |
141 | 984: e0 92 4e 02 sts 0x024E, r14 |
142 | 988: f0 92 4f 02 sts 0x024F, r15 |
143 | 98c: 00 93 50 02 sts 0x0250, r16 |
144 | 990: 10 93 51 02 sts 0x0251, r17 |
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.
1 | #include <stdio.h> |
2 | |
3 | int main(int argc, char * argv[]) |
4 | {
|
5 | int a = -1; |
6 | |
7 | printf("a / 2 = %d\n", a / 2); |
8 | printf("a >> 1 = %d\n", a >> 1); |
9 | |
10 | return 0; |
11 | }
|
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!
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.