Forum: Mikrocontroller und Digitale Elektronik Shift-Operator und Performance


von Regler (Gast)


Lesenswert?

Hallo,

ist euch schonmal aufgefallen, dass der Shift-Operator ziemlich viel 
Rechenleistung erfordert?

Und es macht einen deutlichen Unterschied, um wie viele Stellen 
geshiftet wird, also
.

Ich vermute (beherrsche leider kein ASM), dass der Algorithmus rekursiv 
in ASM vom Compiler umgesetzt wird.

Ist mir beim Debuggen zufällig aufgefallen.

Weiß jemand mehr darüber, warum der Shift-Algorithmus so viele Ops 
braucht? Hätte vermutet, dass der sehr effizient vom AVR umgesetzt 
werden kann. Liegts am Compiler (und gibt es gescheiten inline-ASM), 
oder am AVR und dessen OP-Set selbst?

von Simon K. (simon) Benutzerseite


Lesenswert?

Regler schrieb:
> Hallo,
>
> ist euch schonmal aufgefallen, dass der Shift-Operator ziemlich viel
> Rechenleistung erfordert?
Bei einem x86er sicher nicht.

>
.

Ja ne is klar ;-)

> Ich vermute (beherrsche leider kein ASM), dass der Algorithmus rekursiv
> in ASM vom Compiler umgesetzt wird.
Rekursion? Was ist denn jetzt los?

> Weiß jemand mehr darüber, warum der Shift-Algorithmus so viele Ops
> braucht?
Tut er ja gar nicht auf einem x86er

> Hätte vermutet, dass der sehr effizient vom AVR umgesetzt
> werden kann. Liegts am Compiler (und gibt es gescheiten inline-ASM),
> oder am AVR und dessen OP-Set selbst?
Oh, jetzt redest du ja auf ein mal von AVRs. Da haben wir wohl 
aneinander vorbeigeredet ;-)

Es liegt einfach daran, dass der AVR als Maschinenzyklus nur einen 
einfachen Shift hat. Das heißt, wenn man um 4 shiften möchte, braucht 
man 4 einzelne Shifts.

von Regler (Gast)


Lesenswert?

> Es liegt einfach daran, dass der AVR als Maschinenzyklus nur einen
> einfachen Shift hat. Das heißt, wenn man um 4 shiften möchte, braucht
> man 4 einzelne Shifts.

hab selbst was gefunden:
Beitrag "Verständnisproblem: Programgröße ändert sich mich Wert des shift-Faktors"
Ich war im falschen Forum am Suchen. Sorry.

von Simon K. (simon) Benutzerseite


Lesenswert?

Aber erst mal die Schuld auf Rekursion schieben? ;-) Informatik-Studium 
geschädigt? :-)

von Regler (Gast)


Lesenswert?

Simon K. schrieb:
> die Schuld auf Rekursion

Na, wenn die Code-Größe mit der Anzahl der Stellen steigt, kann man das 
doch mal durchaus vermuten. Oder gibt es andere mögliche Gründe für so 
ein Verhalten? (Ich lerne gerne dazu...)

Bin übrigens Maschbauer...

von Klaus W. (mfgkw)


Lesenswert?

Rekursief geht's meistens schief!

von Simon K. (simon) Benutzerseite


Lesenswert?

Klaus Wachtler schrieb:
> Rekursief geht's meistens schief!

Eben! :-D Ich programmier schon ein paar Jährchen, mir ist aber noch nie 
was rekursives untergekommen (außer mal ne Knobelaufgabe damals anner 
Berufsschule).

Kannst ja mal Karl Heinz Buchegger fragen, mit wievielen rekursiven 
Sachen er schon so zu tun hatte in seiner Laufbahn ;-)

von Klaus W. (mfgkw)


Lesenswert?

och, also ich brauche das öfter mal.

Es gibt etliche Sachen, die sich nicht rekursiv nicht vernünftig
erschlagen lassen (Suchen, Sortieren, Bäume durchlaufen...).

Eher weniger auf einem Controller, aber sonst schon.

von Klaus W. (mfgkw)


Lesenswert?

Regler schrieb:
> Bin übrigens Maschbauer...

Das sind doch sowieso die besseren Programmierer!
Willkommen im Club.

