An alle Logiker

[Mensch Müller (Gast)]

Habt ihr eine Idee, wie man das vereinfachen könnte, um es dem Compiler 
(avr-gcc) einfacher zu machen? Ich ziele auf einen möglichst kurzen Code 
ab. Ich denke, das Problem ist, dass die Variablen 32 Bit breit sind. 
Daher wären (wahrscheinlich) so wenige Vergleiche wie möglich am 
besten??

uint32 a, b, x;

// ...

if (a > b) {
  if ((x >= b) && (x < a)) return 1;
  return 0;
} else {
  if ((x >= a) && (x < b)) return 0;
  return 1;
}

[Christian B. (casandro)]

Also ich denke diesen Code sollte Dein Compiler gut optimieren können, 
zumindest mit -Os. Lass Dir doch mal den Assemblercode ausgeben und 
schau mal nach was da raus kommt. Wir können hier jetzt viel 
diskutieren, was am Ende zählt ist was der Compiler wirklich real macht.

[Sina A. (sinapse)]

return (a > b)? ((x >= b) && (x < a)):((x >= a) && (x < b));

aber denke auch, dass hier lesbarkeit wichtiger ist und der compiler das 
schon hinbekommt

lg

[tictactoe (Gast)]

Erster Ansatz:

bool xa = x < a;
bool xb = x < b;
if (a > b)
  return xa && !xb;
else
  return xa || !xb;  // !(!xa && xb)

Musst selber ausprobieren, ob das was bringt.

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

Eine universelle Regel kann es schon deshalb nicht geben, weil sich 
nicht alle Maschinen gleich verhalten. Schlimmer noch: Die Effizient des 
Codes kann davon abhängen, wie die Wahrscheinlichkeit der Vergleiche 
ausfällt. Manche Compiler können aus einer Laufzeitanalyse des in der 
ersten Phase erstellten Programms schliessen, welche 
Optimierungsstrategie in der zweiten Phase sinnvoller ist.

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

tictactoe schrieb:
> Musst selber ausprobieren, ob das was bringt.

Yep. Beim avr-gcc sind in egal welcher Version eine Unzahl von 
Sprungbefehlen drin. Beim arm-gcc in der Originalversion einer, in 
deiner kein einziger.

[Nur geraten (Gast)]

C kennt ja wohl nur bitweises XOR, kein logisches. Und 0 ist zwar false, 
aber true nicht unbedingt immer 1.

Aber so etwas könnte ja gehen?

return ((a > b) ? 0 : 1) ^ (((x >= b) && (x < a)) ? 1 : 0)

[Falk B. (falk)]

@ Mensch Müller (Gast)

>Habt ihr eine Idee, wie man das vereinfachen könnte, um es dem Compiler
>(avr-gcc) einfacher zu machen?

Warum? Ist es zu komplex? Ist die Ausführungszeit zu groß?

https://www.mikrocontroller.net/articles/AVR-GCC-Codeoptimierung#Prinzipien_der_Optimierung

> Ich ziele auf einen möglichst kurzen Code
>ab.

Der ist schon kurz.

> Ich denke, das Problem ist, dass die Variablen 32 Bit breit sind.
>Daher wären (wahrscheinlich) so wenige Vergleiche wie möglich am
>besten??

Du hast doch schon einen logischen Baum. Das kann so falsch nicht sein.
Deine Funktion prüft, ob x innerhalb der Grenzen a < x <= b liegt, wobei 
das Ganze auch laufen soll, wenn a und b vertauscht sind. OK. Braucht 
immer 3 Vergleiche. Die kriegt der avr gcc schon gut hin. Schau dir den 
ASM Output an.

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

Nur geraten schrieb:
> C kennt ja wohl nur bitweises XOR, kein logisches.

Bei 0/1 schon: !=

> (a > b) ? 0 : 1)

Das ist auch nix anderes als !(a > b) oder (a <= b).

[Mensch Müller (Gast)]

Also, der Code wird nur ganz seltenst ausgeführt. Wie lange es dann 
braucht, ist eigentlich egal. Deswegen sollte der foot print im Flash so 
klein wie möglich sein.
Ich dachte, es gibt irgendeine fancy logische "Umformung", die ich 
übersehen habe.

[Johann L. (gjlayde)]

Würd ich ähnlich hinschreiben wie tictac:

#include <stdint.h>
#include <stdbool.h>

bool in_interval (uint32_t x, uint32_t a, uint32_t b)
{
    bool ge_b = x >= b;
    bool lt_a = x < a;

    if (a > b)
        return ge_b & lt_a;
    else
        return lt_a | ge_b;
}

Am besten kannst bei sowas mit Inlining sparen, das vermeidet dann 
nämlich das Rumgeschaufel der Argumente.

Evtl. auch mal die Wirkung von -fno-split-wide-types begutachten.

Übrigens: wenn Werte mehrfach verwendet werden, z.B. wie bei min, max, 
etc. schneiden Inline-Funktionen gerne mal besser ab als Makros.

[Johann L. (gjlayde)]

Meine Intuition sagt mir aber, dass es noch einen Trick gibt :-)

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

Johann L. schrieb:
> Meine Intuition sagt mir aber, dass es noch einen Trick gibt :-)

Noch besser als die Variante von "Nur geraten"?
  return (a <= b) ^ ((x >= b) && (x < a));

[Salewski (Gast)]

Verwendet man bei bool-werten bitweises und/oder ? Hätte ich so nicht 
erraten, habe aber bool in C noch nie verwendet.

[asdfasd (Gast)]

    return (x >= a) == (x < b);

Ist zwar lesbar aber nicht allzu verständlich ;-)

[Salewski (Gast)]

Ah, den Trick muss ich mir mal merken. Ist schon verständlich wenn man 
es sich aufmalt.

