Hallo,
folgendes Problem:
Gegeben sind zwei Byte-Vektoren, beispielsweise zweimal je 10 Bytes
(vorzeichenlos, also uint8_t). Nun soll die Summe der beiden gebildet
werden.
In Assembler ginge das prima in einer Schleife auf folgende Art:
- Zeiger X zeigt auf den Anfang des ersten,
- Zeiger Y zeigt auf den des zweiten Vektors.
- Byte 1 von X lesen.
- Byte 2 von Y lesen mit Postinkrement (ld R, X+).
- Byte 2 zu Byte 1 addieren mit Übertrag.
- Byte 1 nach X schreiben mit Postinkrement.
(logischerweise sollte man den Übertrag zu Beginn der Schleife
löschen...)
Wie aber verklicker ich das in C dem GCC möglichst effizient? Das
Übertragsflag gibts in C ja nicht, es würde also auf hässliche
Überlauftests hinauslaufen, die der GCC nicht gerade kompakt umsetzt.
Vielen Dank und Gruß,
Sven
Sven P. schrieb:> Wie aber verklicker ich das in C dem GCC möglichst effizient? Das> Übertragsflag gibts in C ja nicht, es würde also auf hässliche> Überlauftests hinauslaufen, die der GCC nicht gerade kompakt umsetzt.
Wenn es auf die Performance drauf ankommt, würde ich einfach die
Function in Assembler belassen/schreiben und dann reinlinken (.global
für die zu exportierenden Symbole, dazu ein passendes header file). Geht
schmerzlos. Die Doku zur avr-libc enthält ein Kapitel dazu, wie die
Parameterübergabe funktioniert.
Ansonsten für die Summe einen grösseren Datentyp deklarieren und
regelmässig/am Schluss prüfen (meinuint16>>8).
Sven P. schrieb:> Wie aber verklicker ich das in C dem GCC möglichst effizient? Das> Übertragsflag gibts in C ja nicht, es würde also auf hässliche> Überlauftests hinauslaufen, die der GCC nicht gerade kompakt umsetzt.
uint8_t vector0[10];
uint8_t vector1[10];
uint16_t ergebnis[10];
for(uint8_t i=0;i<10;i++)
{
ergebnis[i] = vector0[i]+vector1[i];
}
Die Rechnung müsste eigentlich schon von selbst mit 16 bit ablaufen,
ansosnten kann man es noch casten.
Läubi, Floh:
Die Rechnung ist so aber leider falsch.
Ich hab mich auch etwas dumm ausgedrückt: Gemeint ist, dass die zehn
Bytes in den beiden Vektoren eine 80-Bit-Zahl darstellen sollen, daher
auch das Problem mit dem Carry. Ich hoffe, so ists verständlicher.
(Inline-)ASM wollte ich nach Möglichkeit vermeiden :-/
Wenn ich Dich richtig verstanden habe, hast Du 2 Arrays vom Typ uint8_t
und der Größe 10. Die möchtest Du als 80-Bit-Zahlen interpretieren und
zueinander addieren mit 80-Bit-Ergebnis. Das höchste Bit fällt wohl
raus.
Wenn's denn besonders effizient und/oder klein sein muss, würde ich das
in Assembler machen. Entweder inline oder als externe Function (im
letzteren Fall hast Du halt noch den Overhead für Subroutine-Aufruf und
-Rücksprung, sieht für mich aber schöner aus).
Edit: Hat sich mit Deiner Antwort überschnitten.
Kompiliert mit -O2 oder -Os ca. 20% kleiner, und ohne 16bit-Operationen:
1
uint8_tvector0[10];
2
uint8_tvector1[10];
3
4
uint8_ta,b,r1,r2,carry;
5
uint8_t*p=&vector0[0];
6
constuint8_t*q=&vector1[0];
7
8
for(uint8_ti=10;i>0;i--){
9
a=*p;
10
b=*q++;
11
r1=a+b;
12
r2=r1+carry;
13
carry=(r1<a)|(r2<r1);
14
*p++=r2;
15
}
Inspiriert vom Generic-Code der GMP-Library, oftmals gut geeignet als
Quelle von optimierten Algorithmen für High-Precision-Arithmetik
(allerdings ggf. Vorsicht wegen GPL geboten!).
Die Schleife zählt absichtlich rückwärts, da das noch den Vergleich für
den Schleifenabbruch im generierten Code einspart.
Andreas
Andreas Ferber schrieb:> Kompiliert mit -O2 oder -Os ca. 20% kleiner, und ohne 16bit-Operationen:
Super :) Und wenn du jetzt noch vernünftige Variablennamen nehmen
würdest, wärs sogar gut lesbar ;-)
Nur ist diese Version trotz kryptischer Namen und etwas krampfiger
Versuche, dem Compiler das Leben möglichst einfach zu machen, deutlich
langsamer als meine Version, die das Optimieren dem Compiler überlasst
(22T vs 15T pro Iteration bei avr-gcc 4.3.4 -Os).
PS: Man sollte Leerzeilen nicht mitzählen ;-). Es sind 20T vs 15T.
Der Compiler ist letztlich nicht übel. Es liessen sich nur noch 2 Takte
einsparen, wenn man diesen C Code manuell optimiert aber beim Verfahren
bleibt. Einzig die Schleifenendbedingung lässt zu wünschen übrig, der
Rest ist bereits optimal.
A. K. schrieb:> Nur ist diese Version trotz kryptischer Namen und etwas krampfiger> Versuche, dem Compiler das Leben möglichst einfach zu machen, deutlich> langsamer als meine Version, die das Optimieren dem Compiler überlasst> (22T vs 15T pro Iteration bei avr-gcc 4.3.4 -Os).
Sicher? Bei meinem Compiler (ebenfalls avr-gcc 4.3.4 mit -Os oder -O2)
sind es 22T (deine Version) vs. 21T (meine Version), jeweils verpackt in
eine Funktion, die vector0/vector1 als Parameter übergeben bekommt.
Zusätzlich ist die Registerlast deutlich geringer, so dass keine
Register auf den Stack gepusht werden müssen (bei dir: 2 Register). Der
Code vor und nach der Schleife sind 16T (du) vs. 6T (ich), jeweils das
RET am Ende der Funktion mitgerechnet.
Insgesamt werden also unterm Strich 20 Takte gespart, nicht
überwältigend, aber immerhin ca. 8,5%.
Andreas
Kommt offenbar stark darauf an, wo die Vektoren liegen. Bei sind sie
statisch. Zwar hatte ich bei obiger Rechnung die 2 Takte für LD+ und ST+
nicht auf der Rechnung, aber das verschiebt die Bilanz nur zu 22/17.
Wie wär's damit als Synthese? Vektoren als Parameter, Übertrag implizit
über 16-Bit Rechnung statt teurer Vergleiche und ein dekrementierender
Zähler ergibt nun 15T.
Den Code davor/dahinter rechne ich bei dominanter Schleife nicht mit.
Jeder Befehl davon geht nur mit 1/10 in die Rechnung ein. Zumal hier
nichts auf dem Stack landet.
Wobei man, das zeigten meine Versuche, statt der hässlichen
do-while-Konstruktion auch einfach eine for-Schleife nehmen kann. Die
ist irgendwie intuitiver und genauso schnell.
Mag sein, dass das aber nur in den zwei, drei Testfällen funktioniert
hat, ich wahr, offen gestanden, auch überrascht und werde das weiter
verfolgen.
Sven P. schrieb:> Wobei man, das zeigten meine Versuche, statt der hässlichen> do-while-Konstruktion auch einfach eine for-Schleife nehmen kann. Die> ist irgendwie intuitiver und genauso schnell.
Sie braucht einen Takt länger, wenn man addv3.c entsprechend umbaut. Bei
do/while ist kein Vergleich erforderlich.
A. K. schrieb:> Wie wär's damit als Synthese? Vektoren als Parameter, Übertrag implizit> über 16-Bit Rechnung statt teurer Vergleiche und ein dekrementierender> Zähler ergibt nun 15T.
Ack, sieht gut aus :-)
Der entscheidende Punkt scheint wirklich die Verwendung (bzw.
Nichtverwendung ;-) der Schleifenvariablen als Arrayindex zu sein. Siehe
auch mein Post dazu im anderen Thread:
Beitrag "Re: Sind ALLE Rechenoperationen automatisch 16-bit breit?"A. K. schrieb:> Sven P. schrieb:>> Wobei man, das zeigten meine Versuche, statt der hässlichen>> do-while-Konstruktion auch einfach eine for-Schleife nehmen kann. Die>> ist irgendwie intuitiver und genauso schnell.> Sie braucht einen Takt länger, wenn man addv3.c entsprechend umbaut. Bei> do/while ist kein Vergleich erforderlich.
Bei
1
for(uint8_ti=10;i>0;i--){
2
/* ... */
3
}
optimiert der GCC bei mir auch den Vergleich weg. Entscheidend ist hier
wohl, dass der Schleifenabbruch beim Erreichen von 0 erfolgt.
Andreas