von Purzel H. (hacky)


Lesenswert?

Der Controller kann nur einzelne Shifts. Die muss man dann eben mehrmals 
beanspruchen. Mehr Arbeit gibt es bei groesseren Datentypen, zb einem 
Longword.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Klaus Wachtler schrieb:
> Rekursief geht's meistens schief!

Ach geh, Rekursion ist auch nicht mehr, was es mal war...
1
#include <stdint.h>
2
3
uint8_t lsl_n (uint8_t x, uint8_t n)
4
{
5
    return n ? lsl_n (x << 1, n-1) : x;
6
}
7
8
uint8_t lsl_7 (uint8_t x)
9
{
10
    return lsl_n (x, 7);
11
}

avr-gcc 4.5.1 -Os ... macht daraus
1
lsl_n:
2
.L3:
3
  tst r22
4
  breq .L2
5
  lsl r24
6
  subi r22,lo8(-(-1))
7
  rjmp .L3
8
.L2:
9
  ret
10
11
lsl_7:
12
  ror r24
13
  clr r24
14
  ror r24
15
  ret

von Simon K. (simon) Benutzerseite


Lesenswert?

Hehe! Mööööp. :-)

von Andreas B. (Gast)


Lesenswert?

Nur weils länger dauert muss man keine Rekursion vermuten — schließlich 
gibts auch Schleifen. Natürlich kann man jede Schleife auch rekursiv 
implementieren, aber außerhalb von funktionalen Programmiersprachen 
macht man das wohl kaum.

Aber um auf die originale Frage zurückzukommen, um beliebig viele 
Stellen auf einmal zu shiften, braucht man einen Barrel-Shifter. Und die 
brauchen viel Logik, 24 Multiplexer für 8 bit.

Bei so kleinen Mikrocontrollern wie dem AVR kommt es mehr auf kleine 
Größe und Einfachheit als Performance an, deshalb findet man dort keine 
Barrel-Shifter. Manche Prozessoren können ohne den zumindest 
eigenständig eine Schleife im Mikrosequencer implementieren. Nicht der 
AVR, da gibt es von vornherein nur Instruktionen die um eine Stelle 
shiften.

von Peter D. (peda)


Lesenswert?

Johann L. schrieb:
> Ach geh, Rekursion ist auch nicht mehr, was es mal war...

Rekursionen sind eben so ineffektiv, daß sogar der Compiler sie nicht 
mag.

Ich wüßte auch kein Beispiel wo ne Rekursion Sinn macht.

Manchmal kann man damit ne sehr kurze Schreibweise erreichen, dafür 
sitzt man dann Stunden davor, um sie auch zu verstehen.

Programme mit ner Schleife sind dagegen in der Regel gut verständlich.


Peter

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Regler schrieb:

> Liegts am Compiler (und gibt es gescheiten inline-ASM),
> oder am AVR und dessen OP-Set selbst?

Assembler kann für den Fall helfen, wo nur eine 1 geschoben wird um eine 
Maske zu erhalten. Ich hab mal in meinen Quellen gebuddelt, wo ich sowas 
in 'ner zeitkritischen ISR hatte (avr-as):
1
// r25 = 1 << r24
2
ldi  25, 1
3
sbrc 24, 1
4
ldi  25, 4
5
sbrc 24, 2
6
swap 25
7
sbrc 24, 0
8
lsl  24

Wenn ich's recht sehe, dürfte ein C-Compiler eine solche Sequenz 
allerdings nicht verwenden für 1 << n. (Ich steh irgendwie auf Kriegsfuß 
mit den C promotion rules.)

von ARM dran (Gast)


Lesenswert?

Peter Dannegger schrieb:
> Ich wüßte auch kein Beispiel wo ne Rekursion Sinn macht.

Beispiel:

Minimaler "Recursive Descend"-Parser.
Schnell hingeschrieben, leicht zu verstehen.

Umgekehrt: Aus dem (dafür Nicht Rekursiven) Output von 
flex/bison/yacc/antlr/... wieder die Grammatik erkennen? Nur was für 
Masochisten.
Allein um die "Tabellen-Magie" dahinter zu verstehen, wär ne 
Erstsemester-Vorlesung Informatik hilfreich...

