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?
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.
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...
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 ;-)
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.
Der Controller kann nur einzelne Shifts. Die muss man dann eben mehrmals
beanspruchen. Mehr Arbeit gibt es bei groesseren Datentypen, zb einem
Longword.
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.
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
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.)
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...
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?
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
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.
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).
Ü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.
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.
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.
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!?
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).
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....
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
staticint32_tWert;
6
int32_tNeuerWert=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.
>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.