[tictactoe (Gast)]

asdfasd schrieb:
> return (x >= a) == (x < b);
>
> Ist zwar lesbar aber nicht allzu verständlich ;-)

Es wird ganz gut lesbar, wenn du dir folgendes als Idiom merkst: == bei 
Booleschen Werten bedeutet "genau dann wenn" (also Äquivalenz; != wäre 
dann Antivalenz).

[Peter D. (peda)]

Nur geraten schrieb:
> Und 0 ist zwar false,
> aber true nicht unbedingt immer 1.

Falsch geraten, C muß immer 1 für True zurück liefern.
Nur wenn Du selber C einen Ausdruck übergibst, wertet es alles != 0 als 
True aus.
Braucht man die 1, kann man das so erzwingen:

!!(Ausdruck)

[Johann L. (gjlayde)]

asdfasd schrieb:
>

return (x >= a) == (x < b);

Leider falsch :-(

Für x < a < b liefert das Original 1, dein Ausdruck jedoch 0.

[Bülent C. (mirki)]

Nutze doch das Karnaugh Diagramm dafür
https://de.wikipedia.org/wiki/Karnaugh-Veitch-Diagramm

[Stefan Salewski (Gast)]

return (a <= b) ^ ((x >= b) && (x < a));

wäre dann also nicht weiter zu vereinfachen. Naja, immerhin nur noch 
eine Zeile, und für mich persönlich auch der Ausdruck mit der besten 
Lesbarkeit.

Wobei, in Ruby würde ich für die Lesbarkeit eventuell auch schreiben:

a, b = b, a if a < b
return x >= b && x < a

[Johann L. (gjlayde)]

Stefan Salewski schrieb:

> return (a <= b) ^ ((x >= b) && (x < a));

> wäre dann also nicht weiter zu vereinfachen.

Das ist aber auch falsch:

Für x = a < b liefert das Original 0, dieser Ausdruck aber 1.

[Falk B. (falk)]

@ Mensch Müller (Gast)

>Also, der Code wird nur ganz seltenst ausgeführt. Wie lange es dann
>braucht, ist eigentlich egal. Deswegen sollte der foot print im Flash so
>klein wie möglich sein.

Du verschwendest sinnlos Zeit und Energie an der falschen Stelle. Lass 
es wie es ist, das ist lesbar. Fertig.

[Mensch Müller (Gast)]

Sehe ich nicht so. Ich habe schon durch unzählige kleinere Optimierungen 
Platz für neue Features geschaffen, die sonst nicht in den begrenzten 
Flash gepasst hätten.

[Falk B. (falk)]

@Mensch Müller (Gast)

>Sehe ich nicht so. Ich habe schon durch unzählige kleinere Optimierungen
>Platz für neue Features geschaffen, die sonst nicht in den begrenzten
>Flash gepasst hätten.

Dann hast du den falschen Controller/Flashgröße gewählt. Bestenfalls bei 
Stückzahlen von 10k++ ist sowas sinnvoll.

[Carl D. (jcw2)]

Mensch Müller schrieb:
> Sehe ich nicht so. Ich habe schon durch unzählige kleinere
> Optimierungen Platz für neue Features geschaffen, die sonst nicht in
> den begrenzten Flash gepasst hätten.

Neu, Moby gibt's nun auch in C!
;-)

Bevor man aber seine Source unlesbar macht, sollte man ALLE 
Kommandozeilenregister des avr-gcc gezogen haben.

[Salewski (Gast)]

Falk B. schrieb:
> Bestenfalls bei
> Stückzahlen von 10k++ ist sowas sinnvoll.