von Klaus W. (mfgkw)


Lesenswert?

Peter Dannegger schrieb:
> Johann L. schrieb:
>> Ach geh, Rekursion ist auch nicht mehr, was es mal war...
>
> Rekursionen sind eben so ineffektiv, daß sogar der Compiler sie nicht
> mag.

Wahrscheinlich nimmt er sie hier nur nicht, weil er sie selbst nicht 
verstanden hat :-)

>
> Ich wüßte auch kein Beispiel wo ne Rekursion Sinn macht.

Wieviele willst du?

von Peter D. (peda)


Lesenswert?

ARM dran schrieb im Beitrag #1926629:
> Minimaler "Recursive Descend"-Parser.
> Schnell hingeschrieben, leicht zu verstehen.

Da muß ich gestehen, daß ich davon absolut 0,nix Ahnung habe.

Ich programmiere nur MCs und daher habe ich damit nichts zu tun.
Da benutze ich nur ganz einfache Parser (Kommandostring, Parameter 1, 
... Parameter n) ohne Rekursion.


Peter

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Peter Dannegger schrieb:

> Ich wüßte auch kein Beispiel wo ne Rekursion Sinn macht.
1
void fatal (const char * msg)
2
{
3
    fprintf (stderr, msg);
4
    exit (1);
5
}
6
7
void fprintf (FILE * stream, const char * fmt, ...)
8
{
9
   ...
10
   if (EOF == fputs (..., stream))
11
   {
12
       fatal ("Ein schwerer Fehler ist aufgetreten!\n");
13
   }
14
   ...
15
}

von Peter D. (peda)


Lesenswert?

@Johann L.

Lustig.
Wenn stderr EOF liefert, läßt Du also einfach den Stack überlaufen.


Peter

von Andreas B. (Gast)


Lesenswert?

Johann L. schrieb:
> // r25 = 1 << r24
> ldi  25, 1
> sbrc 24, 1
> ldi  25, 4
> sbrc 24, 2
> swap 25
> sbrc 24, 0
> lsl  24
>
> Wenn ich's recht sehe, dürfte ein C-Compiler eine solche Sequenz
> allerdings nicht verwenden für 1 << n. (Ich steh irgendwie auf Kriegsfuß
> mit den C promotion rules.)

Abgesehen davon, dass die letzte Zeile wohl "lsl 25" heißen sollte, ist 
doch das einzige was fehlt, dass r25=0 sein müsste falls eines der Bits 
3-7 in r24 gesetzt ist. Das dürfte wohl vor oder nach dieser Sequenz 
behandelt worden sein.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Andreas B. schrieb:
> Johann L. schrieb:
>> Wenn ich's recht sehe, dürfte ein C-Compiler eine solche Sequenz
>> allerdings nicht verwenden für 1 << n. (Ich steh irgendwie auf Kriegsfuß
>> mit den C promotion rules.)
>
> Abgesehen davon, dass die letzte Zeile wohl "lsl 25" heißen sollte, ist

Ja.

> doch das einzige was fehlt, dass r25=0 sein müsste falls eines der Bits
> 3-7 in r24 gesetzt ist. Das dürfte wohl vor oder nach dieser Sequenz
> behandelt worden sein.

Nö, dass muss nicht behandelt werden, da in C unspezifiziert ist wenn 
weiter als die Typbreite geschoben wird. Allerdings versteh ich die 
C-Regel da nicht ganz, ob da er nach 16 Bit promoted werden muss. In dem 
Falle wär's kein Ersatz.

Jedenfalls bekomm ich es momentan mit avr-gcc nicht hin, einen 8-Bit 
Shift erzeugen zu lassen (4.5.1). Es muss aber gehen, sonst gäb es im 
gcc keine Pattern dafür. Möglicherweise ist's irgende Optimierung die 
sich wieder mal selber ins Knie schiesst. In dem Falls wäre die Sequenz 
in avr-gcc ok (natürlich mit r25 und nur für O2+, da die Sequemz 2 Byte 
länder ist als ne Schleife. Wobei letztere allerdings den Eingabewert 
zerstört und er nicht wiederverwendbar ist. Wenn also ne Kopie nötig 
wird, ist es sogar für Os gleich gut).

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Übrigens führt das dazu, daß ein n-facher Shift um 1 in C ein anderes 
Ergebnis haben kann als einen Wert n-fach zu Shiften, nämlich wenn die 
Shiftweite breiter ist als der Typ.

