Wie optimiert man Systematisch (AVR GCC)

In dem du das hier durchgehst:

AVR-GCC-Codeoptimierung

Ganz wichtig ist, immer nur kleine Schritte umzusetzen. Dann kompilieren 
und Codegröße checken.
Dann führst du dein Programm aus. Das macht natürlich nur dann Sinn, 
wenn du in deinem Programm die Abarbeitungszeit messen und ausgeben 
kannst. Schließlich brauchst du Werte, die du vergleichen kannst.

Optimieren ist eine 'schwarze Kunst'

Das einfachste ist es, sich zunächst mal die Datentypen der beteiligten 
Variablen anzusehen. Muss es ein 16 Bit int sein oder reichen 8 Bit?

Gibt es Tests (Bedingungen in if's), die sich gegenseitig abdecken?

Kann man die alte Regel 'Space for Time' nutzbringend anwenden? Sowohl
in die eine Richtung als auch in die andere.

Ehe man dann weiter macht auf relativ niedriger Ebene zu optimieren:
Zurücklehen. Die Frage lautet: Ist mein algorithmisches Verfahren 
generell gut geeignet? Gibt es Alternativen? Was würden die bringen?

Gerade bei letzterem holt man oft die meiste Zeit raus: Optimieren durch 
Einsatz der grauen Zellen und kritischer Betrachtung des verwendeten 
Algorithmuses.

Assembler-Listing ansehen
Welche Codeteile sehen im Assembler Code so aus, als ob sie vom Compiler 
sehr aufwändig implementiert werden. Dann darüber nachdenken warum das 
so ist, welche (möglicherweise obskure) C Regel ist dafür 
verantwortlich, dass der Compiler nicht so optimieren kann, wie ich mir 
das vorstelle. Hatten wir letztens hier im Forum: Der Compiler konnte 
eine Division nicht durch Schiebeoperationen ersetzen, weil er nicht 
davon ausgehen konnte das die beteilgten Zahlen immer positiv sind. Ein 
entsprechender Hinweis (mit einem zusätzlichen unsigned) ermöglichte 
dann die Optimierung.

Wenn auf Speicher optimiert werden muss:
bei SRAM Knappheit: kann ich Strings sinnvollerweise aus dem SRAM ins 
Flash verbannen? Kann ich es mir leisten mehere Flag-Variablen in ein 
Byte zusammenzufassen, auch wenn dann die Zugriffe mglw. etwas langsamer 
werden.


Dir obersten Regeln in der Optimierung lauten:
"Premature optimization is the root of all evil"
"Optimization: Don't do it!"
"Optimization: Don't do it yet!"

Auch wichtig bei Optimierungen: Identifiziere erst mal ob du überhaupt 
ein Problem hast, welches Optimierungsbedarf erfordert.
Auf einem µC ist das zwar nicht ganz so krass, aber man geht davon aus, 
das rund 90% der Laufzeit eines Programmes von lediglich nur 10% Code 
hervorgerufen werden. Beim Optimieren ist es daher wichtig, diese 10% zu 
identifizieren. Dort bringt Optimieren was. Was jedoch nichts bringt, 
das ist eine Funktion um den Faktor 10 schneller zu machen, die von 1 
Minute Programmlaufzeit lediglich 1 Sekunde verbraucht. Die 
Programmlaufzeit sinkt dann von 60 Sekunden auf 59.1 Sekunden. Das sind 
gerade mal 1.5% Laufzeitgewinn. Der Aufwand, die Funktion um einen 
Faktor 10 schneller zu machen ist aber meistens beträchtlich! Kann ich 
aber den Code, der für die 59 Sekunden verantwortlich ist um einen 
Faktor 10 schneller machen, dann sinkt die Gesamtlaufzeit von 60 
Sekunden auf 6.9 Sekunden. Dort bringt Optimieren augenscheinlich viel 
mehr!

Lord Ziu schrieb:
> In dem du das hier durchgehst:
>
> AVR-GCC-Codeoptimierung

Hat eigentlich schon mal wer kontrolliert, welche der Tips in diesem 
Artikel mit dem aktuellen GCC noch Gültigkeit haben.

Ein paar dieser Optimierungen erscheinen da sehr zweifelhaft.

Fortgeschrittener Anfänger schrieb:
> Ok, soweit ist mir klar, das der erste schritt der Optimierung beim
> schreiben des Programms anfängt, z.B. wie in dem von Lord Ziu
> angehängten Link beschrieben, statt for schleifen auf do - while
> schleifen umzusteigen.

Gerade diesen Tip wage ich massiv in Frage zu stellen!

Solche Sachen musst du immer mit deinem aktuellen Compiler ausprobieren! 
Und in der nächsten Compilerversion kann sich das alles wieder umdrehen.


Generell solltest du davon ausgehen:
"Die Compilerbauer sind keine Trotteln. Die verstehen von Optimierungen 
viel mehr, als ich das je könnte. Also überlass ich solche Low-Level 
Optimierungen lieber dem Compiler. Maximal seh ich mir an, ob ich nicht 
im C-Code dem Compiler den Weg für eine Optimierung verbaut habe, indem 
ich zb ungünstige Datentypen benutzt habe."

(Der Tip mit der Multiplikation fällt zb auch in diese Kategorie. Ich 
wette, wenn man sich den Code ansieht den der Autor beschreibt, dann 
findet man im C Code die Ursache, warum der Compiler die Multiplikation 
nicht selbst durch Schieben ersetzen konnte. Compiler machen gerade 
solche Ersetzungen seit Jahrzehnten!)

> Aber wie geht man vor wenn das Kind schon in den Brunnen gefallen ist.
> Die routinen die zu langsam sind findet man durch austesten raus.
> Aber wie findet man die grossen Speicherfresser?

Punkt 1:
map File studieren

Punkt 2:
Hilfsmittel einkaufen oder selber bauen. Es gilt rauszufinden, welche 
Funktion massig Stack durch lokale Variablen verbraucht. Stacktracer 
können das. Wenn man keinen hat, dann muss man sich eben selber einen 
bauen, indem man den Stackpointer mitlogt.
Zur Not einen Code-Review machen: Alle Funktionen optisch durchgehen und 
die identifizieren, die viele Variablen anlegen. Dann die 
Aufrufhierarchie der Funktion feststellen: Wirken sich die vielen 
Variablen überhaupt aus oder ensteht mein Problem durch eine tiefe 
Funktionsaufrufhierarchie, bei der zwar wenige Variablen pro Funktion im 
Spiel sind, aber die Menge der ineinandergeschachtelten Aufrufe 'das 
Kraut fett macht'

Fortgeschrittener Anfänger schrieb:

> Im MAP File finde ich es nicht, das scheint aber ein "Tomaten auf den
> Augen" Problem zu sein.

Das seh ich auch so.
Denn im Map File ist das (indirekt) aufgeschlüsselt.
In der .text section sind alle Funktionen mit ihren Startadressen 
drinnen.


Wenn du Probleme mit dem Flash hast und viele kurze Funktionen, könnte 
es etwas bringen, wenn du dem Compiler das inlinen von Funktionen 
verbietest. (Space for Time)

Fortgeschrittener Anfänger schrieb:

> Aber wie geht man vor wenn das Kind schon in den Brunnen gefallen ist.

Hast du ein konkretes Problem?

Wenn ja, dann stells mal rein.
Gerade bei eigenem Code ist man oft betriebsblind.

Fortgeschrittener Anfänger schrieb:

> was bedeutet "inlinen von Funktionen" ?

Das der Compiler den Aufruf einer Funktion durch den Funktionsrumpf 
ersetzt

1

static int foo( int i )

2

{

3

  return 2 + i;

4

}

5

6

int main()

7

{

8

  int j;

9

10

  j = foo( 5 );

11

}

Ein perfekter Funktionsaufruf.
Nur dauert das Aufrufen der Funktion, inklusive Register sichern und 
wiederherstellen etc. wesentlich länger als die eigentliche Abarbeitung 
der Funktion.
Der Compiler wird so eine Funktion inlinen, d.h. er setzt den 
Funktionsrumpf an der Stelle des Funktionsaufrufs ein.
Er compiliert also das hier:

1

int main()

2

{

3

  int j;

4

5

  {

6

    j = 2 + i;

7

  }

8

}

und vereinfacht dadurch nebenbei den Code.

Jetzt kann aber auch das hier passieren:

* die Funktion hat einen gewissen Speicherverbrauch
  der Funktionsaufruf in main auch
  mit jedem zusätzlichen Aufruf dieser Funktion steigt der
  komplette Speicherverbrauch nur um das bischen was auf
  Aufruferseite notwendig ist um die Funktion aufzurufen

* wird geinlined, so findet zwar kein Funktionsaufruf mehr statt
  der Code wird daher eingespart.
  Dafür taucht aber der Code der Funktion an jedem Funktionsaufruf
  erneut auf. Und zwar jedes mal.

Wenn daher der Funktionskörper länger ist, als das was der Compiler 
benötigt um die Funktion aufrufen zu können, dann steigt mit jedem 
'Aufruf' der Funktion der Speicherverbrauch um die Differenz.

Fortgeschrittener Anfänger schrieb:

> Wie gewöhnt man das dem Compiler ab? Ich würde gerne Testweise mal sehen
> was sich an der Codegrösse tut. Ist das Inlining standartmässig
> aktiviert?


http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

Einzubauen im AVR-Studio im "Project / Configuration Options" Dialog.
Du willst  -fno-inline


PS: es heißt standard  mit einem weichen d. Eine Standarte (mit hartem 
t) ist etwas ganz anderes.

Karl heinz Buchegger schrieb:
> Lord Ziu schrieb:
>> In dem du das hier durchgehst:
>>
>> AVR-GCC-Codeoptimierung
>
> Hat eigentlich schon mal wer kontrolliert, welche der Tips in diesem
> Artikel mit dem aktuellen GCC noch Gültigkeit haben.

Einige davon hatten noch nie Gültigkeit, da sie auf einer Atmel-AppNote 
für IAR basieren.

Andere sind schlichtweg Unsinn, zB "register volatile". GCC hat intern 
überhaupt nicht die Möglichkeit, ein Register als volatile zu 
definieren.

Aus gcc/rtl.h

1

  /* 1 in a MEM or ASM_OPERANDS expression if the memory reference is volatile.

2

     1 in an INSN, CALL_INSN, JUMP_INSN, CODE_LABEL, BARRIER, or NOTE

3

     if it has been deleted.

4

     1 in a REG expression if corresponds to a variable declared by the user,

5

     0 for an internally generated temporary.

6

     1 in a SUBREG with a negative value.

7

     1 in a LABEL_REF, REG_LABEL_TARGET or REG_LABEL_OPERAND note for a

8

     non-local label.

9

     In a SYMBOL_REF, this flag is used for machine-specific purposes.  */

10

  unsigned int volatil : 1;

Tatsächlich hab ich schon beobachtet, daß in einer Schleife ein globales 
Register wegoptimiert wurde. gcc 4 benutzt lediglich life info zur 
Ermittlung der Lebensdauer etc.

http://gcc.gnu.org/PR17336
http://gcc.gnu.org/PR34351

Globale Register können durchaus gewinnbringend eingesetzt werden, 
allerdings ändert man damit das ABI. Ich verwende zB globale Register in 
meinem Scope-Uhr Projekt, um x/y-Koordinaten zu transferieren.

Um globale Register korrekt einzusetzen ist einiges an Wissen über den 
Compiler nötig, und es ist vor allem nötig, zu verstehen, was "global" 
in letzter Konsequenz bedeutet. Für den unbedarften Anwender, der 
globale Register handhabt wie globale (volatile) Variablen, ist die 
Chance, daß er sich selbst aufs Kreuz legt, nicht gerade klein.

http://www.roboternetz.de/phpBB2/viewtopic.php?p=506013#506013

Auch -min8 bewirkt eine ABI-Änderung und wird zudem in neueren 
gcc-Versionen nicht weiter gepflegt. D.h. wenn's einen Fehler gibt, wird 
das eher dadurch behoben werden, daß -mint8 ganz rausfliegt, als daß der 
Bug gefixt wird.

Beitrag "Re: Windows-Build von avr-gcc 4.5.0"

Thema "Statische (globale) Variablen in ein struct sammeln".

Damit kann deutlich Platz gespart werden, wenn das Umfeld stimmt. Es ist 
aber ebensogut möglich, daß man sich damit selbst ins Bein schiesst.

Wieder ist Kenntnis über die Arbeitsweise/Vorliebe des Verwendeten 
Compilers notwendig.

Als Checkliste mal dieses:

(I)
Über die verwendeten Algorithmen/Datenstrukturen etc. meditieren, s.o.

(II)
Sich mit ABI-konformen Compiler-Optionen vertraut machen, zb -Os, -O2, 
-fno-inline-small-function, -finline-limit=, -fno-split-wide-types

(III)
Sich mit der Arbeitsweise des Compilers vertraut machen, d.h.: wie sieht 
der Code aus, den er erzeugt. Wie gut ist er am angenommenen Optimum und 
welche Performance-Verluste sind akzeptabel weil der Verwendung eines 
Compilers geschuldet? Um die Codegüte beurteilen zu können dauert es ne 
Weile.

(IV)
Was kann an der Quelle ABI-konform geändert werden, zB Inlining, 
Verwendung von Attributen (const, pure, noreturn, always_inline), 
Verwendung von stdint.h.

(V)
Für welche Funktionen legt der Compiler einen Frame an?
Welche Variablen leben im Frame und warum? Frames sind teuer, ebenso die 
Verwendung von Variablen, die darin leben: Es wird über den FP 
zugegriffen, man hal also kein Y-Reg mehr für eigene Varablen und damit 
ein wertvolles Pointer-Register weniger. Zur Verwendung müssen die 
Variablen geladen/gespeichert werden, der Frame muss auf-/abgebaut 
werden, etc.

(VI)
Wie kann die Quelle geändert werden, so daß sie besseren Code ergibt? 
Eine Quelle so hinzuschreiben, daß sie für einen bestimmten Compiler 
schmackhaft ist, ist nicht wünschenswert. Der Compiler sollte die Quelle 
gut übersetzen, nicht die Quelle sich gut an den Compiler anpassen. 
Insbesondere hat man bei Portierungen hier seinen Spaß...

(VII)
Gibt es Schalter, die einen Einfluss auf die Codegüte haben, aber das 
ABI verändert? (-funsigned-bitfields, -mint8, ...) Sind diese notwendig, 
erwünscht, unerwünscht, ...?

(VIII) Welche Features können eingesetzt werden, die stark Hardware- und 
Compilerabhängig sind und evtl. nicht ABI-konform sind. Hierzu gehören
-- (Inline) Assembler
-- Globale Register
-- Verwendung von GPRs wie GPIOR0 für globale Flags
-- Verwendung transparenter Funktionen
Bei diesem Punkt ist man i.w. auf sich selbst gestellt, weil die Infos, 
die im Netz zu finden sind, nicht selten inkorrekt, unvollständig oder 
missverständlich sind. s.o.

Weiters sollte man folgende Punkte gegeneinander abwägen:

-- Codeverbrauch
-- Datenverbrauch. Statisch/Stack/Heap
-- Mittlere/maximale Laufzeit
-- Entwicklungszeit
-- Portabilität (Compiler, Hardware, ...)
-- Verständlichkeit der Quelle
-- ABI-Konformität

Generall dank ich, daß viele Optimierungen "Angst-Optimierungen" sind, 
die nicht wirklich nötig sind. Die Gefahr mit Optimierungen ist, den 
Code tot zu optimieren. Ich muss gestehen, daß ich selbst oft (zumindest 
in privaten Projekten) in die Optimierungs-Falle trete und optimiere, wo 
es nicht wirklich nötig ist, was zu Code führt, der schwerer wartbar 
ist.

Fortgeschrittener Anfänger schrieb:
> Nö, ein konkretes Problem habe ich nicht, aber es passiert mir immer
> wieder das ich ein Progrämmchen geschrieben habe, was zwar tut was es
> soll aber einfach "gefühlt" zu gross ist.
> Das hinterlässt dann immer den faden Beigeschmack, das man zwar was
> geschafft hat, es aber immer noch nicht optimal ist.
> Als ich noch auf dem 8051 in Assembler Programmiert habe, hatte ich
> dieses "Gefühl" relativ selten. ;)

