Optimiert der Compiler Division durch 2^n wirklich?

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

Gruß
Dennis

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.

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?

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?

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...

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.

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)

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?

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

Verneinen natürlich...

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.

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!

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.

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:

1

// Die Anzahl der Funktionsaufrufe

2

#define COUNT_INIT     100  

3

4

// Der Teiler bzw. Shift-Wert

5

#define TEILER      32

6

#define SHIFT       5  // = log2(TEILER)

7

8

// der zu unteruchende Datentyp

9

#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:

1

test_t scale(test_t x, uint8_t y){ 

2

3

  return(x + y);     

4

}

5

6

7

test_t scale(test_t x, uint8_t y){ 

8

9

  return(x / (test_t) TEILER + y);     

10

}

11

12

13

test_t scale(test_t x, uint8_t y){ 

14

15

  x = (x >> (test_t) SHIFT);

16

17

  if (x < 0)

18

    return(++x + y);

19

  else

20

    return(x + y);

21

}

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....

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?

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.

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?

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.

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?

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 ....

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. ;)

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.

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?

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.

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.

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! ;)

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.

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

1

test_t scale(test_t x){ 

2

3

  if (x < 0)

4

     x += TEILER - 1;

5

6

  return(x >> (test_t) SHIFT);

7

}

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.

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.

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..

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.

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.

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.

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.

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.

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.

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.

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...