www.mikrocontroller.net

Forum: Compiler & IDEs Optimiert der Compiler Division durch 2^n wirklich?


Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Division durch 2^n soll ja automatisch in effiziente Shift-Operationen 
vom Compiler umgesetzt werden. Hab das schon häufiger gehört und daher 
brav alle Skalierungen in meinem Programm mit /-Operatoren realisiert.

Beim Prüfen der Berechnungszeit habe ich dann aber festgestellt, dass 
die Berechnungen zu lange dauern. Länger rumgesucht, dachte erst an den 
relativ breiten Datentyp int32_t.

Aber nein: Schuld waren die Divisionen.
Ich habe sie gegen die Version mit Rechts-Shift ersetzt und den 
Rundungsfehler mit vorhergehender Addition eleminiert:

#define P_TERM_SCALE(x)        (((x)+2)>>2)   // entspricht /4

Die Defines dienen einer einfacheren nachträglichen Anpassung.

Trotz eines uC (ATtiny26) ohne Barrel-Shifter, brachte das
1. einiges an frei werdenden Speicher
2. eine wesentliche (Faktor ca. 2) Beschleunigung des Programms.

Was ist also dran an dem Gerücht? Oder liegt es an meinen 
Compiler-Schaltern?

avr-gcc  -mmcu=attiny26 -Wall -gdwarf-2 -std=gnu99 
-fno-inline-small-functions -finline-limit=3 -ffunction-sections 
-fdata-sections -ffreestanding      -fno-split-wide-types 
-fno-tree-scev-cprop --combine -fwhole-program -Os -funsigned-char 
-funsigned-bi
tfields -fpack-struct -fshort-enums -MD -MP -MT ZKS.o -MF dep/ZKS.o.d 
-c  ../ZKS.c

Ich habe im Verdacht, dass der vom Compiler erzeugte Assembler-Code noch 
Überläufe und sowas abfängt (...hab mir das mit dem breiten Datentyp 
sparen können). Aber kann sowas so lange dauern (...ich rede von ca.5us 
pro Division...)?

Habt ihr ähnliche oder vielleicht völlig andere Erfahrungen gemacht?

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> Division durch 2^n soll ja automatisch in effiziente Shift-Operationen
> vom Compiler umgesetzt werden. Hab das schon häufiger gehört und daher
> brav alle Skalierungen in meinem Programm mit /-Operatoren realisiert.
>
> Beim Prüfen der Berechnungszeit habe ich dann aber festgestellt, dass
> die Berechnungen zu lange dauern. Länger rumgesucht, dachte erst an den
> relativ breiten Datentyp int32_t.

Und genau da steckt dein Fehler.
Mach einen uint32_t daraus und der Compiler ersetzt dir die Division 
durch Shiften.

> Was ist also dran an dem Gerücht? Oder liegt es an meinen
> Compiler-Schaltern?

Es liegt daran, dass du den falschen Datentyp gewählt hast.
Bei einem vorzeichenbehafteten Datentyp ist nämlich Division und Shiften 
nicht identisch. Bei negativen Zahlen kommt ein anderes Ergebnis raus. 
Und das weiß auch der Compiler.