Genau das meinte ich eben mit "Angst-Optimierung" :-)

Johann L. schrieb:

> Code tot zu optimieren. Ich muss gestehen, daß ich selbst oft (zumindest
> in privaten Projekten) in die Optimierungs-Falle trete und optimiere, wo
> es nicht wirklich nötig ist, was zu Code führt, der schwerer wartbar
> ist.

Ist mir auch schon passiert.

Ich hab an einem cleveren Triangulierer gearbeitet, der qualitativ gute 
Triangulierungen für Sonderfälle erzeugen sollte. War ein rekursives 
Divide and conquer Verfahren.
Beim Testen ist mir aufgefallen, dass da viele geometrische Berechnungen 
doppelt, dreifach und n-fach gemacht werden. Also musst ein Cache her, 
der die Zwischenergebnisse aufnimmt. Ist aber nicht so einfach, denn es 
muss auch sicher gestellt werden, dass alte Werte aus dem Cache 
rausfliegen, wenn sich die geometrische Situation durch Aufbrechen des 
Poylgons verändert.

Langer Rede kurzer Sinn: Das ganze wurde relativ komlpex, ich hab 2 Tage 
daran gearbeitet.

Dann die Stunde der Wahrheit: Laufzeitvergleich!
Ernüchternd ... der neue High-Tech Code war langsamer als der alte Bruth 
Force Code.

