Compilerintelligenz für Teilungsoperation

[Compiler (Gast)]

moin,

sagt mal, wenn ich in meinem Code eine Zeile habe:


uint16_t teile(uint16_t wert, uint16_t teiler)
{
uint16_t temp = wert/teiler;

return temp;
}

nun rufe ich die Funktion in der main z.b. so auf:

teile(wert, 8);

Frage:
erkennt mein Compiler selbständig, dass die Funktion teile 
sinnvollerweise durch folgendes ersetzt werden könnte:

uint16_t temp = wert>>3;


Vorausgesetzt, die Funktion wird nur mit zweierpotenzen genutzt.


mfg


PS.: ist die IAR emb. Workbench. Controller MSP430

[Coder (Gast)]

Du kannst das selber prüfen. Schau die den Assembler-Code an.

[Peter II (Gast)]

wenn es alles ein einer Datei ist, dann eventuell. Wenn die funktion in 
einer anderen Datei ist dann auf jeden fall nicht.

Teste es doch einfach und schau dir an was der compieler gemacht hat

[Compiler (Gast)]

...gut danke.

Anschlussfrage:

Wie lange dauert eine nicht optimierte Division?

[Timmo H. (masterfx)]

Wenn du in deinem Quellcode nur einmal die "teile" Funktion mit "(wert, 
8)" im gesamten Programm aufrufst, dann sollte er das schnellste nehmen.
Wenn der Teiler jedoch variabel ist, kann er das natürlich nicht machen. 
Ebenso wenig wenn du anstatt uint int genommen hättest, da dann das 
Schieben bei den negativen zahlen "falsch runden" würde.

[Coder (Gast)]

Da musst Du Dir erzeugten Assembler Code anschauen und die Taktzyklen 
zählen (lassen). Generell schaust Du in das Datenblatt von deinem 
Mikrocontroller.

Tut mir leid.

[Karl H. (kbuchegg)]

Compiler schrieb:
> ...gut danke.
>
> Anschlussfrage:
>
> Wie lange dauert eine nicht optimierte Division?

Kann man so nicht sagen.
Das hängt davon ab, welche Operationen die CPU bereitstellt. Hat die 
eine Divisionsoperation in Hardware, dann gehts ratzfatz. Wenn nicht, 
dann muss die CPU das dann eben "händisch" mit anderen zur Verfügung 
stehenden Operationen machen.

Und zu guter letzt hängt es auch noch davon ab, ob du von 8, 16, 32 oder 
64 Bits sprichst.

Sieh dir den Code an, schnapp dir die Befehlssatzbeschreibung und 
addiere die Zyklen.


Aber: Hängt die Funktionalität deines Programmes wirklich daran, ob eine 
Division optimiert wird? Spielt es tatsächlich die große Rolle, ob eine 
Division jetzt 1µs oder 10µs dauert?

Die Amerikaner sind mit einer Rechenleistung zu Mond geflogen, die der 
einer heutigen Kaffeemaschine entspricht. Das ging, weil sie eine 
clevere Programmorganisation hatten, nicht weil die Rechner damals so 
schnell waren.

[Compiler (Gast)]

...nun grundsätzlich ist ein Unterschied von 1us zu 10us nominell zwar 
wenig, tatsächlich aber liegt ein Faktor 10 dazwischen.

Da lohnt sich eine Optimierung meiner Meinung nach grundsätzlich.

[Andreas B. (andreasb)]

Compiler schrieb:
> ...nun grundsätzlich ist ein Unterschied von 1us zu 10us nominell zwar
> wenig, tatsächlich aber liegt ein Faktor 10 dazwischen.
>
> Da lohnt sich eine Optimierung meiner Meinung nach grundsätzlich.

Mach mal noch ein "static" vor deine "teile" Funktion, dann kann diese 
nur aus diesem File aufgerufen werden, und der Compiler kann optimieren.

Ohne dieses Static kann es sein das die Funktion auch von anderen Files 
aufgerufen wird, und dann wird der Compiler eher nicht optimieren.

