Wie viel kann ich reklamieren? Wie viel kann ich reklamieren? Wie viel ca! @ # QFSD @ $ RFW

19

Die Arduino Uno-Karte verfügt über einen begrenzten Arbeitsspeicher, was bedeutet, dass ein begrenzter Aufrufstapel verfügbar ist. Manchmal ist die Rekursion die einzige schnelle Option, um einen bestimmten Algorithmus zu implementieren. Wenn der Aufrufstapel stark eingeschränkt ist, wie kann man dann feststellen, dass bei einem bestimmten Programm auf der Platine genau wie viele rekursive Aufrufe möglich sind, bevor ein Stapelüberlauf auftritt (und schlimme Dinge passieren)?

Ascheshr
quelle
2
Können Sie ein Beispiel für einen Algorithmus nennen, bei dem die Wahl zwischen einer rekursiven und einer nicht rekursiven Lösung so eindeutig ist?
Cybergibbons
1
@ Cybergibbons In letzter Zeit musste ich RDP in kurzer Zeit schreiben und testen , also fuhr ich mit der rekursiven Implementierung fort. Ich sage nicht, dass eine Iteration nicht möglich ist, nur, dass es möglicherweise einfacher ist, mit der rekursiven Version fortzufahren.
Asheeshr
Was bedeutet das im Fragentitel How much ca!@#QFSD@$RFW:? Ich bin gespannt, warum das in den letzten 4 Jahren von niemandem sinnvoller herausgearbeitet wurde.
Nick Gammon
Die Antwort ist 211mal (abhängig von vielen Faktoren) :). Siehe meine Antwort hier: arduino.stackexchange.com/a/51098/7727 . @ NickGammon, er tut so als ob er "flucht", denke ich. Es ist ein Wortspiel für "Rekurs". Ich habe eine Minute gebraucht, um das herauszufinden. War anfangs ziemlich verwirrend.
Gabriel Staples
Oh ich verstehe. Ich dachte, die SE-Server hätten einen Fehler gehabt :)
Nick Gammon

Antworten:

15

Wenn Sie wirklich wiederkehren möchten (und wie @jippie sagte, ist es eine schlechte Idee; unterschwellige Meldung: Tun Sie es nicht ) und wissen möchten, wie viel Sie wiederkehren können, müssen Sie einige Berechnungen und Experimente durchführen. Außerdem haben Sie im Allgemeinen nur eine Annäherung, da dies stark vom Speicherstatus zum Zeitpunkt des Aufrufs Ihrer rekursiven Funktion abhängt.

Zu diesem Zweck sollten Sie zunächst wissen, wie SRAM in AVR-basiertem Arduino organisiert ist (dies gilt beispielsweise nicht für Arduino Galileo von Intel). Das folgende Diagramm von Adafruit zeigt es deutlich:

SRAM-Organisation

Dann müssen Sie die Gesamtgröße Ihres SRAM kennen (hängt von der Atmel-MCU ab, daher welche Art von Arduino-Karte Sie haben).

In diesem Diagramm ist es einfach, die Größe des statischen Datenblocks zu ermitteln, da dieser zur Kompilierungszeit bekannt ist und sich später nicht mehr ändert.

Die Größe des Heapspeichers kann schwieriger zu ermitteln sein, da sie zur Laufzeit variieren kann, abhängig von den dynamischen Speicherzuweisungen ( mallocoder new), die von Ihrer Skizze oder den verwendeten Bibliotheken durchgeführt werden. Die Verwendung von dynamischem Speicher ist auf Arduino recht selten, aber einige Standardfunktionen tun dies ( Stringich denke, Typ verwendet ihn).

Die Stack- Größe variiert auch während der Laufzeit, basierend auf der aktuellen Tiefe der Funktionsaufrufe (jeder Funktionsaufruf benötigt 2 Byte im Stack, um die Adresse des Aufrufers zu speichern) und der Anzahl und Größe der lokalen Variablen einschließlich der übergebenen Argumente ( die auch auf dem Stack gespeichert sind ) für alle bisher aufgerufenen Funktionen.

Nehmen wir also an, Ihre recurse()Funktion verwendet 12 Bytes für ihre lokalen Variablen und Argumente, und jeder Aufruf dieser Funktion (der erste von einem externen Aufrufer und der rekursive) verwendet 12+2Bytes.

