(nur so als Info)
vielleicht ists allgemein bekannt, für mich wars jedenfalls neu: Ich
nahm an, dass eine lokale Variable erst dann auf dem Stack landet, wenn
sie aus "C"-Sicht bekannt ist. Ich stellte mir vor, dass der C-Compiler
zB. an der "<-- da" den SP für das Array "dummy" decrementieren würde,
um ihn an der Stelle "<-- dort" wieder zu incrementieren.
***das ist aber nicht so***
1
#include<avr/io.h>
2
3
staticuint16_tdebug;
4
5
voidtest()
6
{
7
debug=SP;
8
9
{// <-- da
10
chardummy[23];//--- Aus "C"-Sicht erst ab hier bekannt ---
11
debug=SP;//--- Trotzdem schon von Anfang an auf dem Stack ---
Hier ists doch egal.
Aber mach dochmal davor nen Unterprogrammaufruf in nem anderen Objekt.
Wenn diese Funktion auch Variablen anlegt, hätte man dadurch ne viel
höhere unnötige Stackbelastung.
Peter
>Hier ists doch egal.
das da oben sollte ja auch nur ein Beispiel sein.
Ich hatte mein Verständnisproblem in einer Parser-Funktion entdeckt, die
sich selber rekursiv aufruft, und zwar entweder tief mit kleinen
Buffern, oder weniger tief aber dann mit großen Buffern. Die Buffer
hatte ich wie oben in dem Beispiel in eigenen Namensräumen deklariert,
und war dann überrascht, dass trotzdem der Stack schnell überlief, -
weil nämlich jedesmal sämtliche Buffer auf dem Stack reserviert wurden,
und nich wie beabsichtigt nur die gerade benötigten. Aber kein Problem,
ich löse das dann halt anders.
Grüße Ralf
Rekursionen sind ne Erfindung von Mathematikern, um Algorithmen
möglichst kompliziert und undurchschaubar darzustellen.
Ich kenne keine Architektur, die Rekursionen effektiv ausführen und
keinen Compiler, der Rekursionen effektiv umstellen kann.
Schon allein der Call+Return+Stackvariablen-Overhead läßt eine ganz
schwummrig werden, wenn man mal den generierten Assembler ansieht.
Besonders katastrophal sind Rekursionen, die sich 2-fach aufrufen (f(n),
f(n-1)), dann steigt der Rechenzeitbedarf exponentiell.
Ich war völlig verduzt, als ein rekursiver Algorithmus plötzlich bei
Rekursion 30 viele Sekunden auf nem 3GHz Pentium brauchte.
Auf nem 12MHz 8051 als Schleife aufgelöst, war die Zeit dagegen nicht
mehr manuell meßbar (Enter drücken, Ergebnis stand sofort auf LCD).
Wenn man wirklich effektive CPU-Zeit und SRAM-Nutzung haben will, muß
man selber die Rekursion in ne Schleife umformen.
Peter
Um Rekursion zu verstehen muss man zuerst Rekursion verstehen :-)
bei µC's würde ich auch soweit auf Rekursion verzichten, falls man diese
irgendwie aufdröseln kann.
Weiterhin meide ich persönlich Funktionen, wo man den Worst-Case der
Speichernutzung nicht abschätzen kann
Gruß
Roland
Roland Praml wrote:
> Um Rekursion zu verstehen muss man zuerst Rekursion verstehen :-)
Ich verstehe Rekursionen, sie sehen auf den ersten Blick auch schön kurz
aus, allerdings wirklich nur auf den allerersten Blick.
Ich würde sogar soweit gehen Rekursionen für AKW- oder
Raumfahrtsteuerungen usw. pauschal zu verbieten, weil sie eben
unkalkulierbar sind.
Der Hauptnachteil ist die fehlende Abbruchbedingung bei unvermuteten
Eingangsparametern.
Eine Schleife über n Felder kann dagegen bei n+1 sofort abbrechen und ne
Fehlermeldung ausgeben ohne den Stack zu korrumpieren und alle anderen
Prozesse damit zu killen.
Sie hat neben der wesentlich schnelleren Ausführung also noch den
Vorteil der wesentlich höheren Sicherheit.
Ich hatte mal ein DIR /S auf ein Netzlaufwerk gegeben, UNIXer haben aber
irgendwie die Angewohnheit, das Homeverzeichnis . nochmal als virtuelles
Unterverzeichnis anzulegen.
Die DOS-Fehlermeldung nach einigen Stunden war wirklich seltsam.
Irgendwann hat man ihnen aber gesagt, daß rekursive Unterverzeichnisse
Schwachsinn sind und dann konnte man wieder normal aufs Netz zugreifen.
Peter
Hallo Peter,
ok, wechseln wir zum Thema "Rekursonen allgemein".
Und dazu meine ich dass man Rekursionen immer dann verwenden sollte,
wenn es für die Lösung des Problems zweckmäßig ist. Rekursionen
gegenüber linearer Programmierung als generell unsicherer zu bezeichnen,
halte ich für falsch.
Durch geeignete Maßnahmen hat man beide Techniken im Programm gut im
Griff, und es muß nicht notwendigerweise die Gefahr eines korrumpierten
Stacks bestehen. Falls eine Rekursion (problembedingt) zum Aufbau eines
tiefen Stacks neigt, dann würde üblicherweise auch die zu einem linaren
Programm abgerollte Variante Daten zwischenspeichern müssen, zB. in
einem Stack, welcher ebenfalls überlaufen kann.
Zur Frage der wesentlich schnelleren Ausführung eines linearen Programms
gegenüber einer rekursiven Lösung meine ich, dass das möglicherweise,
dann aber nur fast stimmt, denn ich glaube nicht, dass die Unterschiede
"wesentlich" ausfallen würden, bestenfalls ist eine lineare Lösung
geringfügig schneller als eine Rekursion. Wenn eine lineare Lösung
deutlich schneller sein sollte, dann wäre eine rekursive Lösung für
dieses Problem wahrscheinlich ohnehin die falsche Wahl gewesen.
Um mal einen schönen Angriffspunkt zu liefern (oder gleich mehrere),
sage ich, worum es bei meiner Rekursion im Detail geht: Ich schreibe an
einem Parser für arithmetische Ausdrücke (für meinen BASIC-Interpreter).
Anhand der für BASIC üblichen Syntax soll er mathematische Berechnungen
durchführen, und dazu einen String so Parsen, dass er Operatoren,
Operanden und Klammern erkennt, und abhängig von deren Rangfolge korrekt
berechnet (also Punkt vor Strichrechnung). Ich löse das mit einem
rekursiven Algorithmus. Jetzt wäre die Frage offen, wie gut, wie schnell
und wie übersichtlich sich das mit einem linearen Algorithmus lösen
läßt, und ob er einer rekursiven Lösung in Sicherheitsaspekten überlegen
wäre.
Grüße Ralf
Peter Dannegger wrote:
> Ich hatte mal ein DIR /S auf ein Netzlaufwerk gegeben, UNIXer haben aber> irgendwie die Angewohnheit, das Homeverzeichnis . nochmal als virtuelles> Unterverzeichnis anzulegen.> Die DOS-Fehlermeldung nach einigen Stunden war wirklich seltsam.>> Irgendwann hat man ihnen aber gesagt, daß rekursive Unterverzeichnisse> Schwachsinn sind und dann konnte man wieder normal aufs Netz zugreifen.
. und .. sind virtuelle Verzeichnisse die vom System bereitgestellt
werden, sowohl unter Windows als auch unter Unix. Dass dir /s in diese
Verzeichnisse absteigt kann ich mir nicht vorstellen - dann würde es
überhaupt nicht funktionieren.
Rekursion ist weiter nichts als eine Variante dynamischer Ressourcen-
verwaltung, mit all ihren Vor- und Nachteilen. Man kann damit z.B.
eben ein beliebig komplexes C-Programm zerlegen, wobei das "beliebig"
in der Praxis halt durch die verfügbaren Systemressourcen begrenzt
wird. Da selbige bei einem AVR deutlich knapper sind als auf meinem
PC, wird man die Rekursion folglich auf diesem seltener antreffen.
Sinnvoll kann sie aber trotzdem sein, genauso wie auch malloc()
durchaus sinnvoll sein kann.
Peter Dannegger wrote:
> Ich hatte mal ein DIR /S auf ein Netzlaufwerk gegeben, UNIXer haben aber> irgendwie die Angewohnheit, das Homeverzeichnis . nochmal als virtuelles> Unterverzeichnis anzulegen.> Die DOS-Fehlermeldung nach einigen Stunden war wirklich seltsam.>> Irgendwann hat man ihnen aber gesagt, daß rekursive Unterverzeichnisse> Schwachsinn sind und dann konnte man wieder normal aufs Netz zugreifen.
Du bist hier vermutlich über einen Softlink gestolpert. Wenn der auf das
aktuelle Verzeichnis zeigt, dann passiert genau sowas. Die Unix-Tools
können damit natürlich umgehen, aber da es bei DOS das Konzept von
virtuellen Unterverzeichnissen so nicht gibt, haben die beim
Verzeichnis-Export das eben auf normale Unterverzeichnisse gemappt.
Markus
Ralf Rosenkranz wrote:
> Um mal einen schönen Angriffspunkt zu liefern (oder gleich mehrere),> sage ich, worum es bei meiner Rekursion im Detail geht: Ich schreibe an> einem Parser für arithmetische Ausdrücke (für meinen BASIC-Interpreter).
Soll der Parser etwa auf nem AVR laufen ?
Dann machs doch so, wie in Bascom, also immer nur eine Berechnung pro
Zeile erlauben.
Richtige Parser kenne ich eigentlich nur bei C-Compilern.
Peter
Peter Dannegger wrote:
> Ralf Rosenkranz wrote:>>> Um mal einen schönen Angriffspunkt zu liefern (oder gleich mehrere),>> sage ich, worum es bei meiner Rekursion im Detail geht: Ich schreibe an>> einem Parser für arithmetische Ausdrücke (für meinen BASIC-Interpreter).>> Soll der Parser etwa auf nem AVR laufen ?> Dann machs doch so, wie in Bascom, also immer nur eine Berechnung pro> Zeile erlauben.> Richtige Parser kenne ich eigentlich nur bei C-Compilern.
Jetzt untertreibst du aber. Auch der AVR-Assembler kann
arithmetische Ausdrücke mit Konstanten auflösen.
Ist auch weiter keine Hexerei. Man kann das mit eigenen
Stacks machen oder einen 'recursive decent parser' aufsetzen.
Ich muss gestehen, dass ich für Letzteres ein Faible habe,
auch wenn ich die mittlerweile nicht mehr selbst schreibe sondern
einen Compiler-Compiler darauf ansetze.
> Wenn eine lineare Lösung deutlich schneller sein sollte,> dann wäre eine rekursive Lösung für dieses Problem wahrscheinlich> ohnehin die falsche Wahl gewesen.
Das Problem ist, dass Rekursion meistens mit 2 Beispielen
gelehrt wird:
* Fakultät einer Zahl
* Fibonacci Zahlen
Beide Problemstellungen kann man rekursiv lösen, jedoch
speziell bei Fibonacci Zahlen ist die naive rekursive
Variante eindeutig die schlechtest mögliche Variante,
wenn man auf Laufzeit aus ist. Fakultät ist auch nicht
anderes: Man kann es rekursiv machen, hat dann aber eine
schlechte Wahl getroffen.
Bei Listen bzw. Bäumen sind Rekursionen jedoch ein
natürliches Mittel um durch die Datenstruktur durchzugehen
(Bäume. Was Peter da beschrieb, ist kein Baum sondern ein
Netz. Das DOS Programm musste scheitern, nicht weil es rekursiv
verfasst wurde, sondern weil es nicht mit einem Netz gerechnet
hat. Das kann man aber kaum der Rekursion anlasten. Auch eine
lineare Lösung wäre kläglich gescheitert). OK, bei Listen sind
rekrusive Lösungen nicht unbedingt naheliegend und man wird
in der Regel keine rekursive Lösung wählen.
> Ich hatte mein Verständnisproblem in einer Parser-Funktion entdeckt,> die sich selber rekursiv aufruft, und zwar entweder tief mit> kleinen Buffern, oder weniger tief aber dann mit großen Buffern.
Darf ich mal fragen, wie du den Parser aufbaust?
Ich hab schon viele Parser geschrieben, aber wenn ich mich
so zurückerinnere, fällt mir kein Beispiel ein, bei dem
es notwendig warm irgendwelche größeren Buffer anzulegen.
Die meisten Funktionen kommen mit 1, 2, 3
lokalen Variablen aus. Mehr ist eigentlich selten.
Vor allem bei arithmetischen Ausdrücken.
(f)lex und yacc/bison ersetzen Programmspeicher durch erheblichen
Einsatz von Datenspeicher. Nicht gerade sinnvoll bei Microcontrollern
mit Harvard-Architektur.
@Karl heinz,
>> Ich hatte mein Verständnisproblem in einer Parser-Funktion entdeckt,>> die sich selber rekursiv aufruft, und zwar entweder tief mit>> kleinen Buffern, oder weniger tief aber dann mit großen Buffern.>> Darf ich mal fragen, wie du den Parser aufbaust?> Ich hab schon viele Parser geschrieben, aber wenn ich mich> so zurückerinnere, fällt mir kein Beispiel ein, bei dem> es notwendig warm irgendwelche größeren Buffer anzulegen.> Die meisten Funktionen kommen mit 1, 2, 3> lokalen Variablen aus. Mehr ist eigentlich selten.> Vor allem bei arithmetischen Ausdrücken.
öhm, ich habe nicht erwähnt, dass mein BASIC-Parser neben numerischen
Werten auch an (bisher) einer Stelle kleine Strings verarbeinten kann.
Ich behandele das Semikolon ";" wie einen Operator, welcher Srings
zusammenfügt. (Später kommt noch das Komma dazu). Sobald der erste
String-Operand feststeht (möglicherweise auch als Ergebnis einer
Rekursion) und das Semikolon als Operator gefunden wurde, dann parse ich
den zweiten Operanden rekursiv weiter. Vor den Eintritt in die Rekursion
muß ich den ersten Operanden im Stack behalten, um ihn am Ende der
Rekursion vor den zweiten Operanden hängen zu können. Das ist dann also
dieser Fall, wo ich einen großen Buffer brauche.
Hier wäre ein Link zu meinem ursprübgichen Mini-BASIC-Interpreter, den
ich mal in Java im Rahmen eines Javaquiz geschrieben hatte:
http://basic.3dc.de
Der kann in etwa das, was die portierte avr-Version auch kann, dh.
letztere hat noch ein paar zusätzliche Einschränkungen, und ist etwas
unübersichtlicher als die Java-Version. Aber es reicht (wie schon
geschrieben) bei beiden so gerade eben zum Apfelmännchenberechnen aus :)
Grüße Ralf
> öhm, ich habe nicht erwähnt, dass mein BASIC-Parser neben> numerischen Werten auch an (bisher) einer Stelle kleine Strings> verarbeinten kann.
Ah, ok. Wenn Strings in Spiel kommen siehts natürlich anders
aus.
Gestern hats mich noch gepackt: Wieder mal einen Parser schreiben.
Ich hab mir dann noch schnell einen Rechner auf AVR-Basis
über UART gemacht. Nichts aufregendes: Grundrechenarten +-*/%
und Klammern, Punkt vor Strich. Die normale Expr-Term-Faktor
Grammatik halt. Ist zwar völlig sinnlos, aber hat Spass
gemacht :-)
A.K. wrote:
> (f)lex und yacc/bison ersetzen Programmspeicher durch erheblichen> Einsatz von Datenspeicher.
Allerdings nur voller konstanter Tabellen, die müssten sich eigentlich
auch in den ROM auslagern lassen. Hab ich aber zugegebenermaßen noch
nicht ernsthaft versucht.
Nein, sie "ersetzen" keinen Programmspeicher damit, sondern sie bauen
(wenn richtig benutzt) durchaus recht kompakten und schnellen Code,
indem sie eine state machine aufbauen. Das ist normalerweise deutlich
effektiver als irgendwelche strcmp-Orgien, und wenn man Dinge wie das
Parsen von Strings mit aufnehmen will, hat man in irgendeiner Form
auch immer dynamischen Speicher mit dabei.
> Ich kenne keine Architektur, die Rekursionen effektiv ausführen> und keinen Compiler, der Rekursionen effektiv umstellen kann.
Schau dir mal eine funktionale Sprache an, dann bekommst du eine andere
Sichtweise zu sehen.
In Haskell zum Beispiel ist Iteration gar nicht möglich, weil diese
Sprache "rein funktional" ist: Es gibt keine veränderbaren Variablen,
nur Funktionen und deren Aufrufe. Parameter sind unveränderbar ("const")
und Funktionsaufrufe sind referenziell transparent; das heißt, eine
Funktion liefert immer exakt dasselbe Ergebnis, wenn man sie mit
denselben Parametern aufruft, und ist absolut seiteneffektfrei. Das gilt
für alle Funktionen, sogar für solche wie getLine, die statt eines
Strings ein "IO-String-Objekt" liefern, das die Aktion "lies eine Zeile
von stdin" beschreibt.
Mit ghc gibt es einen sehr guten Haskell-Compiler, der bei manchen
Programmen sogar einem äquivalenten C-Programm das Wasser reichen kann.
Allerdings ist Haskell für Mikrocontroller wohl weniger geeignet, weil
die benötigte Laufzeitbibliothek recht umfangreich ist.
"Allerdings nur voller konstanter Tabellen, die müssten sich eigentlich
auch in den ROM auslagern lassen. "
Klar geht das. Weil aber GCC aber nicht mit Attributierung der
entsprechenden Typen und Tabellen zufrieden ist, sondern pgm_read_...
benötigt, muss man die Templates und evtl. den Codegenerator an beliebig
vielen Stellen entsprechen anpassen. Das wird Arbeit. Wenn die Grammatik
nicht zu komplex ist, ist man daher mit einem klassischen recursive
decent parser besser dran.
Und das oben skizzierte Problem mit String-Variablen hat man so oder so.
Auch yacc hat einen Stack, nur halt nicht für Rekursion sondern als
Bestandteil seiner engine.
Nö, das ist einfach kein passender Job für AVRs. Eher schon für MSP430
oder natürlich ARMs.
Mal zurück zur Rekursion selbst. Klar lässt sich jedes rekursive Problem
auch iterativ erledigen. Neben Effizienz des laufenden Codes gibt es
allerdings auch eine Effizienz bei der Programmierung und insbesondere
bei der Pflege des Codes. Und da kann Rekursion weit lesbarer sein als
dessen krampfige Vermeidung.
@Karl heinz Buchegger
> Ich hab mir dann noch schnell einen Rechner auf AVR-Basis> über UART gemacht ...
oh interessant. Wäre mal spannend, wie ein solches Gerät vom C-Profi
geschrieben innen aussieht. Ich komme ja mehr aus der Java-Ecke und
schreibe zudem nicht so sehr kompakten Code, und so sieht mein Parser
dann auch aus. Wir können ja einen neuen Thread starten: "Die schönsten,
die fettesten, die schnellsten, die umständlichsten, und alle anderen
UART-Rechner-Implementierungen auf dem ATmega8" oder so.
> ... Ist zwar völlig sinnlos, aber hat Spass gemacht :-)
gerade die sinnlosen Dinge machen ja oft den größten Spaß :)
Grüße Ralf
Ralf Rosenkranz wrote:
> @Karl heinz Buchegger>>> Ich hab mir dann noch schnell einen Rechner auf AVR-Basis>> über UART gemacht ...>> oh interessant. Wäre mal spannend, wie ein solches Gerät vom C-Profi> geschrieben innen aussieht.
Ich muss dich aber warnen. Das war 1 Uhr nachts.
Wenn ich zu Hause bin, poste ich das mal.
So. Da ist das Machwerk.
Wie gesagt: Ist schnell zusammengeschustert.
Es implementiert die übliche Grammatik
Expression := Term | { [ '+' | '-' ] Term }.
Term := Faktor { [ '*' | '/' | '%' ] Faktor }.
Faktor := [ '-' ] ( Number | ( '(' Expression ')' ) ).
Für einen lexikalischen Parser war ich zu faul. Das
Zahlenparsen hab ich daher in die Grammatik verlagert.
Number := Digit { Digit }.
@Karl heinz Buchegger
alle Achtung, da scheint kein Gramm überflüssiger Code in Deinem Parser
zu sein, genial gelöst finde ich. Schlank und präzise.
na der Vollständigkeit halber habe ich auch meinene Parserbasteleien mal
in der angehängten Datei zusammengefasst (und etwas zusammengekürzt),
alles darin ist zugegebenermaßen etwas umständlicher als in Deinem Code.
Und auch die Parserstrategie ist anders, nicht so konsequent rekursiv
wie bei Dir. Aber man kann trotzdem rechnen damit, +-*/ und Klammern.
Die Ein- und Ausgabe erfolgt ebenfalls über UART mit 9600 Baud,8,n,1
Grüße Ralf
Thread beobachten
Seitenaufteilung abschalten