von Karl H. (kbuchegg)


Lesenswert?

Simon K. schrieb:

> Kannst ja mal Karl Heinz Buchegger fragen, mit wievielen rekursiven
> Sachen er schon so zu tun hatte in seiner Laufbahn ;-)


Ach, gar nicht mal so wenig.
Sobald es um Bäume geht wird es eigentlich meistens rekursiv. Und Bäume 
finden sich bei dem was ich beruflich mache sowieso mehr als genug.
Bei Listen ist Rekursion auch möglich, aber eher selten.

Für mich ist Rekursion oft ein sehr natürlicher Zugang zu vielen 
Problemstellungen und ein Werkzeug, das ich nicht missen möchte :-)
Hat man erst mal die Denkweise intus, ist Rekursion auch nicht einfacher 
oder schwieriger als das Denken in Schleifen. Übrigens ist die 
pragmatische Sichtweise der Objektorientierung (darum kümmere ich [das 
Objekt] nicht selber, sondern das delegiere ich an ein anderes Objekt, 
das ist dafür zuständig) nicht ganz unähnlich der Sichtweise mit der man 
Rekursionen zu Leibe rücken kann.

von Simon K. (simon) Benutzerseite


Lesenswert?

Allerdings ist bei Mikrocontrollern der benötigte Stack immer relativ 
schwer hervorzusehen, weshalb man sowas eher vermeidet. Also ich 
zumindest :-)

Klar, bei Bäumen gehts schon fast gar nicht anders als rekursiv. Hat man 
aber auch selten bei Mikrocontrollern.

von Regler (Gast)


Lesenswert?

Hallo,

danke für die ausführlichen Erklärungen. Ich habe zwar zwischendrin nur 
Bahnhof verstanden("Recursive Descend"-Parser,flex/bison/yacc/antlr/..., 
...), aber da hat man dann wieder was zum googlen und lernen...

Und das mit dem Barrel-Shifter, den Muxern etc. war die Erklärung, die 
ich eigentlich suchte.

Peter Dannegger schrieb:
> Ich wüßte auch kein Beispiel wo ne Rekursion Sinn macht.

Korrigier mich, wenn ich falsch liege, aber viele Filter sind doch 
rekursiv (in der Zeit-Domäne) implementiert, da sonst VIEL zu aufwendig. 
Ich denke da an Killer-Berechnungen wie Matrizeninversionen 
(Stichwort:Sherman-Morrison-Woodbury), aber auch an den einfachen 
Moving-Average-Filter.

Muss aber gestehen, das ich mich vielleicht in der Terminologie 
vergriffen habe!?

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Regler schrieb:

> Muss aber gestehen, das ich mich vielleicht in der Terminologie
> vergriffen habe!?

Vielleicht eine Konfusion Rekursion/Iteration?

von Simon K. (simon) Benutzerseite


Lesenswert?

Regler schrieb:
> Korrigier mich, wenn ich falsch liege, aber viele Filter sind doch
> rekursiv (in der Zeit-Domäne) implementiert, da sonst VIEL zu aufwendig.
> Ich denke da an Killer-Berechnungen wie Matrizeninversionen
> (Stichwort:Sherman-Morrison-Woodbury), aber auch an den einfachen
> Moving-Average-Filter.

Stimmt schon. Gewisse digitale Filterstrukturen werden rekursiv 
implementiert. Das heißt aber meines Wissens, dass das Ausgangssignal 
wieder in die nächste Berechnung mit einfließt.
Das heißt aber noch lange nicht, dass solche Filter rekursiv 
programmiert werden (müssen).

von Regler (Gast)


Lesenswert?

Häh?
Wie will man einen rekursiven Filter nichtrekursiv implementieren? Oder 
anders: Der Unterschied zwischen "rekursiv implementiert" und "rekursiv 
programmiert" leuchtet mir gerade nicht richtig ein.