Autor: DNS (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
AVRs haben doch auch eine Funktion "Arithmetic Shift Right" - Kennt der 
Compiler die nicht?

Gruß
Dennis

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
DNS schrieb:
> AVRs haben doch auch eine Funktion "Arithmetic Shift Right" - Kennt der
> Compiler die nicht?

Probiers aus.
Negative Zahlen nach rechts geschoben runden in die falsche Richtung.

-9 >> 1   ergibt -5
-9 / 2    ergibt aber -4

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bei 16 Bits findet diese Optimierung auch statt, mit entsprechender 
Korrektur. Bei 32 Bits offenbar nicht. Und bei 64 Bits läuft er völlig 
aus dem Ruder. Jedenfalls gcc 4.3.4.

Zu beachten ist, dass aufgrund des erwähnten Unterschieds zwischen 
einfachem Shift und Division der Code mit Shift+Korrektur u.U. länger 
als der Aufruf der Laufzeitfunktion ist, was bei Optimierung auf Grösse 
zum Aufruf führen kann.

Wobei bei solcher Abwägung nur der direkt erzeugte Code zählt, nicht der 
Rattenschwanz an Library-Code. D.h. das Gesamtprogramm kann dank 
Library-Code grösser werden, auch wenn der direkt erzeugte Code kleiner 
wird.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:
> -9 >> 1   ergibt -5
> -9 / 2    ergibt aber -4

Die Lösung mit Shift und Addition ja auch, allerdings liefert die für

(9 + 2) >> 2 = 5 // und nicht...
 9 / 2 = 4

Was ja im Sinne einer Division auch "korrekt gerundet" ist.

Wenn ich das richtig sehe, ist der Compiler gezwungen, sich an den 
C-Standard (der mathematisch weniger Korrekt ist) zu halten und kann 
daher nicht wie oben beschrieben optimieren.

Im mathematischen Sinne, ist die Operation mit shift+Add doch genauer. 
Und sie erzeugt keinen "Sprung" beim Runden um 0. Da der Algorithmus in 
einer Regelung eingesetzt wird, ist das ja gar nicht so schlecht (bei 
Nulldurchgängen.).

Nun ist es ja nicht nur in meinem Interesse, dass der Code mathematisch 
korrekt ist. Warum hat man C denn so spezifiziert?

A. K. schrieb:
> Wobei bei solcher Abwägung nur der direkt erzeugte Code zählt, nicht der
> Rattenschwanz an Library-Code. D.h. das Gesamtprogramm kann dank
> Library-Code grösser werden, auch wenn der direkt erzeugte Code kleiner
> wird.

Und sowas kann der Compiler nicht von selbst feststellen? Krass. Dann 
sollte man sich auf die ganzen Optimierungen beim Kompilieren gar nicht 
so sehr verlassen und sollte auch selbst auf die Suche nach 
Optimierungsmöglichkeiten gehen. Bin desillusioniert.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:

> Wenn ich das richtig sehe, ist der Compiler gezwungen, sich an den
> C-Standard (der mathematisch weniger Korrekt ist) zu halten und kann
> daher nicht wie oben beschrieben optimieren.

definiere 'korrekt'.
Die Forderung des Standards beim Int-Dividieren lautet: Die Division 
wird so durchgeführt, als ob eventuelle Nachkommastellen abgeschnitten 
werden würden. Das 'Runden' (in Wirklichkeit wird da überhaupt nichts 
gerundet) findet also immer in Richtung 0 statt.

> Nun ist es ja nicht nur in meinem Interesse, dass der Code mathematisch
> korrekt ist. Warum hat man C denn so spezifiziert?

Weil so Integer Division am einfachsten Durchzuführen ist.
So wie du das in der Grundschule auch gelernt hast:
9 Äpfel und 2 Kinder: Jedes Kind kriegt 4 Äpfel und 1 bleibt übrig.
Der 1 Rest interessiert bei Integer Division nicht, nur das ganzzahlige 
Ergebnis zählt.

Allerdings muss gewährleistet sein:

    a = x / y
    b = x % y

    x = a * y + b

und das muss auch bei negativen Zahlen funktionieren.

> Und sowas kann der Compiler nicht von selbst feststellen?

Der Compiler kann das überhaupt nicht feststellen. Schon alleine 
deswegen nicht, weil er das komplette Programm im Normalfall nie zu 
Gesicht bekommt. Wenn überhaupt dann könnte das höchstens der Linker 
machen, der ändert aber wohlweislich an der grundsätzlichen Codestruktur 
nur mehr wenig bis gar nichts mehr, sondern fügt nur noch die 
Einzelteile zusammen.

Beim gcc und den traditionell kleinen Programmen auf einem AVR könnte 
der Optimierungsschalter -fwhole_program (Hab die genaue Schreibweise 
nicht im Kopf) eventuell etwas bewirken.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:

> Beim gcc und den traditionell kleinen Programmen auf einem AVR könnte
> der Optimierungsschalter -fwhole_program (Hab die genaue Schreibweise
> nicht im Kopf) eventuell etwas bewirken.

Wohl kaum, da der Compiler nur weiss, dass es eine Lib gibt, er aber 
weder die Grösse deren Einzelkomponenten kennt, noch die Summe 
sämtlicher möglicher Platzersparnisse vor der endgültigen Optimierung 
protokollieren wird.

Theoretisch könnte man das machen, klar. Aber dazu müssten Programme für 
4KB-Flash Maschinchen das Designziel des Compilers sein, nicht Multi-MB 
Programme aus SpecMarks.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:
> Karl heinz Buchegger schrieb:
>
>> Beim gcc und den traditionell kleinen Programmen auf einem AVR könnte
>> der Optimierungsschalter -fwhole_program (Hab die genaue Schreibweise
>> nicht im Kopf) eventuell etwas bewirken.
>
> Wohl kaum, da der Compiler nur weiss, dass es eine Lib gibt,

Auch wieder wahr.

> er aber
> weder deren Grösse kennt, noch die Summe sämtlicher möglichen
> Platzersparnisse im Vorfeld protokollieren wird, um später anhand dessen
> entscheiden zu können.

Gut. Man könnte diese Info in eine Lib mit aufnehmen und den Compiler 
entsprechend kompliziert machen. Aber soweit lehnt sich kein Compiler, 
kein Librarien und kein Linker aus dem Fenster. Man darf ja auch nicht 
vergessen, dass der gcc von µC bis zu Supercomputern alles abdeckt. Und 
bei allen Ebenen über einem µC spielen die paar Bytes Programmcode nicht 
wirklich eine große Rolle.


Edit: A.K. stösst ja dann auch ins selbe Horn

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Okay soweit klar.

Wenn man aber "mathematisch" korrekt runden will, also 1.5->2, 0.5-> 1, 
-0.5->0 und -1.5->-1, dann stimmen weder der Shift-Operator noch die 
Division bei Ganzzahlen in C, richtig? Dass der C-Standard wegen der 
Modulo-Operators das so handhaben muss, kann ich nachvollziehen.
Aber, dass man für die korrekte Ermittlung eines Mittelwertes so einen 
Aufwand treiben muss, wundert mich. Warum gibt es keine Funktionen in C 
dafür? Historisch, Logisch oder Hardware-bedingt?

Karl heinz Buchegger schrieb:
> -fwhole_program

Schau mal in mein 1. Post. Der bringts tatsächlich, aber leider nicht 
bei der Division... Das Rausschmeißen der Divisionen hat noch mal 
einiges zusätzlich gebracht. Hab jetzt wieder ordentlich Luft für 
weiteren Code und weitere Berechnungen.

Karl heinz Buchegger schrieb:
> Und
> bei allen Ebenen über einem µC spielen die paar Bytes Programmcode nicht
> wirklich eine große Rolle.

Aber ist der AVR-GCC nicht genau für solche Fälle optimiert? Ich habe 
den immer als einen auf genau solche Fälle optimierten Kompiler 
verstanden.

Oder liegt der Unterschied zum GCC hauptsächlich in den zusätzlichen 
includes für AVRs?

Zumindest verstehe ich jetzt, warum trotz Optimierungschalter der Code 
langsamer UND größer ist. Also lag ich mit meiner Vermutung gar nicht so 
falsch und man sollte nicht, wie oft geraten, immer brav die Division 
mit / realisieren um das Programm übersichtlicher zu halten, da "der 
Compiler das schon erkennt und optimiert".

Dem ist anscheinend eben nicht so.

Was ich nicht verstehe: Warum man keine #defines oder Funktionen oder 
dergleichen für sowas gemacht hat. Denn auch die korrekte Division nach 
C ließe sich ja wahrscheinlich einfacher mittels Schieben realisieren, 
als mit der von der lib bereitgestellten Routine.

Ein Schalter bei der Optimierung, der hier einen manuellen Eingriff 
ermöglicht, würde das Problem ja auch lösen, oder?

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> Oder liegt der Unterschied zum GCC hauptsächlich in den zusätzlichen
> includes für AVRs?

Es gibt keinen "Unterschied zum GCC", der AVR-GCC ist ein GCC.
Es ist einfach ein GCC, der für den AVR konfiguriert wird (und damit
insbesondere ein Cross-Compiler), nicht mehr und nicht weniger.

Die "zusätzlichen Includes für AVRs" sind (technisch gesehen)
Bestandteil der avr-libc, die ein separates Projekt ist.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:

> Aber ist der AVR-GCC nicht genau für solche Fälle optimiert? Ich habe
> den immer als einen auf genau solche Fälle optimierten Kompiler
> verstanden.

GCC ist der Standardcompiler für Linux und wird auch in Unix und sogar 
Windows gerne gesehen. Von Anfang an konzipiert für eher grosse 32-Bit 
Systeme, bei denen der Platzaufwand solcher Runtime-Libs irrelevant ist.

AVR-GCC ist ein GCC mit Zielmaschine AVR. GCC teilt sich in einem 
grossen maschinenübergreifenden und einen kleinen maschinenabhängigen 
Teil. Optimierungsstrategien sind in gcc weitgehend 
maschinenübergreifend implementiert, allgemeingültige Tricks wie shift 
vs divide eingeschlossen, nur die dafür nötige Kostenabschätzung der 
Operationen ist abhängig von der Zielmaschine.

Um solche globalen Optimierungen wie hier angesprochen unter Einschluss 
der Runtime-Libs in GCC einbauen zu können müsste man wahrscheinlich 
heftig im maschinenunabhängigen Teil rumferkeln und ganze Abläufe neu 
gestalten. Bischen im maschinenabhängigen Teil rumzuferkeln reicht dafür 
mit Sicherheit nicht aus.

AVR-GCC ist ein für die Hauptentwickler des gcc wenig relevantes 
Nebenprodukt. AVR ist die einzige 8-Bit Architektur, die überhaupt 
Einzug in den offiziellen Code gefunden hat. Dementsprechend wenig 
Rücksicht wird darauf genommen, und dementsprechend spassig ist es bei 
jeder neuer Release (4.5 => 4.6 => ...).

> Was ich nicht verstehe: Warum man keine #defines oder Funktionen oder
> dergleichen für sowas gemacht hat.

???

> Denn auch die korrekte Division nach
> C ließe sich ja wahrscheinlich einfacher mittels Schieben realisieren,
> als mit der von der lib bereitgestellten Routine.

Wie schon erwähnt wird das ja auch gemacht, aber eben nur ohne 
Vorzeichen und für 16 Bit Datentypen und es greift manchmal nur bei 
Optimierung auf Geschwindigkeit.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jörg Wunsch schrieb:
> Es gibt keinen "Unterschied zum GCC", der AVR-GCC ist ein GCC.
> Es ist einfach ein GCC, der für den AVR konfiguriert wird (und damit
> insbesondere ein Cross-Compiler), nicht mehr und nicht weniger.
>
> Die "zusätzlichen Includes für AVRs" sind (technisch gesehen)
> Bestandteil der avr-libc, die ein separates Projekt ist.

Ok! Wieder was gelernt. Wie ihr merkt habe ich keine Informatik 
studiert. Wenn die eine oder andere Frage deshalb in euren Ohren 
Blödsinn ist: Bitte drüber hinwegsehen.

Ich will nur die groben Zusammenhänge nachvollziehen können. Ich gehe ja 
schon davon aus, dass sich diejenigen, die sowas wie GCC auf die Beine 
stellen, schon ihre Gründe haben, das alles so umzusetzten, wie es 
umgesetzt ist...

Ich frage mal einfacher:

Wieso wird dieses Gerücht, auch HIER und für AVR-GCC nach wie vor in die 
Welt gesetzt, wenn nichts dran ist?

Und kann man AVR-GCC und/oder avr-libc nicht an die Architektur, den 
Befehlssatz und Bedingung eines kleine uController anpassen, so dass die 
Compiler-Schalter auch das tun, was sie tun sollen: Optimieren?

Compiler sind ja genau dafür gemacht, dass man sich eben nicht mehr mit 
Details zur Hardware/Befehlssatz/Speicherbedarf oder dergleichen 
rumschlagen muss, oder?

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:

> Wieso wird dieses Gerücht, auch HIER und für AVR-GCC nach wie vor in die
> Welt gesetzt, wenn nichts dran ist?

Kann es sein, dass du deine kleine Welt mit dem Universum verwechselst? 
Bloss weil du über die ineffiziente Implementierung einer Operation 
gestolpert bist, bricht für dich die Welt zusammen?

Der weitaus häufigste Typ in avr-gcc ist uint8_t, danach kommen beide 
16-Bit Typen und 32/64-Bit sind weniger relevant. Der Fokus von avr-gcc 
liegt bei 16-Bit Typen, grössere werden nicht immer gleichermassen 
optimiert, insbesondere nicht die 64-Bit Typen.

Lesbare Operationen durch schlechter lesbare in bestimmten Fällen 
schnellere Operationen zu ersetzen kann sinnvoll sein. Wie du 
feststellt, wird der Compiler das oft schaffen, aber eben nicht immer. 
Danach ist es jedermanns Abwägung, ob er eher universell lesbaren oder 
eher auf eine bestimmte Maschine optimierten Quellcode hinschreibt. Wenn 
der Fokus auf maximaler Performance liegt, muss man ggf. auch man auf 
Assembler-Ebene runter.

> Und kann man AVR-GCC und/oder avr-libc nicht an die Architektur, den
> Befehlssatz und Bedingung eines kleine uController anpassen, so dass die
> Compiler-Schalter auch das tun, was sie tun sollen: Optimieren?

Natürlich kann man das. Es müsste sich nur jemand finden, der es tut. 
Weshalb nicht du? Auf geht's, mach es!

Die avr-libc Library ist ziemlich weitgehend optimiert. Die Kompromisse 
stecken im Compiler.

Autor: Bob (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> so dass die
> Compiler-Schalter auch das tun, was sie tun sollen: Optimieren?

Genau das machen die doch. Optimieren.

Nur dass es eben einen Unterschied zwischen "Optimieren" und "Optimalen 
Code erzeugen" gibt, muss der Programmierer im Hinterkopf behalten. Egal 
ob AVR oder Core i7, egal ob GCC oder VCC oder ICC, egal ob C, C++, Java 
oder Basic...

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:
> Die Kompromisse
> stecken im Compiler.

Und selbst dort sind diese größtenteils gar nicht so sehr durch die
Architektur des GCC selbst festgefahren, sondern sehr oft Ausdruck
fehlender man power.  Während das vergleichsweise unwichtige AVR-
Backend durchaus von allgemeinen Optimierungen profitiert, die für
alle Zielarchitekturen dann (einigermaßen) gleichmäßig erfolgen,
fehlt es gerade an speziellen Optimierungen im AVR-Backend einfach
mal an Leuten, die willens und in der Lage wären, dort mitzumachen.
So konzentrieren sich vorgefertigte Optimierungen (für die im
Backend spezielle Implementierungen vorgenommen worden sind) auf die
häufig benutzten Datentypen, und es ist einfach nur unser Glück, dass
der GCC den Rest mit "vorgekochten" (automatisch generierten)
Implementierungen ergänzen kann, die dann zwar nicht optimal für den
AVR zugeschnitten sind, uns aber in die Lage versetzen, überhaupt
erst einmal bspw. 64-bit-Ganzzahltypen zu haben, ohne dass jemals
jemand im AVR-Backend dafür auch nur einen müden Finger gerührt
hätte.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke für die ausführliche Antworten. So langsam verstehe ich, dass 
meine Ansichten bezüglich des Aufwands sowas zu implementieren 
vielleicht etwas naiv sind.

>> Was ich nicht verstehe: Warum man keine #defines oder Funktionen oder
>> dergleichen für sowas gemacht hat.
>
> ???

S.o. P_SCALE_TERM.

Kann man natürlich noch eleganter und variabler mit 2 Argumenten machen, 
aber vom Prinzip genau sowas.

>> Denn auch die korrekte Division nach
>> C ließe sich ja wahrscheinlich einfacher mittels Schieben realisieren,
>> als mit der von der lib bereitgestellten Routine.
>
> Wie schon erwähnt wird das ja auch gemacht, aber eben nur ohne
> Vorzeichen und für 16 Bit Datentypen

..obwohl es für die anderen Fälle mit AVRs auch gut geht.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> Okay soweit klar.
>
> Wenn man aber "mathematisch" korrekt runden will, also 1.5->2, 0.5-> 1,
> -0.5->0 und -1.5->-1,

Das was du meinst, nennt sich übrigens "kaufmännisches Runden".
Und Runden ist gar nicht so einfach, wie man auf den ersten Blick 
glauben möge
http://de.wikipedia.org/wiki/Rundung

> dann stimmen weder der Shift-Operator noch die
> Division bei Ganzzahlen in C, richtig?

Das liegt aber daran, dass es hier gar kein Material zum Runden gibt.
Noch mal: Es herrscht oft die Vorstellung, dass ein Computer 
grundsätzlich alles mit Nachkommastellen berechnet. Dem ist nicht so!
Bei Divisionen mit ganzen Zahlen entstehen gar keine Nachkommastellen. 
Sie werden nie berechnet.


> Dass der C-Standard wegen der

C hat sich hauptsächlich eines auf die Fahnen geschrieben:
You don't get, what you didn't ask for.

Soll heißen: Im Zweifelsfall wurde in der Sprache immer der einfachstem 
kürzeste, schnellste Weg gewählt. Ganzzahldivisionen sind seit jeher 
bekannt. Auch wie man sie realisiert, so dass sich ganz von alleine ein 
Abschneiden der Kommastellen ergibt. Wir alle haben in der Grundschule 
gelernt wie man das macht. Nämlich einfach durchdividieren und wenn der 
Dezimalpunkt erreicht ist, hört man einfach auf.

Das ist das was von C gefordert wird.
Wenn du andere mathematischen Konventionen brauchst, wie zb ein 
kaufmännisches Runden, dann musst du dich darum selber kümmern. Dies 
deshalb weil es aufwändiger ist als das ganz banale Dividieren aber 
damit realisierbar! UMgekehrt würde das nicht mehr gehen.

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Schau daoch einfach im ASM-Code (LST-File), was der Compiler aus der 
Berechnung macht und vergleiche die beiden Varianten:

((x)+2)>>2)

oder einfach

(x/2)

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:

> Der weitaus häufigste Typ in avr-gcc ist uint8_t, danach kommen beide
> 16-Bit Typen und 32/64-Bit sind weniger relevant. Der Fokus von avr-gcc
> liegt bei 16-Bit Typen, grössere werden nicht immer gleichermassen
> optimiert, insbesondere nicht die 64-Bit Typen.

Und dadurch das C eigentlich auf dem Basistyp int aufbaut (im avr-gcc 
ein int16_t bzw uint16_t) hat der avr-gcc so manchesmal seine liebe Mühe 
Optimierungen bzw. Shortcuts die mit uin8_t möglich wären auch zu 
realisieren.

Aber alles in allem macht er einen guten Job. Speziell für einen AVR 
geschriebene Compiler, die dann auch schon mal die C-Spezifikation nicht 
ganz genau nehmen (weil auf einer 8-Bit Maschine kontraprodktiv), sind 
zwar manchmal einen Tick besser, aber über alles gesehen ist der avr-gcc 
schon ganz gut.

Und wenn du in die Situation kommst, dass tatsächlich eine läppische 
Division über funktioniert bzw. funktioniert nicht enscheidet, dann 
stimmt meistens schon an ganz anderen Stellen etwas nicht.
Im Einzelfall, wenn man hart an die Flash Grenzen kommt, mag das mit dem 
gcc unangenehm sein, aber im Regelfall spielt es keine Rolle ob man 
jetzt 5 oder 10% mehr Flash verbraucht als minimalistisch gesehen 
notwendig wäre.
Und größer ist die Differenz nicht.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Peter schrieb:
> oder einfach
>
> (x/2)

Du meintest (x/4), oder? ;)

Mein Problem: Ich bin kein Informatiker, froh überhaupt C zu 
beherrschen, wie ich es beherrsche, kann überhaupt und gar kein ASM und 
bin daher bestimmt auch nicht der Bestgeeignetste, um am GCC 
rumzuspielen...

