"Optimierung" bei Multiplikation

add ist bis zu einer gewissen Grenze bei der Anzahl der Schleifen 
wesentlich schneller als auch ein hardware MUL

oder etwa doch nicht?
dann ist der Kompiler bemüht, hier zu optimieren wo es nicht nötig wäre.
Also ab in die AVR Referenz, sorry...

Habe in der Tat zu dem Thema was gefunden:

Unter: 
http://mekonik.wordpress.com/2009/03/18/arduino-avr-gcc-multiplication/

The way AVR GCC handles multibyte multiplication is caused by writing 
the code in C that doesn’t allow for exact specifications of the operand 
and result sizes and as such it is not a bug, it’s a feature that we 
have to be aware of. But there is a bug in AVR GCC that causes the 
compiler to produce a suboptimal code for multiplications by a constant, 
see forum post at AVR Freaks forum. The problem is that multiplication 
by a power of 2 is interpreted as shifts even when it is worse than 
actual multiplication. Shifts are sometimes worse because AVR offers 
only 1-bit shifts of 8-bit operands. For instance, the simple code

1

int a = -10;

2

int x;

3

4

void setup() {

5

  x = a * 64;

6

}

7

8

gets compiled as

9

10

  ca:  36 e0         ldi  r19, 0x06  ; 6

11

  cc:  88 0f         add  r24, r24

12

  ce:  99 1f         adc  r25, r25

13

  d0:  3a 95         dec  r19

14

  d2:  e1 f7         brne  .-8

15

16

This takes more then 30 cycles, while writing this as a multiplication would take 8. That’s a huge difference.

Der AVR Freaks Forum post zu diesem Thema ist:

http://www.avrfreaks.net/index.php?name=PNphpBB2&file=viewtopic&t=75909

Das ganze ist wohl schon ein kleiner Hammer.

Bei großen Wortlängen und Power of Two bin ich aber aus frühester 
Kindheit immer noch ein Freund von SHIFT oder ADD. Aber ich hatte 
vergessen wie Leistungsfähig der AVR MUL ist.

So wie es ausieht könnte es ein wenig aber nur ein wenig helfen, wenn 
keine der VARs global ist sondern lokal und am besten static. Das ist 
aber ein ziemliches Getue und geht nicht immer.

Der Bug ist unter

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39250

zu sehen und wird wohl gefixt werden. Offen seit FEB 2009? wie es 
ausshieht.

Es wird eben zu hart auf Shift oder ADD gewechselt bei Zweierpotenzen. 
Bei *2 ists ok, aber ab *4 aufwärts total schlecht.

Die Optimierung ist nicht schaltbar und unabhängig vom Target, ob es MUL 
hat oder nicht.

Das geht den meisten so, daß man zwar schnell merkt, daß der AVR-GCC auf 
dem falschen Dampfer ist, aber dann kommt sofort die Totschlagkeule: 
"Dann schreib doch nen Patch".

Also bin ich lieber still und akzeptiere es.
Außer beim ATtiny2313 hat ja Atmel den Flash deutlich hochgeschraubt, da 
läßt sichs verschmerzen. Selbst die 8-Pinner haben schon 8kB.

Der AVR-GCC ist sehr störrisch, er merkt fast immer, wenn man ihn in die 
richtige Richtung schubsen will und ignoriert es.
Versuch mal ne Variable abhängig von nem Bit auf 0 oder 1 zu setzen, das 
wird ne riesen 16Bit-Schiebe-Zähl-Maskiere-Orgie, völlig egal, wie Du es 
schreibst.

Extrem unlustig ist er beim Register-Renaming. Der AVR hat ja 32 
Register, aber das interessiert den GCC nicht. Er hat den starken Hang 
unnütz Variablen zwischen Registern umherzuschaufeln. Das gibt 
zusätzlich noch nen Haufen unnötiger PUSH/POPs. Am liebsten schaufelt er 
grundlos auf R18, R19.


Peter