Wenn wir das annehmen:

  • du bist auf Arduino UNO (SRAM = 2K)
  • Ihre Skizze verwendet keine dynamische Speicherzuordnung (kein Heap )
  • Sie kennen die Größe Ihrer statischen Daten (sagen wir 132 Bytes)
  • Wenn Ihre recurse()Funktion aus Ihrer Skizze aufgerufen wird, ist der aktuelle Stapel 128 Byte lang

Dann verbleiben Ihnen die 2048 - 132 - 128 = 1788verfügbaren Bytes auf dem Stack . Die Anzahl der rekursiven Aufrufe Ihrer Funktion beträgt somit 1788 / 14 = 127einschließlich des ersten Aufrufs (der kein rekursiver Aufruf ist).

Wie Sie sehen, ist es sehr schwierig, aber nicht unmöglich, das zu finden, was Sie suchen.

Eine einfachere Möglichkeit, die zuvor verfügbare Stack-Größe abzurufen, recurse()ist die Verwendung der folgenden Funktion (im Adafruit Learning Center verfügbar ; ich habe sie nicht selbst getestet):

int freeRam () 
{
  extern int __heap_start, *__brkval; 
  int v; 
  return (int) &v - (__brkval == 0 ? (int) &__heap_start : (int) __brkval); 
}

Ich empfehle Ihnen nachdrücklich, diesen Artikel im Adafruit Learning Center zu lesen .

jfpoilpret
quelle
Ich sehe, dass Peter-R-Bloomfield seine Antwort gepostet hat, während ich meine schrieb. seine antwort sieht besser aus, da sie den inhalt des stapels nach einem aufruf vollständig beschreibt (ich hatte den registerstatus vergessen).
jfpoilpret
Beide Antworten sind von sehr guter Qualität.
Cybergibbons
Statische Daten = .bss + .data, und was wird von Arduino als "RAM von globalen Variablen belegt" oder was auch immer gemeldet, richtig?
Gabriel Staples
1
@ GabrielStaples ja genau. Im Einzelnen werden .bssdie globalen Variablen ohne Anfangswert in Ihrem Code dargestellt, wohingegen dataes sich um globale Variablen mit Anfangswert handelt. Letztendlich verwenden sie jedoch denselben Platz: Statische Daten im Diagramm.
jfpoilpret
1
@ GabrielStaples hat eines vergessen, technisch gesehen sind dies nicht nur globale Variablen, sondern Sie haben auch Variablen, die staticin einer Funktion deklariert sind.
jfpoilpret
8

Rekursion ist eine schlechte Praxis auf einem Mikrocontroller, wie Sie bereits selbst angegeben haben und Sie möchten sie wahrscheinlich nach Möglichkeit vermeiden. Auf der Arduino-Website stehen einige Beispiele und Bibliotheken zum Überprüfen der freien RAM-Größe zur Verfügung . Sie können dies zum Beispiel verwenden, um herauszufinden, wann eine Rekursion zu unterbrechen ist, oder um etwas schwieriger / riskanter, Ihre Skizze zu profilieren und das darin enthaltene Limit festzuhalten. Dieses Profil wäre für jede Änderung in Ihrem Programm und für jede Änderung in der Arduino-Toolkette erforderlich.

jippie
quelle
Einige der anspruchsvolleren Compiler wie IAR (die AVR unterstützen) und Keil (die AVR nicht unterstützen) verfügen über Tools, mit denen Sie den Stapelspeicher überwachen und verwalten können. Es ist wirklich nicht ratsam auf etwas so klein wie ein ATmega328.
Cybergibbons
7

Das hängt von der Funktion ab.

Jedes Mal, wenn eine Funktion aufgerufen wird, wird ein neuer Frame auf den Stapel gelegt. Es enthält normalerweise verschiedene kritische Elemente, die möglicherweise Folgendes umfassen:

  • Rücksprungadresse (der Punkt im Code, von dem aus die Funktion aufgerufen wurde).
  • Der lokale Instanzzeiger ( this), wenn eine Member-Funktion aufgerufen wird.
  • Parameter, die an die Funktion übergeben werden.
  • Registrieren Sie Werte, die nach Beendigung der Funktion wiederhergestellt werden müssen.
  • Platz für lokale Variablen innerhalb der aufgerufenen Funktion.