Ich denke du meinst den Unterschied "rekursiv in der Zeitdomäne" und 
"rekursiv im Programmablauf". Da liegt auch (glaub ich) der Grund meiner 
"Konfusion". ;)

Aber rekursiv ist und bleibt rekursiv und bedeutet doch, dass das 
Ergebnis von einem vorhergehenden Ergebnis derselben Funktion abhängt, 
so wie Du es bereits geschrieben hast. Zumindest habe ich es bisher so 
verstanden. Bin aber kein Experte der Nachrichtentechnik....

von (prx) A. K. (prx)


Lesenswert?

Rekursion lässt sich ggf. iterativ umformulieren. Im Fall der 
Endrekursion tut dies bereits der GNU-Compiler, wie Johann oben 
demonstrierte.

von Simon K. (simon) Benutzerseite


Lesenswert?

Regler schrieb:
> Häh?
> Wie will man einen rekursiven Filter nichtrekursiv implementieren? Oder
> anders: Der Unterschied zwischen "rekursiv implementiert" und "rekursiv
> programmiert" leuchtet mir gerade nicht richtig ein.

Wenn der Filter rekursiv ist, heißt das nur, dass das Ergebnis beim 
letzten Durchlauf dies mal wieder mitverwendet wird.
Wie willst du einen rekursiven Filter denn rekursiv implementieren? ;-)

Ein Beispiel für einen rekursiven Moving-Average Filter ist:
1
#define N    8
2
3
....
4
5
static int32_t Wert;
6
int32_t NeuerWert = Eingabequelle;
7
8
Wert = (Wert * (N-1) + NeuerWert) / N;
9
10
....

Deswegen hat das mit einer programmiertechnischen Rekursion überhaupt 
nichts zu tun.

> Ich denke du meinst den Unterschied "rekursiv in der Zeitdomäne" und
> "rekursiv im Programmablauf". Da liegt auch (glaub ich) der Grund meiner
> "Konfusion". ;)
Ja. Das ist zwar der gleiche Begriff mit der gleichen Bedeutung, aber 
die Anwendung ist grundverschieden.

von Huch (Gast)


Lesenswert?

>Ich denke du meinst den Unterschied "rekursiv in der Zeitdomäne" und
>"rekursiv im Programmablauf". Da liegt auch (glaub ich) der Grund meiner
>"Konfusion". ;)

Wenn man das Thema denn auf diese Weise diskutieren will, muss man 
feststellen das es eine Rekursion in der Zeit (nach bisherigem 
Kenntnisstand) nicht gibt. Denn man kann nicht einen Zustand der Welt zu 
einem gewissen Zeitpunkt zu einem davor liegenden Zeitpunkt herstellen.

Um aber auf die eigentliche Frage zurückzukommen, möchte ich sie so 
formulieren. Enthält die Implementierung eines rekursiven Filters 
notwendig einen rekursiven Funktionsaufruf?

Definitiv nein. Der (IMHO naheliegendste) Ablauf ist eine Iteration, bei 
der am Schleifenanfang der aktuelle Eingangswert gelesen, das Produkt 
und die Summe gebildet wird und schliesslich das Ergebnis ausgegeben und 
für die nächste Verwendung zwischengespeichert wird.

Der Unterschied liegt in der Frage was man betrachtet. Den Signal- bzw. 
Datenfluss oder den Kontrollfluss. Bei einem rekursiven Filter ist der 
Datenfluss rekursiv aber, entsprechend des eben gesagten, nicht 
(notwendigerweise) der Kontrollfluss. Bei einem rekursiven 
Kontrollfluss, z.B. bei der Abarbeitung von Bäumen ist der Datenfluss im 
engeren Sinne nicht rekursiv obwohl man andererseits argumentieren kann, 
dass, weil  üblicherweise Zeiger auf ganze Bäume bzw. Teilbäume 
übergeben, die Daten "fast" dieselben sind. Bei anderen rekursiven 
Algorithmen wird man (nach meiner Vermutung vielleicht sogar 
grundsätzlich) solche Daten-Rückführung finden. Bei rekursiven 
Algorithmen liegt aber der Schwerpunkt der Betrachtung auf dem 
Kontrollfluss.

Ich hoffe das ist hilfreich.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.