Peter Dannegger schrieb:

> Versuch mal ne Variable abhängig von nem Bit auf 0 oder 1 zu setzen, das
> wird ne riesen 16Bit-Schiebe-Zähl-Maskiere-Orgie, völlig egal, wie Du es
> schreibst.

1

  var = (PORTB & (1<<PB4)) > 0;

2

  56:  80 e0         ldi  r24, 0x00  ; 0

3

  58:  2c 99         sbic  0x05, 4   ; 5

4

  5a:  81 e0         ldi  r24, 0x01  ; 1

5

  5c:  80 93 00 01   sts  0x0100, r24

6

7

  var = (var & (1<<4)) > 0;

8

  56:  80 91 00 01   lds  r24, 0x0100

9

  5a:  90 e0         ldi  r25, 0x00  ; 0

10

  5c:  84 fd         sbrc  r24, 4

11

  5e:  91 e0         ldi  r25, 0x01  ; 1

12

  60:  90 93 00 01   sts  0x0100, r25

;-)

Plutimikation schrieb:

> Ich wage zu behaubten, daß mehr als 90% aller AVR-Programme unter diesem
> Bug "leiden" und eigentlich schneller + kürzer sein könnten. Auf einem
> Tiny kann das sehr weh tun.

Dieser Tiny hat allerdings keinen Multiplier.

Notfalls muss man eben mit Hilfsfunktionen nachhelfen. Sollte eigentlich 
der Compiler tun, aber zumindest solange Johanns Patches nicht drin sind 
kann man sich so behelfen.

Auf den Tinys geht das natürlich auch nicht.

Hallo,
ein paar mehr Varianten von GCC-Inline-Multiplikationen gibt es auch 
noch bei

Beitrag "GCC Inline Assembler Multiplikationen"

Gruß

Dirk

Stefan Ernst schrieb:
>

1

  var = (PORTB & (1<<PB4)) > 0;

2

>   56:  80 e0         ldi  r24, 0x00  ; 0

3

>   58:  2c 99         sbic  0x05, 4   ; 5

4

>   5a:  81 e0         ldi  r24, 0x01  ; 1

5

>   5c:  80 93 00 01   sts  0x0100, r24

6

>

Genau das ist es, was mich ärgert.
Der Compiler weiß, wie es richtig geht, aber macht es absichtlich 
aufwendig.

Man braucht also ein extra Wörterbuch, wo alle Ausdrücke drinstehen, 
welche dem Compiler gefallen.

Warum kann er den Code nicht genau so compilieren, wie ich ihn 
hinschreibe?


Peter

Peter Dannegger schrieb:

> Warum kann er den Code nicht genau so compilieren, wie ich ihn
> hinschreibe?

Weil man so im Workstation- und High-Performance-Bereich keinen 
Blumentopf gewinnt. Diese Optimierungen finden im maschinenunabhängigen 
Teil statt und manchmal vergessen die Leute, dafür Schalter vorzusehen, 
die man beim AVR dann nutzen könnte.

A. K. schrieb:
> Weil man so im Workstation- und High-Performance-Bereich keinen
> Blumentopf gewinnt. Diese Optimierungen finden im maschinenunabhängigen
> Teil statt und manchmal vergessen die Leute, dafür Schalter vorzusehen,
> die man beim AVR dann nutzen könnte.

Mal ne rein theoeretische Frage (patchen ist ja für einen Benutzer 
praktisch unmöglich), wo würde dann ein Patch ansetzen?

Würde er schon die Deoptimierung abbrechen oder würde er sie erst im 
maschinenabhängigen Teil erkennen und rückgängig machen?


Peter

yalu schrieb:
> Übrigens lohnt es sich, hin und wieder eine aktuelle Version des AVR-GCC
> anzuschauen.

Mache ich doch.
Aber der aktuelle WINAVR ist leider erst 4.3.2, da muß man sich wohl 
noch in Geduld üben.


Peter

Peter Dannegger schrieb:

> Mal ne rein theoeretische Frage (patchen ist ja für einen Benutzer
> praktisch unmöglich), wo würde dann ein Patch ansetzen?

Spezialist hierfür ist Johann L. Wir hatte hier schon einmal einen 
Thread zu genau diesem Thema.

Patchen ist etwas einfacher, wenn man Zielplattformen verwendet, die 
sich aus dem offiziellen Sourcecode von GCC heraus ohne einen 
Rattenschwanz an Sonderpatches verwenden lassen (die bei AVR oft 
anfallen, nicht zuletzt weil sich diese Zielplattform schlecht live 
testen lässt). Und man mit Linux arbeitet.

Da ich im Compiler nicht so tief drinstecke würde ich einen Code-Teil, 
der für zweifelhafte "Optimierung sorgt", schlicht um einen Schalter 
(wie -flassmichinruhe) bereichern.

Eine bessere Lösung für manche dieser Optimierungsprobleme würde wohl 
versuchen, die evtl. mitunter falsche Einschätzung zur Komplexität von 
Operationen zu korrigieren.

Für die 16x8-Multiplikationen hat Johann bereits einen Patch gebaut, der 
das entsprechende Template hinzufügt. Damals möglicherweise nur 
unsigned, aber das gleichePrinzip funktioniert ja auch signed.

Peter Dannegger schrieb:

> Aber der aktuelle WINAVR ist leider erst 4.3.2, da muß man sich wohl
> noch in Geduld üben.

Wie du ja weisst ist das nicht immer nur ein Vorteil. So hat(te?) die 
4.4-er bei ARMs die hässliche Angewohnheit, an den hirnrissigsten völlig 
überflüssige Stellen Sign/Zeroextensions durchzuführen.

Plutimikation schrieb:

> Es wäre wirklich mal Zeit für einen Fork des GCC, der dann auch mit
> 8-Bit besser klar kommt.

Mach doch.

Wenn du dich wirklich so gut im GCC auskennst, wie du hier tust, warum
gehörst du dann nicht schon längst zu denjenigen, die sich solcher
Probleme einfach mal annehmen statt hier große Bögen zu spucken?  Man
könnte einen großen Teil der existierenden Probleme wohl ganz sicher
bereits in der jetzigen Codebasis lösen, wenn, ja wenn nur, die
benötigte man power überhaupt erst einmal da wäre.

Aber ohne man power wird auch dein beschworener Fork ein reiner
Papiertiger bleiben, den kein Schwanz benutzen will.  Seltsamerweise
werfen Leute mit vernünftigen Namen und erwiesenem Durchblick im
GCC-Code sehr selten mit solchen Parolen um sich.  Dafür sieht man von
denen auch mal Code, der was repariert.

Das Ganze hat übrigens mit GCCs nicht gerade vorhandener Vorliebe für
8-Bitter ausnahmsweise mal recht wenig zu tun, im Gegenteil: eine
derartige Optimierung braucht man gerade bei kleinen Prozessoren
ohne Hardware-Multiplikation, also auch und gerade bei einem Teil der
AVRs (ATtiny).

Plutimikation schrieb:
> Ganz im Gegenteil, man benötigt sogar weniger man-power, ...

Wir warten immer noch auf deinen Beitrag.  Nicht in Form von Worten,
sondern in Form von Code.  Alles andere hilft keinem weiter.

Plutimikation schrieb:

> Aha, das übliche "Totschlagargument". Andere scheint es ja nicht zu
> geben :-)

Dein Argument "investiert gefälligst mehr von eurer unbezahlten Zeit 
damit ich ein kostenloses Produkt besser nutzen kann" ist besser?

Open Source heisst, dass man entweder selber Hand anlegt, oder mit dem 
lebt was andere zur Verfügung stellen. Drüber meckern aber nicht 
konstruktiv beitragen entspricht nicht dem Business-Modell solcher 
Software. Dafür gibt es kommenzielle Entwicklungssysteme.

