Forum: Compiler & IDEs Rekursiver Funktionsaufruf (AVR)


von Michael Summer (Gast)


Lesenswert?

Hallo,
habe da mal ne Frage an euch Profis (bin noch nicht so bewandert mit
dem AVR):

Ich habe vor ein Spiel (ist kein komplexes Siel, ist so ne art 3 in
einer reihe) mit dem AVR (Mega128) zu realisieren. Dabei soll nach
jedem Zug die Spielsituation bewertet werden, anhand der nächsten
möglichen Spielmöglichkeiten. Soll so ne art KI werden. Dabei ruft die
Funktion die die Spielsituation bewertet sich immer wieder selbst auf
(rekursiv).

Auf dem PC läuft das Prog schon (Konsole) sind ein paar kB. Jetzt
möchte ich das Spiel auf den Mega128 bringen, kann es da Probleme mit
dem Rekursiven Funktionsaaufruf geben? Kann ich das im Vorfeld schon
mit einem Tool checken, wieviel Speicher im worstcase mit der Rekursion
draufgeht? Oder was gibt es da für möglichkeiten?

Ich hoffe ihr versteht mein Problem.
Danke schon mal für die Antworten.

von Karl heinz B. (kbucheg)


Lesenswert?

> kann es da Probleme mit dem Rekursiven Funktionsaaufruf geben?

Probleme kann es immer geben :-)
Kann, muss aber nicht.

> Kann ich das im Vorfeld schon mit einem Tool checken, wieviel
> Speicher im worstcase mit der Rekursion draufgeht?

Den tatsächlichen Speicherverbrauch kann man nur
feststellen indem das Programm läuft. Allerdings könnte
man das in einem Simulator machen.

> Oder was gibt es da für möglichkeiten?
Eine Möglichkeit ist zb. folgende:

Du sorgst dafür, dass am Anfang der Speicher in dem der
Stack residiert mit einem Bitmuster gefüllt wird, zb 0xAA
dann lässt du das Programm laufen und wenn es durchgelaufen
ist, schaust du dir den Speicher wieder an. Alles was immer
noch 0xAA ist, ist offensichtlich niemals angetascht worden.
Zur Sicherheit macht man das dann noch mit einem 2-ten
Muster (was ist, wenn zufällig 0xAA auf den Stack geschrieben
wurde), zb. 0x55.
Damit kannst du feststellen, wieviel Stack in diesem einen
Programmlauf verbraucht wurde. Es liegt dann an dir dein
Programm so zu bedienen, dass du den Fall 'maximaler
Stackverbrauch' vorliegen hast.

von Oliver (Gast)


Lesenswert?

Eine Simulation mit vmlab kann da auch weiterhelfen. (Version 3.12 ist
freeware).

Oliver

von Karl heinz B. (kbucheg)


Lesenswert?

Anmerken sollte man noch: Nur mir den Mitteln einer Hochsprache ist
das etwas schwierg zu lösen. Du wirst also darauf angewiesen sein,
dass die dein Simulator funktionen bereitstellt, mit denen
du vor und nach Programmausführung an den simulierten Speicher
rankommst.

von Stefan (Gast)


Lesenswert?

Der Tipp von Karl Heinz mit dem markierten Stackbereich ist gut und
schnell zu implementieren. Das Bitmuster könnte man sogar z.B. im
Startup-Code defaultmäßig schreiben lassen.

Ich hätte noch weitere Ideen:

Hol dein modifiziertes Programm in einen Debugger und schau dir den
Stackpointer an den notorischen Stellen an.

Modifiziert heisst, dass du nur die Rekursion nicht durchführst, aber
sonst den Code unverändert lässt. Du bekommst so den Stackverbrauch für
ein Funktionslevel. Für jeden Aufruf in der Rekursion addierst du diesen
Wert auf.

Die notorischen Stellen sind Stackpointer nach dem Rücksprung der
Funktion und an der Stelle mit dem höchsten Stackverbrauch in der
Funktion.

Der höchste Stackverbrauch ist oft am Funktionsanfang nach dem Anlegen
der Autovariablen. Genauer kann man die optimale Prüfposition mit dem
Sourcecode festlegen ggf. sogar im Assemblerlisting nachsehen wo SP
maximal verändert ist.

Ein anderer Weg wäre, dass du eine Stackprüffunktion (Stackpointer per
Inline ASM holen) an den Anfang der Rekursionsfunktion stellst. Diese
Prüffunktion kann den aktuellen Stackpointer ausgeben und/oder prüfen,
ob sich der Stackpointer einer kritischen Grenze nähert. Damit kannst
du zur Laufzeit der Rekursion Infos bekommen und experimentell
herausfinden, ob Gefahr besteht, dass es knallt.

von Peter D. (peda)


Lesenswert?

Rekursionen sind eine spezielle mathematische Schreibweise und daher
nicht so effizient, wie andere Lösungen.

Sie sind teilweise sogar extrem ineffizient, wenn darin mehrere
Vorgänger benötigt werden, da dann Rekursionen exponentiell umsonst
berechnet werden müssen.


In der Regel lassen sich Rekursionen einfach in Schleifen umformen und
laufen dann viel schneller und benötigen viel weniger Speicherplatz.


Peter

von Daniel M. (usul27)


Lesenswert?

Also wenn wir hier von KI sprechen, dann sind diese rekursiven Sachen
wohl höchstwahrscheinlich Suchoperationen in einem potentiell sehr
grossen Zustandsraum - vermutlich eine Art MIN-MAX-Algorithmus. Solche
Sachen lassen sich nun wieder in der Regel NICHT in Schleifen umformen
(wenn wir mal von speziellen Zustandsräumen absehen). Das einzige was
da bleibt ist es "nutzlose" Zweige möglichst früh zu erkennen und
nicht abzuarbeiten.

von Malte _. (malte) Benutzerseite


Lesenswert?

Alternative zur oben geschriebenen Analyse wäre, sich den erzeugten
Assemblercode anzusehen und mal zu zählen wie viele push/pop und
call/ret (2Byte) bei jeder Rekursion insgesammt ausgeführt werden. Dann
diese Zahl mit der Suchtiefe multiplizieren. Bei meiner 4-Gewinnt
Routine schafft ein AVR rund 6 Rekursionen bei weniger als 1KB RAM
Verbrauch. Für mehr ist der AVR schlicht zu langsam, der Speicher ist
aber (zumindest bei mir) kein Problem.

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.