Hätte ich gleich einen Profiler darauf angesetzt, hätte ich gesehen, 
dass die Rechenarbeit gar nicht das Problem darstellen.

Die Lektion werd ich nie vergessen.

Fortgeschrittener Anfänger schrieb:

> Aber was mich immer wieder wundert ist, man hat eine kleine
> übersichtliche routine geschrieben die genau das tut was sie soll und
> wieder sind 2K Flash futsch.

Ich gesteh dir natürlich zu, dass du hier ein wenig übertreibst.

Aber so schlimm ist es auch wieder nicht.

Optimierer einschalten
keine Floating Point Operationen
Formeln umstellen und zusammenfassen
uint8_t wo's nur geht.

alleine damit hält sich der Flash-Verbrauch meistens schon ganz gut im 
Rahmen.

Und einen kleinen Penalty zahlt man nun mal für den Compiler. Mit 
Assembler kann man natürlich noch das eine oder andere Byte einsparen, 
weil man zb. die SREG Flags cleverer einsetzen kann. Aber diese paar 
Bytes sind mir der Komfort eines Compilers allemal wert.

> Natürlich hilfts, wenn mal jemand anders
> drüberschaut, aber das kann man ja auch nicht jedes mal machen. Und
> deswegen wäre eine generelle Strategie von Vorteil, wie man
> Codeoptimierung betreibt.