Ist schon ganz gut auch mal etwas nachzudenken. Der ursprüngliche Code 
ganz oben sieht für mich jedenfalls recht hässlich aus. Dass der 
Compiler das wahrscheinlich eh gut optimiert ist klar. Dass es auf 
wenige eingesparte Bytes nicht ankommen kann ist eh klar, und auf einige 
eingesparte Taktzyklen wohl in der Regel auch nicht. Ich hatte bei der 
Umformung nur geraten ohne wirklich nachzudenken -- man muss da schon 
etwas aufpassen. Mit einer ähnlichen, scheinbar trivialen, aber falschen 
Umformung habe ich kürzlich einen halben Tag vergeudet :-(

[Mensch Müller (Gast)]

Naja, das Projekt ging mit dem mega168 los, weil es was anderes nicht 
gab! Stückzahl ist 1000+, wir würden aber noch gerne Updates anbieten. 
Warum auch nicht, funktioniert ja alles.

Kommandozeilenparameter haben wir uns ganz besonders intensiv gewidmet, 
haben sogar letztendlich ein Script geschrieben, das >200 
avr-gcc-Optionen einzeln durchprobiert, um herauszufinden, was etwas 
bringt und was nicht. Die paar Optionen, die etwas bringen haben wir 
dann (teilweise) kombiniert. Manche wirkten gegeneinander, die flogen 
dann natürlich raus.

[Johann L. (gjlayde)]

Carl D. schrieb:
> Bevor man aber seine Source unlesbar macht,

??? Sogar Assembler bietet die Möglichkeit, Code zu kommentieren:

Und ja, zur Beschreibung darf man auch Pseudo-Code, mathematische 
Notation und ineffizientere aber einfacher zu erfassende Codesequenzen 
verwenden.

[Carl D. (jcw2)]

Johann L. schrieb:
> ??? Sogar Assembler bietet die Möglichkeit, Code zu kommentieren:
>
> Und ja, zur Beschreibung darf man auch Pseudo-Code, mathematische
> Notation und ineffizientere aber einfacher zu erfassende Codesequenzen
> verwenden.

Zu solchen eher kryptischen Compiler-Überredungs-Konstrukten Gesellen 
aber oftmals "Leerkommentare".

@Mensch Müller:
Auch LTO? Dabei ist nicht nur wichtig, daß man -flto an Compiler und 
Linker gibt, man muß auch das -Os an beide geben.
Ich hab das nicht so systematisch durchgetestet, aber bin von der "ich 
optimier mal so, als ob alles in einem File stehen würde"-Method in der 
Regel begeistert.

[Mensch Müller (Gast)]

Ja, natürlich -flto, gerade -flto bringt viel!

Man kann das alles in einem Rutsch machen:

avr-gcc -xc *.c [...] -o output.elf

Auch haben wir verschiedene gcc-Versionen durchgetestet, manche bringen 
mehr, manche weniger, haben merkwürdige Bugs oder brauchen andere 
Parameterkombinationen!

Hier schwirrt z.B. eine 5.2.1 herum, aber die ist teilweise kaputt: Man 
kann -flto und -fipa-pta nicht kombinieren, was eventuell etwas bringen 
könnte.

[Yalu X. (yalu) (Moderator)]

Sollte die Zeile

if (a > b) {

nicht

if (a >= b) {

heißen?

Dann könnte man den Code nämlich umschreiben in

return x-b < a-b;

Das ist nicht nur im Quellcode kürzer, sondern spart auch im Binärcode
einige Bytes. Hier sind die beiden Alternativen jeweils in eine Funktion
verpackt:

#include <stdio.h>
#include <stdint.h>

uint8_t f1(uint32_t a, uint32_t b, uint32_t x) {
  if (a >= b) {
    if ((x >= b) && (x < a))
      return 1;
    return 0;
  }
  else {
    if ((x >= a) && (x < b))
      return 0;
    return 1;
  }
}

uint8_t f2(uint32_t a, uint32_t b, uint32_t x) {
  return x-b < a-b;
}

$ avr-gcc-4.7.4 -mmcu=atmega8 -Wall -Os -ffunction-sections -c test.c
$ avr-size -A test.o
test.o  :
section    size   addr
.text         0      0
.data         0      0
.bss          0      0
.text.f1     78      0
.text.f2     50      0
.comment     18      0
Total       146

Die Funktion f2 spart gegenüber f1 also mehr als ein Drittel Flash ein.
Die neueren GCCs ab 4.9 schneiden da leider nicht mehr ganz so gut ab.

[Johann L. (gjlayde)]

Mensch Müller schrieb:
> Hier schwirrt z.B. eine 5.2.1 herum, aber die ist teilweise kaputt:
> Man kann -flto und -fipa-pta nicht kombinieren, [...]

Ist für die 5.3 behoben:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66705#c7

Momentan ist GCC für die 5.3 eingefroren, d.h. es kann sich nur noch um 
wenige Tage handeln bis zur Release 5.3.

Yalu X. schrieb:
> Sollte die Zeile

> if (a > b) {

> nicht

> if (a >= b) {

> heißen?

Hab ich mich auch schon gefragt; scheint aber um ein halboffenes 
Intervall zu gehen, und das ist leer für a = b.

> Dann könnte man den Code nämlich umschreiben in

> return x-b < a-b;

Das sind aber immer noch 3 32-Bit Operationen (2 falls a und b zur 
Compilezeit bekannt sind).  Aber besser gehts wohl nicht.

Übrigens ist das GCCs Methode, um zu testen, ob ein Wert X in einem 
Intervall [B,A] liegt falls B und A bekannt sind:
Aus

if (X >= B && X <= A)

wird

XB = X - B;
if (XB <= (unsigned) A-B)

[Yalu X. (yalu) (Moderator)]

Ich sehe gerade, dass es auch mit

if (a > b) {

geht.

Der gekürzte Code lautet dann:

return x-a >= b-a;

Der Binärcode wird dadurch sogar noch 2 Bytes kürzer:

$ avr-gcc-4.7.4 -mmcu=atmega8 -Wall -Os -ffunction-sections -c test.c
$ avr-size -A test.o
test.o  :
section    size   addr
.text         0      0
.data         0      0
.bss          0      0
.text.f1     78      0
.text.f2     48      0
.comment     18      0
Total       144

[Mensch Müller (Gast)]

Wir warten sehnsüchtigst auf eine Windows-Version der 5.3

[Yalu X. (yalu) (Moderator)]

Johann L. schrieb:
> Das sind aber immer noch 3 32-Bit Operationen (2 falls a und b zur
> Compilezeit bekannt sind).  Aber besser gehts wohl nicht.

Ja, aber für den Originalcode erzeugt der Compiler 5 32-Bit-Vergleiche
(von denen allerdings maximal 3 ausgeführt werden).

Selbst wenn man die Vergleiche in der drittletzten Zeile logisch so
umformt, dass jeweils zwei Vergleiche sichtbar doppelt auftreten (also
!(x<a) statt x>=a und !(x>=b) statt x<b), wird das Ergebnis nicht
besser.

Man könnte, um die Anzahl der Vergleiche zu reduzieren, die Ergebnisse
von x>=b und x<a in Variablen zwischenspeichern, etwa so:

uint8_t f0(uint32_t a, uint32_t b, uint32_t x) {
  uint8_t xb = x>=b, xa = x<a;
  return a > b ? xb && xa : xa || xb;
}

Jetzt erzeugt der Compiler tatsächlich nur noch 3 32-Bit-Vergleiche, der
Binärcode wird aber sogar noch größer, er wächst von 78 auf 86 Bytes
(GCC 4.7.4)

[Johann L. (gjlayde)]

Carl D. schrieb:
> Johann L. schrieb:
>> ??? Sogar Assembler bietet die Möglichkeit, Code zu kommentieren:
>>
>> Und ja, zur Beschreibung darf man auch Pseudo-Code, mathematische
>> Notation und ineffizientere aber einfacher zu erfassende Codesequenzen
>> verwenden.
>
> Zu solchen eher kryptischen Compiler-Überredungs-Konstrukten Gesellen
> aber oftmals "Leerkommentare".

ad Leer-Kommentar:

Wer seinen eigenen Code nicht mehr versteht — insbesondere weil er nicht 
kommentiert / dokumentiert — ist selbst Schuld.  Im professionellen 
Bereich ist ernsthaftes Code-Reviewing ebenso wichtig wie Spezifikation 
und Testing.

ad Compiler-Überredungs-Konstrukten:

Compiler sind keine Computer-Algebra-Systeme und werden IMHO in 
absehbarer Zeit auch keine CAs darstellen, enthalten bzw. anbinden.

In diesem Sinne sehe ich die Suche nach besseren Formulierungen ähnlich 
wie die Suche nach besseren Algorithmen bzw. Datenstrukturen.  Ein 
Compiler wird wird dir z.B. auch kein Bubblesort durch ein Quicksort 
ersetzen.

[Falk S. (db8fs)]

Hab auch noch 'nen Ansatz:

inline void swap( uint32_t* a, uint32_t* b )
{
    uint32_t tmp = *a;
    *a = *b;
    *b = tmp;
}

uint32_t myfun( uint32_t a, uint32_t b, uint32_t x)
{
    int result = (a <= b);

    if( result )
    {
        swap( &a, &b );
    }

    if( x >= a && x < b )
        return !result;

    return result;
}

Liefert mir übersetzt mit

avr-gcc -mmcu=atmega8 -Wall -Os -ffunction-sections -c test2.c -std=c99

falk@thinkpad /tmp $ avr-size -A test.o
test.o  :
section       size   addr
.text            0      0
.data            0      0
.bss             0      0
.text.myfun     92      0
.comment        43      0
Total          135

[Johann L. (gjlayde)]

Yalu X. schrieb:
> Der gekürzte Code lautet dann:

> return x-a >= b-a;

Ha, wusst ich's doch.  Wo's bei mir nur bis zur Intuition reicht kommt 
Yalu alsbald mit der Inkarnation. :-)

Mensch Müller schrieb:
> Wir warten sehnsüchtigst auf eine Windows-Version der 5.3

Den hab ich mir sellemols unter Linux selbst compiliert. Alles was für 
den Canadian-Cross benötigt wird ist ein linux-mingw32 Cross-Compiler — 
und natürlich eine (virtuelle) Linux Maschine.

[老手 (Gast)]

Nur geraten schrieb:
> Und 0 ist zwar false, aber true nicht unbedingt immer 1.

Man muss in C schon dankbar sein, true immer !false ist.

[Yalu X. (yalu) (Moderator)]

Johann L. schrieb:
> In diesem Sinne sehe ich die Suche nach besseren Formulierungen ähnlich
> wie die Suche nach besseren Algorithmen bzw. Datenstrukturen.  Ein
> Compiler wird wird dir z.B. auch kein Bubblesort durch ein Quicksort
> ersetzen.

Du müsstest dich nur mal hinsetzen und so etwas in den GCC einbauen ;-)

Schon der Fortran-Compiler der Cray-Vektorrechner vor mehr als 30 Jahren
hat vom Programmierer implementierte Funktionen mitunter automatisch
durch eigene Funktionen ersetzt. Man las dann Meldungen ähnlich dieser
(den genauen Wortlaut auf Englisch weiß ich leider nicht mehr):

Hey, wie ich sehe, hast du gerade versucht, eine Funktion für die
Matrizenmultiplikation zu schreiben. Das ist zwar gut gemeint, aber ich
habe eine viel bessere in meiner Bibliothek, die ich anstelle der deinen
verwenden werde.

[Falk B. (falk)]

@Salewski (Gast)

>> Bestenfalls bei
>> Stückzahlen von 10k++ ist sowas sinnvoll.

>Ist schon ganz gut auch mal etwas nachzudenken.

Dagegen ist nix einzuwenden. Aber Krampfoptimierungen nach Gefühl sind 
meistens Schrott. Man wirft den Schinken nach der Wurst.

>Der ursprüngliche Code
>ganz oben sieht für mich jedenfalls recht hässlich aus.

Bitte? Der ist doch sonnenklar?

>Dass der
>Compiler das wahrscheinlich eh gut optimiert ist klar. Dass es auf
>wenige eingesparte Bytes nicht ankommen kann ist eh klar,

So klar ist das gar nicht, zumindest nicht für den OP!

>etwas aufpassen. Mit einer ähnlichen, scheinbar trivialen, aber falschen
>Umformung habe ich kürzlich einen halben Tag vergeudet :-(

Womit du deinen Einwand ad absurdum führtst!

Ich verweise nochmals auf

https://www.mikrocontroller.net/articles/AVR-GCC-Codeoptimierung#Prinzipien_der_Optimierung

Mit der Betonung auf

"Verfrühte Optimierung ist die Wurzel allen Übels"

[Falk B. (falk)]

@ Yalu X. (yalu) (Moderator)

>Dann könnte man den Code nämlich umschreiben in

>return x-b < a-b;

Lesbarkeit?

>Total       146

>Die Funktion f2 spart gegenüber f1 also mehr als ein Drittel Flash ein.

Satte 50 Bytes!

>Die neueren GCCs ab 4.9 schneiden da leider nicht mehr ganz so gut ab.

Aha.

[Falk S. (db8fs)]

Nochmal auf C++ mit avr-gcc-4.9.3, wie oben unter Annahme, dass wirklich 
die echt-kleiner Operation notwendig ist:

#include <stdint.h>

template<typename T>
void swap( T & a, T & b)
{
    T tmp(a);
    a = b;
    b = tmp;
}

bool inInterval( uint32_t a, uint32_t b, uint32_t x)
{
    bool inverted(a > b);

    if( inverted )
    {
        swap( a, b );
    }

    if( x >= a && x < b )
        return !inverted;

    return inverted;
}

Kommt total bei 131 raus. Die einzige Kopplung ist halt noch an die 
bool-Variable, aber vielleicht findet man da auch noch 'nen besseren 
Bezeichner dafür. Sollte aber schon recht lesbar sein und halbwegs 
beschreiben, was eigentlich genau die Funktion leistet.

[Stefan Salewski (Gast)]

Falk B. schrieb:
>>Der ursprüngliche Code
>>ganz oben sieht für mich jedenfalls recht hässlich aus.
>
> Bitte? Der ist doch sonnenklar?

Klar ist der klar -- aber hässlich nach meiner Ansicht. Das errinnert 
mich irgendwie an Java in der Anfängervorlesung.

Yalus Umformung ist wirklich beachtlich -- vielleicht nicht so sehr für 
die Praxis, aber für das Grundsätzliche. Auch ein sehr schönes Beispiel 
für einen Programmierkurs.

[Falk B. (falk)]

@ Stefan Salewski (Gast)

>> Bitte? Der ist doch sonnenklar?

>Klar ist der klar

DAS REICHT! Und ist viel wichtiger als B-Note!

> -- aber hässlich nach meiner Ansicht. Das errinnert
>mich irgendwie an Java in der Anfängervorlesung.

Jaja, zu trivial. Was soll man dann auch an so einer "Funktion" 
optimieren. Da gibt es keine Blumentopf zu gewinnen!

>Yalus Umformung ist wirklich beachtlich --

Wirklich?

> vielleicht nicht so sehr für
>die Praxis, aber für das Grundsätzliche.

Aha. Der Schöngeist spricht. Aber der erleidet in der PRAXIS nur 
allzuoft SCHIFFBRUCH!

> Auch ein sehr schönes Beispiel für einen Programmierkurs.

Obfuscated C! :-(

[Stefan Salewski (Gast)]

Falk B. schrieb:
> Aha. Der Schöngeist spricht.

Weißt Du noch, als Gauss in der Schule die Zahlen 1 bis 100 addieren 
sollte?

[Yalu X. (yalu) (Moderator)]

Falk B. schrieb:
> @ Yalu X. (yalu) (Moderator)
>
>>Dann könnte man den Code nämlich umschreiben in
>
>>return x-b < a-b;
>
> Lesbarkeit?

Ich zitiere mal asdfasd:

asdfasd schrieb:
> Ist zwar lesbar aber nicht allzu verständlich ;-)

In einem realen Programm gehört deswegen noch ein Kommentar dazu.

Das gilt aber auch für den Originalcode:

Lesbar ist er ohne Zweifel (auch wenn das Lesen wegen der vielen
Vergleichsoperationen und Returns deutlich länger dauert als bei meinem
Code).

Verständlich ist er ohne Kommentar aber auch nicht, wie an den vielen
Fehlversuchen, den Code zu vereinfachen, unschwer zu erkennen ist. Auch
ich habe ihn zunächst falsch verstanden und bin deswegen in dieselbe
Falle gestolpert wie asdfasd:

asdfasd schrieb:
> return (x >= a) == (x < b);

Verstanden hat man so ein Konstrukt erst, wenn man in wenigen Worten,
losgelöst vom Quellcode und möglichst ohne mathematische Formalismen
umschreiben kann, was es tut. Das ist aber bei diesem Beispiel gar nicht
so einfach.

[Falk B. (falk)]

@Stefan Salewski (Gast)

>> Aha. Der Schöngeist spricht.

>Weißt Du noch, als Gauss in der Schule die Zahlen 1 bis 100 addieren
>sollte?

Ja, der war drei Klassen unter mir ;-)

JA, DORT ist es WIRKLICH sinnvoll gewesen, vor allem ohne Computer!

[Eric B. (beric)]

Falk B. schrieb:
>>Weißt Du noch, als Gauss in der Schule die Zahlen 1 bis 100 addieren
>>sollte?
>
> Ja, der war drei Klassen unter mir ;-)

Die Schule war in einem vier-stockigen Gebäude? ;-)

[Paul B. (paul_baumann)]

Eric B. schrieb:
>> Ja, der war drei Klassen unter mir ;-)
>
> Die Schule war in einem vier-stockigen Gebäude? ;-)