Plutimikation schrieb:
> Aha, das übliche "Totschlagargument". Andere scheint es ja nicht zu
> geben :-)

Klar.  Du theoretisiert über Dinge, von denen du offensichtlich
keinen Schimmer hast und stellst irgendwelche Behauptungen auf, die
du nicht einmal ansatzweise beweisen kannst.  Einen Namen willst du
uns auch nicht verraten.  Wie soll man dich da irgendwie ernst
nehmen?

Plutimikation schrieb:
> Wo auch immer du das herausliest, es ist falsch. Ich schrieb doch klipp
> und klar, daß ich der Ansicht bin, daß man sogar weniger Zeit braucht ?

Das schriebst du, und genauso begründungslos schreibe ich dir, dass
ich diese Ansicht für Quatsch halte.  Wir (die AVR-Gemeinde) profi-
tieren an vielen Stellen von der generischen Arbeit des GCC, um unseren
eigenen Kram müssten wir uns halt nur selbst kümmern.  Solange es aber
nur 1,5 aktive AVR-GCC-Entwickler gibt, werden da keine großen Sprünge
passieren.  Da wird auch dein Fork nicht helfen.

Hm... könnte man den wenn man wollte beim AVR-GCC überhaupt 
"mitentwickeln"? Ich stelle mir das nicht so einfach vor da mal eben 
einzusteigen...

Läubi .. schrieb:
> Hm... könnte man den wenn man wollte beim AVR-GCC überhaupt
> "mitentwickeln"?

Im Prinzip schon.  Allerdings benötigt man dazu ein brauchbares
Verständnis der internen Abläufe im GCC.  Ich habe zwei-, dreimal
Anlauf genommen, aber das ist leider nicht mein Ding.

Am Ende kocht aber jeder nur mit Wasser, und keinem ist in die
Wiege gelegt worden, mal GCC-Code schreiben zu können. ;-)  Denis
Chertykov hat sich seinerzeit eben auch einfach mal hingesetzt und
überhaupt eine Portierung gemacht, und Anatolij Sokolov als derzeit
wesentlicher AVR-GCC-Maintainer ist in diese Rolle auch nur dadurch
gelangt, dass er gezeigt hat, dass er einerseits die Materie versteht
und andererseits gewillt ist, aktiv daran zu arbeiten.  (Eine formale
Voraussetzung gibt's noch, man muss der FSF eine Copyright-Abtritts-
Erklärung unterschreiben.  Ist ein Papiertiger, insbesondere da man
als Deutscher ein Copyright gar nicht abtreten kann...)

Jörg Wunsch schrieb:
> gelangt, dass er gezeigt hat, dass er einerseits die Materie versteht
> und andererseits gewillt ist, aktiv daran zu arbeiten.  (Eine formale
> Voraussetzung gibt's noch, man muss der FSF eine Copyright-Abtritts-
> Erklärung unterschreiben.  Ist ein Papiertiger, insbesondere da man
> als Deutscher ein Copyright gar nicht abtreten kann...)
Das heißt ich muß denen ein Papier unterschreiben bevor man mitarbeiten 
darf? Das ist natürlich eher... unattraktiv.

Läubi .. schrieb:

> Das heißt ich muß denen ein Papier unterschreiben bevor man mitarbeiten
> darf? Das ist natürlich eher... unattraktiv.

Naja, es ist nicht tragisch, sofern sich die FSF zumindest einigermaßen
beeilt.  Leider haben sie offenbar nur eine Teilzeit-Sekretöse dafür,
und ich weiß von Johann Lay, dass er seinerzeit mächtig gewartet hat,
bis von denen endlich eine Bestätigung kam (wenn's überhaupt schon
geschafft ist).  Ich habe das Ganze vor Jahren mal für GCC, Binutils
und GDB auf einmal eingereicht, und es ging vergleichsweise zügig (alles
in allem zwei Monate oder so).  Dadurch haben wir ja nun zumindest die
0b-Konstanten ganz offiziell im GCC drin. ;-)