Wenn es eine gäbe, würden die Compilerbauer sie in die Compiler einbauen 
:-)

Karl heinz Buchegger schrieb:
>> AVR-GCC-Codeoptimierung
> Hat eigentlich schon mal wer kontrolliert, welche der Tips in diesem
> Artikel mit dem aktuellen GCC noch Gültigkeit haben.
>
> Ein paar dieser Optimierungen erscheinen da sehr zweifelhaft.

Einige davon sehen auf den ersten Blick so aus, als hätte sich da jemand 
erstmal überlegt, wie er selbst den Code in Assembler schreiben würde, 
und hat dann den Compiler solange "getriezt", bis endlich das gewünschte 
herauskam.

IMO ist dieses Vorgehen ein komplett falscher Ansatz. Wenn man konkret 
ganz bestimmten Code wünscht/braucht, dann soll man ihn gefälligst auch 
in (Inline-)Assembler hinschreiben. Damit ist dann wenigstens auch 
garantiert, dass das mit der nächsten Compilerversion immer noch 
denselben Code ergibt.

Natürlich soll das nicht heissen, dass man sich nicht den Assemblercode 
ansehen soll, um Optimierungspotential zu finden, und ggf. auch durch 
kleine Codeumstellungen oder Attributierungen dem Optimizer 
Hilfestellung zu geben. Man soll nur eben nicht versuchen Assembler als 
C hinzuschreiben, es sollte schon sauberes C bleiben.