Dann kam ich in die Schule,
ich konnte nichts dafür:
Stand meistens nur im Klassenbuch
oder draußen vor der Tür.
;-)
MfG Paul

[Johann L. (gjlayde)]

Falk B. schrieb:
> "Verfrühte Optimierung ist die Wurzel allen Übels"

Die Wurzel allen Übels?

Das ist doch Käse — auch wenn's von Knuth stammt.

Ich hab schon Kunden gesehen (> 1e10€ Jahresumsatz) die sind so 
Unterkante Oberkiefer mit der Performance ihere Software dass sie aus 
Verzweiflung sogar neue µCs designen lassen und einsetzen.  Nur weil die 
Software so am Arcsh und so fukcing unwartbar ist und "Design"-Pattern 
benutzt wo es jedem Hobby-Programmierer schlecht wird.  Irgendwelche 
"Design"-Entscheidungen von vor xx Jahren in einem absolut unwartbaren 
Hack mit Soße, und keiner deren BWL-Entscheider Fuzzis hat die Eier in 
der Hose um das Zeug auf ein tragfähiges Design zu portieren oder den 
Rotz komplett in die Tonne zu treten.  MISRA einsetzen und dann 
Toolchains mit Hacks aufbohren lassen, damit das Zeugs nicht die 
Zertifizierung verliert.  Also komm mit nicht mit der Wurzel allen 
Übels!

