Hi Leute!
Ich habe rein aus Interesse mal ausprobiert, in wie weit sich Codegröße
und Laufzeit gegeneinander verhalten, wenn man Divisionen und
Multiplikationen anstatt mit den üblichen Operatoren "/" und "*" rein
durch Addition und Subtraktion durchführt. Ich habe mir dazu selber eine
Funktion geschrieben, die sowohl teilt, als auch multipliziert:
Klar, die Funktion sieht erstmal ziemlich übertrieben aus, ist sie wohl
auch, aber sie arbeitet halt rein durch Addition/Subtraktion.
Im Programm führe ich nun folgende Rechenoperation aus:
Die Funktion ruft sich also selber nochmal auf.
So...wenn ich die Boardmittel vom Compiler benutze, also regulär mit
Punkt und Strich rechne, dann sieht das ganze so aus:
Das Fazit des ganzen ist, dass meine eigene Variante nicht nur mehr
Speicher benötigt (ca. 100Byte), RAM bleibt gleich, sondern auch noch
extreeeemst viel langsamer ist.
Ich habe dazu einen Pin vor und nach der Rechnung seinen Zustand ändern
lassen...das Ergebnis: meine eigene Variante braucht wahnsinnige 26ms
(8MHz Takt), wogegen die normale Variante gerade mal 96us braucht.
Und jetzt die Frage: Wie kommt das? Also was macht der Compiler anders,
bzw. um wieviel tausend Lichtjahre ist seine Variante besser als die
eigene? Wie rechnet der uC das intern? Dachte ja eigentlich auch, dass
Addition/Subtraktion platzsparender ist...aber nichtmal das ;-)
Nun, schlauer bin ich auf jeden Fall, dennoch würde ich gerne mal eure
Meinungen dazu hören.
Gruß
hast du wenigsten die Optimierung eingeschaltet?
das Problem könnte auch sein das du eine funktion für beides hast. Wenn
du es in 2 funktionen zerlegst, dann müsste es schneller sein weil die
vergleiche wegfallen.
MisterX schrieb:> (((adc_value - adc_control.adc_lower_value)*10000) /> Und jetzt die Frage: Wie kommt das?
Die Compilerfunktionen arbeiten sich auf Bitebene durch die Zahl durch.
Eine 32 Bit Multiplikation ist im Prinzip 32 mal eine (32-Bit)Addition
mit entweder 0(*) oder der Originalzahl und ein wenig SChieben.
Deine Version hingegen macht konkret 10000 (in Worten: Zehntausend)
Additionen. Die Version kann nur verlieren. 10000 Addition gegen 32
Additionen und ein wenig 32 Bit Schieben .... so lang kann das Drumherum
in einer normalen bitweisen Multiplikation gar nicht dauern
(und wenn der µC multiplizeren in Hardware kann, dann siehts noch
schlimmer aus)
Fazit: Bei wirklich kleinen Faktoren kann Addition/Subtraktion schneller
sein. Aber irgendwann ist der Breakeven erreicht, an dem bessere
Verfahren schneller sind als "Brutale Gewalt", selbst wenn die Brutale
Gewalt ein wenig einfacher ist.
(*) die natürlich nicht gemacht wird. Nicht das wir uns da falsch
verstehen.
MisterX schrieb:> Und jetzt die Frage: Wie kommt das? Also was macht der Compiler anders,
Nix, nur der Schreiber der internen Funktion nutzt einen deutlich
cleveren Algorithmus.
Dein Weg ist in etwa so effizient, als würdest du versuchen eine
Addition (a + b) durch b mal increment von a ersetzen. Das kann
schneller sein wenn b klein ist, wenn b aber 10000 ist dann ist ein (a +
b) doch signifikant schneller.
OK, vielen Dank für die Antworten!
Ich habe schon ein wenig im Internet gesucht, aber werde nicht
fündig...gibt es irgendwo beschrieben, wie so eine höchst-optimierte
Berechnung aussieht?
Das würde mich jetzt doch mal interessieren?
Karl Heinz Buchegger schrieb:> Die Compilerfunktionen arbeiten sich auf Bitebene durch die Zahl durch.> Eine 32 Bit Multiplikation ist im Prinzip 32 mal eine (32-Bit)Addition> mit entweder 0(*) oder der Originalzahl und ein wenig SChieben.
Darunter kann ich mir nämlich noch nicht so viel vorstellen.
MisterX schrieb:> Ich habe schon ein wenig im Internet gesucht, aber werde nicht> fündig...gibt es irgendwo beschrieben, wie so eine höchst-optimierte> Berechnung aussieht?
Lernt man heute noch, wie man mit Papier und Bleistift multipliziert?
Das geht binär exakt gleich, nur eben mit Bits statt Dezimalziffern.
http://en.wikipedia.org/wiki/Binary_multiplier#Multiplication_basics
man könnte schon mal bei der multiplikation die Faktoren tauschen damit
der kleinste wert für die Scheife verwendet wird.
Deine Funktion ist viel langsamer wenn man
1 * 100000
rechnet als wenn man
100000 * 1 rechnet.
MisterX schrieb:> Mal so nebenbei - arbeitet jemand mit IAR und kann mir sagen, wie ich> die Optimierungen einschalte? Oder wie ich einen Release-Build mache?
Wenn Du Glück hast, steh das im Compiler Handtuch.
Also, Augen waschen, gut trocknen und dann lesen.
MisterX schrieb:> OK, vielen Dank für die Antworten!>> Ich habe schon ein wenig im Internet gesucht, aber werde nicht> fündig...gibt es irgendwo beschrieben, wie so eine höchst-optimierte> Berechnung aussieht?>> Das würde mich jetzt doch mal interessieren?
Da ist überhaupt nichts "optimiert". Das funktioniert genau gleich, wie
du es auch in der Grundschule gelernt hast. Nur deutlich einfacher :-)
Denn im Grunde musst du dir nur merken
0 mal irgendeine_Zahl ergibt 0
1 mal irgendeine_Zahl ergibt diese Zahl
und der Rest ist genau gleich, wie wenn du am Papier multiplizierst
34 * 12
-------
34
68
-----
428
(nur dass man im Rechner nicht x Zahlen untereinander schreibt, die dann
alle auf einmal addiert werden, sondern immer gleich addiert.
AVR-Tutorial: Arithmetik8: Multiplikation
Karl Heinz Buchegger schrieb:> Fazit: Bei wirklich kleinen Faktoren kann Addition/Subtraktion schneller> sein.
Und auch in dem Fall sollte man nicht anfangen, das was man meint
(Multiplikation) durch etwas weniger offensichtliches (Kombination aus
Additionen) zu ersetzen. Denn das kann auch der optimierende Compiler
machen, da lässt man das Programm lieber lesbar.
Der Algorithmus entsprich also tatsächlich einer
Schulbuch-Implementierung. Er ist auf Codegröße getrimmt, denn die
Controller, die nicht über MUL verfügen, haben nur seehr wenig Flash.
Die Implementierung verwendet Sequenzen, wie
1
ROR A0
2
BRCS 1b
3
SBCI A1, 0
4
BRNE 2b
die eher unüblich sind und ein C-Compiler kaum erzeugen dürfte. Dies
spart zusätzlich ein paar Ticks und Instruktionen ein.
Wie Peter II bereits schrieb, könnte durch Tauschen der Operanden der
Algroithmus schneller gemacht werden, und zwar können im Mittel 31/6 ≈ 5
Schleifendurchläufe dadurch gespart werden (zumndest wenn ich mich net
verrechnet hab).
Der GCC-Code macht das allerdings nicht, weil das zu viel Speicherplatz
kostst, nämlich rund 16 Instruktionen was den Code rund 70% größer
machen würde.
A. K. schrieb:> MisterX schrieb:>> Ich habe schon ein wenig im Internet gesucht, aber werde nicht>> fündig...gibt es irgendwo beschrieben, wie so eine höchst-optimierte>> Berechnung aussieht?>> Lernt man heute noch, wie man mit Papier und Bleistift multipliziert?> Das geht binär exakt gleich, nur eben mit Bits statt Dezimalziffern.>> http://en.wikipedia.org/wiki/Binary_multiplier#Mul...>
Da gibt es aber deutlich effizientere Multiplikationsalgorithmen.
BWLer schrieb:> Da gibt es aber deutlich effizientere Multiplikationsalgorithmen.
In Software ist das der allgemeine Ansatz wenn nicht mindestens eine
partielle Hardware-Multiplikation zur Verfügung steht. Klar kann man
noch optimieren, mit early out und dem billigeren Operand auf der
richtigen Seite. Aber das wäre kaum der nächste Schritt nach seiner
etwas zu primitiv geratenen Version oben.
Ansonsten darfst du ihm selbstverständlich diese Algorithmen jederzeit
näher bringen.
BWLer schrieb:> Da gibt es aber deutlich effizientere Multiplikationsalgorithmen.
Dann zeig uns mal eine 32-Bit-Multiplikation mit 32-Bit-Ergebnis für
AVRs ohne Hardware-Multiplizierer, die deutlich effizienter ist als der
drei Beiträge weiter oben von Johann gepostete Code.
Ich bin sehr gespannt :)
P.S.: Ich habe eine leise Ahnung, worauf du hinaus möchtest. Aber ist
das wirklich die Lösung für das vorliegende Problem?
Yalu X. schrieb:> BWLer schrieb:>> Da gibt es aber deutlich effizientere Multiplikationsalgorithmen.>> Dann zeig uns mal eine 32-Bit-Multiplikation mit 32-Bit-Ergebnis für> AVRs ohne Hardware-Multiplizierer, die deutlich effizienter ist als der> drei Beiträge weiter oben von Johann gepostete Code.
Er ist BWLer, (weg)optimieren ist sein Beruf!
Nur so aus Neugier:
Woher hast Du diesen Ausdruck?
> source_number = ( source_number - (source_number + source_number));
Schon diesen könnte man nämlich vereinfachen:
Thomas K. schrieb:> source_number = -source_number;
source_number *=-1;
in der hoffnung dass der compiler dann noch durch das vorzeichen togglen
was raus holt.
Ist subtraktion um 1 und togglen des ersten bits oder?
Grundsätzlich: Natürlich kann man Funktionen schreiben, die schneller
sind, als die in den Bibliotheken. Die Leute, die diese implementiert
haben, sind meist extrem gute Programmierer - aber saumäßige Hellseher.
Wenn die eine Routine für die Multiplikation schreiben, dann so, dass
sie praktisch unter allen Umständen funktioniert, wasserfest und
bügelfrei ist.
Was die Leute, natürlich nicht, wissen können ist, dass du z.B. nur
Zahlen mit 0, 1 und 2 multiplizierst. In diesem Falle ist natürlich
Wissen = Mach und eine angepasste Funktion ist immer schneller.
Jemanden
der erstens unter Langeweile leidet
und zweitens sehr genau weiß was er tut
und drittens von speziellen statt allgemeinen Fällen umgeben ist
dem kann ich nur empfehlen: Mach‘s selber.
Der einzige Fall, in dem ich mir so etwas antun würde ist, wenn ich
Rechenzeitprobleme hätte.
Eine Funktion, die 100000 Mal aufgerufen wird und in der nur ein
Register gesichert wird, dass in meiner Anwendung gar nicht verwendet
wird (kein Hellseher), oder dass ich vorher einmalig sicheren kann -
bringt natürlich einiges an Zeitersparnis.
wenn du wirklich eine schnelle Multiplikation haben möchtest: mein
Informatik Prof meint (ich glaube ihm, habe es aber noch nie getestet)
dass sich alle Grundrechenarten auf Bit-Operationen und Schleifen
zurückführen lassen. Deine Funktion mit den + und - ist letztendlich
eine Bitverschiebung mit Schleife, was du mehrere male durchlaufen
lässt. Daher ist deine deutlich langsamer als die die von Leuten
entwickelt wurden die sonst nix zu tun haben (sprich Mathematiker)
es ist immer ein kompromiss zwischen Größe und geschwindigkeit.
Die schnellste Lösung ist wohl eine Tabelle sein. Das wird wohl nich in
dem Ram von Atmel passen. - aber schnell ist sie.
Die Idee mit der Tabelle ist wirklich toll.
Eine 32x32 Bit Multiplikation bringt Werte zwischen 0 und 4294967296
Die Preisfrage lautet somit: Wie komme ich zum Index des Ergebnisses
ohne ...
Übrigens coco jack dein Prof. hat natürlich recht wie auch die
Ausführungen von Karl Heinz Buchegger implizieren.
Sebastian S. schrieb:> Die Preisfrage lautet somit: Wie komme ich zum Index des Ergebnisses> ohne ...
einfach beide zahlen zu einer 64bit zahlen zusamensetzen?
int64 == int32 << 32 | int32
Peter II schrieb:> Sebastian S. schrieb:>> Die Preisfrage lautet somit: Wie komme ich zum Index des Ergebnisses>> ohne ...>> einfach beide zahlen zu einer 64bit zahlen zusamensetzen?>> int64 == int32 << 32 | int32
Genau.
Und danach muss man nur noch das Ergebnis aus dem 134217728 Tera-Byte
großen Speicher lesen. In Tera-Byte Platten und schön gestapelt, ist
das ein Quader mit 512 512 512 Platten...
EIn Glück, daß es die 3. Binomische Formel gibt, damit braucht man nur
noch 72 Giga-Byte (2^33 * 9 Bytes).
Sebastian S. schrieb:> Eine 32x32 Bit Multiplikation bringt Werte zwischen 0 und 4294967296
falsch 0xffFFffFF * 0xffFFffFF = 0xFFffFFfe00000001, das sind:
he - warum gibt mir der win7 Taschenrechner hier eine signed Zahl? egal
- Es sind auf jeden natürlich Fall 64bit.
Bei Multiplikation addieren sich die Bittiefen
Johann L. schrieb:> das ein Quader mit 512 512 512 Platten...
bescheuerte Formatiererei. So soll es heißen:
> das ein Quader mit 512 * 512 * 512 Platten...
.. eine Tabelle ...
Na klar, und das ganze dann (immerhin etwa 64'000'000 Terabytes) auf
SSDs ablegen und mit einer Zugriffszeit von 100us auslesen... ;)
Stimmt: Ich habe etwas übertrieben.
Der Bereich ist nur:
0 ... 4294836225 und nicht
0 ... 4294967296
Trotzdem bleibt das Problem: Wie komme ich zum Index des Ergebnisses?
Sebastian S. schrieb:> Stimmt: Ich habe etwas übertrieben.
nein, du hast hoffnungslos unertrieben
32bit * 32bit macht 64bit
edit:
2^32-1 * 2^32-1 = 2**64 - 2**33 +1
4294967295 * 4294967295 = 18446744065119617024
Wertebereich ist also
0 ... 18446744065119617024
also 10Mrd mal größer als deiner
Thread beobachten
Seitenaufteilung abschalten