Hallo zusammen,
ich bin gerade dabei, ein Programm für einen ATmega644 mit dem GCC zu
erstellen. Das geht auch nicht schlecht, der GCC produziert in den
meisten Fällen ganz ordentlichen Code. Aber eben nur in den meisten
Fällen. Was mir aufgefallen ist, ist, dass die Bitschieberei scheinbar
nicht so toll implementiert ist...
Am extremsten ist das bei diesem Code:
RF_MyAddress ist ebenfalls ein uint32_t. Zugegeben, diese Schieberei ist
nicht ganz ideal, da ich ein Offset von 4 Bit ausgleichen muss (address
und RF_MyAddress beinhalten jeweils 28 Bit Daten). Aber was der GCC da
produziert (Optimierung -Os) ist doch etwas krass:
1
@00000259: rf_send
2
92: void rf_send(const uint32_t address) {
3
+00000259: 92EF PUSH R14 Push register on stack
4
+0000025A: 92FF PUSH R15 Push register on stack
5
+0000025B: 930F PUSH R16 Push register on stack
6
+0000025C: 931F PUSH R17 Push register on stack
7
+0000025D: 93CF PUSH R28 Push register on stack
8
+0000025E: 93DF PUSH R29 Push register on stack
9
+0000025F: 017B MOVW R14,R22 Copy register pair
10
+00000260: 018C MOVW R16,R24 Copy register pair
11
93: RDD_MOSI |= _BV(PIN_MOSI);
12
+00000261: 9A25 SBI 0x04,5 Set bit in I/O register
Ganz toll finde ich da besonders die Schleife bei der Verschiebung um 20
Bit, die durch den folgenden Cast ja ohne Weiteres entfallen könnte,
sowie solche Spielereien:
1
+0000028E: 9180037E LDS R24,0x037E Load direct from data space
2
+00000290: 9190037F LDS R25,0x037F Load direct from data space
3
+00000292: 91A00380 LDS R26,0x0380 Load direct from data space
4
+00000294: 91B00381 LDS R27,0x0381 Load direct from data space
5
+00000296: 2F8B MOV R24,R27 Copy register
6
+00000297: 2799 CLR R25 Clear Register
7
+00000298: 27AA CLR R26 Clear Register
8
+00000299: 27BB CLR R27 Clear Register
Ahja. Man lade vier Register um sie dann auch gleich wieder zu
überschreiben. Ganz toll.
Ich will ja nicht sagen, dass der GCC schlecht optimiert, noch verlange
ich, dass jeder Code bis in's letzte Detail ausgefeilt ist. Doch bei -Os
dürfte man doch eigentlich schon erwarten, dass wenigstens solche
offensichtlichen Ehrenrunden vermieden werden. Die schlagen sich ja dann
sowohl auf der Codegrösse, als auch auf der Ausführungszeit nieder...
Also, zum Schluss auch noch meine Frage:
Wie könnte ich den Code umschreiben, dass er besser optimiert wird? Oder
gibt es nur die Möglichkeit, das ganze Zeug direkt in Assembler zu
schreiben? Letzteres möchte ich eigentlich vermeiden, nicht weil ich ASM
nicht mag, sondern weil das schlussendlich wohl mehr Probleme produziert
als löst...
Danke schonmal für alle (konstruktiven) Antworten und freundliche
Grüsse,
Philipp
GCC lebt davon, dass er von Leuten verbessert wird. Mach es! Du hast
keinen Anspruch darauf, dass andere es tun.
Ausserdem kannst du der Optimierung auch im Quellecode nachhelfen. Statt
Andreas Kaiser wrote:
> GCC lebt davon, dass er von Leuten verbessert wird. Mach es! Du hast> keinen Anspruch darauf, dass andere es tun.
Ich wusste doch, dass das kommt ;)
Würde ich gerne tun, leider habe ich vom Compilerbau wenig bis keine
Ahnung. Wenn es so trivial wäre, wäre es auch bestimmt schon gemacht.
> Ausserdem kannst du der Optimierung auch im Quellecode nachhelfen. Statt>
1
>rf_sendspi((uint8_t)(address>>20));
2
>rf_sendspi((uint8_t)(address>>12));
3
>
> schreibst du einfach>
1
>rf_sendspi((uint16_t)(address>>16)>>4);
2
>rf_sendspi((uint16_t)(address>>8)>>4);
3
>
Ja, genau sowas habe ich gesucht. Danke! Mal sehn, was er draus macht.
> Probier mal -O1 oder - O2. Die erzeugen nach meiner Erfahrung einen> kleineren und schnelleren Code.
Bringt hier nichts. Der Compiler müsste mehr Lösungensansätze für 32bit
Shifts implementieren als er tut. Also beispielsweise Shifts in 2 Stufen
realisieren, die erste mit n*8 durch Byteversatz, dann den Rest. Bei
16bit macht er das, bei 32bit offenbar nicht.
Sowas ist entweder drin und wirkt immer, oder es ist nicht drin.
Optimierung hat darauf meist wenig Einfluss.
> Wenn es so trivial wäre, wäre es auch bestimmt schon gemacht.
So schwierig dürfte es tatsächlich nicht sein. Jedenfalls nicht die
reine Shiftoptimierung, die ich grad skizziert habe. Dazu muss man nur
entsprechenden Code für die betreffenden Shiftoperationen einbauen.
Erheblich schwieriger ist es, Erkenntnisse, die von der Reihenfolge der
Operationen her später gewonnen werden, in vorherige Operationen
zurückwachsen zu lassen. Also zu erkennen, dass nur 8 Bits vom Ergebnis
gebraucht werden, und dies nicht erst danach, sondern bereits in der
Shiftoperation selbst zu berücksichtigen.
>void rf_send(const uint32_t address) {
Könnte einer der C-Gurus vielleicht mal kurz erklären was hier das
Attribut "const" bewirkt bzw. warum es notwendig ist? Ich kenne "const"
eher in Verbindung mit Zeigern. Auf den ersten Blick würde ich denken,
address ist ein konstanter 32-bit-Wert, d.h. dass nur Aufrufe wie
rf_send(1), rf_send(2) usw. erlaubt sein sollen. Ist das gemeint?
Gruß
Stefan Salewski
Ist noch nicht ideal, aber schon ein grosses Stück besser als mit den 20
Schleifendurchläufen :)
EDIT: btw, kann es sein, dass der GCC den swap-Befehl nicht kennt? Damit
liessen sich die Verschiebungen um 4 Bit wesentlich effizienter
gestalten.
EDIT2: O1 und O2 machen unwesentlich grösseren Code, optimiert wird aber
leider nicht besser.
Wer sich dran versuchen will: In gcc\config\avr\avr.c sind dafür die
Funktionen a/lshrqi3_out (8bit), -shrhi3_out (16bit) und -shrsi3_out
(32bit) zuständig. Bei 8- und 16bit sind die meisten Shiftcounts
handoptimiert, bei 32bit nur 8,16,24,31.
@Stefan:
"const" bewirkt hier, dass der Parameter in der Funktion nicht verändert
werden kann. Das kann u.U. dem Compiler etwas bei der Optimierung
helfen. Und es schliesst Fehlerquellen aus.
> EDIT: btw, kann es sein, dass der GCC den swap-Befehl nicht kennt? Damit> liessen sich die Verschiebungen um 4 Bit wesentlich effizienter> gestalten.
Doch er kennt ihn. An genau dieser Stelle greift nun doch die vom
Benedikt skizzierte Optimierungseinstellung, weil die Swap-Variante
deutlich länger ist:
das produziert den besten code unter gcc.
Dann Linksshift auf einem ATMega mit einem Shift größer als 1 immer als
Multplikation machen, das ist im Durchschnitt schneller und kompakter.
Statt
Philipp Burch schrieb:
>"const" bewirkt hier, dass der Parameter in der Funktion nicht verändert>werden kann. Das kann u.U. dem Compiler etwas bei der Optimierung>helfen. Und es schliesst Fehlerquellen aus.
Ah ja, danke. Hatte ich wohl auch irgendwann mal gelesen aber wieder
vergessen!
> Dann Linksshift auf einem ATMega mit einem Shift größer als 1 immer als> Multplikation machen, das ist im Durchschnitt schneller und kompakter.
Bei 32bit Operationen und nicht konstantem Faktor? Na wenn du meinst...
probiers einfach aus, fertig.
Eine MUL benötigt 2 Takte, ein Links Shift des gleichen Bytes um I Bits
benötigt 2 * i Takte minimal, ohne den Branch zu berücksichtigen.
Gilt logischerweise nur für Megas die eine HW-MUL unterstützen.
Normalerweise setzt man solche Optimierungen im Compiler voraus, sie
sind Standard. Klar das dies für GCC nicht gelten kann, lebt dieser von
der Eigenintiative ambtionierter Programmierer.
Ich denke das keiner hier GCC oder deren Entwickler angreifen möchte,
esw geht einfach nur darum zu lernen was der GCC wann macht und was man
als klein Hausmittelt so in seiner Apotheke hat um Kleinigkeiten besser
machen zu können. Es ist wohl auch klar das man mit solchen Tricks die
Kompatibilität des C Source aufhebt, auch dies ist logisch. (Nur um den
vielen gutgemeinten Ratschlägen die auf solche Threads folgen
vorzubeugen)
Gruß Hagen
Andreas Kaiser wrote:
>> EDIT: btw, kann es sein, dass der GCC den swap-Befehl nicht kennt? Damit>> liessen sich die Verschiebungen um 4 Bit wesentlich effizienter>> gestalten.>> Doch er kennt ihn. An genau dieser Stelle greift nun doch die vom> Benedikt skizzierte Optimierungseinstellung, weil die Swap-Variante> deutlich länger ist:
Genau aus diesem Grund verwende ich immer O1 oder O2 und nie Os. Denn
der Compiler versucht bei Os zwanghaft den kleinsten Code zu erzeugen.
Das sind oftmals dumme Schleifen (wie auch hier), oder bei y=x/128 wird
kein Shift verwendet, sondern die Divisionsroutine, da der Aufruf kürzer
ist (vorausgesetzt die Routine wird wo anderst sowiso benötigt). Die
Geschwindigkeitssteigerung liegt je nach Code bei bis zu >100%.
Ok, stimmt auch bei 32bit, ist aber abhängig von der Shiftcount. Bei
kleiner Shiftcount ist der Shift schneller als die Laufzeitfunktion zur
Multiplikation.
Der Code wird zwar absolut hässlich, aber das soll's mir an der Stelle
wert sein. Hab' vielen Dank!
@Benedikt:
Leider bringt O2 auch an der Stelle nicht die gewünschte Verbesserung,
da bereits keine Schleifen mehr existieren, die noch wegoptimiert werden
könnten...
Und keine Sorge, ich habe nicht vor, den Code mit einem anderen Compiler
zu kompilieren, daher kann ich schon solche "Hacks" machen.
EDIT:
Und hier noch die Variante mit einem "normalen" Shift:
rf_sendspi(HH8(address) * 0x0f | HL8(address) >> 4);
ist aber nicht identisch zu
rf_sendspi(HH8(address) << 4 | HL8(address) >> 4);
du multiplizierst mit 0x0F = 15 statt mit 0x10 = 16 = 2^4.
In diesem Falle ist 2. Lösung aber effizienter !
Gruß Hagen
>Ok, stimmt auch bei 32bit, ist aber abhängig von der Shiftcount. Bei>kleiner Shiftcount ist der Shift schneller als die Laufzeitfunktion zur>Multiplikation.
Laufzeitfunktion ? Einfache Miltiplikationen, zb. ein Byte * Byte werden
auf einem Mega der eine HW-MUL hat direkt umgesetzt. Da wird keine
Laufzeitbiliothek benötigt. Bei der Division ist das was anderes.
Das Beispiel aus diesem Thread arbeitet nicht mit 32Bit Zahlen sondern
nur mit Bytes.
Normale Shifts die nicht 8,16,24 sind werden als simple Schleifen
gebaut. Ein Byte kann maximal um +7 Bits geschoben werden. Da der GCC
den Shiftwert nicht optimiert wird bei einem Variablen Shift im
Durchschnitt der Wert 3 vorkommen, ergo 3*2 = 6 Takte. Im Gegensatz zu 2
Takten ohne Branches bei der MUL.
Auch bei den Shift mit 8,16,24 arbeitet der GCC ineffizient. In diesem
Falle fügt er unnötige CLR und MOV der selben Register ein.
Das ist aber nicht nur GCC spezifisch auch der Keil hat solche Sachen
drauf.
Ok ich gebe zu das sind jetzt schon Tricks die ziemlich am Rande der
sauberen Programmierung stehen und bei denen man sich die Frage stellen
muß ob sie wirkich notwendig sind. Aber es zu wissen, das man noch was
rausholen kann und den Compiler besser vesteht, hat auch seinen Wert.
Gruß Hagen
Ok, aber auch dann wäre die MUL schneller. Zb. ein 16 Bit um 2^5
shifted. Als normale Schleife sind das 3 * 5 Takte, 3 Takte weil ja 2
Bytes shift + 1 Takt Schleife. Per MUL würden 3 MULs ausreichen, also 6
Takte statt 15.
Je größer der Datentypen je höher der Aufwand für die Schleife wie auch
MUL, aber das Ratio veräöndert sich immer mehr zu Gunsten der MUL.
Gruß Hagen
Hagen Re wrote:
> rf_sendspi(HH8(address) * 0x0f | HL8(address) >> 4);>> ist aber nicht identisch zu>> rf_sendspi(HH8(address) << 4 | HL8(address) >> 4);>> du multiplizierst mit 0x0F = 15 statt mit 0x10 = 16 = 2^4.
Argh, Schande über mein Haupt. Du hast natürlich recht.
> In diesem Falle ist 2. Lösung aber effizienter !>> Gruß Hagen
Erstmal ein grosses Dankeschön für eure Vorschläge, so ist es jetzt kein
Problem mehr. Ob eine Operation nun drei Takte länger dauert oder nicht
ist mir ja eigentlich auch egal, aber wenn halt eine Schiebeoperation
dermassen ineffizient erzeugt wird, dann bin ich schon froh um solche
Optimierungen.
Hagen Re wrote:
> Ok, aber auch dann wäre die MUL schneller.
Nochmal: 32 Bits. Zweiunddreissig. Nicht 8 Bits, nicht 16 Bit. Der
Multiplikationsbefehl multipliziert aber nur 8x8=>16.
Die Libfcn enthält folglich 10 MULs und noch ein paar mehr ADD/ADCs,
insgesamt ~48 Takte plus Overhead weil Funktionsaufruf statt
Inline-Code. Die Schleife braucht 7 Takte/Iter, d.h. ab ungefähr n=8
dürfte die Multiplikation im Vorteil sein.
Hm, lass uns mal streiten ;)
eine 32Bit 8Bit MUL benötigt 4 8x8Bit MUL + 1 ADD + 2 ADC, nicht mehr
und nicht weniger.
4*2 + 3 Takte also macht 11 Takte, vorrausgesetzt wir vernachlässigen
mal das Laden der Register, da dies bei beiden Methoden mit festen
Overhead einhergeht.
Ein Shift über 4 Bytes benötigt 4 Takte + 1 Takt Spungbefehlt, macht 5
Takte um 1 Bit zu schieben.
1 Bit = 5 Takte
2 Bit = 10 Takte
31 Bit = 155 Takte
5+10+...155 / 31 = 80 Takte im Durchschnitt. Also wenn man vorraussetzt
das gleichverteilt im Bereich von 1 bis 31 Bits ein 32 Bit Wert links
geschoben wird so belaufen sich die Kosten auf
Shiftloop = 80 Takte im Durchschnitt
MUL Methode = konstante 11 Takte
Na das nenn ich mal ein ordentliches Ratio, oder ?
Klar, wenn man C Source voraussetz und die auf Univeralität
programmierte MUL Methode der Standardlib die nicht nur 32x8 Bit sondern
auch 32x16 und 32x32 rechnen kann, dann sind das 48 Takte. Aber auch das
ist besser als die 80 Takte mit Loops.
Wo ist jetzt mein Rechenfehler ?
Gruß Hagen
> Wo ist jetzt mein Rechenfehler ?
Du hast für die Bitschieberei zuwenig Takte veranschlagt ;-)
Ein branch-Befehl braucht zwei Takte, wenn er springt. Macht also 6
Takte pro geschobenem Bit, nicht 5. Beim letzten Durchlauf wird zwar
nicht gesprungen, was einen Takt spart, aber den braucht man dafür dann
zum Initialisieren des Schleifenzählers.
Bis auf den Sprung nirgends. Jetzt sind wir beisammen. Ich schrieb, auf
Basis der Libfunktion, dass kleine Shiftcounts drunter liegen. Du, dass
die optimale aber nirgend realisierte Multiplikation ebenso wie die
mittlere angenommene Shiftcount drüber liegen. Kein Widerspruch, stimmt
beides.
Wenn wir weiter streiten wollen, dann allenfalls über die angenommene
Gleichverteilung bei den Shiftcounts ;-).
;)
Ok, das mit dem Branch stimmt. Und bei der MUL Methode müssen wir auf
Grund der Eigenheiten das der AVR immer über Register r1:r0 geht wohl
auch noch par Takte hinzurechnen, für die MOVW Opcodes, falls wir mehr
als 8 Bit schieben wollen.
Auf alle Fälle benutze ich den MUL Trick immer dann wenn ich zb. in
meinen Grafik Libraries oä. per Inline Assembler arbeite. Dieser Schritt
ist eh kontraproduktiv aus Sicht der Portierbarkeit, also kann man auch
solche Tricks da anwenden. Gerade bei Ausgabe von Bitmapfonts oder
kodierten Bitmaps benötigt man oft Shifts. Als erstes baue ich die
Datenformate immer so das ich mit Links Shifts auskomme statt mit Rechts
Shifts. Dann kann ich später für die ATMega's das per MULs optimieren.
Das macht dann schon einen großen Unterschied in der Performance aus,
wenn zb. ein Fontzeichen 14x12 Pixel hat und pro Pixel shifted werden
muß.
Oder bei sehr zeitkritischen ISRs. Dort ist es wünschenswert das die ISR
sehr schnell arbeitet aber noch viel wichtiger das sie mit konstanten
Taktanzahlen auskommt. Dh. die ISR soll immer die gleiche Taktanzahl
besitzen um damit im Gesamtsystem besser berechnebar zu sein. Und die
MUL Methode benötigt immer die gleiche Taktanzahl unabhängig wieviele
Bits geschoben werden. Die Loop Methode logischerweise nicht.
Gruß Hagen
Da ist mir doch gleich noch eine Ungereimtheit aufgefallen:
1
121: if (RPI_MISO & _BV(PIN_MISO)) *s_address |= (1UL << 24);
2
+000002CF: 9B1E SBIS 0x03,6 Skip if bit in I/O register set
3
+000002D0: C008 RJMP PC+0x0009 Relative jump
4
+000002D1: E040 LDI R20,0x00 Load immediate
5
+000002D2: E050 LDI R21,0x00 Load immediate
6
+000002D3: E060 LDI R22,0x00 Load immediate
7
+000002D4: E071 LDI R23,0x01 Load immediate
8
+000002D5: 2AE4 OR R14,R20 Logical OR
9
+000002D6: 2AF5 OR R15,R21 Logical OR
10
+000002D7: 2B06 OR R16,R22 Logical OR
11
+000002D8: 2B17 OR R17,R23 Logical OR
12
+000002D9: 2F89 MOV R24,R25 Copy register
13
+000002DA: 958A DEC R24 Decrement
14
+000002DB: F7F1 BRNE PC-0x01 Branch if not equal
Kann mir jemand erklären, was die Schleife dort am Ende soll? R25
beinhaltet den Wert 2. Soll das eine etwas andere Variante darstellen um
ein Register zu nullen? Warteschleife oder sowas hat's nicht in der
Nähe.
EDIT: Und gleich nochwas: Was ist das Problem, wenn ich die Zeile so
abändere?
1
if(RPI_MISO&_BV(PIN_MISO))HH8(*s_address)|=0x01;
Da haut mir der Compiler den Fehler "error: invalid lvalue in
assignment" um die Ohren...
Oha, Kommando zurück. In der nächsten Zeile steht ja _delay_us(1) ich
Idiot... Damit hat sich das Problem wohl erledigt. Warum aber die zweite
Möglichkeit mit HH8() nicht funktioniert ist mir immer noch nicht ganz
klar...
Niemand eine Idee, warum das nicht geht? Sind die Elemente einer Union
schreibgeschützt oder so? Kaum, oder?
Ausserdem motzt er ja den lvalue an und da kommt doch eigentlich nur
HH8(*s_address) rechts vom '=', sowie 0x01 in Frage. Was soll daran
falsch sein?