[Johann L. (gjlayde)]

s/hab/hatte/

[lalala (Gast)]

klärt mich auf! Ist nicht

return x-a >= b-a

dasselbe wie

return x >= b

und damit nicht richtig.

[Johann L. (gjlayde)]

Du rechnest weder in R noch in Z noch in Q sondern in Z mod mZ.  Aber 
zum Merken ist der Zusammenhang gut.  Und ja, im Endeffekt ist die 
Renormierung auf a=0 die Idee hinter der Umformung.

[Falk B. (falk)]

@Johann L. (gjlayde) Benutzerseite

>> "Verfrühte Optimierung ist die Wurzel allen Übels"

>Die Wurzel allen Übels?

Im philosophischen Sinne ;-)

>Das ist doch Käse — auch wenn's von Knuth stammt.

Es ist nicht absolut gemeint.

>Ich hab schon Kunden gesehen (> 1e10€ Jahresumsatz) die sind so
>Unterkante Oberkiefer mit der Performance ihere Software dass sie aus
>Verzweiflung sogar neue µCs designen lassen und einsetzen.  Nur weil die
>Software so am Arcsh und so fukcing unwartbar ist und "Design"-Pattern
>benutzt wo es jedem Hobby-Programmierer schlecht wird.

Dort steht aber nicht die Frage nach Optimierung sondern nach AUFRÄUMEN 
und HAUSAUFGABEN machen!