Andreas

Hi,
Ich bin der Ansicht, wenn man auf einer Ebene gut sein will, sollte man 
Ahnung von der tiefer liegende Ebene haben.
Ich hab schon viele Algorithmen (hauptsächlich Crypto) in Assembler 
optimiert implementiert, und dadurch gelernt wie man Code so schreibt, 
dass der Compiler da was anständiges raus machen kann.

Das do{...}while(...); loop Konstrukt ist da ein gutes Beispiel.
Die Verwendung von Schleifen dieser Art macht es dem Compiler möglich 
einfach guten Code zu erzeugen. Das liegt daran das diese Art von 
Schleife sehr einfach in wenige ASM Befehle umgesetzt werden kann 
(Codeblock; Condition-Code; konditionaler Sprung).

Es hilft auch zu wissen, dass es nur 3 Pointer-Register gibt (wovon eins 
evtl. als Frame-Pointer benötigt wird). Auch die Adressierungmodi zu 
kennen hilft auch.

Also mein Tipp für alle die ernsthaft optimierten Code produzieren 
wollen ist sich mehr mit der Maschine und der Maschinensprache zu 
befassen.
Natürlich sind Wissen über den Compiler und seine Optionen ebenfalls 
sehr hilfreich um ihn zur Erzeugung guten Codes zu bewegen.

