hi,
mir ist aufgefallen, dass unter Umständen bei GCC der Code kleiner wird,
wenn man so etwas:
1
unsigned char a[bla][blo] |= 12;
durch das hier ersetzt:
1
unsigned char * tmp_p = &a[bla][blo];
2
*tmp_p |= 12;
Unter Umständen deshalb, da der Code in manchen Fällen kleiner wird, in
manchen nicht.
Ich kann mir natürlich auch denken warum, vermutlich wird die Adresse im
ersten Fall zweimal berechnet.
Gibt es bei soetwas irgendwelche allgemeinen Tips/Richtlinien um den
Code schön klein und schnell zu bekommen?
Hallo,
Ich kann glaube ich von mir behaupten, mich ganz gut mit C/C++
auszukennen, aber deine erste Code-Zeile macht für mich überhaupt keinen
Sinn.
Dennoch: Vom avr-gcc darf man keine Wunder erwarten, er hat einige
Schwächen, ist aber meines Erachtens der beste C-Compiler für die AVR.
Vor allem weigert er sich Zwischenergebnisse, die mehrfach verwendet
werden, in Register zu packen. In diesem Falle hilft es, einfach diese
Werte manuell in eine lokale Variable zu stecken. Diese werden für
gewöhnlich nicht "wegoptimiert", was einer "Verschlimmbesserung"
entspräche...
Wenn Arrays innerhalb von Funktionen benötigt werden, die nicht rekursiv
aufgerufen werden, dann sollten diese unbedingt "static" sein, denn dies
spart die umständliche Veränderung des Stack-Speichers.
Und weiterhin sollte auf Arrays nicht direkt, sondern über einen Zeiger
zugegriffen werden, dies erzeugt wirklich guten Code, *ptr++ mag der
avr-gcc am liebsten, entweder nutzt er dann ldd oder ld ptr+.
Ich schaue grundsätzlich in das Assemblerlisting und optimiere dann per
Hand, dies führt zu den Ergebnissen, die ich mir wünsche. Wenn es gar
nicht anders geht, nutze ich Inline-Assembler, die Möglichkeiten diesen
mit dem restlichen C-Code zu verbinden sind bei dem avr-gcc ziemlich gut
- finde ich zumindest.
Wenn man durch Zweierpotenzen teilen möchte, sollte man besser einen
Shift nutzen, der avr-gcc macht dies nicht selbst, sondern ruft immer
__udivmodhi auf oder wie diese Funktion heißt.
So etwas ist auch schlecht:
for (uint8_t n = 0; n < 8; n++)
{
if (test & (1 << n))
....
}
Besser:
uint8_t shift = 0x01;
for (uint8_t n = 0; n < 8; n++)
{
if (test & shift)
...
shift <= 1;
}
Das sind die Dinge, die mir nach und nach aufgefallen sind.
Seit zwei oder drei Wochen habe ich auf avr-gcc 4.5.0 umgestellt, durch
die LTO kann man nochmals deutlich schlankeren Code rausholen. (-flto
und -fwhole-program). Der Aufruf von -Os darf auch beim Linkvorgang
nicht vergessen werden, sonst wird der Code wieder riesig.
Aufpassen muss man allerdings, dass durch die LTO nicht andere Sachen
wegoptimiert werden, da diese "scheinbar" nicht genutzt würden. Dafür
gibt es aber ein Attribut namens externally_visible in GCC 4.5.0.
Viele Grüße,
Lars
@Lars R.:
Du solltest mal die Optimierung beim AVR GCC einschalten! Du wirst
sehen, dass er dann viele deiner tollen "Handoptimierungen" von selber
macht! Bei dem was du da schreibst, hast du entweder die Optimierung
nicht an, oder beziehst dein wissen aus einer 15 Jahre alten gcc
Version.
Hallo Klaus,
> @Lars R.:>> Du solltest mal die Optimierung beim AVR GCC einschalten! [...]
Ist diese Antwort ernst gemeint, soll ich nun lachen?!?
Ich aktiviere grundsätzlich die Optimierungsstufe -Os beim avr-gcc. Ich
habe auch extra noch angemerkt, dass bei der Nutzung von LTO auch dem
Linker diese Optimierungsstufe mitgegeben werden muss.
Wenn man die Optimierung ausschaltet, also -O0, dann führt dies dazu,
dass der avr-gcc völlig unsinnigen Code produziert, wie mehrere
mov-Befehle hintereinander, die nur Daten hin- und herschieben. Ganz
beliebt sind dann auch unnötige push/pop-Folgen oder UND-Verknüpfungen
mit 0xFF obwohl danach nicht SREG abgefragt wird usw.
Ohne Optimierung wird das Programm sowieso so groß und langsam, dass der
Einsatz des Compilers fraglich würde...
Ich nutzte bis zur Umstellung auf 4.5.0 die Version 4.3.4 von avr-gcc,
die 4.4er-Versionen erzeugten weitaus größeren Code, erst mit 4.5.0
wurden, wenigstens meine Programme, wieder kleiner.
Eventuell bin auch nur zu empfindlich, das mag sein, aber ich schaue mir
halt auch das Assemblerlisting an. Dass ein größerer Code durch den
Einsatz von C entsteht, nehme ich als gegeben hin, aber zwischen einem
größeren Code und einem riesigen Code liegt doch noch ein schöner
Unterschied.
Ich freue mich jedenfalls auch, wenn ich durch eine kleine Veränderung
im C-Code 18 oder 20 Bytes einsparen kann, es gibt Projekte, da benötigt
man jedes freie Byte.
Da ich keine bessere Alternative zu avr-gcc kenne, nutze ich diesen
Compiler klaglos, ich weiß ja, wie ich die Ausgabe so hinbekomme, wie
ich sie haben will. Von I*R gibt es einen kommerziellen C-Compiler für
die AVR, der bietet nicht so viele Möglichkeiten des Eingreifens.
Ich entwickele auch Programme für den 8051, den kommerziellen C-Compiler
von K**l kenne ich zur Genüge, den freien SDCC auch. Das ist Gegensatz
zu avr-gcc bei beiden eine echte Strafarbeit! Beispiel: Es gibt acht
Register plus DPH/DPL (bilden zusammen DPTR) doch obwohl noch fünf
Register frei sind, beginnt der Compiler die Funktionsparameter im RAM
anzuordnen und das ist meistens sehr bescheiden (128 oder 256 Bytes).
Viele Grüße,
Lars
Bei einem konkreten Optimierungsproblem hilft ein konkretes
nachvollziehbares(!) Beispiel mehr, als eine allgemein Anfrage über
gewisse Codierungstips. Letztere gibt es zwar, aber so herum ist das ein
Stochern im Nebel - und ersetzt Arbeit, die der Fragesteller selbst
leisten sollte, durch Arbeit die die Antworter leisten müssten.
Der gcc hat als nicht Spezial-8Bit Compiler sicherlich seine Schwächen,
wenn es um Optimierung von Byteoperationen geht. Der C Standard verlangt
nun mal, dass zuallererst alles in int gerechnet wird und nur wenn der
Compiler durch Datenflussanalyse beweisen kann, dass das selbe Ergebnis
erhalten wird, wenn er nicht full-blown 16-Bit rechnet, sondern in 8
Bit, können die Berechnungen für das High-Byte wegfallen.
Das ist sicherlich eine Problem, für das der gcc aber nicht sooo
wahnsinnig viel kann, wird ihm doch dieses Verhalten vom C-Standard aufs
Auge gedrückt. Im grossen und ganzen macht der gcc hier allerdings einen
guten Job.
Diese Tips aber
> Und weiterhin sollte auf Arrays nicht direkt, sondern über einen> Zeiger zugegriffen werden, dies erzeugt wirklich guten Code,> *ptr++ mag der avr-gcc am liebsten, entweder nutzt er dann ldd> oder ld ptr+.> Wenn man durch Zweierpotenzen teilen möchte, sollte man besser> einen Shift nutzen, der avr-gcc macht dies nicht selbst, sondern> ruft immer __udivmodhi auf oder wie diese Funktion heißt.
würde ich ganz gerne in Aktion sehen.
Speziell zweiteres ist so für mich absolut nicht nachvollziehbar. Dieses
unsinnige 'Ich bin schlauer als mein Compiler und ersetze
Multiplikationen/Divisionen durch Shifts' sollte per Strafe verboten
werden. Diese Optimierung ist eine von der allereinfachsten Sorte und
Compiler beherrschen sie seit über 30 Jahren. Ganz im Gegenteil:
Compiler haben normalerweise für viele kleine Integer ausgeklügelte
Shift/Add/Subtrakt Strategien mit.
Und die erste der beiden 'Optimierungen': Arrayzugriffe finden oft in
Schleifen statt. Man sollte sich sehr genau ansehen, was man da
schreibt. Speziell in Schleifen ist es eigentlich auch schon seit
vielen, vielen Jahren Standard, dass der Compiler die Transformation
Indexzugriff-> Pointerindizierung von alleine macht, wenn gewisse
Voraussetzungen vorliegen.
Ich lass mich allerdings auch gerne eines besseren belehren. Wie gesagt,
ich würde gerne Beispiele sehen, die die vorgeschlagenen händischen
Optimierungen untermauern.
Karl heinz Buchegger schrieb:> Ich lass mich allerdings auch gerne eines besseren belehren. Wie gesagt,> ich würde gerne Beispiele sehen, die die vorgeschlagenen händischen> Optimierungen untermauern.
Dem schließe ich mich an! Besonders eine Division durch 2^n, bei der der
gcc auch ne Division erzeugt, würde ich gerne mal sehen!
Karl heinz Buchegger schrieb:> Ich lass mich allerdings auch gerne eines besseren belehren. Wie gesagt,> ich würde gerne Beispiele sehen, die die vorgeschlagenen händischen> Optimierungen untermauern.
Meine Absicht war es eigentlich nicht, mich hier für meine Beobachtungen
rechtfertigen zu müssen... Aber gut, ein Beispiel habe ich noch
gefunden:
Was ist kürzer und damit auch schneller?
Wenn ich jetzt nicht auf die Schnelle einen Fehler beim Umstrukturieren
der Funktion gemacht habe, müsste der Code identisch sein.
Man sieht, dass der avr-gcc keine Zwischenergebnisse sichert. Er
berechnet auch jedesmal den Shift für den Vergleich mit der Variablen n
neu. Bloß durch Einfügen einiger Variablen spare ich somit 128(!) Bytes
ein...
Anderes Beispiel:
1
uint16_ttest=BringMirEinenInt();
2
uint8_ta=test/100;
3
uint8_tb=test%100;
Eine Division wäre korrekt. <__udivmodhi4> liefert gleichzeitig auch den
Rest mit, doch was macht avr-gcc? Richtig, er berechnet den ganzen Kram
nochmals um dieses Mal nicht das Ergebnis sondern den Rest zu nutzen...
Also schreibe ich:
Aber wieso muss ich das schreiben? Das macht doch so keinen Spaß...
Vermutlich werde ich jetzt als Antworten bekommen, dass mein Code
schlecht ist und dass ich besser dies oder das benutzen solle und das
avr-gcc wunderbar sei.
Dabei braucht ihr gar nicht so angegriffen zu sein, ich nutze avr-gcc
weil es dort die wenigsten Probleme dieser Art gibt! Ich bin doch
zufrieden wenn ich weiß, wie ich die Schwächen umgehen kann...
Ein Beispiel für die Divisionen bei 2^n konnte ich jetzt nicht finden,
eventuell ist dies tatsächlich schon verbessert. avr-gcc 4.3.3 und 4.5.0
machen Shifts und UND-Verknüpfungen...
Was GetFSymbols angeht: Das Stichwort hier heisst "Aliasing". Der
Compiler kann sich nicht sicher sein, dass die Arrays
symbols,values,entries alle vollständig disjunkt sind. Folglich kann er,
sobald ein Element darin modifiziert wird, nachfolgende Zugriffe auch
auf Elemente der anderen Arrays nicht wegoptimieren.
Siehe dazu die GCC Doku und das C99 Keyword "__restrict__".
jw schrieb:> Wo kann ich denn den WinAVR mit gcc 4.5.0 bekommen?> Der aktuelle WinAVR 20100110 bassiert auf gcc 4.3.3.
Den Quelltext von GCC 4.5.0 herunterladen, configure für den
Cross-Compiler "avr-gcc" angeben und kompilieren. Fertige Builds kenne
ich keine.
A. K. schrieb:> Was GetFSymbols angeht: Das Stichwort hier heisst "Aliasing". Der> Compiler kann sich nicht sicher sein, dass die Arrays> symbols,values,entries alle vollständig disjunkt sind. Folglich kann er,> sobald ein Element darin modifiziert wird, nachfolgende Zugriffe auch> auf Elemente der anderen Arrays nicht wegoptimieren.>> Siehe dazu die GCC Doku und das C99 Keyword "__restrict__".
Das mag ja sein, dass der Compiler hier auf Nummer sicher gehen will.
Das erklärt aber nicht, wieso er dreimal einen Shift berechnet, obwohl
dies nur einmal möglich wäre, nämlich für "entry" und für den
Bitvergleich mit "n" würde es reichen, nach jedem Durchgang einen "lsl"
einzufügen.
Und, das sehe ich ja jetzt erst, wieso wird mit 8 geteilt??? Kein Shift.
Ich denke, dass dies seit dreißig Jahren Standard sei... Auch beim
Modulo wird schon wieder die Schleife durchgerattert, er kennt scheinbar
"and rXX,0x07" genau so wenig wie die Zwischenspeicherung der
Ergebnisse.
Wenn ich jetzt noch damit anfange, den Arrays zig verschiedene Attribute
zu verpassen, wie "__restrict__", dann kann ich auch gleich meine
"Optimierungen", durchführen, oder?
Besser lesbar wird der Code durch die ganzen Sonderattribute sowieso
nicht.
Lars R. schrieb:> Eine Division wäre korrekt. <__udivmodhi4> liefert gleichzeitig auch den> Rest mit, doch was macht avr-gcc? Richtig, er berechnet den ganzen Kram> nochmals um dieses Mal nicht das Ergebnis sondern den Rest zu nutzen...
Yep, diese mögliche Optimierung berücksichtigt GCC nicht. Die beiden
Ausdrücke sind für ihn getrennte Operationen, die nur zufällig auf die
gleiche Runtime-Funktion hinauslaufen.
> Aber wieso muss ich das schreiben?
Weil kein Compiler der Welt absolut optimalen Code erzeugt. Er hat
bestimmte interne Schemata und diese Optimierung darin einzubauen dürfte
nicht ganz trivial sein.
Lars R. schrieb:> Und, das sehe ich ja jetzt erst, wieso wird mit 8 geteilt??? Kein Shift.
Probier mal -O1 oder -O2, könnte sich dadurch ändern.
Der Haken hier ist, dass eine vorzeichenbehaftete Division nicht
unmittelbar durch einen Shift ersetzt werden kann und der entsprechende
Ersatzcode zwar schneller ist als die Division, aber deutlich mehr Platz
benötigt. -Os ist nun einmal eine Optimierung auf kurzen nicht auf
schnellen Code.
Bei entries[n]/8 kann er ableiten, dass die Rechnung ohne Vorzeichen
durchgeführt werden darf, aber bei (entries[n]-1)/8 kann er das nicht
mehr.
>> Und, das sehe ich ja jetzt erst, wieso wird mit 8 geteilt??? Kein Shift.>> Probier mal -O1 oder -O2, könnte sich dadurch ändern.
Ändert nichts.
> Der Haken hier ist, dass eine vorzeichenbehaftete Division nicht> unmittelbar durch einen Shift ersetzt werden kann und der entsprechende> Ersatzcode zwar schneller ist als die Division, aber deutlich mehr Platz> benötigt. -Os ist nun einmal eine Optimierung auf kurzen nicht auf> schnellen Code.
Wie bitte?
Mein Code ist 128 Bytes kürzer als der, den der avr-gcc fabriziert, wenn
ich machen lasse, wie er will... Um die Geschwindigkeit geht es mir
nicht, sonst würde ich ja -O2 aktivieren.
(-O3 ist ja auch so eine Sache, der Code wird noch größer und dadurch
noch langsamer...)
> Bei entries[n]/8 kann er ableiten, dass die Rechnung ohne Vorzeichen> durchgeführt werden darf, aber bei (entries[n]-1)/8 kann er das nicht> mehr.
Der AVR kennt einen Assembler-Befehl namens "asr". Der macht genau
das... Und Array-Zugriffe mit negativen Zahlen kennt C doch gar nicht,
also müsste der Unsinn auffallen.
Dass kein Compiler perfekt ist, weiß ich. Ich weiß auch, dass dies eine
hochkomplexe Angelegenheit ist. Daher kritisiere ich ja die Macher von
avr-gcc auch gar nicht. Ich bin denen dankbar, dass diese einen so guten
Compiler kostenlos vertreiben, doch trotzdem will ich auch darauf
hinweisen können dürfen, wenn ich etwas entdecke, dass nicht dem
entspricht, wie ich es persönlich lösen würde, wenn ich Assembler selbst
schreiben würde.
Lars R. schrieb:> Das erklärt aber nicht, wieso er dreimal einen Shift berechnet, obwohl> dies nur einmal möglich wäre, nämlich für "entry" und für den> Bitvergleich mit "n" würde es reichen, nach jedem Durchgang einen "lsl"> einzufügen.
Es erklärt nicht, weshalb er innerhalb des Statements
Lars R. schrieb:> Wie bitte?>> Mein Code ist 128 Bytes kürzer als der, den der avr-gcc fabriziert, wenn> ich machen lasse, wie er will... Um die Geschwindigkeit geht es mir> nicht, sonst würde ich ja -O2 aktivieren.
Ich bezog mich auf an dieser Stelle ausdrücklich auf eine einzelne
Divisionsoperation, nicht auf das Gesamtprogramm.
Deine These war, dass er einen Ausdruck x/8 durch eine Shiftoperation
ersetzen sollte. Das kann er nur, wenn er weiss, das x nie negativ wird.
Wenn es negativ werden kann, was hier der Fall ist, dann wird der Code,
den er für /8 einsetzen muss, deutlich länger als der Aufruf der
Laufzeitfunktion. Folglich musste sich der Compiler an dieser Stelle für
die Laufzeitfunktion entscheiden.
Dass der Gesamtcode länger ist, hat nichts mit dieser Einzelentscheidung
zu tun.
> (-O3 ist ja auch so eine Sache, der Code wird noch größer und dadurch> noch langsamer...)
Ist bei AVR zwar oft so, aber grösser ist nicht zwangsläufig langsamer.
> Der AVR kennt einen Assembler-Befehl namens "asr". Der macht genau> das...
Nein.
-3 / 2 = -1;
-3 >> 1 = -2.
> Und Array-Zugriffe mit negativen Zahlen kennt C doch gar nicht,
In deinem Code ist weit und breit kein Array zu sehen. Nur lauter
Pointer. Und bei denen ist ein negativer Index das sehr wohl zulässig,
denn p[i] ist per Definition identisch mit *(p+i) (und folglich auch mit
i[p]). Wenn der Pointer mitten in ein Array zeigt, dann passt das
wunderbar.
Lars R. schrieb:> Der AVR kennt einen Assembler-Befehl namens "asr". Der macht genau> das...
Nein.
ASR macht keine signed-Division, sondern einen arithmetischen Shift
nach rechts.
Versuch's einfach mal mit (-1)/8
> erneut rechnet, denn durch symbols[...] = ... kann sich entries[...]> verändert haben.
Nun ja, wie man ihm das abgewöhnen kann, dass sich die Arrays eben nicht
überlappen, weiß ich ebenfalls nicht. Weder "*restrict" noch "*
__restrict__" führen zum Ziel:
Das mit den überlappenden Arrays ist sowieso unmöglich definiert. Will
man strcpy nutzen, um innerhalb eines sich überlappenden Bereichs etwas
zu unternehmen, kommt nur Müll raus.
Wenn diese Funktion von n - 1 bis 0 zählen würde und nicht von 0 bis n,
dann ginge es sowohl mit überlappenden als auch mit nicht überlappenden
Arrays. Aber dies ist genau so merkwürdig wie:
1
for(uint8_tn=10-1;n>0;n--);
Dies funktioniert mit avr-gcc nicht, da er die Abbruchbedingung
wegoptimiert... Also eine Endlosschleife erzeugt. Also muss man
schreiben:
1
for(uint8_tn=10-1;;n--)
2
if(!n)
3
break;
Lasse ich die erste Schleife aber durch einen C/C++-Compiler für die
PC-Welt laufen, wie den Microsoft Visual C++-Compiler, dann klappt es
anstandslos.
Wieso dies so ist weiß ich nicht. Vielleicht steht ja auch in
irgendeiner Norm, dass Schleifen nicht rückwärts zählen dürfen...
Gerade dies schätze ich an C ja so:
1
for(Node*n=&first;n!=NULL;n=&n->next);
In anderen Programmiersprachen wird eine Zahl getestet, hier wird ein
logischer Ausdruck getestet, vollste Freiheit!
Lars R. schrieb:> Dies funktioniert mit avr-gcc nicht, da er die Abbruchbedingung> wegoptimiert... Also eine Endlosschleife erzeugt. Also muss man> schreiben:
Ich kann mit nicht vorstellen, dass er bei
1
for(uint8_tn=10-1;n>0;n--);
die Abbruchbedingung wegoptimiert. Durchaus aber bei
1
for(uint8_tn=10-1;n>=0;n--);
denn n kann als uint8_t nicht negativ werden.
Es hindert dich aber niemand daran, das als
A. K. schrieb:>> Der AVR kennt einen Assembler-Befehl namens "asr". Der macht genau>> das...>> Nein.>> -3 / 2 = -1;> -3 >> 1 = -2.
Stimmt, da hatte ich unrecht. Ich habe mehr an die Bits gedacht, als an
die Bedeutung für die Zahlenwerte.
> In deinem Code ist weit und breit kein Array zu sehen. Nur lauter> Pointer. Und bei denen ist ein negativer Index das sehr wohl zulässig,> denn p[i] ist per Definition identisch mit *(p+i) (und folglich auch mit> i[p]). Wenn der Pointer mitten in ein Array zeigt, dann passt das> wunderbar.
Stimmt auch, da kann der Compiler nichts dafür. In Gedanken war ich ja
schon wieder beim Gesamtprojekt, wo die eigentlichen Daten in Arrays
liegen.
Es hätte ja aber auch sein können, dass man mit malloc usw. hantiert,
dann könnte man auch wieder keine Schlüsse ziehen usw.
> denn n kann als uint8_t nicht negativ werden.
Das würde aber auffallen, denn dann käme so etwas wie "Comparison is
always true". Ich aktiviere immer -Wall und -Wextra und noch ein paar
weitere Schalterchen. -Wlogical-ops ist glaube ich neu und -pedantic ist
auch immer aktiviert.
Lars R. schrieb:> Das mit den überlappenden Arrays ist sowieso unmöglich definiert. Will> man strcpy nutzen, um innerhalb eines sich überlappenden Bereichs etwas> zu unternehmen, kommt nur Müll raus.
Die Hilfe zu strcpy sagt dazu:
> The strcpy() function copies the string pointed to by src> (including the terminating `\0' character) to the array pointed to by> dest. The strings may not overlap, and the destination string dest must> be large enough to receive the copy.
Analoges gilt für memcpy. Es gibt aber memmove um überlappende Bereiche
zu kopieren.
Lars R. schrieb:> Allerdings weiß er nun wieder, dass man auch shiften kann:
logisch.
Jetzt hast du ihm ja auch den Hinweis gegeben, dass
[(uint8_t)(entries[n] - 1)
nicht negativ werden kann.
Dadurch braucht er die Funktionsaufrufe nicht mehr, dadurch werden dann
aber auch Register frei, die sonst für den Funktionsaufruf benutzt
werden müssten und dadurch hat er jetzt auch den Platz, um sich
Zwischenergebnisse in Register aufzuheben.
Bei mir siehts so aus:
Funktion, wie von dir gepostet: 444 Bytes
Funktion, / und % ersetzt 316 Bytes
Funktion, original mit cast 308 Bytes
(alleine der cast bringt also schon ein besseres Ergebnis, als das
Ersetzen von / und % durch >> und &)
Funktion, Pointer Variante 252 Bytes
Nur durch den Hinweis, dass das Ergebnis von entries[n] - 1 nicht
negativ werden kann, ist die Index Variante an die Pointer Variante
schon ganz schön rangekommen.
In einem geb ich dir allerdings recht (und das hat mich verblüfft). Der
gcc stellt sich hier beim Herausziehen des immer gleichen Ausdrucks
(entries[n] - 1) tatsächlich nicht sehr geschickt an. Da kann man ihm
tatsächlich helfen.
Johann L. schrieb:> Die Hilfe zu strcpy sagt dazu:>> [...]>> Analoges gilt für memcpy. Es gibt aber memmove um überlappende Bereiche> zu kopieren.
Das weiß ich ja alles.
Würde sich aber memcpy so wie memmove verhalten, wäre letzteres unnötig
und dennoch würde auch das funktionieren, was momentan mit memcpy
gemacht wird.
Lars R. schrieb:> Arrays. Aber dies ist genau so merkwürdig wie:>>
1
for(uint8_tn=10-1;n>0;n--);
>> Dies funktioniert mit avr-gcc nicht, da er die Abbruchbedingung> wegoptimiert... Also eine Endlosschleife erzeugt. Also muss man> schreiben:
?
Das klingt allerdings in der Tat nach einem heftigen Compiler-Bug, wenn
sich das bestätigen lässt.
Meiner (eine etwas ältere Version), macht das anstandslos
1
voidfoo()
2
{
3
7c:89e0ldir24,0x09;9
4
for(uint8_tn=10-1;n>0;n--)
5
i=n;
6
7e:80936000sts0x0060,r24
7
8
volatileuint8_ti;
9
10
voidfoo()
11
{
12
for(uint8_tn=10-1;n>0;n--)
13
82:8150subir24,0x01;1
14
84:e1f7brne.-8;0x7e<foo+0x2>
15
i=n;
16
}
17
86:0895ret
( i ist eine globale volatile uint8_t, damit der Compiler die Schleife
nicht überhaupt wegoptimiert. Man sieht auch dass er n komplett
eingespart hat und die Schleife gleich auf i aufsetzt)
Lars R. schrieb:
> Den Quelltext von GCC 4.5.0 herunterladen, configure für den> Cross-Compiler "avr-gcc" angeben und kompilieren. Fertige Builds kenne> ich keine.
wie kann ich es für windows machen?
könnte mich jemand helfen bzw. wo finde sone Einleitung wie ich es für
windows kompilieren kann? ober besser gesagt wie kann ich GCC 4.5.0 in
WinAVR 20100110 integrieren?
A. K. schrieb:>> Und Array-Zugriffe mit negativen Zahlen kennt C doch gar nicht,>> In deinem Code ist weit und breit kein Array zu sehen. Nur lauter> Pointer. Und bei denen ist ein negativer Index das sehr wohl zulässig,> denn p[i] ist per Definition identisch mit *(p+i) (und folglich auch mit> i[p]). Wenn der Pointer mitten in ein Array zeigt, dann passt das> wunderbar.
Auch bei Feldern hat der Compiler nichts gegen negative Indices
einzuwenden.
Ob man das wirklich will, steht auf einem anderen Blatt, aber es ist
sehr wohl zulässig.
Klaus Wachtler schrieb:> Auch bei Feldern hat der Compiler nichts gegen negative Indices> einzuwenden.
Bei a[N] sind aber nur Indizes 0..N definiert - wenn a[] ein echtes
Array ist (nicht nur ein derart deklarierter Parameter). Damit wäre es
prinzipiell zulässig, aus a[i/8] zu schliessen, dass man i ohne
Vorzeichnen rechnen darf.
Eine Ersetzung erkennt der gcc offenbar nicht, die du uns
stillschweigend untergjubelt hast :-)
for( n = ... ) {
if( value & ( 1 << n ) )
...
}
Hier schreckt der Compiler davor zurück, value zu modifizieren, so wie
du das gemacht hast. Vielleicht erbarmt sich mal wer und baut eine
entsprechende Optimierung ein. Aber bis dahin gilt die Devise: Finger
weg von Shiften mit variablen Bitzahlen
Ziehe ich das nach:
1
for(unsignedcharn=0;n<8;n++)
2
{
3
unsignedcharentry=entries[n]-1;
4
5
if(entry&&entry<=18)
6
{
7
symbols[entry/8]|=(1<<(entry%8));
8
if(value&0x01)
9
values[entry/8]|=(1<<(entry%8));
10
}
11
value>>=1;
12
}
bin ich bei 258 Bytes und damit praktisch bei deiner hochoptimierten
Pointer-Lösung. Und das ohne das ich den Code grossartig modifiziert
oder unkenntlich gemacht hätte. Im Grunde sieht der Code (fast) immer
noch genauso aus, wie die Urversion, was man von der Pointer-Variante
nicht behaupten kann.
Karl heinz Buchegger schrieb:> Eine Ersetzung erkennt der gcc offenbar nicht, die du uns> stillschweigend untergjubelt hast :-)
Doch, dies hatte ich bereits in meinem ersten Beitrag erwähnt, auch wenn
ich dort anstelle von ">>= 1" aus Versehen "<= 1" geschrieben habe; in
der Eile macht man oft solche Fehler. Aber für den Forumsbeitrag war ich
zugegeben nicht so bei der Sache, da ich noch etwas "produktiveres"
nebenbei gemacht habe... ;-)
Du hast es jedenfalls geschafft, meiner Lösung sehr nahe zu kommen, auch
sieht deine Lösung, zugegeben, besser aus als meine Pointer-Lösung. Aber
wir nutzen ja C, dort gibt es ja die schönen Pointer, also wieso nicht
nutzen?
Was ich aber eigentlich schon ganz zu Beginn deutlich machen wollte, war
doch einfach nur, dass man sich das Assembler-Listing ansehen muss,
wenn man schlanken Code haben will. Alle Lösungen hätten zwar
funktioniert, manche aber ewig gedauert oder wären fast doppelt so groß
geworden...
Es ist einfach viel Handarbeit gefragt, da kann einem auch der
C-Compiler nicht helfen. Und im Zweifel traue ich ihm dann auch durchaus
einmal viel weniger zu, als er vielleicht doch noch zu leisten im Stande
gewesen wäre.
Wenn der Quellcode von GCC nicht so ein abschreckendes Beispiel wäre,
wie ein Programm möglichst nicht sein sollte, wäre es ja auch möglich,
selbst gewisse Änderungen vorzunehmen. Aber alleine das einmalige
Compilieren des Compilers dauert länger als eine Stunde auf meinem Apple
Power Mac...
Da vergeht mir zumindest die Lust am experimentieren, aber bei den
Unix-Programmen scheint dies so üblich zu sein dank autoconf und wie das
alles heißt, ich bin froh, dass man zum Schluss dennoch die Wahl hat,
welches OS man einsetzt.
Und: Als ich es zum ersten Mal geschafft habe GCC selbst zu compilieren
war ich richtig stolz! Ehrlich.
Lars R. schrieb:> Was ich aber eigentlich schon ganz zu Beginn deutlich machen wollte, war> doch einfach nur, dass man sich das Assembler-Listing ansehen muss,> wenn man schlanken Code haben will.
Ja, das ist manchmal nützlich.
> selbst gewisse Änderungen vorzunehmen. Aber alleine das einmalige> Compilieren des Compilers dauert länger als eine Stunde auf meinem Apple> Power Mac...
Du musst ihn ja nicht jedesmal komplett übersetzen. Wenn dran rumspielt
wird meist nur sehr wenig neu übersetzt.
> selbst gewisse Änderungen vorzunehmen. Aber alleine das einmalige> Compilieren des Compilers dauert länger als eine Stunde auf meinem Apple> Power Mac...
Blöde Frage als Aussenstehender: Gibt es dafür kein funktionierendes
make script? Gut ums linken kommst Du nicht rum, das kann je nachdem
auch noch dauern aber die compiles sollten dann ja kein Problem mehr
sein sofern Du nicht in irgendwelchen global benutzten Headern spielst.
U.R. Schmitt schrieb:> Blöde Frage als Aussenstehender: Gibt es dafür kein funktionierendes> make script?
Doch, natürlich. Aber wenn man sich vom ersten Mal so abschrecken lässt,
dass man ein zweites Mal erst garnicht probiert...
Lars R. schrieb:> Karl heinz Buchegger schrieb:>> Eine Ersetzung erkennt der gcc offenbar nicht, die du uns>> stillschweigend untergjubelt hast :-)>> Doch, dies hatte ich bereits in meinem ersten Beitrag erwähnt, auch wenn> ich dort anstelle von ">>= 1" aus Versehen "<= 1" geschrieben habe;
Entschuldigung.
War mir entfallen.
> in> der Eile macht man oft solche Fehler.
Du sagst es
> Du hast es jedenfalls geschafft, meiner Lösung sehr nahe zu kommen, auch> sieht deine Lösung, zugegeben, besser aus als meine Pointer-Lösung. Aber> wir nutzen ja C, dort gibt es ja die schönen Pointer, also wieso nicht> nutzen?
Hast schon recht.
Mir gehts um die Prämisse: Nur wer Divisionen durch Shifts ersetzt,
erzeugt gut optimierten Code (oder so ähnlich).
Wie sich gezeigt hat, stimmt das einfach nicht. Compiler ersetzen das
schon selber. Nur: Man muss natürlich die C-Regeln kennen und wissen,
was den Compiler daran hindern kann. Da gibt es natürlich versteckte
Fallen wo du dem Compiler Wissen vorenthältst, das du selbst beim
Optimieren aber benutzt hast.
> Was ich aber eigentlich schon ganz zu Beginn deutlich machen wollte, war> doch einfach nur, dass man sich das Assembler-Listing ansehen muss,> wenn man schlanken Code haben will.
Volle Zustimmung.
Auf der anderen Seite sind die Code Modifikationen in meinem letzten
Posting von der Natur, die ich sowieso jedem nahelegen würde:
Klaren Code erhält man nicht dadurch, dass man denselben Sub-Ausdruck
wieder und immer wieder benutzt. Durch das Vorziehen in eine Variable
suggeriert man dem Leser auch: Das ist immer derselbe Ausdruck. In der
ausgeschriebenen Form muss man erst die auf den ersten Blick ähnlich
aussehenden Teilausdrücke vergleichen um festzustellen "Sind tatsächlich
alle gleich"
Das ist also eine naheliegende Modifikation, die jeder der sauberen Code
abliefern will von sich aus macht.
OK. die andere ist vieleicht nicht so naheliegend. Geb ich zu.
Aber die Quintessenz "Schreib Code so, dass er sauber ist und überlass
den Rest dem Compiler" hat wieder mal gezeigt, dass sie gar keine so
schlechten Ergebnisse bringt.
Dazu gehört natürlich auch
die Sprache auch in den Details und Feinheiten lernen
darüber nachdenken was man tut
sich mit einmal hingeschriebenem Code nicht zufrieden geben, sondern
sich auch mal zurücklehnen und sich überlegen "wie kann ich mein
Machwerk verständlicher formulieren". Da gehts noch gar nicht um
Optimierung, sondern um generelle Code-Richtlinien.
Ich gebe zu: Ich hätte auf Anhieb auch nicht gesehen, dass der Compiler
hier keinen Shift benutzen wird. Aber nach einem Blick ins
Assembler-Listing und ein wenig nachdenken war klar, warum das so ist.
> Es ist einfach viel Handarbeit gefragt, da kann einem auch der> C-Compiler nicht helfen. Und im Zweifel traue ich ihm dann auch durchaus> einmal viel weniger zu, als er vielleicht doch noch zu leisten im Stande> gewesen wäre.
Das ist dein gutes Recht.
Mir gehts auch hauptsächlich um diese pauschalen 'Clever-Optimierungen'
wie eben das Ersetzen von Multiplikationen/Divisionen durch Shifts. In
Wirklichkeit (wenn man die C-Regeln anwendet) haben sie keine
Berechtigung. Ein Programmierer wird heutzutage nicht mehr dadurch zum
Hacker (in seiner ursprünglichen Wortbedeutung), weil er derartige
Tricks kennt (die jeder bessere Compiler auch kennt, wenn man ihn nur
lässt)
A. K. schrieb:> Doch, natürlich. Aber wenn man sich vom ersten Mal so abschrecken lässt,> dass man ein zweites Mal erst garnicht probiert...
Auch wenn ich Gefahr laufe, mich unbeliebt zu machen, macht es dir Spaß,
Anderen das Wort im Munde herum zu drehen?
Abschrecken lasse ich mich von so etwas nicht, sonst würde ich mir nicht
die Mühe machen, avr-gcc selbst zu compilieren. Aber ich gebe zu, dass
ich es nicht machen würde, wenn beispielsweise jedesmal alle Targets
auch als Binary zur Verfügung gestellt würden.
Man muss MPC erst einmal kompilieren, dann für LTO bei GCC 4.5.0 libelf,
dann dies und dann auch noch das. Dann kommen kryptische Fehlermeldungen
beim configure-Script, weil irgendeine Library nicht gefunden wurde,
also wieder nach dem passenden Parameter suchen, damit man den Pfad
direkt übergeben kann usw.
Nicht zuletzt erschwert sich die ganze Situation auch noch dadurch, dass
man einen unter Windows lauffähigen Compiler haben will usw. Dann gibt
es manchmal Probleme mit dem Backslash, weil die Linux-Tools den
"normalen" Slash haben wollen, also braucht man eine Emulation wie MSYS,
MinGW muss auch erst einmal zusammen gesucht werden.
Dann fängt erst das Abenteuer an, sobald man "make" eingibt... Tausende
Warnungen, dann ewiglanges Linken ohne Ausgabe auf der Konsole und dann
irgendwann bekommt man, wenn man Glück hat, einen funktionsfähigen
Compiler - oder aber, wenn man eben kein Glück hat, eine Fehlermeldung,
dass irgendein wichtiger Test kein okay gibt. Dann fängt man wieder bei
configure an...
Daher vermeide ich es, viel an den Sachen herum zu spielen, dass sollen
die machen, die Unix tagtäglich nutzen und sich wirklich auskennen. Ich
kenne mich mit Visual Studio und XCode aus, da geht es einfacher.
Karl heinz Buchegger schrieb:> In einem geb ich dir allerdings recht (und das hat mich verblüfft). Der> gcc stellt sich hier beim Herausziehen des immer gleichen Ausdrucks> (entries[n] - 1) tatsächlich nicht sehr geschickt an. Da kann man ihm> tatsächlich helfen.
Auch hier lautet das Zauberwort wieder Aliasing. Der Compiler kann nicht
wissen, ob durch die Zuweisung an symbols[...] nicht vielleicht auch
entries[n] verändert wurde. Innerhalb der beiden Statements berechnet
er (entries[n]-1) in der Tat nur jeweils einmal, obwohl es zweimal
vorkommt.
Lars R. schrieb:> Würde sich aber memcpy so wie memmove verhalten, wäre letzteres unnötig> und dennoch würde auch das funktionieren, was momentan mit memcpy> gemacht wird.
Nur ist memmove() ineffizienter als memcpy(), da erstmal eine
Fallunterscheidung auf die verschiedenen Überlappungsmöglichkeiten nötig
ist, um dann je nachdem vorwärts oder rückwärts zu kopieren. Auch wenn
der eine Vergleich von der Laufzeit her gegenüber der eigentlichen
Kopiererei meistens eher klein sein dürfte, wird die Codegrösse (bei
Inlining der Funktion) auf den meisten Architekturen mal eben mehr oder
weniger verdoppelt.
Andreas
Lars R. schrieb:> Nun ja, wie man ihm das abgewöhnen kann, dass sich die Arrays eben nicht> überlappen, weiß ich ebenfalls nicht. Weder "*restrict" noch "*> __restrict__" führen zum Ziel:
Ich hab' nochmal ein bisschen gegraben und rumexperimentiert.
Der Haken an der Sache ist hier, dass offenbar im GCC-Optimizer irgendwo
die Regel drinsteckt "char darf immer alles aliasen" (und uint8_t ist
für den GCC intern weitgehend dasselbe wie char). Vermutlich historisch
bedingt, da in den Anfangszeiten von C "char *" ja häufig dort benutzt
wurde, wo heute "void *" benutzt wird. Siehe dazu auch die Dokumentation
der Option "-fstrict-aliasing".
Wenn du in dem Code mal alle Typen durch "uint16_t" ersetzt, dann siehst
du einen Unterschied zwischen mit und ohne "__restrict__" (bei mir 228
vs. 262 Bytes).
Auf Architekturen mit 16 und mehr Bits Wortbreite ist der Einfluss der
genannten Regel auf die Optimierung vermutlich eher gering, deshalb hat
sich bis jetzt niemand die Mühe gemacht, die Einschränkung zu beheben.
Andreas
Andreas Ferber schrieb:> Lars R. schrieb:>> Nun ja, wie man ihm das abgewöhnen kann, dass sich die Arrays eben nicht>> überlappen, weiß ich ebenfalls nicht. Weder "*restrict" noch "*>> __restrict__" führen zum Ziel:>> Ich hab' nochmal ein bisschen gegraben und rumexperimentiert.>> Der Haken an der Sache ist hier, dass offenbar im GCC-Optimizer irgendwo> die Regel drinsteckt "char darf immer alles aliasen"
Ja, und das ist so wegen der C-Spec.
> (und uint8_t ist> für den GCC intern weitgehend dasselbe wie char). Vermutlich historisch> bedingt, da in den Anfangszeiten von C "char *" ja häufig dort benutzt> wurde, wo heute "void *" benutzt wird. Siehe dazu auch die Dokumentation> der Option "-fstrict-aliasing".
GCC führt Alias-Analysen durch, allerdings sind die (noch) nicht voll
durchgezogen, weil das nicht so ganz trivial ist und auch recht
resourcenhungrig.
Johann L. schrieb:>> Der Haken an der Sache ist hier, dass offenbar im GCC-Optimizer irgendwo>> die Regel drinsteckt "char darf immer alles aliasen"> Ja, und das ist so wegen der C-Spec.
Aber nicht wenn die fraglichen Pointer mit restrict qualifiziert sind
(oder auf derartigen Pointern basieren) und über mindestens einen davon
schreibend zugegriffen wird. GCC geht aber trotzdem davon aus, dass sie
aliasen können.
> GCC führt Alias-Analysen durch, allerdings sind die (noch) nicht voll> durchgezogen, weil das nicht so ganz trivial ist und auch recht> resourcenhungrig.
Hier wäre aber bei weitem keine volle Analyse nötig, es geht ja gerade
um einen sehr einfachen Fall, wo schon der Standard selbst sagt, dass
der Compiler einfach davon ausgehen darf, dass kein Aliasing vorliegt.
Es gilt dann noch abgeleitete Pointer zu berücksichtigen, das sollte
aber in der internen Tree-Repräsentierung des GCC (die fraglichen
Optimierungen finden vor dem Wechsel zur RTL statt) noch relativ einfach
hinzubekommen sein. Nur ist die Bedeutung für Nicht-8Bit-Architekturen
eben eher gering, deshalb macht es keiner.
Andreas
Andreas Ferber schrieb:> [...] um einen sehr einfachen Fall, [...]sagt, dass
Merke: in GCC ist nichts einfach. Weder der Build-Prozess, noch durch
die Quellen durchzusteigen noch Patches einfliessen zu lassen, noch
Patches zu verifizieren, noch...
Klaus schrieb:> [...] Bei dem was du da schreibst, hast du entweder die Optimierung> nicht an, oder beziehst dein wissen aus einer 15 Jahre alten gcc> Version.
Selbst vor 15 Jahren hat der gcc schon Multiplikationen/Divisionen von
Zweierpotenzen durch Shifts ersetzt.
Gruß,
Frank, der den gcc schon seit Mitte der 80er kennt
hi,
einige Tips hier konnte ich Anwenden und meinen Code deutlisch schlanker
machen. Optimierung -s habe ich selbstverständlich an!
Das Modulo-"Macro" habe ich mir gleich mal in meine Macrosammlung
gepackt
vielen dank :-)
@ Frank M. (ukw) Benutzerseite
>Selbst vor 15 Jahren hat der gcc schon Multiplikationen/Divisionen von>Zweierpotenzen durch Shifts ersetzt.
Wirklich? Der GCC allgemein vielleicht, der AVR-GCC bisweilen nicht.
1
intmul_2(inta){
2
returna*2;
3
}
4
5
intdiv_2(inta){
6
returna/2;
7
}
8
9
intmain(void){
10
11
}
Daraus wird, siehe Anhang.
Multiplikation durch ADD ersetzt, OK, Division als normale Funktion,
also durchgefallen.
MFG
Falk
Falk Brunner schrieb:> int mul_2 (int a) {> return a*2;> }>> int div_2 (int a) {> return a/2;> }> Multiplikation durch ADD ersetzt, OK, Division als normale Funktion,> also durchgefallen.
Es handelt sich um signed integers. Der Compiler verhält sich völlig
korrekt.
@ Michael Buesch (mb_)
>Es handelt sich um signed integers. Der Compiler verhält sich völlig>korrekt.
Hmm, stimmt 8-0. Mit unsigned passt das, siehe Anhang.