ps. hängt alles vom Compiler / Optimizer ab.


mfg Andreas

[Peter (Gast)]

>Frage: erkennt mein Compiler selbständig, dass die Funktion teile
>sinnvollerweise durch folgendes ersetzt werden könnte:
>uint16_t temp = wert>>3;

Nee, der Compiler wird das kaum auf diese Weise optimieren! Aber anstatt 
eine Funktion aufzurufen, kannst Du ja dem Compiler helfen und direkt 
den Shift Befehl nutzen!

[Karl H. (kbuchegg)]

Compiler schrieb:
> ...nun grundsätzlich ist ein Unterschied von 1us zu 10us nominell zwar
> wenig, tatsächlich aber liegt ein Faktor 10 dazwischen.
>
> Da lohnt sich eine Optimierung meiner Meinung nach grundsätzlich.

NIcht wirklich.
Dein Faktor 10 bringt dir nämlich gar nichts, wenn die entsprechende 
Operation lediglich 1% der Gesamtlaufzeit ausmacht.

Braucht dein Programm 100 Sekunden (für was auch immer) und ist der 
bewusste Programmteil davon für 1 Sekunde verantwortlich, dann sinkt 
deine Programmlaufzeit mit einer 10er-Optimierung von 100 Sekunden auf 
99.1 Sekunden. Also so gut wie gar nichts. Aus deinem Faktor 10 sind 
aufs Gesamtprojekt bezogen gerade mal 0.9% geworden.

Genau aus dem Grund lautet die zweite Regel in der Optimierung:
messen, messen, messen und blos nicht auf gut Glück und Raten drauflos 
optimieren.
(Die erste Regel lautet: Don't do it!
 Regel 1-B lautet: Don't do it, yet!
)

In den meisten Fällen optimiert man nämlich an Stellen, die im 
Gesamtkontext des Programmes in der Realität nichts bringen. Im Gegenzug 
handelt man sich aber mit derartigen Mikrooptimierungen oftmals 
Strukturprobleme ein. (Ganz abgesehen davon, dass Compiler mitlerweile 
gut genug darin sind, derartige Mikrooptimierungen selbst vorzunehmen, 
wenn es möglich ist)

Kümmere dich lieber um Optimierungen auf algorithmischer Ebene. Sorge 
dafür, dass du sinnvolle Datentypen benutzt, keinen offensichtlichen 
Unsinn programmierst. Und im übrigen programmiere so, dass man auch in 5 
Jahren, wenn man die Details längst vergessen hat, den Code immer noch 
warten kann.
 #Das# bringt tatsächlich was.

[Floh (Gast)]

Compiler schrieb:
> Da lohnt sich eine Optimierung meiner Meinung nach grundsätzlich.

Voreilige Optimierung ist die Wurzel allen Übels.

Ohne erkennbaren Nutzen macht Optimierung halt einfach keinen Sinn.
Auch kommen ab und zu ähnliche Fragen vor, irgendwann wird dann der 
komplette Code gezeigt und es steht ein delay_ms drin. Daher die Frage, 
ob du die Geschwindigkeit wirklich benötigst.

Außerdem, warum kapselst du eine einfache Division in eine Funktion?
Was ist besser lesbar:

Geschwindigkeit = Weg / Zeit;
//oder
Geschwindigkeit = teile(Weg, Zeit);

Oder soll das nur exemplarisch sein ? (Was Optimierung komplett sinnlos 
macht)

[Oliver (Gast)]

Karl Heinz Buchegger schrieb:
> Die Amerikaner sind mit einer Rechenleistung zu Mond geflogen, die der
> einer heutigen Kaffeemaschine entspricht. Das ging, weil sie eine
> clevere Programmorganisation hatten, nicht weil die Rechner damals so
> schnell waren.

Und die sind erfolgreich gelandet, obwohl der Rechner im 
Landeanflugüberlastet war, weil da eingewisser Neil Armstrong das Ding 
per Hand gelandet hat.