>  Irgendwelche
>"Design"-Entscheidungen von vor xx Jahren in einem absolut unwartbaren
>Hack mit Soße, und keiner deren BWL-Entscheider Fuzzis hat die Eier in
>der Hose um das Zeug auf ein tragfähiges Design zu portieren oder den
>Rotz komplett in die Tonne zu treten.  MISRA einsetzen und dann
>Toolchains mit Hacks aufbohren lassen, damit das Zeugs nicht die
>Zertifizierung verliert.  Also komm mit nicht mit der Wurzel allen
>Übels!

;-)

Wenn dich das Thema dermaßen berührt darfst du auch den Artikel bzw. die 
Formulierung ändern.

[Horst S. (Gast)]

Kann man die Logik der Abfrage nicht umkehren?

return !((x >= a && x >= b) || (x < a && x < b));

(Not yet tested)

[Mensch Müller (Gast)]

Interessanterweise macht die Reihenfolge der Operanden in der if-Abfrage 
(a && b) vs. (b && a) oft einen Größenunterschied aus. gcc scheint keine 
Optimierung durch Vertauschungsversuche durchzuführen. Zugegeben, es 
wäre sicher eine Herausforderung, die Fälle zu erkennen, in denen die 
Reihenfolge wichtig ist (z.B. bei volatile oder Funktionsaufrufen).

[Bauteiltöter (Gast)]

Soweit ich weiß darf der Compiler die beiden Teile einer &&-Verknüpfung 
gar nicht umdrehen da der Standard garanteriert, das bei

if( a() && b()) )
{...}

b() nicht ausgeführt wird wenn a() schon false ergibt.

[Mensch Müller (Gast)]

Ja, das meinte ich. Auch bei

if (a() || b()))

wird ja b nicht ausgeführt, wenn a() schon true ist.

Aber bei normalen non-volatile Variablen ginge es eben problemlos. Und 
da tritt auch eine Größendifferenz auf.

[Mensch Müller (Gast)]

(in gewissen Fällen)

[Johann L. (gjlayde)]

Jaja, so ist das. Andere Programme können zu anderem Code führen...

[Johann L. (gjlayde)]

Falk B. schrieb:
> @Johann L. (gjlayde) Benutzerseite
>> Ich hab schon Kunden gesehen (> 1e10€ Jahresumsatz) die sind
>> so Unterkante Oberkiefer mit der Performance ihrer Software dass
>> sie aus Verzweiflung sogar neue µCs designen lassen und einsetzen.
>>  Nur weil die Software so am Arcsh und so fukcing unwartbar ist und
>> "Design"-Pattern benutzt wo es jedem Hobby-Programmierer schlecht
>> wird.
>
> Dort steht aber nicht die Frage nach Optimierung sondern nach
> AUFRÄUMEN und HAUSAUFGABEN machen!

Eine Software, die zig MB Binärcode erzeugt und von x anderen Firmen 
mitverwendet wird (und die auch noch entsprechend Code zuprogrammierten) 
"räumst" du nicht einfach mal so auf.  Vor allem wenn die Software 
millionanfach auf der Straße rumfährt...

Nur weil irgendein Techie mal ne Schnapsidee hatte, es offenbar keine 
(funktionierenden) Review-Prozesse gibt, die Hybris vorherrscht mit 
Knete sei alles machbar, usw.

Die Wurzel eines Übels steckt ganz ganz oft im Design, und das Design 
ist eines der ersten Dinge bei der Softwareentwicklung.  Das wollte 
ich damit ausdrücken.

Und auch Knuth hat mit seinen Algorithmen und Datenstrukturen wichtige 
Beiträge zum Design geliefert.  Von daher finde ich solche absoluten 
Zitate von überaus zweifelhaftem Wert — und mit Philosophie hat es auch 
nix zu tun.

>> MISRA einsetzen und dann Toolchains mit Hacks aufbohren lassen,
>> damit das Zeugs nicht die Zertifizierung verliert.  Also komm
>> mir nicht mit der Wurzel allen Übels!
>
> Wenn dich das Thema dermaßen berührt

