Hallo,
ich habe ein C Programm für einen AVR ATmega geschrieben. Welches Modell
ich wähle steht noch nicht fest; im Moment arbeite ich mit dem
ATmega328p @ 16 MHz. Nun an mein Programm gibt es eine
Echtzeitanforderung.
Zur Struktur der Hauptfunktion:
1
void foo() {
2
3
unsigned char a, b, c; // Alle Variablen die im folgenden verwendet werden
4
unsigend char icnt = 400000; // Durchläufe der Schleife (fest)
5
6
do {
7
a := einGelesenerWert;
8
9
switch (a) {
10
11
case 0x2a:
12
// tue was
13
break;
14
15
// ...
16
17
}
18
19
icnt--;
20
} while (icnt);
21
22
}
Also im Kern ein switch Statement, das auf lokalen Variablen (die nicht
wieder in den Speicher geschrieben werden) operiert. Nun es gibt circa
160 Fälle in dem switch Statement. Von der Compiler-Optimierung habe ich
alles ausgeschöpft und alle möglichen Flags durchprobiert. Ich bin jetzt
bei einer mittelmäßigen Zeit, müsste das aber noch verbessern.
Der Punkt ist folgender: für manche Fälle in dem switch Statement habe
ich, nach meiner Berechnung, ~ 30 Zyklen des µcs Zeit und für den Rest
habe ich ~ 90 - 200 Zyklen zur Abarbeitung Zeit, um mein Echtzeitziel
einzuhalten. Nun sind die switch Fälle nicht nach eben dieser
"Dringlichkeit" sortiert sondern kreuz und quer.
Jetzt habe ich mir gedacht, dass es vielleicht schneller wird, wenn man
zu Beginn des switch Statements erst alle dringlichen Fälle hinschreibt
(also mit max. 30 Zyklen) und dann alle anderen. Die Idee dahinter:
vielleicht geht Assembler ja so vor (keine Ahnung wie er vorgeht, die
.s-Dateien sind für mich wenig aufschlussreich):
1
dec a ; enthält Wert a aus dem switch
2
biz 0x2a ; branch if zero
3
dec a
4
biz 0x42
5
...
und dann würde ja ein Statement, dass kritisch ist und gaaanz am Ende
steht, erst 160 solcher Dekrementierungen mitmachen müssen. Und das
braucht ja schon die Zyklen alle auf (160 mal DEC und 160 mal BIZ). Mit
einer Sortierung der Fälle, wo zuerst die Fälle kommen für die wenig
Zeit zur Verfügung steht und dann die für die mehr Zeit zur Verfügung
steht, würden ja zuerst die abgegangen die dringend sind. Gibt es jetzt
42 solcher dann muss auch maximal 42 mal DEC und BIZ ausgeführt werden,
damit man prüfen kann, ob so ein Fall vorliegt.
Wiederum könnte der Compiler ja trotzdem das ganze nach den Werten die
Fälle sortieren und mir so mein Kalühl kaputt machen.
Was meint Ihr dazu? Habt Ihr noch andere Ideen zur Optimierung so
"on-the-fly"?
Es gibt außerdem auch keine Funktionsaufrufe aus "foo()" und ich werde
das Gefühl nicht los, dass ich einfach am Rand der Optimierungsgrenze
stehe.
Ansonsten müsste ich eben den Schritt nach Assembler machen und alles in
plain old Assembler implementieren.
Viele Grüße,
DerGast
DerGast schrieb:> unsigend char icnt = 400000;
diese Zeile solltest du als erstes in Ordnung bringen. Und dann schau
dir mal an, wie viel Zyklen dein uC allein für das Dekrementieren und
die Abfrage braucht. Bei zwei "30 Zyklen" Fällen hintereinander musst du
nämlich diese Zeit auch noch mit einbeziehen.
Hi
Wie sieht denn dei "tu was" aus?
Du könntest ja dein "tu was" in eine funktion packen und dann ein Array
aus funktionspointern basteln, auf das du ohne switch zugreifen kannst.
Sry, dass ich kein Beispiel schreibe. Ist mit nem Tablet echt blöde.
Wenns noch keiner nachträgt, liefer ich das noch
Grüße
Kannst du mal den kompletten Quelltext anhängen und das lss file. Dann
sieht man wie das Switch umgesetzt ist. Im schlimmsten fall sind es
viele If Bedingungen, das könnte man mit einer Jump-Table verbessern.
Hallo,
oh, natürlich ist selbst unsigned char etwas begrenzt. Das war nur ein
dummer Typo. Natürlich muss das vom Typ "unsigned long" sein - oder
zumindest habe ich das so gewählt.
Also "tueWas" ist i.d.R. relativ kurz; dort wird etwas berechnet z.B. "x
= (42 * a + b) % 100" oder so und dann wird das Ergebnis noch mit ein
paar Abfragen getestet auf bestimmte Kriterien.
@Funktionspointer: und das ist schneller? Allerdings kann man die
Variablen ja dann nicht mehr lokal halten sondern die werden immer
wieder aus dem Speicher geladen.
Gruß,
DerGast
Mhm, also ich kapiers nicht:
1) was ist die Echtzeitanforderund (was muss wann wie gemacht werden)?
Ist das Tu-Was?
2) Echtzeit und dann eine While-Schlaufe??? Wieso nicht aufteilen?
3) Ev. hilft dir eine Sprungtabelle für den Switch weiter
4) Tu-Was als Inline definieren, dann sparst du dir den Funktionsaufruf
und noch ein paar weitere Befehle...
Zusammenfassend: Zeig den ganzen Code und erklähr mahl etwas
ausführlicher was du wie machen musst/willst (oder ist das geheim?).
DerGast schrieb:> @Funktionspointer: und das ist schneller? Allerdings kann man die> Variablen ja dann nicht mehr lokal halten sondern die werden immer> wieder aus dem Speicher geladen.
das werden sie auch bei lokalen variablen, denn es gibt ja nicht
beliebig viele Register wo sie reinpassen.
Die switch-Anweisung optimieren wird wahrscheinlich nichts bringen. Der
gcc kann das gut optimieren, und sollte je nach Anzahl und
Beschaffenheit der cases eine Sprungtabelle oder binäre Suche verwenden.
Von daher glaube ich auch nicht, dass es etwas bringt, wenn du die
"dringenden" Fälle besonders behandelst.
Bin ja noch nicht so der große Programmierer und halte mich mal aus dem
Meisten hier raus, aber ist es nicht so, dass gerade Berechnungen
erhebliche Zeit brauchen können, auf so einem ATmega, weil die
Architektur das so nicht hergibt?
Und ist dann gerade dieses "Tu was!" nicht wichtig zu wissen, um hier zu
sehen wo wirklich was hängt?
Ich habe in meinem Buch gelesen, dass Fließkommarechnungen erhebliche
Anforderungen an den uC stellen.
Es gibt da mehrere Möglichkeiten.
Zum einen kannst du den Wert nehmen und daraus eine Position in einer
Sprungtabelle berechnen, deren Eintrag zur gewünschten Funktion führt.
der Vorteil ist hierbei eine schnelle Auswertung. Der Nachteil, du musst
für alle möglichen Werte einen Tabelleeintrag anlegen. Sonst wird die
Tabelle zu groß oder du springst ins Nirvana.
Zum anderen kannst du für die Auswertung einen binären Baum verwenden.
Das skaliert gegenüber deiner linearen Lösung um log2 besser. Das währe
auch von Vorteil, wenn du Strings oder größere Werte auswerten möchtest.
Das Stichwort hierfür ist binäre Suchbaum unter anderem bei Wikipedia.
Marek Walther schrieb:> Es gibt da mehrere Möglichkeiten.>
Naja, der Punkt ist: der Compiler wird je nachdem was besser geeignet
ist schon die richtige von diesen Möglichkeiten wählen, wenn man nicht
gerade die Optimierung ausschaltet, oder nur eine handvoll cases hat.
Der ist ja nicht doof. :)
Nein, das ist keine Frage der Complieroptionen. Wir sprechen hier über
Verfahren oder Algorithmen, das liegt in der Verantwortung des Mannes
vor dem Compiler.
>AVR-Programm muß effizienter werden
Wie sagte der ehemalige Bundespräsident Herzog sinngemäß:
"Es muß ein Ruck durch den Kompiler gehen!"
;-)
MfG Paul
Marek Walther schrieb:> Nein, das ist keine Frage der Complieroptionen. Wir sprechen hier> über> Verfahren oder Algorithmen, das liegt in der Verantwortung des Mannes> vor dem Compiler.
Sorry, das ist Quatsch. switch/case hat eine relativ eingeschränkte
Funktionalität, daher ist es einfach für den Compiler zu optimieren. Und
die machen das so gut, wie es ein Assembler-Programmierer hinbekommt.
Beispiel (gcc 4.7.2, -Os):
1
volatile unsigned char a;
2
volatile unsigned char b;
3
4
int main(int argc, char **argv)
5
{
6
switch (a) {
7
case 1: b = 47; break;
8
case 2: b = 23; break;
9
case 3: b = 6; break;
10
case 4: b = 125; break;
11
case 5: b = 23; break;
12
case 6: b = 11; break;
13
case 7: b = 39; break;
14
case 8: b = 20; break;
15
case 9: b = 29; break;
16
case 10: b = 1; break;
17
}
18
19
return 0;
20
}
Das erzeugt eine einwandfreie Sprungtabelle, Laufzeit O(1):
1
main:
2
/* prologue: function */
3
/* frame size = 0 */
4
/* stack size = 0 */
5
.L__stack_usage = 0
6
lds r24,a
7
ldi r25,0
8
movw r30,r24
9
sbiw r30,1
10
cpi r30,10
11
cpc r31,__zero_reg__
12
brsh .L2
13
subi r30,lo8(-(gs(.L13)))
14
sbci r31,hi8(-(gs(.L13)))
15
ijmp
16
.section .progmem.gcc_sw_table,"ax",@progbits
17
.p2align 1
18
.L13:
19
rjmp .L3
20
rjmp .L7
21
rjmp .L5
22
rjmp .L6
23
rjmp .L7
24
rjmp .L8
25
rjmp .L9
26
rjmp .L10
27
rjmp .L11
28
rjmp .L12
29
.section .text.startup
Wenn die case-Werte nicht gut geeignet für eine Sprungtabelle sind,
z.B.:
1
volatile unsigned char a;
2
volatile unsigned char b;
3
4
int main(int argc, char **argv)
5
{
6
switch (a) {
7
case 10: b = 47; break;
8
case 21: b = 23; break;
9
case 30: b = 6; break;
10
case 40: b = 125; break;
11
case 55: b = 23; break;
12
case 250: b = 1; break;
13
case 67: b = 11; break;
14
case 71: b = 39; break;
15
case 85: b = 20; break;
16
case 92: b = 29; break;
17
}
18
19
return 0;
20
}
Dann schmeisst der folgenden Code raus, eine binäre Suche, Laufzeit
O(log n):
1
main:
2
/* prologue: function */
3
/* frame size = 0 */
4
/* stack size = 0 */
5
.L__stack_usage = 0
6
lds r24,a
7
cpi r24,lo8(55)
8
breq .L7
9
brsh .L13
10
cpi r24,lo8(21)
11
breq .L7
12
brsh .L14
13
cpi r24,lo8(10)
14
brne .L2
15
rjmp .L3
16
.L14:
17
cpi r24,lo8(30)
18
breq .L5
19
cpi r24,lo8(40)
20
brne .L2
21
rjmp .L6
22
.L13:
23
cpi r24,lo8(85)
24
breq .L10
25
brsh .L15
26
cpi r24,lo8(67)
27
breq .L8
28
cpi r24,lo8(71)
29
brne .L2
30
rjmp .L9
31
.L15:
32
cpi r24,lo8(92)
33
breq .L11
34
cpi r24,lo8(-6)
35
brne .L2
36
rjmp .L12
Wenn 1-2 cases besonders schnell behandelt werden sollen, kann man die
switch/case-Anweisung in zwei Anweisungen aufsplitten, aber es ist
fragwürdig, ob das etwas bringt. Besser als die obige Lösung geht es
kaum.
DerGast schrieb:
Deine Zeit geht nicht durch das switch flöten, welches GCC bei so
vielen Cases in einer Sprungtabelle umsetzt -- wodurch die
Behandlungszeit unabhängig von der Anzahl der Cases und dem jeweiligen
Case ist -- sondern in dem % 100 in:
> Also "tueWas" ist i.d.R. relativ kurz; dort wird etwas berechnet> z.B. "x = (42 * a + b) % 100" oder so
Dein Problem liegt also im "z.B." oder im "oder so" deines Codes.
Kurz in der Quelle bedeutet nicht, dass es schnell in Assembler ist!
Die Optimierung ist schon beeindruckend, welches O Level ist das?
Im Grunde kann man dann auch durch brutales ASM nicht weiter per Hand
optimieren. Allerdings stellt sich mir dort die Frage, ob der Switch
wirklich das Problem ist.
Schaue ich mir mal den folgenden Teil an und gehen von dem Fall aus, das
kein Sprungfall eintritt, komme ich auf folgende Zyklen:
1
.L14:
2
cpir24,lo8(30)
3
breq.L5
4
cpir24,lo8(40)
5
brne.L2
6
rjmp.L6
6 Zyklen incl. rel. Sprung.
Jede bedingte Sprung kostet mit Vergleich 3 Zyklen, wenn er ausgeführt
wird. Ansonsten mindestens 2 Zyklen.
Bei deinem Beispiel komme ich im schlechtesten Fall auf c. 14/15 Zyklen.
Ich könnte das ganze ggf. mittels Rotation durch das Carry auswerten.
Das wären dann bei 8 Stufen (da 8Bit) im schlechtesten Fall 24 Zyklen.
Im besten Fall 16 Zyklen. Zuzüglich einem Zyklus zum Laden.
Bei deinem Beispiel mit der Sprungtabelle komme ich auch auf ca. 14/16
Zyklen. Hier wäre noch der Vorteil, dass die Laufzeit dieses Abschnittes
ziemlich konstant ist.
Mhm nee, auf Anhieb könnte ich da jetzt auch nichts weiter optimieren.
Hi
Leute, ihr macht mich irre... bitte redet nicht von Zyklen, wenn ihr
Takte meint. Ein Zyklus bezieht sich auf einen Programmdurchlauf und hat
eine entsprechende Anzahl von Takten. Deshalb redet man auch von
Zykluszeit. Ich hab mich schon gewundert über die Aussage:
>Der Punkt ist folgender: für manche Fälle in dem switch Statement habe>ich, nach meiner Berechnung, ~ 30 Zyklen des µcs Zeit und für den Rest>habe ich ~ 90 - 200 Zyklen zur Abarbeitung Zeit, um mein Echtzeitziel>einzuhalten.
Gruß oldmax
160 Fälle in einem Switch-Case? Wenn mir sowas unterkommen würde müsste
ich auf die Tastatur brechen. Ich wette, dass man da noch stark
vereinfachen kann. Aber dazu müsste der TE mal seinen kompletten Code
rausrücken.
btw. ist das hier:
> a := einGelesenerWert;
Pascal und nicht C ;-)
DerGast schrieb:> unsigend char icnt = 400000; // Durchläufe der Schleife (fest)
unsigned char geht von 0 bis 255.
Fuer 400000 brauchst Du mindestens eine 3-byte Variable.
Steel schrieb:> 160 Fälle in einem Switch-Case? Wenn mir sowas unterkommen würde müsste> ich auf die Tastatur brechen.
Wenn der Compiler das in eine Jump Table umsetzt ist das doch kein
Problem?
Uwe Bonnes schrieb:> Wenn der Compiler das in eine Jump Table umsetzt ist das doch kein> Problem?
Es ist trotzdem irre unübersichtlich sofern nicht jeder Case nur ein
Einzeiler ist. Und wie gesagt vermute ich ganz stark, dass es hier noch
Potential zur Vereinfachung gibt.
Uwe Bonnes schrieb:> Wenn der Compiler das in eine Jump Table umsetzt ist das doch kein> Problem?
Ich denke auch, wie Steel, das das weniger ein technisches als viel mehr
ein logistisches Problem ist. Hand aufs Herz: bei welchem switch-case
braucht man 160 unterschiedliche cases? Das stinkt förmlich danach, dass
hier irgendwas mit einem switch-case aufgedröselt wird, was rechenbar
wäre (sieht man zb oft bei der 'Umsetzung' eines ADC Wertes in eine
Temperatur und der Entwickler ist nicht fähig, sich eine einfache Formel
herzuleiten bzw. eine Lookup Tabelle in Form eines Arrays zu machen).
Eine State Machine mit 160 Zuständen ist zwar möglich, wäre aber schon
ein ordentliches Monster und da glaub ich ehrlich gesagt nicht, das das
nicht sinnvoll in 'Themenkreise' gegliedert werden kann mit einem
übergeordnetem Masterswitch.
Auch Pinabfragen sieht man manchmal, bei denen der Programmierer alle
Kombinationen ausprogrammiert, weil er um Bitabfragen einen Bogen macht,
wie der Teufel ums Weihwasser.
Aber: was genaues weiß man nicht. Gefühlsmässig hätte ich gesagt, dass
der switch-case nicht das eigentliche Laufzeit-Problem ist, sondern eher
ein Symptom dafür, dass hier die falsche Technik zur Lösung der
Aufgabenstellung eingesetzt wird. Ohne nähere Angaben ist das aber nicht
entscheidbar und so wie meistens, fehlen diese.
Marek Walther schrieb:> Die Optimierung ist schon beeindruckend, welches O Level ist das?
Einfach -Os, steht doch im Post.
Es wäre bei diesem Problem aber tatsächlich interessant zu wissen, warum
die 160 cases nötig sind... vielleicht ist das Problemlösung von hinten
durch die Brust ins Auge. ;) Also mehr Details wären wichtig.
Thread beobachten
Seitenaufteilung abschalten