Wie Sie sehen, hängt der für einen bestimmten Aufruf erforderliche Stapelspeicherplatz von der Funktion ab. Wenn Sie beispielsweise eine rekursive Funktion schreiben, die nur einen intParameter verwendet und keine lokalen Variablen verwendet, benötigt sie nicht viel mehr als ein paar Bytes auf dem Stapel. Das heißt, Sie können es rekursiv weitaus mehr aufrufen als eine Funktion, die mehrere Parameter und viele lokale Variablen verwendet (was den Stapel viel schneller auffrisst).

Offensichtlich hängt der Status des Stapels davon ab, was im Code noch vor sich geht. Wenn Sie eine Rekursion direkt in der Standardfunktion starten loop(), ist wahrscheinlich noch nicht viel auf dem Stapel. Wenn Sie es jedoch in anderen Funktionen mehrere Ebenen tief verschachtelt starten, ist weniger Platz vorhanden. Dies hat Einfluss darauf, wie oft Sie wiederkehren können, ohne den Stapel zu erschöpfen.

Es ist erwähnenswert, dass es auf einigen Compilern eine Optimierung der Schwanzrekursion gibt (obwohl ich nicht sicher bin, ob avr-gcc dies unterstützt). Wenn der rekursive Aufruf das allerletzte Element in einer Funktion ist, ist es manchmal möglich, das Ändern des Stapelrahmens überhaupt zu vermeiden. Der Compiler kann den vorhandenen Frame einfach wiederverwenden, da der übergeordnete Aufruf (sozusagen) ihn nicht mehr verwendet. Das bedeutet, dass Sie theoretisch so oft rekursiv arbeiten können, wie Sie möchten, solange Ihre Funktion nichts anderes aufruft.

Peter Bloomfield
quelle
1
avr-gcc unterstützt keine Schwanzrekursion.
Asheeshr
@AsheeshR - Gut zu wissen. Vielen Dank. Ich hielt es für unwahrscheinlich.
Peter Bloomfield
Sie können eine Tail-Call-Eliminierung / -Optimierung durchführen, indem Sie Ihren Code überarbeiten, anstatt zu hoffen, dass der Compiler dies tut. Solange sich der rekursive Aufruf am Ende der rekursiven Methode befindet, können Sie die Methode sicher neu schreiben, um eine while / for-Schleife zu verwenden.
Abasterfield
1
Der Beitrag von @TheDoctor widerspricht "avr-gcc unterstützt keine Schwanzrekursion", ebenso wie mein Test seines Codes. Der Compiler hat tatsächlich eine Schwanzrekursion implementiert, wodurch er auf eine Million Rekursionen kam. Peter hat recht - es ist dem Compiler möglich, call / return (als letzten Aufruf einer Funktion) durch einen einfachen Sprung zu ersetzen . Es hat das gleiche Endergebnis und verbraucht keinen Stapelspeicher.
Nick Gammon
2

Ich hatte genau die gleiche Frage, als ich " Jumping into C ++" von Alex Allain , Kapitel 16: Rekursion, S. 230, las. Deshalb führte ich einige Tests durch.

TLDR;

Mein Arduino Nano (ATmega328 mcu) kann 211 rekursive Funktionsaufrufe ausführen (für den unten angegebenen Code), bevor er einen Stapelüberlauf hat und abstürzt.

Lassen Sie mich zunächst auf diese Behauptung eingehen:

Manchmal ist die Rekursion die einzige schnelle Option, um einen bestimmten Algorithmus zu implementieren.

[Update: ah, ich habe das Wort "schnell" überflogen. In diesem Fall haben Sie eine gewisse Gültigkeit. Trotzdem denke ich, dass es sich lohnt, Folgendes zu sagen.]

Nein, ich halte das nicht für eine wahre Aussage. Ich bin mir ziemlich sicher, dass alle Algorithmen ausnahmslos sowohl eine rekursive als auch eine nicht rekursive Lösung haben. Es ist nur manchmal deutlich einfachereinen rekursiven Algorithmus verwenden. Allerdings ist Rekursion für die Verwendung auf Mikrocontrollern sehr verpönt und würde in sicherheitskritischem Code wahrscheinlich niemals zugelassen werden. Trotzdem ist es natürlich möglich, dies auf Mikrocontrollern zu tun. Um zu wissen, wie "tief" Sie in eine bestimmte rekursive Funktion eintauchen können, testen Sie sie einfach! Führen Sie es in Ihrer realen Anwendung in einem realen Testfall aus, und entfernen Sie die Grundbedingung, damit es unendlich oft wiederkehrt. Drucken Sie einen Zähler aus und überzeugen Sie sich selbst, wie tief Sie gehen können, damit Sie wissen, ob Ihr rekursiver Algorithmus die Grenzen Ihres Arbeitsspeichers zu weit ausschöpft, um praktisch verwendet zu werden. Hier ist ein Beispiel, um einen Stapelüberlauf auf einem Arduino zu erzwingen.