Ich bin naiver Maschinenbauer der "eure" Tools verwendet und verstehen 
möchte, warum sie so funktionieren, wie sie es tun. Daher vielen Dank 
für die vielen Rückmeldungen, die erklären, warum das der Status-Quo 
ist.
Meine Vermutung, dass man das auch noch besser machen könnte, ist ja 
durch die eine oder andere Rückmeldung auch bestätigt worden. Habe viel 
dazu gelernt, auch wenn mir natürlich klar war/ist, dass in C beim 
Dividieren von Ganzzahlen die Nachkommastellen wegfallen...

Dennoch möchte ich euch in einem Punkt wiedersprechen:

Karl heinz Buchegger schrieb:
> Dies
> deshalb weil es aufwändiger ist als das ganz banale Dividieren aber
> damit realisierbar!

EBEN NICHT! Zumindest nicht in meinem speziellen Fall. Und ich rede 
nicht von 1-2 Bytes. Sondern von geschätzten 20% der 2KB, die ich hab 
(ist allerdings mehr als eine Division...)! Und schneller und genauer 
ist es auch noch.

Daher sollte man beim AVR-GCC nicht von einer geschickten Übersetzung 
des Compilers ausgehen und hier Engpässe gezielt suchen. Hätte ich das 
gewußt, hätte ich mir ein paar Stunden Suchen, Umprogrammieren & 
Debuggen sparen können. Habe die Engpässe erstmal ganz woanders gesucht.

Ein Grund ein vor ein paar Tagen gemachten Post nochmal auszugraben:

Beitrag "Re: AVR-Studio - Code Größe anzeigen"
Beitrag "Re: AVR-Studio - Code Größe anzeigen"

Dieser Artikel zur Code-Optimierung gehört geschlossen oder (besser) 
kritisch gereviewt.

Ich hatte im Betreff eine Frage gestellt: Die muss man doch bejahen, 
oder?

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:

> Daher sollte man beim AVR-GCC nicht von einer geschickten Übersetzung
> des Compilers ausgehen und hier Engpässe gezielt suchen.

Dies gilt beileibe nicht nur für GCC. Jeder Compiler hat seine 
Schwächen. Wenn man Engpässe hat, ob in Performance oder Platz, dann ist 
es durchaus lohnend, sich den erzeugten Code mal anzusehen. Bei avr-gcc 
im Mapfile, um die Klöpse zu finden, und im LSS-File, um bekannte 
performancekritische Codestellen zu kontrollieren.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> Ich hatte im Betreff eine Frage gestellt: Die muss man doch bejahen,
> oder?

Verneinen natürlich...

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:

> Verneinen natürlich...

Die korrekte Antwort ist: JEIN, oder auf Neudeutsch: "it depends".

Wenn dir dieser Antwortstil nicht so liegt ;-), dann ist dir vielleicht 
der lieber: Er optimiert bestimmte Operationen mit bestimmten Datentypen 
und bestimmter Optimierungseinstellung nicht so wie man es gerne hätte.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:
> Regler schrieb:
>
>> Daher sollte man beim AVR-GCC nicht von einer geschickten Übersetzung
>> des Compilers ausgehen und hier Engpässe gezielt suchen.
>
> Dies gilt beileibe nicht nur für GCC. Jeder Compiler hat seine
> Schwächen. Wenn man Engpässe hat, ob in Performance oder Platz, dann ist
> es durchaus lohnend, sich den erzeugten Code mal anzusehen. Bei avr-gcc
> im Mapfile, um die Klöpse zu finden, und im LSS-File, um bekannte
> performancekritische Codestellen zu kontrollieren.

Ja ist klar. Genau das habe ich gemacht. Nur eben bei den falschen 
Verdächtigen (Programmstruktur, structs, Reihenfolge und Initialisierung 
von Variablen, etc...)

Ich glaube ich habe mich oben zu undeutlich ausgedrückt: Mit "hier" 
meinte ich die Division von ganzen Zahlen durch Konstante Ausdrücke 2^n.

Da habe ich dem oft gehörten Argument geglaubt: Das optimiert der 
Compiler schon von alleine, wenn es was bringt.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:

> Ich glaube ich habe mich oben zu undeutlich ausgedrückt: Mit "hier"
> meinte ich die Division von ganzen Zahlen durch Konstante Ausdrücke 2^n.

Dann zeig doch mal den konkreten Code.

> Da habe ich dem oft gehörten Argument geglaubt: Das optimiert der
> Compiler schon von alleine, wenn es was bringt.

Und dabei sollte es auch bleiben. Derartige Kleinoptimierungen
machen die Compiler wenn es möglich ist (und sie natürlich eine
 Optimierung dafür mithaben :-)
bringen in den seltensten Fällen den ganz großen Durchbruch.


Insbesonders letzteres sollte nicht unterschätzt werden.


Für den Programmierer sollte die Maxime gelten:
Ich benutze die Operation, die in der vorliegenden Situation der 
Problemstellung angemessen ist. Wenn es Division ist, dann ist das 
Division; wenn es Schieben ist, dann ist das Schieben.


Das man davon in Einzelfällen abweichen kann, weil es extrem gute Gründe 
dafür gibt, sollte klar sein. Auch in der Programmierung gibt es keine 
Dogmen, die man nicht in Frage stellen darf. In wohl keinem anderen 
technischen Bereich gibt es soviele 'Prinzipien', die man bei Bedarf 
auch über den Haufen schmeissen darf und manchmal auch muss. Gerade in 
der Programmierung ist nichts so hinderlich wie eine 
Glaubenskongragation, auch wenn ihre Grundregeln einen an die Hand 
nehmen und zu einer ersten vernünftigen Lösung führen, die sehr oft gut 
genug ist. Und das langt dann auch meistens schon.
Diese Grundregeln haben schon ihren Sinn und ihre Berechtigung. Zb das 
berühmte GOTO. Für einen Neuling sollte gelten "Finger weg". Denn die 
Alternative, wenn man das in den ersten 1 bis 2 Jahren nicht konsequent 
bestraft ist meistens Spaghetticode. Und zwar von der üblen Sorte. Hat 
man dann Erfahrung und denkt bei Schleife nicht automatisch an "ich muss 
dorthin springen" oder "ein goto wäre jetzt was feines" sondern denkt 
man automtisch in strukturierten Gebilden, dann verliert der GOTO ganz 
automatisch sein Nichtverwendungsdogma und man kann ab und zu mal einen 
einsetzen, wenn es denn unbedingt sein muss. Die Erfahrung wann und wo 
ein GOTO dann hilfreich sein kann, hat man und damit ist dann das Dogma 
aufgehoben (damit aber keine falschen Vorstellungen aufkommen. Ich war 
15 Jahre in einem Projekt mit ungefähr 2 Millionen Lines of Code - kein 
einziger GOTO)

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:

>> Dies
>> deshalb weil es aufwändiger ist als das ganz banale Dividieren aber
>> damit realisierbar!
>
> EBEN NICHT! Zumindest nicht in meinem speziellen Fall.

Du machst schon wieder den Fehler, von deinem speziellen Fall auf die 
Allgemeinheit zu schliessen.

> Und ich rede
> nicht von 1-2 Bytes. Sondern von geschätzten 20% der 2KB, die ich hab
> (ist allerdings mehr als eine Division...)! Und schneller und genauer
> ist es auch noch.

d.h. du hast ein anderes Ergebnis als bei einer Division rauskommen 
würde?
Dann hast du per Definition keine Division mehr. Zumindest nicht in dem 
Sinne, in dem sie in C verstanden wird.

Autor: Michael Buesch (mb_)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> Karl heinz Buchegger schrieb:
>> Dies
>> deshalb weil es aufwändiger ist als das ganz banale Dividieren aber
>> damit realisierbar!
>
> EBEN NICHT! Zumindest nicht in meinem speziellen Fall. Und ich rede
> nicht von 1-2 Bytes. Sondern von geschätzten 20% der 2KB, die ich hab
> (ist allerdings mehr als eine Division...)! Und schneller und genauer
> ist es auch noch.

Der Binärcode muss sich sowohl mit eingeschalteter Optimierung als auch 
mit abgeschalteter Optimierung identisch verhalten (Bis auf 
Geschwindigkeit und einige wenige Ausnahmen die z.B. auf inline-tricks 
beruhen).

Das ist bei dir nicht gegeben. Dem Compiler ist es natürlich nicht 
gestattet mit -O2 zu einem anderen (wenn auch in deinem Verständnis 
genaueren) Ergebnis zu kommen als mit -O0.

Fakt ist, dass Rechtsshift bei signed-typen nicht das gleiche macht 
wie division. Also darf der Compiler das eine nicht gegen das andere 
austauschen.

Ich denke es empfiehlt dir auch niemand (mit Ahnung von der Materie) bei 
signed typen ein / anstatt von >> zu machen "weil der compiler das 
sowieso optimiert". Er KANN_ es _nicht optimieren, weil es zu einem 
anderen Ergebnis kommt.
Wenn dir irgendjemand so eine Empfehlung gibt, darfst du ihn gerne auf 
seinen Fehler hinweisen. Denn die Empfehlung / anstatt >> zu verwenden 
gilt nur für unsigned Typen.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Och Jungs...  Wollt ihr mich bewußt falsch verstehen? Ich gebe zu, dass 
meine Posts manchmal ein wenig pauschale Aussagen enthalten. Dass man 
die Welt nicht in Schwarz einteilen kann ist mir auch klar. Sorry, bitte 
um etwas Nachsicht.

Ich werde jetzt nicht wieder und wieder meine Aussagen formulieren um 
irgendwelche Spitzfindigkeiten auszuräumen. Bin doch kein Jurist! ;)

> Da habe ich dem oft gehörten Argument geglaubt: Das optimiert der
> Compiler schon von alleine, wenn es was bringt.

Und genau wegen solchen Aussagen habe ich die Engstelle aufwendig 
woanders gesucht. Diese Aussage ist genauso pauschal und falsch wie 
deren Negierung.

Ich versuche es nochmal:

Der Compiler optimiert es wahrscheinlich für unsigned Variablen bis 
16-Bit. Alles andere ist Glücksache und sollte bei Platznot oder zu 
wenig Rechenpower kritisch untersucht werden und zwar nur dann.

Es kann(!) vorkommen, dass der Compiler meint die Implementierung 
mittels Division sei besser. In meinem(!) Fall ist es jedenfalls nicht 
so:
Es ist langsamer UND größer, also bestimmt nicht optimal.

Ein Hinweis im AVR-GCC-Tutorial und sei es in einem Nebensatz, dass dies 
der Fall sein kann(!) oder wenigstens im Artikel im Code-Optimierungs 
wäre wünschenswert.

Karl heinz Buchegger schrieb:
> Und schneller und genauer
>> ist es auch noch.
>
> d.h. du hast ein anderes Ergebnis als bei einer Division rauskommen
> würde?
> Dann hast du per Definition keine Division mehr. Zumindest nicht in dem
> Sinne, in dem sie in C verstanden wird.

Mit "genauer" meinte ich: TROTZ der besseren Flashnutung und 
Performance. Aber man erreicht mittels Schieben und einer bedingten 
Addition bestimmt ein zur C-Division äquivalentes Ergebnis mit ähnlicher 
Performance.

Danke nochmals für Eure Aufklärung!

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:

> Ein Hinweis im AVR-GCC-Tutorial und sei es in einem Nebensatz, dass dies
> der Fall sein kann(!) oder wenigstens im Artikel im Code-Optimierungs
> wäre wünschenswert.

Nur zu. Das ist ein Wiki.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> Och Jungs...  Wollt ihr mich bewußt falsch verstehen?

Nein.
Genausogut könnten wir die Aussage umdrehen.
Willst du uns falsch verstehen, dass man aus einer Schwalbe noch keinen 
Sommer ableiten kann und soll?

>> Da habe ich dem oft gehörten Argument geglaubt: Das optimiert der
>> Compiler schon von alleine, wenn es was bringt.
>
> Und genau wegen solchen Aussagen habe ich die Engstelle aufwendig
> woanders gesucht. Diese Aussage ist genauso pauschal und falsch wie
> deren Negierung.

Genau.
Jetzt sind wir am Kern.
Es gibt kein Patentrezept um Optimierungen anzugehen!

