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?
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.
AVRs haben doch auch eine Funktion "Arithmetic Shift Right" - Kennt der Compiler die nicht? Gruß Dennis
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
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.
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.
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.
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.
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
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?
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.
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.
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: > 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.
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...
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.
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.
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.
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)
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.
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: > 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.
Regler schrieb: > Ich hatte im Betreff eine Frage gestellt: Die muss man doch bejahen, > oder? Verneinen natürlich...
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.
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.
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)
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.
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.
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!
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.
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.
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.
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.
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>
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....
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.
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?
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.
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.
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.
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.
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?
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.
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: > 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.
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 ....
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. ;-)
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. ;)
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.
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.
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. ;)
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! ;)
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
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.
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.
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 | }
|
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
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.
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.
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.
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..
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.
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. ;)
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.
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.
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.
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.
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.
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.
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).
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.
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.
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.
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
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.
Wieviel Umdrehungen hat diese Diskussion eigentlich schon durch? Hat jemand mitgezählt?
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...
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;
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.