Nun ein paar Anmerkungen:

Wie viele rekursive Aufrufe oder "Stapelrahmen" Sie erhalten können, hängt von einer Reihe von Faktoren ab, darunter:

  • Die Größe Ihres RAM
  • Wie viel Zeug ist bereits auf Ihrem Stapel oder auf Ihrem Haufen (dh: Ihr freier RAM ist wichtig; free_RAM = total_RAM - stack_used - heap_usedoder Sie könnten sagen free_RAM = stack_size_allocated - stack_size_used)
  • Die Größe jedes neuen "Stapelrahmens", der bei jedem neuen rekursiven Funktionsaufruf auf dem Stapel abgelegt wird. Dies hängt von der aufgerufenen Funktion und ihren Variablen und Speicheranforderungen usw. ab.

Meine Ergebnisse:

  • 20171106-2054hrs - Toshiba Satellite mit 16 GB RAM; Quad-Core, Windows 8.1: Endwert vor Absturz gedruckt: 43166
    • Der Absturz dauerte einige Sekunden - vielleicht 5 ~ 10?
  • 20180306-1913hrs Dell High-End-Laptop mit 64 GB RAM; 8-Core, Linux Ubuntu 14.04 LTS: Endwert vor Absturz gedruckt: 261752
    • gefolgt von der Phrase Segmentation fault (core dumped)
    • Der Absturz dauerte nur ungefähr 4 bis 5 Sekunden
  • 20180306-1930hrs Arduino Nano: TBD --- ist bei ~ 250000 und zählt immer noch --- die Arduino-Optimierungseinstellungen müssen dazu geführt haben, dass die Rekursion optimiert wurde ... ??? Ja das ist der fall
    • In #pragma GCC optimize ("-O0")Zum Anfang der Datei und Redo:
  • 20180307-0910hrs Arduino Nano: 32-kB-Flash, 2-kB-SRAM, 16-MHz-Prozessor oder: Endwert vor dem Absturz gedruckt: 211 Here are the final print results: 209 210 211 ⸮ 9⸮ 3⸮
    • es dauerte nur einen Bruchteil einer Sekunde, als der Druck mit einer seriellen Baudrate von 115200 begann - vielleicht 1/10 Sek
    • 2 kiB = 2048 Bytes / 211 Stack-Frames = 9,7 Bytes / Frame (vorausgesetzt, der gesamte Arbeitsspeicher wird vom Stack verwendet - was eigentlich nicht der Fall ist), aber dies scheint dennoch sehr vernünftig zu sein.

Der Code:

Die PC-Anwendung:

/*
stack_overflow
 - a quick program to force a stack overflow in order to see how many stack frames in a small function can be loaded onto the stack before the overflow occurs

By Gabriel Staples
www.ElectricRCAircraftGuy.com
Written: 6 Nov 2017
Updated: 6 Nov 2017

References:
 - Jumping into C++, by Alex Allain, pg. 230 - sample code here in the chapter on recursion

To compile and run:
Compile: g++ -Wall -std=c++11 stack_overflow_1.cpp -o stack_overflow_1
Run in Linux: ./stack_overflow_1
*/

#include <iostream>

void recurse(int count)
{
  std::cout << count << "\n";
  recurse(count + 1);
}

int main()
{
  recurse(1);
}

Das Arduino "Sketch" -Programm:

/*
recursion_until_stack_overflow
- do a quick recursion test to see how many times I can make the call before the stack overflows

Gabriel Staples
Written: 6 Mar. 2018 
Updated: 7 Mar. 2018 

References:
- Jumping Into C++, by Alex Allain, Ch. 16: Recursion, p.230
*/

// Force the compiler to NOT optimize! Otherwise this recursive function below just gets optimized into a count++ type
// incrementer instead of doing actual recursion with new frames on the stack each time. This is required since we are
// trying to force stack overflow. 
// - See here for all optimization levels: https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
//   - They include: -O1, -O2, -O3, -O0, -Os (Arduino's default I believe), -Ofast, & -Og.