Wenn es eines gäbe, dann würden die Compiler das nämlich für dich 
machen. Jeder Fall ist anders, hat eine andere Umgebung. Was für den 
einen eine Optimierung ist für den anderen eine Pessimierung.


> Der Compiler optimiert es wahrscheinlich für unsigned Variablen bis
> 16-Bit.

Möglich.

> Alles andere ist Glücksache und sollte bei Platznot oder zu
> wenig Rechenpower kritisch untersucht werden und zwar nur dann.

Auf dem gcc.
In der jetzigen Compilerversion.

-> Zustimmung.

> Es kann(!) vorkommen, dass der Compiler meint die Implementierung
> mittels Division sei besser. In meinem(!) Fall ist es jedenfalls nicht
> so:
> Es ist langsamer UND größer, also bestimmt nicht optimal.

Aber: Das was der Compiler macht, entspricht dem wie eine Division in C 
definiert ist. Was man von deiner Version nicht in allen Fällen sagen 
kann.

> Ein Hinweis im AVR-GCC-Tutorial und sei es in einem Nebensatz, dass dies
> der Fall sein kann(!) oder wenigstens im Artikel im Code-Optimierungs
> wäre wünschenswert.

Da würdest du vor lauter Hinweisen den Wald nicht mehr sehen :-)

> Mit "genauer" meinte ich: TROTZ der besseren Flashnutung und
> Performance. Aber man erreicht mittels Schieben und einer bedingten
> Addition bestimmt ein zur C-Division äquivalentes Ergebnis mit ähnlicher
> Performance.

Natürlich.
Ist auch für negative Zahlen und 2-er Potenzen ohne weiteres machbar. 
Nur hatte offenbar bisher noch niemand genug Leidensdruck um eine 
derartige Optimierung in den gcc einzubauen.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael Buesch schrieb:
> Wenn dir irgendjemand so eine Empfehlung gibt, darfst du ihn gerne auf
> seinen Fehler hinweisen. Denn die Empfehlung / anstatt >> zu verwenden
> gilt nur für unsigned Typen.

Genau das war wahrscheinlich das Problem. Im Gegenteil es wurde explizit 
darauf hingewiesen, dass das rechts-Shiften sowohl logisch, als auch 
arithmetisch gemeint sein kann, und das GCC automatisch den 2. Typ 
nimmt, wenn es sich um signed-Variablen handelt, damit es (fast, 
natürlich) einer Division durch 2 entspricht, zumindest bei der 
Verwendung des 2er-Komplements.

Und da habe ich eins und eins (falsch) zusammen gesetzt.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:

> Ist auch für negative Zahlen und 2-er Potenzen ohne weiteres machbar.
> Nur hatte offenbar bisher noch niemand genug Leidensdruck um eine
> derartige Optimierung in den gcc einzubauen.

Für "int" ist sie ja drin und funktioniert auch. In -O1.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:
> Karl heinz Buchegger schrieb:
>
>> Ist auch für negative Zahlen und 2-er Potenzen ohne weiteres machbar.
>> Nur hatte offenbar bisher noch niemand genug Leidensdruck um eine
>> derartige Optimierung in den gcc einzubauen.
>
> Für "int" ist sie ja drin und funktioniert auch. In -O1.

Echt?
<Schmunzel>

Autor: Regler (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ich wollte es mal genau wissen und habe ein kleines Testprogramm 
geschrieben und auf einen uC losgelassen. Siehe Anhang. Wollte eine 
praxisnahe Untersuchung am realen Objekt.

Ein Ausgang wird nach jeweils 100 Berechnungen ein- und ausgeschaltet.

Ein Ausgang wird als PWM genutzt, damit die berechneten Daten einem 
Zweck dienen können und nicht vom Compiler wegoptimiert werden.

Der Algorithmus produziert völligen Blödsinn. Darauf kam es bei der 
Programmierung nicht an. Wichtiger war, dass möglichst nur die Operation 
bzw. der Operator den Unterschied in der Code-Größe und der Performance 
ausmacht.

Ich hoffe das ist mir gelungen, aber schauts euch selbst an. Kritik ist 
willkommen.

Um den Einfluss auf die Code-Größe zu untersuchen, kann man an 
verschiedenen #defines rumspielen:
// Die Anzahl der Funktionsaufrufe
#define COUNT_INIT     100  

// Der Teiler bzw. Shift-Wert
#define TEILER      32
#define SHIFT       5  // = log2(TEILER)

// der zu unteruchende Datentyp
#define test_t       uint8_t  

Die zu untersuchende Funktion muss man auskommentieren (Skripten kann 
ich sowas leider nicht :( ). Es gibt 3 Stück: Eine Dummy-Funktion, eine 
richtige Division und einen (hoffentlich) äquivalent rechnenden Shift:
test_t scale(test_t x, uint8_t y){ 
  
  return(x + y);     
}


test_t scale(test_t x, uint8_t y){ 
  
  return(x / (test_t) TEILER + y);     
}


test_t scale(test_t x, uint8_t y){ 
  
  x = (x >> (test_t) SHIFT);

  if (x < 0)
    return(++x + y);
  else
    return(x + y);
}

Die Addtion soll verhindern, dass die Dummy-Funktion anders als die 
anderen Funktionen behandelt wird, wird aber auch bei allen Operationen 
durchgeführt.

Ich habe einen ATtiny26 ohne HW-Multiplier verwendet. (Den verwende ich 
eh gerade und konnte ihn leicht dafür missbrauchen. Das Programm sollte 
aber leicht an andere uController angepasst werden können.) Die Clock 
soll mit 16MHz laufen. Das kann ich schlecht prüfen, da intern vom PLL 
erzeugt.

Die Fuses (...ist wichtig wegen der PLL-Clock!):
High: 0xF7
Low:  0x71

Ich verwende AVR-GCC 4.3.3. Bei allen Tests wurden 100 Berechnugen 
durchgeführt. Bei allen Test ist der Teiler 32 bzw. der Shift-Operator 5 
oder er wird explizit erwähnt.

1. Test:
Die Compilerschalter (erstmal der default in AVR-Studio):

avr-gcc  -mmcu=attiny26 -Wall -gdwarf-2 -Os -std=gnu99 -funsigned-char 
-funsigned-bitfields -fpack-struct -fshort-enums -MD -MP -MT howfast.o 
-MF dep/howfast.o.d  -c  ../howfast.c

Ergebnisse:

Codegröße in Bytes:
       Dummy  Shift  Division
uint8  106    118    122
int8   106    150    172
uint16 120    140    142
int16  120    190    218
uint32 148    176    178
int32  148    284    296

Dauer in usek (Abgelesen am Oszi):
        Dummy Shift Division
uint8   32    50    110
int8    32    94    700
uint16  38    190    290
int16   38    250    1560
uint32  50    265    460
int32   50    360    4000

Noch keine großen Überraschungen. Das meiste wie erwartet. Der Compiler 
scheint mit der Division von uint wesentlich besser zurechtzukommen.
Signed liegt ihm gar nicht bei der Performance, egal bei welchem 
Datentyp.

Am Interessantesten: Mit den Grundeinstellungen ist die Division dem 
Shift-Operator, auch in der "korrigierenden" Form (...sollte mit der 
Division äquivalent sein) nicht einmal überlegen. Insbesondere bei 
großen Datenwerten ist er ihm hoffnungslos in der Performance 
unterlegen. Der Compiler optimiert bereits mit -Os!

So dann mal aus allen Rohren geschossen:

avr-gcc  -mmcu=attiny26 -Wall -gdwarf-2 -std=gnu99 -Os -funsigned-char 
-funsigned-bitfields -fpack-struct -fshort-enums -ffunction-sections 
-fdata-sections  -ffreestanding  -fno-split-wide-types 
-fno-tree-scev-cprop  -fwhole-program  -fno-inline-small-fu
nctions  -finline-limit=3  -MD -MP -MT howfast.o -MF dep/howfast.o.d  -c 
../howfast.c

Ergebnisse:

Codegröße in Bytes:
       Dummy  Shift  Division
uint8  98     104    104
int8   98     122    156
uint16 102    112    112
int16  102    142    194
uint32 110    124    124
int32  110    186    264

Dauer in usek (Abgelesen am Oszi):
       Dummy Shift Division
uint8  31    50    50
int8   31    93    650
uint16 38    192    192
int16  38    250    1560
uint32 50    270    270
int32  50    360    4000

AHA. Jetzt scheint der Compiler die Vereinfachung mit dem Shift zu 
erkennen (...aber nur bei signed Werten) Performance und Codegröße 
stimmen 1:1 mit dem Shift-Operator überein. Bei unsigned ist er 
weiterhin wesentlich schlechter, insbesondere bei großen Datentypen. Die 
Performance wird beim Shiften kaum verändert, die Code-Größe profitiert 
immer.

Wollte zu dem Zeitpunkt eigentlich schon ins Bett gehen, aber die 
Neugier war größer und ich musste nochmal an der "Stellschraube" Teiler 
drehen:

Daher habe ich die 16-Bit nochmal durch 8192 geteilt bzw um 13 
geschiftet:

Codegröße in Bytes:
        Shift     Division
uint16  112       112
int16   94 (!!!)  92 (!!!)

Dauer in usek (Abgelesen am Oszi):
        Shift     Division
uint16  69        69
int16   25 (!!!)  19 (!!!)

Hier scheint der Compiler noch was ganz ausgefuchstes gefunden zu haben. 
Das Programm läuft auf einmal SCHNELLER als mit der Dummy-Funktion!!! 
Bei signed-Werten!!! Den Trick würde ich gerne nachvollziehen können. 
Bei signed Werten bleibt die Performance bei beiden Versionen gleich, 
ist aber besser als beim Teilen durch 32 (was ja auch logisch ist.)

Mich hat interessiert bei welcher Division dieser Turbo eintritt, und 
habe daher für den speziellen Fall int16 nochmal genau untersucht. Habe 
rausgefunden, dass dies überhaupt nichts mit den Shift-Geschichten zu 
tun hat, sondern, dass der Effekt ab einem Teiler 4352 (=4096+256) 
auftritt. Also auch für 4353, 4354, ...
Hier wird also ein anderer, mir unbekannter Trick verwendet.

Als Fazit würde ich vorläufig mal festhalten:

- Die Performance und Kompaktheit der "Division mit Shift" ist sehr oft 
gleichwertig oder besser als bei der "richtigen" Division .

- Die Optimierung "Division durch Shift" wird auch bei signed-Werten 
werten in den Grundeinstellungen von AVR-Studio nicht durchgeführt. 
Allerdings mit ein paar zusätzlichen Schaltern.

-Bei sehr großen Teiler gibts anscheinend einen Trick, der die 
Performance des Dividierens wieder sehr stark (fast 100-fach!) steigern 
kann, und zwar UNABHÄNGIG davon, ob der Teiler eine Potenz von 2 ist.

Viele Vermutungen und Aussagen weiter oben im Thread bestätigt. Einige 
neue Fragen. So ich gehe jetzt mal lieber schlafen....

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:

> Division äquivalent sein) nicht einmal überlegen. Insbesondere bei
> großen Datenwerten ist er ihm hoffnungslos in der Performance
> unterlegen. Der Compiler optimiert bereits mit -Os!

Nur zur Erinnerung: -Os optimiert auf Grösse, nicht auf Laufzeit. Bei 
Laufzeit wäre -O1 angebrachter.

> Bei signed-Werten!!! Den Trick würde ich gerne nachvollziehen können.

Der erzeugte Code wäre interessant.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:
> Nur zur Erinnerung: -Os optimiert auf Grösse, nicht auf Laufzeit. Bei
> Laufzeit wäre -O1 angebrachter.

Mich hat ja beides interessiert.

Aber wenn wir fair bleiben wollen, sollte tatsächlich nochmal -01 
untersucht werden. Bitte schön (Teiler: 32, Compiler-Flags wie oben 
1.Test nur mit -01):

Ergebnisse:

Codegröße in Bytes:
       Dummy  Shift  Division
uint8  172    178    178
int8   172    188    188
uint16 188    204    204
int16  188    230    216
uint32 220    124    236
int32  220    306    352

Dauer in usek (Abgelesen am Oszi):
       Dummy Shift Division
uint8  94    112    110
int8   94    156    144
uint16 136   186    186
int16  136   220    220
uint32 250   470    470
int32  250   600    4000

Was erkennt man:
- Beim einfachen Dummy-Test versagt die Optimierung -O1, der Code ist 
größer und langsamer (teilweise Faktor: 5!) in allen Disziplinen
- Das Ergebnis bei Division und Shift unterscheiden sich sehr wenig bei 
allen unsigned Werten. Ist sehr gut möglich, dass der Compiler den 
gleichen Algorithmus verwendet. Das Ergebnis ist aber sowohl was die 
Codegröße angeht, als auch bei der Ausführungsgeschwindigkeit dem mit 
-0s erzeugten Code unterlegen und nur marginal schneller.
- Bei signed Werten, greift die Optimierung nur bei int8 und int16. Hier 
kann der Compiler wirklich deutlich bessere Werte bei der Division 
liefern. Interessanterweise besser als mit beim Shiften (was macht der 
wohl anders?).
- Beim Shiften ist der Code oft deutlich LANGSAMER(!), als mit -Os!? 
Hier greift die Compileroptimierung nicht wirklich.
- Bei uint32 int32 findet keine Besserung, teilweise eine 
Verschlechterung in beiden Disziplinen statt.

>> Bei signed-Werten!!! Den Trick würde ich gerne nachvollziehen können.
>
> Der erzeugte Code wäre interessant.

Welche Angaben genau fehlen Dir, um den selbst zu erzeugen? Code und 
Compiler-Einstellungen sind doch alle vorhanden bzw. genannt?

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:

> Welche Angaben genau fehlen Dir, um den selbst zu erzeugen? Code und
> Compiler-Einstellungen sind doch alle vorhanden bzw. genannt?

Der exakte Code und der exakte Compiler.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> Welche Angaben genau fehlen Dir, um den selbst zu erzeugen? Code und
> Compiler-Einstellungen sind doch alle vorhanden bzw. genannt?
Gemeint ist wohl das lss File.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:

> Der exakte Code und der exakte Compiler.

Soll heissen: Dort wo ich das i.d.R. untersuche habe ich nicht diese 
Version des Compilers zur Verfügung.

Ergo: Das LSS-File der betreffenden Codevariante(n) ist der einfachste 
Weg.

Autor: Regler (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Habt ihr keine Kommentare? Schade? Ich finde die Ergebnisse schon 
teilweise etwas überraschend...

Code, Compiler und Flags sind übrigens oben alle genannt.

Habe den Code aber nochmal überarbeitet, so dass sich die Funktion jetzt 
über ein Define verändern lässt. Ist zusammen mit 2 lss files angehängt: 
Einmal Teiler 8192 und der erstaunlich kleinen Code-Größe & einmal mit 
Teiler 4096 der "normale" Code.

Nochmal: Das Ergebnis ist auch so gut, wenn der Teiler =4500 oder =4501 
ist.

Hat jemand eine Idee, wie der Compiler das macht? Also dass er mit 
Division  schneller arbeitet und kompakteren Code erzeugt, als ohne (= 
Dummy-Funktion). Ich kann das anhand der Listings leider nicht 
nachvollziehen.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tja, immer schön auf den dummen Optimizer schimpfen aber dann über 
dessen Intelligenz stolpern. Das kommt davon wenn man unsinnigen Code 
schreibt und der Compiler das merkt. ;-)

int16_t temp = 0xABCDEF01; // = 0xEF01 = -4351;

Nach der ersten Division durch 8192 ist temp im Bereich 0..100 und daran 
wird sich auch nichts mehr ändern. Was der Compiler merkt und folglich 
den Funktionsaufruf komplett rauswirft und an der einzig verwendeten 
Stelle durch 0 ersetzt. Einer Stelle, an der die Addition nichts ändert.

Hand auf's Herz: Hätte jemand anders dir diesen Code vorgesetzt, hättest 
du das gemerkt?

Autor: Michael Buesch (mb_)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> Habt ihr keine Kommentare? Schade? Ich finde die Ergebnisse schon
> teilweise etwas überraschend...

Da ist überhaupt nichts überraschendes dran. Lies den assembly code 
(wenn du es nicht kannst, dann lerne es). Das erklärt mehr als 1000 
Worte.
AVR assembly ist so einfach, das lernt man in ein paar Stunden 
(zumindest soweit, dass man listings lesen und verstehen kann).

Aber nur mal so als Hinweis: Der Optimizer kennt die Konstante und 
schmeißt die Berechnung komplett raus.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:
> Tja, immer schön auf den dummen Optimizer schimpfen ...

Wo? Ich hatte nur die Frage gestellt, ob das Gerücht bzgl. Division 
durch 2-er Potenzen stimmt. Und in welchen Fällen. Das hat der Test mAn 
deutlich machen können.

Der GCC ist toll, genau wie seine Entwickler. Und weil ich eben glaube, 
dass alles mehr oder weniger sinnvollerweise so ist wie es ist und die 
Entwickler auf jeden Fall mehr als ich vom Thema verstehen, will ich 
verstehen warum genau und frag nach. Das soll nichts(!) mit "schimpfen" 
zu tun haben. Nur mit Wissenshunger, Interesse... Und dass ich kritisch 
Hinterfrage bzw. dabei nicht immer den neutralsten Ton treffe, liegt 
halt in meinem Naturell. Ist das jetzt soooo schlimm?

> Das kommt davon wenn man unsinnigen Code
> schreibt und der Compiler das merkt. ;-)