Läubi .. schrieb:

> Das heißt ich muß denen ein Papier unterschreiben bevor man mitarbeiten
> darf? Das ist natürlich eher... unattraktiv.

Es handelt sich um eine Absicherung der FSF, weil übers Urheberrecht 
viel schmutzige Wäsche gewaschen wird und man verhindern will, dass ein 
Wettbewerber über diesen Hebel ganze Projekte lahmlegen kann.

Die Abwicklung ist nicht immer reibungslos (eines meiner Assignments 
verschwand im Nirvana), aber eine wirkliche Hürde ist es auch nicht, 
wenn man an einer Mitarbeit interessiert ist und (was immer der Fall 
sein sollte) wirklich nur eigenen Code weitergibt, an dem Dritte keine 
Rechte haben.

Hazeh Zimmerer schrieb:

> Es handelt sich um eine Absicherung der FSF, weil übers Urheberrecht
> viel schmutzige Wäsche gewaschen wird und man verhindern will, dass ein
> Wettbewerber über diesen Hebel ganze Projekte lahmlegen kann.

Ihre offizielle Begründung ist, dass sie nur so in der Lage wären,
beispielsweise bei GPL-Verletzungen selbst rechtliche Schritte
einleiten zu können.  Klingt mir ein wenig an den Haaren herbei
gezogen.

Mir auch.  Die FSF kann sich halt nicht leisten, dass sie fremde Rechte 
verletzt, wo sie doch in dem Minenfeld von Urheberrechten und 
Softwarepatenten ganz vorne tätig ist.  Dass sie sich da absichert, ist 
verständlich.  (Mancher Werk- oder Arbeitsvertrag dürfte ja tatsächlich 
mit dem Assignment kollidieren, einer meiner früheren hätte es 
jedenfalls.)

Hallo,

Ich hätte bei dieser Gelegenheit mal eine ganz einfache Frage, aber 
lacht mich bitte nicht aus...

Wo bekommt man eine aktuelle AVR-GCC-Version her?

Meine Suchen resultierten nur in Verweisen zu Seiten von Anwendern oder 
wie hier zu einem Wiki-Artikel der nur beschreit, was AVR-GCC kann, aber 
nicht, wo man ihn bekommt. Oder ich habe den Link im Wiki übersehen...

Momentan verwende ich die WinAVR-Version von SF. Aber die ist ja 
bestimmt nicht mehr aktuell.

Viele Grüße,

Lars

Lars R. schrieb:

> Momentan verwende ich die WinAVR-Version von SF. Aber die ist ja
> bestimmt nicht mehr aktuell.

Wenn du etwas aktuelleres haben willst, musst du auf die nächste
WinAVR-Version warten oder halt selbst bauen.  Letzteres wird yalu
ganz sicher gemacht haben, um bspw. die GCC-Version 4.4.2 zu testen.

Hallo Jörg,

Danke für deine Antwort.

> Wenn du etwas aktuelleres haben willst, musst du auf die nächste
> WinAVR-Version warten oder halt selbst bauen.  Letzteres wird yalu
> ganz sicher gemacht haben, um bspw. die GCC-Version 4.4.2 zu testen.

Ich würde dies ja auch gerne versuchen, doch wie komme ich an die 
Quelltexte des AVR-GCC?

Gibt es irgendwo eine Website zum Projekt, wo entsprechende Infos zu 
bekommen sind?

Viele Grüße,

Lars

Jörg Wunsch schrieb:
> Wenn du etwas aktuelleres haben willst, musst du auf die nächste
> WinAVR-Version warten oder halt selbst bauen.  Letzteres wird yalu
> ganz sicher gemacht haben, um bspw. die GCC-Version 4.4.2 zu testen.

Es würde ja reichen wenn einmal jemand die kompilierten Binaries online 
stellen würde für x86, muss doch nicht jeder selbst von neuem den Build 
machen?