Compiler schrieb:
> ...nun grundsätzlich ist ein Unterschied von 1us zu 10us nominell zwar
> wenig, tatsächlich aber liegt ein Faktor 10 dazwischen.
>
> Da lohnt sich eine Optimierung meiner Meinung nach grundsätzlich.

Wenn diese 9us in deinem Programm funktionsentscheidend sind (z.B. weil 
die Funktion in einer Schleife einige Milliarden mal aufgerufen wird), 
dann ja, sonst nicht. Denn "nominell wenig" wäre selbst mit einem Fakter 
von 200000000000 immer noch grundsätzlich "nominell wenig".

Oliver

[Andreas B. (andreasb)]

Oliver schrieb:
>> Da lohnt sich eine Optimierung meiner Meinung nach grundsätzlich.
>
> Wenn diese 9us in deinem Programm funktionsentscheidend sind (z.B. weil
> die Funktion in einer Schleife einige Milliarden mal aufgerufen wird),
> dann ja, sonst nicht. Denn "nominell wenig" wäre selbst mit einem Fakter
> von 200000000000 immer noch grundsätzlich "nominell wenig".

Dann müsste man aber ganz anders anfangen, z.B. der Call ist eine 
relativ teure Operation, dann kämen da noch Stichworte wie Loop 
unrolling etc.

http://de.wikipedia.org/wiki/Loop_unrolling


mfg Andreas

[Karl H. (kbuchegg)]

Oliver schrieb:
> Karl Heinz Buchegger schrieb:
>> Die Amerikaner sind mit einer Rechenleistung zu Mond geflogen, die der
>> einer heutigen Kaffeemaschine entspricht. Das ging, weil sie eine
>> clevere Programmorganisation hatten, nicht weil die Rechner damals so
>> schnell waren.
>
> Und die sind erfolgreich gelandet, obwohl der Rechner im
> Landeanflugüberlastet war, weil da eingewisser Neil Armstrong das Ding
> per Hand gelandet hat.

Neil ist nicht von Hand geflogen, WEIL der Rechner überlastet war.
Neil ist von Hand geflogen, weil ihn der Rechner in ein Gebiet mit 
Felsenbrocken gebracht hätte und er einen Krater überfliegen musste. Sie 
waren im Abstieg ein wenig spät drann und es war frühzeitig klar, dass 
sie über das vorgesehene Landegebiet hinausschiessen würden.

Der Rechner hat perfekt funktioniert, WEIL das Betriebssystem clever 
aufgebaut war und Tasks gestoppt hat, die nicht unbedingt notwendig 
waren. Wie zb einen Anzeige-Task der einen bestimmten Wert laufend in 
der Anzeige aktualisierte (ich weiß nicht mehr auswendig welcher das 
genau war, könnte ich aber raussuchen). Der Rest der Berechnungen lief 
davon unbeeindruckt im Computer weiter. Inklusive einem Task, der 
eigentlich zu dem Zeitpunkt gar nicht hätte laufen sollen 
(Randevouz-Radar) und der das Problem verursacht hat. Hätte Aldrin, wie 
vorgesehen, das Randevouz-Radar im Abstieg deaktiviert, wäre keine 
einzige Fehlermeldung vom Rechner gekommen - was nicht heißt, dass er 
den letzten Teil nicht trotzdem mit der Hand geflogen wäre. Das musste 
er sowieso und das war auch im Vorfeld klar.

[Karl H. (kbuchegg)]

Aus aktuellem Anlass

Ich hab da eine Funktion (geschrieben 1992 von einem meiner Vorgänger), 
die Duplikate in einem Pointer-Array entfernen soll.
(Ich zeig jetzt nicht die Funktion im Original, sondern nur symbolisch)

Die Funktion sieht so aus.