AAARRRRGGGGHHHHH! GENAU(!) sowas wollte ich eigentlich verhindern.

> int16_t temp = 0xABCDEF01; // = 0xEF01 = -4351;
>
> Nach der ersten Division durch 8192 ist temp 0 und daran wird sich auch
> nichts mehr ändern. Was der Compiler merkt und folglich den
> Funktionsaufruf komplett rauswirft und durch 0 ersetzt.
>
> Die Addition hilft dir auch nicht, denn 0 zu addieren ändert nix und nur
> mit counter==0 wird PWMVALUE gesetzt.

Okay! Daher weht der Wind... Das erklärt die unglaubliche Performance. 
Hatte das auch schon vermutet. Aber ein Glück tritt der Fehler erst bei 
hohen Werten für den Teiler auf, so dass die Ergebnisse der 3 Tests 
trotzdem brauchbar sein sollten. Vielleicht sollte man mit temp mit 
randn() initialisieren. Dann hat der Compiler keine Chance das 
wegzuoptimieren, oder?

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:
> Hand auf's Herz: Hätte jemand anders dir diesen Code vorgesetzt, hättest
> du das gemerkt?

Natürlich nicht! Wie gesagt: Respekt vor Leuten die Code schreiben, der 
sowas erkennt und wegoptimiert.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael Buesch schrieb:
> Lies den assembly code
> (wenn du es nicht kannst, dann lerne es). Das erklärt mehr als 1000
> Worte.
> AVR assembly ist so einfach, das lernt man in ein paar Stunden

Gibts da ein gutes Tutorial, wie man eine lss auseinandernimmt? Würde 
das wirklich gerne beherrschen.... Oder meinst Du, ich sollte das 
AVR-Tutorial durcharbeiten, um die lss dateien zu verstehen?

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:

> Hatte das auch schon vermutet. Aber ein Glück tritt der Fehler erst bei
> hohen Werten für den Teiler auf, so dass die Ergebnisse der 3 Tests
> trotzdem brauchbar sein sollten.

Ich würde nicht drauf wetten, dass genau das rauskommt, was du dir dabei 
gedacht hast. Besser wär's, die Berechnungsfunktionen in ein separates 
Quellfile auszulagern und kein -fwhole-program verwenden - damit er 
deren Inhalt an der verwendeten Stelle nicht kennt. Das Ergebnis in 
jeder Iteration in was volatilem abzuladen. Und nicht mit einer dem 
Compiler bekannten Konstante zu beginnen.

Autor: Tezet (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> Hier scheint der Compiler noch was ganz ausgefuchstes gefunden zu haben.

uint16 besteht ja aus 2 Bytes. Wenn Du also diese 2 Bytes 8 mal nach 
rechts schiebst, dann kannst Du gleich das obere Byte nach unten 
kopieren und dann das obere Byte löschen.

Beispiel:
- 9 mal schieben
- oberes Byte runterkopieren, oberes Byte löschen, unteres einmal 
schieben

Das kommt aufs gleiche raus (Nimm ein kariertes Papier und schu selbst)

Übrigens:
uint32 und 17 mal schieben ....

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:

> halt in meinem Naturell. Ist das jetzt soooo schlimm?

Nö, ist es nicht. Nur solltest du dann auch damit klar kommen, wenn 
andere Leute dir in ähnlichem Stil antworten. ;-)

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tezet schrieb:
> Regler schrieb:
>> Hier scheint der Compiler noch was ganz ausgefuchstes gefunden zu haben.
>
> uint16 besteht ja aus 2 Bytes. Wenn Du also diese 2 Bytes 8 mal nach
> rechts schiebst, dann kannst Du gleich das obere Byte nach unten
> kopieren und dann das obere Byte löschen.
>
> Beispiel:
> - 9 mal schieben
> - oberes Byte runterkopieren, oberes Byte löschen, unteres einmal
> schieben
>
> Das kommt aufs gleiche raus (Nimm ein kariertes Papier und schu selbst)
>
> Übrigens:
> uint32 und 17 mal schieben ....

NEEEE! Echt?

Sooooo und jetzt rat mal warum ich bei den Test um 5 & 13 geschoben 
habe. ;)

Autor: Michael Buesch (mb_)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> Michael Buesch schrieb:
>> Lies den assembly code
>> (wenn du es nicht kannst, dann lerne es). Das erklärt mehr als 1000
>> Worte.
>> AVR assembly ist so einfach, das lernt man in ein paar Stunden
>
> Gibts da ein gutes Tutorial, wie man eine lss auseinandernimmt? Würde
> das wirklich gerne beherrschen.... Oder meinst Du, ich sollte das
> AVR-Tutorial durcharbeiten, um die lss dateien zu verstehen?

Also ich würde einfach die Dokumentation über den AVR Instruktionssatz 
lesen. Es gibt nicht viele Instruktionen (=> RISC) und sehr viele davon 
werden nur sehr sehr selten gebraucht. Ich würde mal annehmen, dass 
Kenntnis über die 10-15 häufigsten Instruktionen ausreichen um den 
meisten assemblycode zu verstehen.

Einfach mal in den assembly code (listing file) gucken. Wenn dann dort 
eine Instruktion ist die du noch nicht kennst (das wird wohl gleich die 
erste sein ;)), dann diese einfach nachschlagen. Wenn du sie verstanden 
hast, dann weiter zur nächsten.. usw... Du wirst sehr schnell bemerken, 
dass sich Instruktionen wiederholen.

Es gibt natürlich auch unzählige AVR assembly tutorials. Wenn dir sowas 
besser gefällt, einfach mal googlen.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:

> Gibts da ein gutes Tutorial, wie man eine lss auseinandernimmt?

AVR Assembler lesen lernen.

Würde ich für solche Experimente dringend empfehlen, denn bei derartigem 
Testcode sollte man immer in der Lage sein, festzustellen, ob einen der 
Compiler auf den Arm nimmt.

Autor: Michael Buesch (mb_)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Und, btw, hättest du in der Zeit in der du hier diese ganzen mehr oder 
weniger trivialen Dinge gefragt hast AVR assembly gelernt, könntest du 
es jetzt und könntest dir deine Fragen spielend selbst beantworten.
Ist nicht böse gemeint, ist aber Fakt. ;)

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael Buesch schrieb:
> t und könntest dir deine Fragen spielend selbst beantworten.

Bestimmt bei manchen, aber nicht allen Fragen....

Habe viel dazugelernt, auch so. Danke.

Autor: Tezet (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> NEEEE! Echt?
>
> Sooooo und jetzt rat mal warum ich bei den Test um 5 & 13 geschoben
> habe. ;)