Daniel Otte schrieb:
> Das do{...}while(...); loop Konstrukt ist da ein gutes Beispiel.

Was soll denn der Vorteil sein bei do-while gegenüber while?

Sven P. schrieb:
> Aber GCC ist nicht doof.

Ist er doch.
Du kannst Dich auf den Kopf stellen, wenn Du einen Pointerzugriff mit 
Autoincrement machen willst (*ptr++), no chance.
Er macht immer LD + ADIW + RJMP draus.
Für ihn sind 3 Befehle schneller als einer.


Peter

Peter Dannegger schrieb:
> Sven P. schrieb:
>> Aber GCC ist nicht doof.
>
> Ist er doch.
> Du kannst Dich auf den Kopf stellen, wenn Du einen Pointerzugriff mit
> Autoincrement machen willst (*ptr++), no chance.
> Er macht immer LD + ADIW + RJMP draus.
> Für ihn sind 3 Befehle schneller als einer.

Hast du ein bestimmtes Beispiel? Manchmal hilft -fno-tree-loop-optimize

Johann L. schrieb:
> Hast du ein bestimmtes Beispiel? Manchmal hilft -fno-tree-loop-optimize

1

void eeprom_rw( uint16_t eep, uint8_t *sram, uint8_t len, uint8_t write )

2

{

3

  uint8_t edat, sdat;

4

5

  do{

6

    EEAR = eep;

7

    EECR |= 1<<EERE;                    // read

8

    edat = EEDR;

9

    if( write ){                        // write or read action

10

      sdat = *sram++;

11

      if( sdat != edat ){               // if not equal

12

        EEDR = sdat;                    // load data

13

        ATOMIC_BLOCK(ATOMIC_FORCEON){

14

          EECR |= 1<<EEMPE;

15

          EECR |= 1<<EEPE;              // write

16

        }

17

        while( EECR & 1<<EEPE );        // wait until write done

18

      }

19

    }else{

20

      *sram++ = edat;

21

    }

22

    eep++;

23

  }while( --len );                      // 1..256 byte

24

}

Im Anhang das Listing
-fno-tree-loop-optimize braucht sogar 6 Bytes mehr.


Peter

Peter Dannegger schrieb:
> Johann L. schrieb:
>> Hast du ein bestimmtes Beispiel? Manchmal hilft -fno-tree-loop-optimize
[...]

In deinem Beispiel macht dir eine andere Optimierung eine Strich durch 
die Rechnung, vermutlich irgendeiner der "Redundancy 
Elimination"-Schritte. Der Inkrement findet in beiden if-Zweigen statt 
und wird deshalb aus der Verzweigung ausgelagert. Deshalb kann er dann 
in späteren Optimierungsschritten bei der Codegenerierung nicht mehr mit 
dem LD zusammengezogen werden.

Nur zur Demonstration: kommentier mal den else-Zweig komplett aus, dann 
benutzt der gcc auch "LD rXX, Z+".

Andreas