int CleanPtr( void* Ptr_list, int P_len )
{
  register int I,J
  int Incr = 0;

  SortPtr(Ptr_list,*P_len);

  for (I=0; I < *P_len-1; I++)
  {
    J = I;
    while (J < *P_len-1 && Ptr_list[J] == Ptr_list[J+1])

      ++J;

    Incr = J-I;
    if (Incr)
    {
      for (J=I+1; J < *P_len-Incr; J++)
      {
        Ptr_list[J] = Ptr_list[J+Incr];
      }
      *P_len -= Incr;
    }
  }
}

Die Funktionsweise ist nicht auf den ersetn Blick ersichtlich. Ein 
zweiter Blick zeigt:
  erst mal sortieren
  dann jeweils identifizieren, wieviele Einträge hintereinander gleich
  sind
    Die Duplikate entfernen, in dem die dahinterliegenden Einträge
    entsprechend nach vorne geschoben werden.
  das ganze solange, bis man am Ende ist.

Bei größeren Datenmengen ist die Funktion saulangsam.
Du kannst jetzt natürlich rumüberlegen und Stellen finden, an denen man 
eine Operation noch einen Tick schneller machen kann.
Aber das löst das grundsätzliche Problem nicht: Die Funktion hat 
potentiell quadratische Laufzeit und egal welche Mikrooptimierung du 
vornimmst, daran wird sich nichts ändern.

Eine einfache Modifikation des Verfahrens

int CleanPtr( void* Ptr_list, int P_len )
{
  if (*P_len > 0)
  {
    int I, J;

    SortPtr(Ptr_list,*P_len);

    for (J = 0, I = 1; I < *P_len; I++)
    {
      if (Ptr_list[J] != Ptr_list[I])
        Ptr_list[++J] = Ptr_list[I];
    }

    *P_len = J+1;
  }
}

bringt mehr als es jede Mikrooptimierung je könnte, weil jetzt die 
grundsätzliche Laufzeit von potentiell quadratisch auf sicher linear 
gedrückt wurde. Die 'Optimierung' wurde nicht dadurch erreicht, dass man 
anstelle einer for-Schleife eine while-Schleife einsetzt, weil die 
angeblich einen Tick schneller ist, sondern die Optimierung und der 
Zeitgewinn wurde erreicht, indem man nach grundsätzlichen Schwachstellen 
im Algorithmus sucht.

[Erich (Gast)]

Vom Mond zurück wieder zum Thema:
Die Frage war, ob einer "Teilungsfunktion" bei Aufruf mit einer 
Zweierpotenz als Divisior automatisch zu einer Shiftoperation umgesetzt 
wird vom Compiler.
Meine Antwort ist: jein.

Es hängt von vielen Faktoren, v.a. dem Compiler und der 
Optimierungseinstellung ab.
Bei höchstmöglicher Optimierung (auf "speed", nicht "size") wird dies 
i.d.R. so sein, denn dann erfolgt das schon benannte Loop_unrolling 
automatisch.
Es führt dazu, daß alle Aufrufe der "Teilungsfunktion" quasi als #inline 
eingesetzt werden.
Vor vorneherein schlauer ist es, für eine solche Trivialität wie Teilung 
überhaupot keine eigene Funktion zu erstellen, sondern das ganz einfach 
in C Syntax hinzuschreiben:
   uint16_t temp = wert / 8;
In diesem Fall funktioniert die Ersetzung durch 3 Shifts auch ohne 
Loop_unrolling, ggf. abhängig von der Optimierungseinstellung.

Wer's genau wissen will, kann
A)  im .asm oder Disassembler-Listing nachsehen.
oder B):   Alternative wer schwer in .asm rumsuchen will
Man macht selbst einen Versuch: Das mit >>3 hinschreiben, compilieren, 
resultierende .hex Datei sichern (z.B. in ZIP, oder umbenennen).
Dann ersetzen durch /8 , wieder compilieren.
Jetzt kann man die .hex Datzei vergleichen.
Ist sie gleich geblieben, so hat diese Optimierung definitiv erfolgreich 
stattgefunden.

Gruss

[(prx) A. K. (prx)]

Inlining hat mit loop unrolling nichts zu tun. Ersetzung von Division 
durch shifts auch nicht. Das sind verschiedene Optimierungen.