Dein Ton gefällt mir nicht! Du bittest die Leute hier um Hilfe - wegen 
Deiner mangelnden Kenntnisse und es ist menschlich sinnvoller, sachlich 
zu bleiben. OK?

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tezet schrieb:
> Dein Ton gefällt mir nicht! Du bittest die Leute hier um Hilfe - wegen
> Deiner mangelnden Kenntnisse und es ist menschlich sinnvoller, sachlich
> zu bleiben. OK?

Sorry, war nicht böse gemeint. Brauche aber auch wirklich kein 
Karo-Papier um mir Bitschiebereien vorzustellen.... ;). Vielleicht kam 
es aber so rüber.

(Bin zwar kein Informatiker, aber versteh schon etwas von der Materie. 
Sowas wie logischer Entwurf, Rechnertechnologie und C sollten auch 
Maschbauer inzwischen können. So Themen wie Compiler und ASM sind neu 
für mich, ja.)

Deine Antwort war leider keine Erklärung für das beobachtete Verhalten, 
und, sorry, eher trivialer Natur. Da neige ich manchmal zu etwas Ironie.

Schau Dir bitte die Ergebnisse genau an. Das Verhalten war für ALLE 
Teiler ab einem gewissen Wert zu beobachten, unabhängig von 
irgendwelchen Bitschiebereien. Daher war deine Antwort offensichtlich 
keine plausible Erklärung.

Wenn du wirklich helfen willst, (könnte es aber nachvollziehen, falls 
nicht) es gibt noch einige offene Fragen. Auch bin ich für Vorschläge im 
Sinne der Selbsthilfe immer dankbar.

Wollte Dir aber wirklich nicht auf den Schlipps treten. Nicht beleidigt 
sein.

Autor: avion23 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi Regler,
der Ton ist etwas grob hier. Hängt damit zusammen, dass viele 
Fragesteller Idioten sind.

Den von dir beobachteten Effekt habe ich schon öfters beobachtet. Das 
hat bei mir dazu geführt, dass ich inzwischen immer shifte, wenn es 
irgendwie möglich ist. Ich weiß, dass man nicht vorzeitig optimieren 
soll usw. Und ich mache es trotzdem.

Also vielen Dank für die von dir gemachten Untersuchungen.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
avion23 schrieb:
> Hi Regler,
> der Ton ist etwas grob hier.

Da kann ich mit Leben. Solange derjenige nicht nur grob ist, sondern 
auch was konstruktives beiträgt...

> Hängt damit zusammen, dass viele
> Fragesteller Idioten sind.

Danke. ;) Nein im Ernst: Kann ich nachvollziehen, da ich auch Artikel 
alla "Obi irgendwas" kenne und auch kommentiert habe.

Mag halt eben nicht für genau einen solchen gehalten werden, nur weil 
ich keine Compiler entwickle oder ASM-Hacker bin. Glaube auch, dass 
nicht alles was ich hier von mir gebe darauf hinweist.

> Den von dir beobachteten Effekt habe ich schon öfters beobachtet. Das
> hat bei mir dazu geführt, dass ich inzwischen immer shifte, wenn es
> irgendwie möglich ist. Ich weiß, dass man nicht vorzeitig optimieren
> soll usw. Und ich mache es trotzdem.

Mein Fazit aus diesem Thread und meinen Untersuchungen ist auch ein 
Ähnliches. Ich werde mir nochmal überlegen, ob man dass nicht geschickt 
mit einer Bibliothek erschlagen kann. Damit alles übersichtlich bleibt.

Manche können nicht nachvollziehen, dass man mit einem uC auch mal 
richtig rechnen können muss bzw. will. Gerade weil viele Anwendungen 
nicht gleich einen DSP benötigen, zumindest nicht, wenn man nicht vor 
Festkommarechnungen und ein paar Überlegungen zum Thema Wortbreite und 
Filterlängen zurückschreckt. Oder halt wie man durch 2^n am 
geschicktesten teilt. Dass man bei Serien >10 000 wegen ein paar Zeilen 
Code nicht einfach den nächstgrößeren Chip nehmen kann, können wohl 
viele bestätigen.

Ich kenn jemand, der hat einem deutschen Autohersteller etliche 
100Tausend Euro einsparen können, weil er ein paar Schraube erfolgreich 
wegoptimieren konnte. Bei Serien jenseits der Millionen sind auch 1/10 
Cent VIEL.

Optimalerweise ist der Füllstand des Flashs 95%, sonst kann er als 
überdimensioniert angesehen werden.

> Also vielen Dank für die von dir gemachten Untersuchungen.

Bitte! Gerne geschehen. Du bist übrigens der Erste! ;)

Autor: Markus J. (markusj)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Habt ihr auch Mal nachgerechnet was euer Code macht? Wenn ihr damit 
leben könnt, dass -1 durch durch 2^X immer -1 ergibt ... gut, dann viel 
Spaß, aber dieses Verhalten ist NICHT korrekt und entspricht NICHT dem 
Standard. Wer eine eigene Algebra möchte darf sich nicht darüber 
wundern, dass der Compiler diese nicht von Haus aus kennt.

1110 (-2) und 1111 (-1) >> 1 = 1111 (-1)
-1 / 2 = 0 Rest -1 und nicht -1

Der Additionstrick (+2) funktioniert auch nicht:
1110 (-4 + 2) und 1111 (-3 + 2) >> 1 = 1111 (-1)
-4 / 2 = 1 Rest 0 und nicht -1

Übrigens: Ihr solltet dennoch shiften können, wenn ihr einfach vorher 
und hinterher das Vorzeichen korrigiert ... (wenn vorher negativ und 
hinterher ungleich Null, dann wieder negieren)

mfG
Markus

Autor: Michael Buesch (mb_)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
avion23 schrieb:
> Den von dir beobachteten Effekt habe ich schon öfters beobachtet. Das
> hat bei mir dazu geführt, dass ich inzwischen immer shifte, wenn es
> irgendwie möglich ist. Ich weiß, dass man nicht vorzeitig optimieren
> soll usw. Und ich mache es trotzdem.

Das muss man nur machen, wenn man nicht verstanden hat was eine 
Integerdivision (nach C Standard) ist.

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:

> Nur zur Erinnerung: -Os optimiert auf Grösse, nicht auf Laufzeit. Bei
> Laufzeit wäre -O1 angebrachter.

Nö, eher -O2 oder -O3.  -Os ist "mehr" als -O1, denn es werden alle
Optimierungen aus Stufe 2 zusätzlich hinzu gezogen, die (normaler-
weise ;-) den Code nicht vergrößern.

-O3 ist extrem aggressiv auf Geschwindigkeit getrimmt.  Wenn man noch
viel Platz im Controller hat, kann man das spaßeshalber ausprobieren.
Meist holt der Compiler dann gegenüber -Os/-O2 (die beim AVR kaum
einen nennenswerten Unterschied bringen) nochmal an die 10 % an
Geschwindigkeit raus.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus J. schrieb:
> Habt ihr auch Mal nachgerechnet was euer Code macht? Wenn ihr damit
> leben könnt, dass -1 durch durch 2^X immer -1 ergibt ... gut, dann viel
> Spaß, aber dieses Verhalten ist NICHT korrekt und entspricht NICHT dem
> Standard. Wer eine eigene Algebra möchte darf sich nicht darüber
> wundern, dass der Compiler diese nicht von Haus aus kennt.
>
> 1110 (-2) und 1111 (-1) >> 1 = 1111 (-1)
> -1 / 2 = 0 Rest -1 und nicht -1

Upps. Da habe ich mich wohl vertan. Mann, mann, mann. Peinlich, 
peinlich. Danke fürs nicht dumm sterben lassen. Ich glaube zwar nicht 
dass dieser Fehler bei der Berechnung eine große Rolle spielt, und daher 
keinen großen
Schaden anrichtet, sonst hätte ich ihn bemerkt. Aber wenn man 
vergleichen will, dann nicht Äpfel mit Birnen. Interessant, dass du der 
erste bist, der mich darauf hinweist. Nochmal Danke.

Hatte die Idee irgendwo gelesen und nachprogrammmiert. War halt spät. 
Verwende eh eine andere Version (s.g.o.), die aber auch nicht richtig 
rundet. Das erklärt die ganze Geschichte bzw. Ergebnisse. Hätte mich 
auch gewundert...

> Der Additionstrick (+2) funktioniert auch nicht:
> 1110 (-4 + 2) und 1111 (-3 + 2) >> 1 = 1111 (-1)

Warum 2 Addieren, wenn um 1 Shiften? Aber vom Prinzip her: klar!

> -4 / 2 = 1 Rest 0 und nicht -1

Häh?

Jetzt würde ich gerne die obigen Tests wiederholen, aber mit einem 
richtig rechnenden Algorithmus. Aber: ich stehe gerade auf dem Schlauch. 
Was Du meintest mit:

> Übrigens: Ihr solltet dennoch shiften können, wenn ihr einfach vorher
> und hinterher das Vorzeichen korrigiert ... (wenn vorher negativ und
> hinterher ungleich Null, dann wieder negieren)

Warum das? Werde mal schauen, was Knut vorschlägt.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn ich jetzt nicht wieder falsch liege müsste dieser Algorithmus das 
richtige liefern:

test_t scale(test_t x){ 
  
  if (x < 0)
     x += TEILER - 1;
  
  return(x >> (test_t) SHIFT);
}

Autor: Markus J. (markusj)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
>> Der Additionstrick (+2) funktioniert auch nicht:
>> 1110 (-4 + 2) und 1111 (-3 + 2) >> 1 = 1111 (-1)
>
> Warum 2 Addieren, wenn um 1 Shiften? Aber vom Prinzip her: klar!

Pardon, du hattest in deinem ersten Beitrag um zwei geshiftet, meine 
Rechnung entspricht dem also nicht.

Dein neuer Code:
SHIFT = 1, TEILER = 2 (richtig so?)
-1: 1111 -> 0000 >> 1 = 0000 (korrekt)
-2: 1110 -> 1111 >> 1 = 1111 (korrekt)
-3: 1101 -> 1110 >> 1 = 1111 (korrekt)
-4: 1100 -> 1101 >> 1 = 1110 (korrekt)

Der Sonderfall ist abgedeckt, der Code sollte so korrekt funktionieren, 
zumindest fällt mir auf die schnelle kein Problem auf.

mfG
Markus

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hier die Testergebnisse:
Codegröße in Byte:
    -Os  -O1  -alle
u8  118  178  104
i8  140  188  118
u16 140  204  112
i16 152  214  120
u32 176  236  124
i32 194  242  136

Dauer in us:
    -Os  -O1  -alle
u8  50   112  50
i8  88   144  88
u16 195  188  195
i16 210  218  210
u32 265  470  270
i32 280  450  270


JA. Ich hätte den Test nochmal umschreiben sollen, ABER:
 - Alle obigen Testergebnisse wären dann nicht mehr vergleichbar 
gewesen.
 - Der Compiler hat ja bei äquivalenter Rechnung (die jetzt hoffentlich 
gegeben ist), die gleich Chance den Code zu optimieren. Daher sollten 
volatile, externe Files oder randn()zum initialisieren, zwar eine 
quantative Ermittlung wesentlich besser ermöglichen, mir geht es aber 
eher um eine qualitative Aussage. Anderer Code liefert wieder andere 
Bedingungen und daher andere quantitativen Ergebnisse. Daher sind die 
quanitativen Betrachtungen eher weniger interessant.
- Mich interessiert eher die Frage: Sollte man Shiften, statt 
dividieren, weil es was bringt?
 - Die Resonanz spiegelt eher wenig Interesse des Forums an den 
Ergebnissen, daher habe ich auch wenig Lust dazu.
- Außerdem sehe ich mich nicht in der Lage, den Code 100%ig so zu 
schreiben, dass ich einen erneuten Fehler ausschließen kann.

Für mich steht jetzt erstmal soweit fest:

- Vorsicht bei Division mit 32-Bit werten, auch bei 2^n. Kann dauern, 
insbesondere bei signed.

- Der Shift-Operator alleine liefert fast die gleichen Ergebnisse, nur 
die Rundung läuft in die andere Richtungen bei negativen Zahlen. Daher 
Vorsicht, wenn der Algorithmus eine symmetrische Rundung erfordert. Er 
ist auf jeden Fall wesentlich schneller und effizienter...