// I mention `#pragma GCC optimize` in my article here: http://www.electricrcaircraftguy.com/2014/01/the-power-of-arduino.html
#pragma GCC optimize ("-O0") 

void recurse(unsigned long count) // each call gets its own "count" variable in a new stack frame 
{
  // delay(1000);
  Serial.println(count);

  // It is not necessary to increment count since each function's variables are separate (so the count in each stack
  // frame will be initialized one greater than the last count)
  recurse (count + 1);

  // GS: notice that there is no base condition; ie: this recursive function, once called, will never finish and return!
}

void setup()
{
  Serial.begin(115200);
  Serial.println(F("\nbegin"));
  // First function call, so it starts at 1
  recurse (1);
}

void loop()
{
}

Verweise:

  1. Sprung in C ++ von Alex Allain , Kapitel 16: Rekursion, S.230
  2. http://www.electricrcaircraftguy.com/2014/01/the-power-of-arduino.html - im wahrsten Sinne des Wortes: Ich habe in diesem "Projekt" auf meine eigene Website verwiesen, um mich daran zu erinnern, wie ich die Arduino-Compiler-Optimierungsstufen für eine bestimmte Datei ändern kann mit dem #pragma GCC optimizebefehl, da ich wusste, dass ich es dort dokumentiert hatte.
Gabriel Staples
quelle
1
Beachten Sie, dass Sie laut den Dokumenten der avr-lib niemals ohne Optimierung etwas kompilieren sollten, das von der avr-libc abhängt, da einige Dinge nicht garantiert funktionieren, selbst wenn die Optimierung deaktiviert ist. Ich rate Ihnen daher von dem ab, was #pragmaSie dort verwenden. Stattdessen können Sie __attribute__((optimize("O0")))die einzelne Funktion, die Sie nicht optimieren möchten, ergänzen.
Edgar Bonet
Danke, Edgar. Wissen Sie, wo AVR libc dies dokumentiert hat?
Gabriel Staples
1
In der Dokumentation zu <util / delay.h> heißt es: "Damit diese Funktionen wie vorgesehen funktionieren, müssen Compiler-Optimierungen aktiviert sein [...]" (Hervorhebung im Original). Ich bin mir nicht ganz sicher, ob andere avr-libc-Funktionen diese Anforderung erfüllen.
Edgar Bonet
1

Ich habe dieses einfache Testprogramm geschrieben:

void setup() {
  // put your setup code here, to run once:
  Serial.begin(115200);
  recurse(1);
}

void loop() {
  // put your main code here, to run repeatedly: 

}

void recurse(long i) {
  Serial.println(i);
  recurse(i+1);
}

Ich habe es für die Uno kompiliert und während ich schreibe, ist es über 1 Million Mal rekursiv vorgekommen! Ich weiß es nicht, aber der Compiler hat dieses Programm möglicherweise optimiert

Der Doktor
quelle
Versuchen Sie nach einer festgelegten Anzahl von Anrufen ~ 1000 zurückzukehren. Dann sollte es ein Problem geben.
Asheeshr
1
Der Compiler hat die Schwanzrekursion geschickt in Ihre Skizze implementiert , da Sie sehen werden, ob Sie sie zerlegen. Dies bedeutet, dass es die Sequenz call xxx/ retdurch ersetzt jmp xxx. Dies entspricht dem gleichen Vorgang, mit der Ausnahme, dass die Compilermethode den Stack nicht verbraucht. Auf diese Weise können Sie Ihren Code milliardenfach wiederverwenden (andere Dinge sind gleich).
Nick Gammon
Sie können den Compiler zwingen, die Rekursion nicht zu optimieren. Ich werde später zurückkommen und ein Beispiel posten.
Gabriel Staples
Getan! Beispiel hier: arduino.stackexchange.com/a/51098/7727 . Das Geheimnis besteht darin, die Optimierung zu verhindern, indem Sie sie #pragma GCC optimize ("-O0") an die Spitze Ihres Arduino-Programms setzen. Ich glaube, Sie müssen dies am Anfang jeder Datei tun, auf die Sie sie anwenden möchten - aber ich habe das seit Jahren nicht mehr nachgeschlagen, also recherchieren Sie es selbst, um sicherzugehen.
Gabriel Staples