Sorry, mir platzt auch mal die Hutschnur, auch wenn's nur indirekt mit 
diesem Thread zu tun hat.

[Falk B. (falk)]

@ Johann L. (gjlayde) Benutzerseite

>Eine Software, die zig MB Binärcode erzeugt und von x anderen Firmen
>mitverwendet wird (und die auch noch entsprechend Code zuprogrammierten)
>"räumst" du nicht einfach mal so auf.  Vor allem wenn die Software
>millionanfach auf der Straße rumfährt...

Schon klar. Aber was wäre dein Vorschlag?

>Die Wurzel eines Übels steckt ganz ganz oft im Design, und das Design
>ist eines der ersten Dinge bei der Softwareentwicklung.  Das wollte
>ich damit ausdrücken.

Ach so. Kein Einspruch. Gilt das nicht fast überall?

>Und auch Knuth hat mit seinen Algorithmen und Datenstrukturen wichtige
>Beiträge zum Design geliefert.

Du meinst dein Problemdesign?

> Von daher finde ich solche absoluten
>Zitate von überaus zweifelhaftem Wert

Wenn's dir nicht passt, formulier es um. Es ist nicht in Stein 
gemeißelt.
Ich bin da auch kein Fanatiker und ich hab das bestenfalls 
abgeschrieben.

>> Wenn dich das Thema dermaßen berührt

>Sorry, mir platzt auch mal die Hutschnur, auch wenn's nur indirekt mit
>diesem Thread zu tun hat.

Hast du darüber schon mit deinem Therapeuten gesprochen?
Oder wenigstens ein Code review mit ihm gemacht?
;-)

[Mensch Müller (Gast)]

Also, ich würde das als das selbe Programm bezeichnen, egal mit #if 1 
oder #if 0
Zugegeben, hier ist der Unterschied im Binary winzig. Meist gewinne ich 
aber je optimierter if-Abfrage etwa 2-6 Bytes.

#include <avr/io.h>