- Selbst wenn man diesen Fehler korrigiert, ist der Code besser oder 
gleichwertig, als bei der richtigen Division durch 2^n, insbesondere bei 
signed kann viel rausgeholt werden.

- Die Ergebnisse der default Konfiguration in AVR-Studio kann man stark 
verbessern durch ein paar zusätzliche Schalter.

Autor: Michael Buesch (mb_)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> Hier die Testergebnisse:
> Codegröße in Byte:
>     -Os  -O1  -alle
> u8  118  178  104
> i8  140  188  118
> u16 140  204  112
> i16 152  214  120
> u32 176  236  124
> i32 194  242  136
>
> Dauer in us:
>     -Os  -O1  -alle
> u8  50   112  50
> i8  88   144  88
> u16 195  188  195
> i16 210  218  210
> u32 265  470  270
> i32 280  450  270
>
>
> JA. Ich hätte den Test nochmal umschreiben sollen, ABER:
>  - Alle obigen Testergebnisse wären dann nicht mehr vergleichbar
> gewesen.
>  - Der Compiler hat ja bei äquivalenter Rechnung (die jetzt hoffentlich
> gegeben ist), die gleich Chance den Code zu optimieren. Daher sollten
> volatile, externe Files oder randn()zum initialisieren, zwar eine
> quantative Ermittlung wesentlich besser ermöglichen, mir geht es aber
> eher um eine qualitative Aussage. Anderer Code liefert wieder andere
> Bedingungen und daher andere quantitativen Ergebnisse. Daher sind die
> quanitativen Betrachtungen eher weniger interessant.

Tut mir leid, aber das ist doch alles snakeoil.
Wenn der compiler die Konstante kennt ist das ganze komplett Witzlos.
Dann misst du dir im besten Fall vielleicht wie schnell dein controller 
ein bit in einer Schleife togglen kann.

>  - Die Resonanz spiegelt eher wenig Interesse des Forums an den
> Ergebnissen, daher habe ich auch wenig Lust dazu.

Weil die "Ergebnisse" absolut nutzlos sind. Und das gerade mit fehlendem 
assembly code. Wenn du nicht prüfst was der Compiler überhaupt gemacht 
hat, dann misst du irgendwas, aber mit Sicherheit keine Division.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:

> mir geht es aber eher um eine qualitative Aussage.

Eine Analyse eines speziellen unsinnigen Einzelfalls lässt sich ohne 
Kontrolle des erzeugten Codes nicht unbedingt verallgemeinern. 
Vielleicht hast du Glück, vielleicht nicht.

Beispielsweise könnte es immer noch passieren, dass der Compiler die 
ersten N Iterationen separat handhabt, weil er merkt, dass der Wert 
danach 0 bleibt. Also aus einer Schleife 2 macht, die erste mit, die 
zweite ohne Rechnung.

Solche Tipps mit volatile und getrennter Übersetzung stammen schlicht 
aus der Praxis jener, die sich bereits eingehend mit der Problematik 
einzelner isolierter Testcodes beschäftigt haben.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael Buesch schrieb:
> Tut mir leid, aber das ist doch alles snakeoil.
> Wenn der compiler die Konstante kennt ist das ganze komplett Witzlos.
> Dann misst du dir im besten Fall vielleicht wie schnell dein controller
> ein bit in einer Schleife togglen kann.

Hallo? Mal ne Frage: Liest Du auch, was Du zitierst?

Wenn der Compiler sowas wegoptimieren könnte, dann jetzt doch wohl in 
beiden Versionen, oder?

Wie erklärst Du dann die unterschiedlichen Ergebnisse? 4ms verglichen 
mit 270us für das gleiche (!) Ergebnis ist ein Unterschied, selbst wenn 
nur ein bit getoggelt wird!

Die feste Initialisierung soll verhindern, dass unterschiedliche 
Anfangswerte unterschiedliche Laufzeiten erzeugt!

Wer was anderes wissen will kann ja seinen Beispielcode posten. Mich 
würde mal interessieren, ob hier jemand ein Gegenbeispiel liefern kann.

> Weil die "Ergebnisse" absolut nutzlos sind. Und das gerade mit fehlendem
> assembly code. Wenn du nicht prüfst was der Compiler überhaupt gemacht
> hat, dann misst du irgendwas, aber mit Sicherheit keine Division.

Kann dich beruhigen, habe in die Assemblies reingeschaut, mir inzwischen 
auch ein wenig ASM angeeignet und bin mir ziemlich sicher, dass er 
dividiert, da ich den Code auch gedebugt habe.

Wenn Du willst überzeug dich selbst. Code, Compiler, Schalter etc. sind 
alle genannt. Und wenn ich hier alle lss angehängt hätte, hätten mich 
die Moderatoren gesteinigt. Das ist aber auch nicht nötig, wenn man 
selbst AVRGCC hat. Ein File und einen Befehl kopieren ist wohl wirklich 
nicht soviel Arbeit. Also schau doch selbst nach.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:
> Solche Tipps mit volatile und getrennter Übersetzung stammen schlicht
> aus der Praxis jener, die sich bereits eingehend mit der Problematik
> einzelner isolierter Testcodes beschäftigt haben.

Das habe ich gelernt und würde es beim nächsten mal genau so machen. 
Aber alle Test jetzt wiederholen war mir zuviel des guten. Begründung 
s.o..

Autor: Michael Buesch (mb_)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> Michael Buesch schrieb:
>> Tut mir leid, aber das ist doch alles snakeoil.
>> Wenn der compiler die Konstante kennt ist das ganze komplett Witzlos.
>> Dann misst du dir im besten Fall vielleicht wie schnell dein controller
>> ein bit in einer Schleife togglen kann.
>
> Hallo? Mal ne Frage: Liest Du auch, was Du zitierst?
>
> Wenn der Compiler sowas wegoptimieren könnte, dann jetzt doch wohl in
> beiden Versionen, oder?
>
> Wie erklärst Du dann die unterschiedlichen Ergebnisse? 4ms verglichen
> mit 270us für das gleiche (!) Ergebnis ist ein Unterschied, selbst wenn
> nur ein bit getoggelt wird!

Den Unterschied erkläre ich mir gar nicht, weil die Ausgangsituation 
(Optimizer kennt Konstante) schlicht nicht geeignet ist sowas hier zu 
benchmarken.
Und mit einem ungeeigneten Messmittel kann ich mir jedes beliebige 
Ergebnis hinstricken.
Die Messmethode ist das entscheidende Kriterium um ein Messergebnis zu 
beurteilen. Genauso wie Einheiten entscheidend sind um eine Größe 
beurteilen zu können. Wenn du jetzt beispielsweise sagst, dass du 10 
hast und dein Freund nur 5, dann ist das schön und für deinen speziellen 
Fall sicher richtig. Aber daraus zu schließen das 10 immer besser als 5 
sind halte ich für gewagt. Besonders wenn man die Einheit nicht kennt 
oder nennt. ;) Das ist auch der Grund warum diese Gamer-kiddie 
benchmarks nichts taugen. Sie erzeugen irgendeine Zahl, die keine 
Aussage hat. Das gleiche machst du hier.

> Die feste Initialisierung soll verhindern, dass unterschiedliche
> Anfangswerte unterschiedliche Laufzeiten erzeugt!

Feste Initialisierung kann man auch machen ohne das der compiler es als 
Konstante erkennt. Wie das gemacht wird wurde bereits genannt.

> Wer was anderes wissen will kann ja seinen Beispielcode posten. Mich
> würde mal interessieren, ob hier jemand ein Gegenbeispiel liefern kann.
>
>> Weil die "Ergebnisse" absolut nutzlos sind. Und das gerade mit fehlendem
>> assembly code. Wenn du nicht prüfst was der Compiler überhaupt gemacht
>> hat, dann misst du irgendwas, aber mit Sicherheit keine Division.
>
> Kann dich beruhigen, habe in die Assemblies reingeschaut, mir inzwischen
> auch ein wenig ASM angeeignet und bin mir ziemlich sicher, dass er
> dividiert, da ich den Code auch gedebugt habe.
>
> Wenn Du willst überzeug dich selbst. Code, Compiler, Schalter etc. sind
> alle genannt. Und wenn ich hier alle lss angehängt hätte, hätten mich
> die Moderatoren gesteinigt. Das ist aber auch nicht nötig, wenn man
> selbst AVRGCC hat. Ein File und einen Befehl kopieren ist wohl wirklich
> nicht soviel Arbeit. Also schau doch selbst nach.

Darum geht es mir ja gar nicht. Mich interessiert das Ergebnis 
persönlich nicht. Ich will dir nur vermitteln, dass deine Messmethode 
IMO fehlerhaft ist und du somit kein allgemeingültiges Ergebnis bekommen 
kannst.
Du bekommst vielleicht ein Ergebnis was für deinen speziellen Fall 
passt.

Autor: Michael Buesch (mb_)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> A. K. schrieb:
>> Solche Tipps mit volatile und getrennter Übersetzung stammen schlicht
>> aus der Praxis jener, die sich bereits eingehend mit der Problematik
>> einzelner isolierter Testcodes beschäftigt haben.
>
> Das habe ich gelernt und würde es beim nächsten mal genau so machen.
> Aber alle Test jetzt wiederholen war mir zuviel des guten. Begründung
> s.o..

Also du willst tatsächlich deine neuen Ergebnissen mit den alten 
Ergebnissen, die wir vorher schon als eindeutig fehlerhaft entlarvt 
haben vergleichen. Wo das hinführt wirst du selbst sehen. ;)

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael Buesch schrieb:
> Also du willst tatsächlich deine neuen Ergebnissen mit den alten
> Ergebnissen, die wir vorher schon als eindeutig fehlerhaft entlarvt
> haben vergleichen. Wo das hinführt wirst du selbst sehen. ;)

Die waren fehlerhaft für den Shift, ja--> korrigiert mit der letzten 
Messung, da Shift neu geschrieben. Der Rest war identisch.

Der Fehler mit großen Teilern ist weiterhin vorhanden, ja. --> Bei 
Teiler=32 nicht.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael Buesch schrieb:
> Ich will dir nur vermitteln, dass deine Messmethode
> IMO fehlerhaft ist und du somit kein allgemeingültiges Ergebnis bekommen
> kannst.

Es sollte nicht allgemeingültig sein. Aber es gibt Indizien, die man 
beim Coden berücksichtigen kann.

Autor: Regler (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Vielleicht reden wir auch aneinander vorbei:

- Meinst Du mit "Konstante" den Teiler bzw. den Shift? Falls ja, dann 
ist das pure Absicht: Ich will ja sehen, was der Compiler rausholen 
kann, je nach Implementierung, aber bei vorher bekannter Größe. Die 
eigentliche Operation ist ja jetzt identisch für Division und Shift.

- Mir ist auch klar, dass wenn Teiler oder Shift dem Compiler unbekannte 
Variablen wären, die Situation ganz anders aussehen lassen würde. Aber 
das ist bei meinen Anwendungen (Filterbreite, Skalierung...) eher 
weniger der Fall. Da ist selbst das symmetrische Runden oft nicht nötig, 
oder sogar lästig, da "unstetig" um 0.

- Wenn Du aber temp meinst, kann ich deine Argumentation für kleine 
Teiler nicht nachvollziehen. Selbst wenn er die Anfangswerte speichern 
würde (was ich bei 32-Bit für wenig effizient halten würde), kann er das 
unmöglich für viele, viele Schleifen machen. Und da in jeder Schleife 
bis zu 100 addiert werden, kann er die Division auch nicht 
wegoptimieren.

- Und nochmal: Bei gleicher "Berechnung" und unterschiedlicher 
Implementierung hat der Compiler bei beiden Algorithmen die gleich 
Chance unabhängig von der Ausgangsituation.

Habe mal die 2 Fälle Shift und Div mit int32 als lss und den angepassten 
Code angehängt.

Autor: Michael Buesch (mb_)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tja, aber was ist daran jetzt der Erkenntnisgewinn?
Du hast deinen speziellen Fall optimiert. Das ist sehr schön und eine 
gute Leistung. Das ist aber auch schon die ganze Erkenntnis. Jetzt musst 
du nur noch eine konkrete Anwendung finden in dem du diesen speziellen 
Fall in einem richtigen Programm ausnutzen kannst.

Das Ganze ist jetzt ziemlich vom Ursprung weggedriftet, wo es darum ging 
was der gcc optimiert und was nicht. Es ist nämlich jetzt eher eine 
Suche nach Tricks um einen speziellen Algorithmus zu optimieren. Das ist 
ganz normale Entwicklerarbeit. Ich denke es überrascht keinen, dass man 
einen Algorithmus sowohl effizient als auch ineffizient implementieren 
kann.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:

> unmöglich für viele, viele Schleifen machen. Und da in jeder Schleife
> bis zu 100 addiert werden, kann er die Division auch nicht
> wegoptimieren.

Aber nur in jenen Iterationen, in denen 0 addiert wird, wird auch das 
Ergebnis als PWM-Wert genutzt. In den übrigen Fällen füttert die 
Rechnung sich nur selbst. Im Grunde könnte der Compiler die 
überspringen, wenn er das Ergebnis auch ohne kennt.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael Buesch schrieb:
> eine konkrete Anwendung finden in dem du diesen speziellen
> Fall in einem richtigen Programm ausnutzen kannst

Einen Fall für Divisionen durch 2^n? Da fällt mir was ein, habe ich aber 
auch schon genannt.

> Das Ganze ist jetzt ziemlich vom Ursprung weggedriftet, wo es darum ging
> was der gcc optimiert und was nicht.

Und? Tut er's? Nein! Lies halt die Assembly. (Hast Du mir übrigens zu 
geraten.) Es gibt keinen vernünftigen Grund die Division zu verwenden, 
wenn man durch 32 teilt, oder? Die Performance zeigt das. Aber der Code 
machts genau so.

> Im Grunde könnte der Compiler die
> überspringen, wenn er das Ergebnis auch ohne kennt.

Und kennt er's? Nein! Zumindest nicht für kleine Teiler. Also ist es 
egal.

Autor: Michael Buesch (mb_)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dieses Spiel kannst du beliebig weit treiben. Du wirst immer ein 
beliebig komplexes Problem finden was der compiler nicht komplett 
optimieren kann.
Es hat aber auch niemand behauptet, dass dies nicht der Fall ist.

Also um es nochmal zusammenzufassen:

"Optimiert der Compiler Division durch 2^n wirklich?"

Natürlich macht er das. Er macht es halt nicht immer in jedem Fall, 
denn das wäre ziemlich unmöglich.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael Buesch schrieb:
> Natürlich macht er das. Er macht es halt nicht immer in jedem Fall,
> denn das wäre ziemlich unmöglich.

Und ich würde sagen: Verlass Dich nicht drauf. Programmier es als Shift, 
notfalls mit bedingter Addition, aber nur falls nötig (gilt für beide 
Aussagen). Es wird nicht schaden und oft (bei falschen/fehlenden 
Schaltern, signed Werten, Werten > 16 Bit) sehr viel nützen.

Autor: Michael Buesch (mb_)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> Michael Buesch schrieb:
>> Natürlich macht er das. Er macht es halt nicht immer in jedem Fall,
>> denn das wäre ziemlich unmöglich.
>
> Und ich würde sagen: Verlass Dich nicht drauf. Programmier es als Shift,
> notfalls mit bedingter Addition, aber nur falls nötig (gilt für beide
> Aussagen). Es wird nicht schaden und oft (bei falschen/fehlenden
> Schaltern, signed Werten, Werten > 16 Bit) sehr viel nützen.

Und ich würde sagen: Verlass dich nicht drauf. Programmier alles in 
Assembly.
Das ist doch Blödsinn.

Mal ehrlich: Man kann sich in der Praxis auf die Optimierung verlassen, 
wenn man die Spielregeln kennt und beherzigt. Zu diesen Spielregeln 
gehört halt unsigned (Und das ist auch schon so ziemlich alles was man 
wissen muss).

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael Buesch schrieb:

> Mal ehrlich: Man kann sich in der Praxis auf die Optimierung verlassen,
> wenn man die Spielregeln kennt und beherzigt. Zu diesen Spielregeln
> gehört halt unsigned (Und das ist auch schon so ziemlich alles was man
> wissen muss).

In diesem Spiel gibt es keine ehernen Regeln. Wenn man unbedingt die 
Performance rauskitzeln muss, dann hilft nur Kontrolle des erzeugten 
Codes. Auch wenn man die Regeln zu kennen glaubt sollte man ab und zu 
mal reinsehen.

Gottvertrauen ist falsch, manchmal kommt eben doch speiübler Code raus. 
Und dann kann man sich eben entsprechende Anpassung überlegen, wobei das 
eben auch auf Assembler-Code rauslaufen kann, der sich beim GCC besser 
als irgendwo sonst in den normalen Code integrieren lässt.

Das soll jetzt nicht heissen, dass man jeden Code zu Lasten der 
Lesbarkeit mit manueller Optimierung verunstalten sollte.

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael Buesch schrieb:
> die Spielregeln kennt und beherzigt.

Spielregeln? Wo kann man sowas nachlesen? Kenn ich nicht, es sei denn Du 
meinst, dass man sowas wie floats, 64-Bit halt möglichst nicht auf AVRs 
verwendet.

Das man sich auf unsigned Werte beschränken sollte, war mir neu und 
halte ich für "übertrieben". Ohne die Differenz fallen geschätzte 90% 
aller Algorithmen weg. Jeder Regler brauch eine Regeldifferenz...

Willst Du sowas unsigned programmieren? Geht bestimmt, auch wenn ich es 
noch nie gesehen habe, aber mal ehrlich, ist das dann nicht wesentlich 
unleserlicher als ein Shift statt der Division zu verwenden.

Erfahrene Programmierer kennen den Trick eh schon (...wurde uns übrigens 
an der Uni gelehrt, auf uC so zu dividieren!) und erkennen den Shift als 
Division. Für alle anderen: Mit einem Define oder einer Biliothek erhält 
man sich die völlige Transparenz in der Programmierung.

Das es kein Problem ist, die Division durch 2^n auch für signed 
effizient zu realisieren, zeigt die Untersuchung. Und der Compiler 
optimiert das nicht. Und jetzt komm mir bitte nicht mit "beliebig 
komplexen Problem".
Das er es erkennen kann, zeigt er, wenn man den Datentyp ändert.

Und selbst wenn man sich an die Spielregeln hält, muss man darauf achten 
die richtigen Schalter beim Kompilieren genutzt zu haben.

Also ich glaube, du verrennst dich.

Autor: Michael Buesch (mb_)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> Also ich glaube, du verrennst dich.

Hehe. Jedem das was er will.
Alles wurde ausführlich erklärt. Auch warum der Compiler signed 
division nicht als shifts optimiert. Das rolle ich jetzt nicht alles 
nochmal auf, weil es schon dort steht.

Wenn du shiften willst, dann mach es halt. Ich werde es nicht machen wo 
ich weiß, dass der Compiler es richtig macht. Ansonsten könnte ich ja 
auch direkt assembly schreiben um die volle 100% Kontrolle zu haben.

Autor: Markus J. (markusj)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> Erfahrene Programmierer kennen den Trick eh schon (...wurde uns übrigens
> an der Uni gelehrt, auf uC so zu dividieren!) und erkennen den Shift als
> Division. Für alle anderen: Mit einem Define oder einer Biliothek erhält
> man sich die völlige Transparenz in der Programmierung.

Pardon, normalerweise tut man genau das NICHT. Getreu dem Grundsatz, 
dass Code öfters gelesen als geschrieben wird, versucht man ihn 
normalerweise gut Lesbar zu gestalten. Solche (trivialen) Optimierungen 
wie Multiplikation/Division mit Zweierpotenzen überlässt man eigentlich 
dem Compiler, da sie die Lesbarkeit verschlechtern und der Code nicht 
mehr das aussagt was er eigentlich tun soll.

mfG
Markus

Autor: Michael Buesch (mb_)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus J. schrieb:
> ....

Gibs auf. Er wirds nicht verstehen :D

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael Buesch schrieb:
> Alles wurde ausführlich erklärt. Auch warum der Compiler signed
> division nicht als shifts optimiert.

Redet man hier gegen Wände? Oder lest ihr nur jeden 2. Post?
Schau Dir nochmal genau den zuletzt geposteten Code an und dann rechne 
mir mal bitte vor, wo die Shift-Division anders rechnet, als bei der 
richtigen Division, auch bei signed. Dass diese mögliche Optimierung bei 
allen signed nicht gemacht wird und bei unsigned auch nur bei manchen 
Compilereinstellungen, ist anhand der Ergebnisse zumindest sehr 
naheliegend. Ich mache hier den Leuten um AVR-GCC keinen Vorwurf, es ist 
eine einfache Tatsache, mir der jeder Leben muss, der nicht in der Lage 
ist das zu ändern.

Ich halte einen Code, der nicht an den Datentyp oder an die 
Compilereinstellungen angepasst werden muss, um leistungsfähig zu 
übersetzen für portabler und praktischer, als einen, bei dem man sowas 
immer beachten muss, um nicht eine böse Überraschung bei der 
Rechenleistung erleben zu müssen.

> Ich werde es nicht machen wo
> ich weiß, dass der Compiler es richtig macht.

Meinst Du "wo" im Sinne von "kausal" oder "an den Stellen"? Bei ersterer 
Aussage: Genau wegen solchen Aussagen habe ich mich darauf verlassen, 
dass der Compiler das schon optimiert, wenn es geht.
Bei zweiterer: Man kann natürlich nur da den Shift einsetzen, wo eine 
Division kein brauchbares Ergebnis erzeugt. Aber warum nicht von Anfang 
an effizienten Code anlegen und an anderen Stellen optimieren?

Verbreitet bitte weiter das Gerücht, dass der Compiler das schon 
optimiert. Das er das nur bei bestimmten Compilereinstellungen tut und 
auch nur bei bestimmten Datentypen kann, muss man auch nicht immer 
erwähnen, das verwirrt die Anfänger nur.

Markus J. schrieb:
> Pardon, normalerweise tut man genau das NICHT. Getreu dem Grundsatz,
> dass Code öfters gelesen als geschrieben wird, versucht man ihn
> normalerweise gut Lesbar zu gestalten.

Ein Term wie SCALE_ERROR(), CAL_MEAN_OF_INPUTS() oder 
CAL_FILTER_AVERAGE() kann wesentlich mehr aussagen als ein "/i". Aber 
wenn ihr meint...

> Solche (trivialen) Optimierungen
> wie Multiplikation/Division mit Zweierpotenzen überlässt man eigentlich
> dem Compiler,

Eben! Weil es soooo trivial ist und so naheliegend, wundere ich mich ja, 
dass der AVR-GCC das nicht macht und stattdessen eine komplette 
Divisionsroutine in den Code einbaut!
Wenn er es denn immer machen würde, würde ich auch gerne mit der Zahl 
dividieren. Da dies nicht immer der Fall zu sein scheint, mache ich es 
halt nicht mehr im zeitkritischen Bereichen meines Codes.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wieviel Umdrehungen hat diese Diskussion eigentlich schon durch? Hat 
jemand mitgezählt?

Autor: Regler (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:
> Wieviel Umdrehungen hat diese Diskussion eigentlich schon durch? Hat
> jemand mitgezählt?

Viel zu viele... Haben bald die 100 geknackt. Man, man, man...

Autor: Michael Buesch (mb_)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Regler schrieb:
> Redet man hier gegen Wände?

Ja anscheinend, denn...

>> Solche (trivialen) Optimierungen
>> wie Multiplikation/Division mit Zweierpotenzen überlässt man eigentlich
>> dem Compiler,
>
> Eben! Weil es soooo trivial ist und so naheliegend, wundere ich mich ja,
> dass der AVR-GCC das nicht macht und stattdessen eine komplette
> Divisionsroutine in den Code einbaut!

Niemand hat jemals behauptet, dass der GCC dies für signed Typen tut.

Und damit klinke ich mich jetzt aus der Endlosschleife aus.
break;

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.