static uint8_t max_day_in_month(uint8_t year, uint8_t month) {
  static const __flash uint8_t MAX_DAY_IN_MONTH[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  uint8_t d = MAX_DAY_IN_MONTH[month-1];
  #if 1
  if ((month == 2) && (year & 4)) d++;
  #else
  if ((year & 4) && (month == 2)) d++;
  #endif
  return d;
}

int __attribute__((OS_main)) main(void) {
  GPIOR0 = max_day_in_month(GPIOR1, GPIOR2);

  while (1);
}

[Mensch Müller (Gast)]

& 4 ist natürlich Nonsens, hier geht es nur um die Tatsache, dass man 
durch Vertauschung von Operanden Code einspart.

[Johann L. (gjlayde)]

Dei Programme sind aber nicht gleich.  Die Funktion wird statisch nur 1x 
aufgerufen, daher geinlint, und die GPIORx sind nun mal volatile.

[Johann L. (gjlayde)]

...Aber was willst du und mit dem Code sagen?

Für anderen Code bekommst du i.d.R. ein anderes Binary.

Für äquvalenden Code bekommst du ein äquivalentes Binary.

Zwei äquivalentes Binaries sind i.d.R. nicht binärgleich.

[Mensch Müller (Gast)]

Hm, aber die Operation d++ findet ja nicht auf eine volatile Variable 
statt, oder? Selbst, wenn es geinlined wird.

Ich vermute etwas anderes, weil ich es jetzt schon mehrfach beobachtet 
habe:
Wenn man eine Variable benutzt, welche kurz zuvor im Einsatz war, dann 
wird es kleiner. Hier ist es month. Das wird in der Zeile vorher 
benutzt. Wenn es in der if-Abfrage ganz links steht, scheint der 
Compiler es noch in einem Register parat haben zu können. Dreht man es 
um, wird das Register durch day wiederverwendet und muss in einem 
zusätzlichen Schritt neu geholt werden.
Ich habe mir den Assemblercode noch nicht angesehen, aber zumindest ist 
das Schema immer das Gleiche. Schiebt man Variablen, die kurz vorher 
benutzt wurden, an die erste Stelle, spart man Code.

[Johann L. (gjlayde)]

Mensch Müller schrieb:
> Hm, aber die Operation d++ findet ja nicht auf eine volatile Variable
> statt, oder?

Das nicht, aber die Vergleiche sind gegen Volatile, und um vergleichen 
zu können muss erst gelesen werden, und du kannst nicht einfach mal so 
ein Volatile auf Verdacht lesen.

[Mensch Müller (Gast)]

Wenn ich dich richtig verstehe, wird in folgenden Beispiel UDR0 im Fall 
#if 1 nur bei (month == 2) gelesen und im Fall #if 0 jedes Mal.

#include <avr/io.h>

static uint8_t max_day_in_month(uint8_t year, uint8_t month) {
  static const __flash uint8_t MAX_DAY_IN_MONTH[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  uint8_t d = MAX_DAY_IN_MONTH[month-1];
  #if 1
  if ((month == 2) && (year & 4)) d++;
  #else
  if ((year & 4) && (month == 2)) d++;
  #endif
  return d;
}

int __attribute__((OS_main)) main(void) {
  uint8_t y = UDR0;
  uint8_t m = GPIOR1;
  GPIOR0 = max_day_in_month(y, m);

  while (1);
}

Korrekt?

[Johann L. (gjlayde)]

Mensch Müller schrieb:
> Korrekt?

Nein.  Die Reihenfolge der Auswertung von Funktionsparametern ist nicht 
spezifiziert.

[Mensch Müller (Gast)]

Aber dann sind die beiden Zeilen doch tatsächlich äquivalent...

[Johann L. (gjlayde)]

Ich verstehe immer noch nicht was deine Frage ist.

Versteht du was von C nicht oder willst du was über eine konkrete 
C-Implementation (avr-gcc) wissen?

[Mensch Müller (Gast)]

Ich wundere mich darüber, dass gcc das nicht besser auf Codegröße 
optimiert.

[Johann L. (gjlayde)]

Um darüber was zu lernen gibt's mehrere Möglichkeiten.

Zum einen Compiler-Dumps wie mit -fdump-ipa-all -fdump-tree-all 
-fdump-rtl-all.  Zum anderen kann man den Compiler (cc1) debuggen und 
nachvollziehen, wo er wenn warum welche Entscheidung (nicht) trifft. 
Schließlich gibt es noch Logs per -mlog=? und die Assembler-Ausgabe per 
-save-temps und -dP.  Und natürlich Hilfe von den GCC-Autoren in 
Mailin-Listen wie [e-mail] siehe 
http://gcc.gnu.org/lists.html

Zudem denke ich, dass Compiler nie perfekt sein werden ebenso wie 
Menschen — und damit auch die Autoren von GCC — nicht perfekt sind.

Außerdem ist es nicht gewünscht dass Compiler den besten Code erzeugen: 
Den besten Code zu erzeugen impliziert nämlich NP-vollständige Probleme 
zu lösen, und um das zu bewerkstelligen würden Speicherplatz und 
Rechenzeit, die ein Compiler benötigt, um ein Programm zu übersetzen, 
exponentiell mit der größe des Programms steigen.

Weiters gibt es quasi niemanden, der ernsthaft daran interessiert ist, 
dass GCC besseren AVR-Code erzeugt — falls dem so wäre gäb es 
entsprechende Beitäge zu GCC-Entwicklung.

[Yalu X. (yalu) (Moderator)]

Mensch Müller schrieb:
> Ich wundere mich darüber, dass gcc das nicht besser auf Codegröße
> optimiert.

Zu deinem Beispiel mit der &&-Operation:

Zunächst einmal ist die Auswertereihenfolge in

expr1 && expr2

klar definiert, nämlich erst expr1 und dann expr2.

Wenn expr1 und expr2 beide ohne Nebeneffekte sind, dürfte der Compiler
prinzipiell ihre Auswertereihenfolge ändern, da dies am Ergebnis des
Gesamtausdrucks nichts ändert.

Oft möchte man aber gar nicht, dass der Compiler die Operanden
vertauscht, nur um 2 Bytes einzusparen. Ist bspw. expr1 ein Ausdruck,
der schnell auszuwerten und nur ganz selten wahr ist, sollte er auf
jeden Fall als erstes ausgewertet werden, da dadurch in den meisten
Fällen expr2 übersprungen werden kann.

Da nur der Programmierer – nicht aber der Compiler – die
Wahrscheinlichkeit von expr1 schätzen kann, ist es IMHO besser, der
Compiler überlässt die Wahl der Auswertereihenfolge dem Programmierer.

[Mensch Müller (Gast)]

Ah, das ergibt Sinn. Lasse ich als Antwort gelten. Danke.

Aber das ließe sich ja über einen Optimierungsschalter lösen. ;) Ich 
verstehe natürlich, dass man nie "perfekten" Code erzeugen können wird. 
Aber hier hat man ja einen Ansatzpunkt für Verbesserungspotential. Ich 
bin die ganze Zeit davon ausgegangen, dass avr-gcc weiterentwickelt wird 
und man an solchen Ansätzen interessiert ist.

[Johann L. (gjlayde)]

avr-gcc ist Teil von GCC und profitiert damit natürlich auch von den 
Fortschritten an den maschinenunabhängigen Teilen.

Am AVR-Teil gibt's auch Änderungen, aber viele davon machen sich erst 
bemerkbar, wenn man sie auch (aktiv) nutzt.  Beispiele sind Support von 
ATtinyX, ATXmega, __flash, stdfix.h, Device-Specs und neue Attribute, 
die auch gerne mal Erweiterungen in libgcc, dem Build-System, Binutils 
und avr-libc erfordern.

Insgesamt würde ich den Traffic im AVR-Backend aber als gering 
bezeichnen; auf eine Skala von 0 bis 10 vielleicht auf 1 bis selten mal 
2, momentan tendierend zu 0.

Das größte Optimierungspotential bieten momentan IMO die 
avr-spezifischen Kostenfunktionen.  Die zu überarbeiten ist jedoch nicht 
einfach; es genügt ja nicht, ein Programm herzunehmen und anhand dessen 
die Kosten anzupassen.  Um sowas zu machen braucht's viel Zeit, Geduld & 
Spucke und auch einiges an Intuition und Erfahrung mit der Arbeitsweise 
von GCC.

[Mensch Müller (Gast)]

Kommt man an alle diese Kostenfunktionen per Parameter dran? Um sie per 
Script schnell durchzuprobieren? Ich hatte mich mal irgendwann damit 
kurz beschäftigt, aber nur ein oder zwei gefunden, z.B. für Jumps.

[Johann L. (gjlayde)]

Parametrisier ist -mbranch-cost und einiges geht über --param.  An auf 
RTX-Kosten wirkende Optionen gibt's -mmcu und -Os et al., aber das war's 
dann auch schon.  Die RTX-Kosten komplett zu parametrisieren wäre 
ziemlich sinnfrei.

Wenn man nicht weiß, was man da tut, hat man keine Chance.  Mit Kanonen 
schießt sich eben immer noch schlecht auf exponentielle Komplexität...

Für Kosten siehe (ca. 1000 Zeilen) 
http://gcc.gnu.org/viewcvs/gcc/trunk/gcc/config/avr/avr.c?revision=230016&view=markup#l9843