Combien puis-je racheter? Combien puis-je racheter? Combien ca! @ # QFSD @ $ RFW

19

La carte Arduino Uno a une mémoire RAM limitée, ce qui signifie qu'elle dispose d'une pile d'appels limitée. Parfois, la récursivité est la seule option rapide pour implémenter un certain algorithme. Donc, étant donné que la pile d'appels est sévèrement limitée, quelle serait une façon de savoir qu'étant donné un certain programme exécuté sur la carte, combien d'appels récursifs pouvez-vous vous permettre avant qu'il y ait un débordement de pile (et que de mauvaises choses se produisent)?

asheeshr
la source
2
Pouvez-vous donner un exemple d'algorithme où le choix entre une solution récursive et non récursive est si clair?
Cybergibbons
1
@Cybergibbons Plus récemment, j'ai dû écrire et tester RDP dans un court laps de temps, j'ai donc poursuivi l'implémentation récursive. Je ne dis pas que l'itératif n'est pas possible, juste qu'il peut être plus facile d'aller de l'avant avec la version récursive.
asheeshr
Qu'est-ce que cela signifie dans le titre de la question How much ca!@#QFSD@$RFW:? Je suis curieux de savoir pourquoi personne n'a édité cela pour être quelque chose de plus significatif (au cours des 4 dernières années).
Nick Gammon
La réponse est 211fois (en fonction de nombreux facteurs) :). Voir ma réponse ici: arduino.stackexchange.com/a/51098/7727 . @ NickGammon, il fait semblant de "maudire" je pense. C'est un jeu de mot pour "recurse". Cela m'a pris une minute pour comprendre cela aussi. C'était assez déroutant au début.
Gabriel Staples
Oh je vois. Je pensais que les serveurs SE auraient pu avoir un problème :)
Nick Gammon

Réponses:

15

Si vous voulez vraiment recurer (et comme @jippie l'a dit, c'est une mauvaise idée; message subliminal: ne le faites pas ) et que vous voulez savoir combien vous pouvez recurer, alors vous devrez effectuer des calculs et des expériences; vous n'en aurez généralement qu'une approximation car cela dépend beaucoup de l'état de la mémoire au moment où votre fonction récursive sera appelée.

Pour cela, vous devez d'abord savoir comment la SRAM est organisée dans l'Arduino basé sur AVR (cela ne s'appliquera pas, par exemple, à l'Arduino Galileo d'Intel). Le schéma suivant d'Adafruit le montre clairement:

Organisation SRAM

Ensuite, vous devez connaître la taille totale de votre SRAM (dépend du microcontrôleur Atmel, d'où le type de carte Arduino que vous avez).

Sur ce diagramme, il est facile de déterminer la taille du bloc de données statiques tel qu'il est connu au moment de la compilation et ne changera pas plus tard.

La taille du segment de mémoire peut être plus difficile à connaître car elle peut varier au moment de l'exécution, selon les allocations de mémoire dynamique ( mallocou new) effectuées par votre croquis ou les bibliothèques qu'il utilise. L'utilisation de la mémoire dynamique est assez rare sur Arduino, mais certaines fonctions standard le font (le type l' Stringutilise, je pense).

Pour la taille de la pile , elle variera également pendant l'exécution, en fonction de la profondeur actuelle des appels de fonction (chaque appel de fonction prend 2 octets sur la pile pour stocker l'adresse de l'appelant) et du nombre et de la taille des variables locales, y compris les arguments passés ( qui sont également stockés sur la pile ) pour toutes les fonctions appelées jusqu'à présent.

Supposons donc que votre recurse()fonction utilise 12 octets pour ses variables et arguments locaux, puis chaque appel à cette fonction (le premier d'un appelant externe et les appels récursifs) utilisera des 12+2octets.

Si nous supposons que:

  • vous êtes sur Arduino UNO (SRAM = 2K)
  • votre esquisse n'utilise pas d'allocation de mémoire dynamique (pas de tas )
  • vous connaissez la taille de vos données statiques (disons 132 octets)
  • lorsque votre recurse()fonction est appelée à partir de votre esquisse, la pile actuelle fait 128 octets de long

Il vous reste alors des 2048 - 132 - 128 = 1788octets disponibles sur la pile . Le nombre d'appels récursifs à votre fonction est donc 1788 / 14 = 127, y compris l'appel initial (qui n'est pas récursif).

Comme vous pouvez le voir, c'est très difficile, mais pas impossible de trouver ce que vous voulez.

Un moyen plus simple d'obtenir la taille de pile disponible avant l' recurse()appel serait d'utiliser la fonction suivante (trouvée sur le centre d'apprentissage Adafruit; je ne l'ai pas testée moi-même):

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

Je vous encourage fortement à lire cet article au centre d'apprentissage Adafruit.

jfpoilpret
la source
Je vois que peter-r-bloomfield a posté sa réponse pendant que j'écrivais la mienne; sa réponse semble meilleure car elle décrit pleinement le contenu de la pile après un appel (j'avais oublié l'état des registres).
jfpoilpret
Les deux réponses de très bonne qualité.
Cybergibbons
Données statiques = .bss + .data, et ce qui est rapporté par Arduino comme "RAM occupée par des variables globales" ou quoi, n'est-ce pas?
Gabriel Staples
1
@GabrielStaples oui exactement. Plus en détail .bssreprésente les variables globales sans valeur initiale dans votre code, alors que datac'est pour les variables globales avec une valeur initiale. Mais au final, ils utilisent le même espace: les données statiques dans le diagramme.
jfpoilpret
1
@GabrielStaples a oublié une chose, techniquement, ce ne sont pas seulement des variables globales qui y vont, vous avez également des variables déclarées staticdans une fonction.
jfpoilpret
8

La récursivité est une mauvaise pratique sur un microcontrôleur comme vous l'avez déjà dit vous-même et vous voulez probablement l'éviter autant que possible. Sur le site Arduino, il y a quelques exemples et bibliothèques disponibles pour vérifier la taille de la RAM libre . Vous pouvez par exemple l'utiliser pour déterminer quand rompre la récursivité ou un peu plus délicat / plus risqué pour profiler votre croquis et coder en dur la limite. Ce profil serait requis pour chaque modification de votre programme et pour chaque modification de la chaîne d'outils Arduino.

jippie
la source
Certains des compilateurs les plus haut de gamme, tels que IAR (qui prennent en charge AVR) et Keil (qui ne prennent pas en charge AVR) ont des outils pour vous aider à surveiller et gérer l'espace de pile. Ce n'est vraiment pas conseillé sur quelque chose d'aussi petit qu'un ATmega328.
Cybergibbons
7

Cela dépend de la fonction.

Chaque fois qu'une fonction est appelée, une nouvelle trame est poussée sur la pile. Il contiendra généralement divers éléments critiques, notamment:

  • Adresse de retour (le point du code à partir duquel la fonction a été appelée).
  • Le pointeur d'instance local ( this) si vous appelez une fonction membre.
  • Paramètres passés dans la fonction.
  • Enregistrez les valeurs qui doivent être restaurées à la fin de la fonction.
  • Espace pour les variables locales à l'intérieur de la fonction appelée.

Comme vous pouvez le voir, l'espace de pile requis pour un appel donné dépend de la fonction. Par exemple, si vous écrivez une fonction récursive qui ne prend qu'un intparamètre et n'utilise aucune variable locale, elle n'aura pas besoin de beaucoup plus que quelques octets sur la pile. Cela signifie que vous pouvez l'appeler récursivement bien plus qu'une fonction qui prend plusieurs paramètres et utilise beaucoup de variables locales (ce qui consommera la pile beaucoup plus rapidement).

Évidemment, l'état de la pile dépend de ce qui se passe d'autre dans le code. Si vous lancez une récursivité directement dans la loop()fonction standard , il n'y aura probablement pas déjà beaucoup de choses sur la pile. Cependant, si vous le lancez imbriqué plusieurs niveaux profondément dans d'autres fonctions, il n'y aura pas autant de place. Cela affectera le nombre de fois que vous pouvez récéder sans épuiser la pile.

Il convient de noter que l'optimisation de la récursivité de queue existe sur certains compilateurs (même si je ne suis pas sûr que avr-gcc le supporte). Si l'appel récursif est la toute dernière chose dans une fonction, cela signifie qu'il est parfois possible d'éviter de modifier du tout le cadre de pile. Le compilateur peut simplement réutiliser le cadre existant, puisque l'appel «parent» (pour ainsi dire) a fini de l'utiliser. Cela signifie que vous pouvez théoriquement continuer à récurer autant que vous le souhaitez, tant que votre fonction n'appelle rien d'autre.

Peter Bloomfield
la source
1
avr-gcc ne prend pas en charge la récursivité de queue.
asheeshr
@AsheeshR - Bon à savoir. Merci. J'ai pensé que c'était probablement peu probable.
Peter Bloomfield
Vous pouvez faire une élimination / optimisation des appels de queue en refactorisant votre code au lieu d'espérer que le compilateur le fera. Tant que l'appel récursif est à la fin de la méthode récursive, vous pouvez réécrire la méthode en toute sécurité pour utiliser une boucle while / for.
abasterfield
1
Le post de @TheDoctor contredit "avr-gcc ne supporte pas la récursivité de queue", tout comme mon test de son code. Le compilateur a en effet implémenté la récursivité de queue, c'est ainsi qu'il a réussi à atteindre un million de récursions. Peter a raison - il est possible pour le compilateur de remplacer call / return (comme le dernier appel d'une fonction) par simplement jump . Il a le même résultat final et ne consomme pas d'espace de pile.
Nick Gammon
2

J'avais exactement la même question que je lisais Jumping into C ++ par Alex Allain , Ch 16: Recursion, p.230, j'ai donc fait quelques tests.

TLDR;

Mon Arduino Nano (mcu ATmega328) peut faire 211 appels de fonction récursifs (pour le code donné ci-dessous) avant qu'il y ait un débordement de pile et des plantages.

Tout d'abord, permettez-moi de répondre à cette affirmation:

Parfois, la récursivité est la seule option rapide pour implémenter un certain algorithme.

[Mise à jour: ah, j'ai survolé le mot "rapide". Dans ce cas, vous avez une certaine validité. Néanmoins, je pense que cela vaut la peine de dire ce qui suit.]

Non, je ne pense pas que ce soit une vraie déclaration. Je suis pratiquement certain que tous les algorithmes ont une solution récursive et non récursive, sans exception. C'est juste que parfois c'est beaucoup plus faciled'utiliser un algorithme récursif. Cela dit, la récursivité est très mal vue pour une utilisation sur les microcontrôleurs et ne serait probablement jamais autorisée dans le code critique pour la sécurité. Néanmoins, il est bien sûr possible de le faire sur des microcontrôleurs. Pour savoir à quel point vous pouvez entrer dans une fonction récursive donnée, testez-la! Exécutez-le dans votre application réelle dans un cas de test réel, et supprimez votre condition de base afin qu'elle se reproduise à l'infini. Imprimez un compteur et voyez par vous-même jusqu'où vous pouvez aller "en profondeur" pour savoir si votre algorithme récursif repousse les limites de votre RAM trop près pour être utilisé pratiquement. Voici un exemple ci-dessous pour forcer le débordement de pile sur un Arduino.

Maintenant, quelques notes:

Le nombre d'appels récursifs ou de "trames de pile" que vous pouvez obtenir est déterminé par un certain nombre de facteurs, notamment:

  • La taille de votre RAM
  • Combien de choses sont déjà sur votre pile ou prises dans votre tas (c'est-à-dire: votre RAM libre est importante;, free_RAM = total_RAM - stack_used - heap_usedou vous pourriez dire free_RAM = stack_size_allocated - stack_size_used)
  • La taille de chaque nouveau "cadre de pile" qui sera placé sur la pile pour chaque nouvel appel de fonction récursive. Cela dépendra de la fonction appelée, de ses variables et des besoins en mémoire, etc.

Mes résultats:

  • 20171106-2054hrs - Toshiba Satellite avec 16 Go de RAM; quad-core, Windows 8.1: valeur finale imprimée avant le crash: 43166
    • a pris plusieurs secondes pour planter - peut-être 5 ~ 10?
  • 20180306-1913hrs Ordinateur portable Dell haut de gamme avec 64 Go de RAM; 8 cœurs, Linux Ubuntu 14.04 LTS: valeur finale imprimée avant le crash: 261752
    • suivi de la phrase Segmentation fault (core dumped)
    • n'a pris que ~ 4 ~ 5 secondes environ pour planter
  • 20180306-1930hrs Arduino Nano: TBD --- est à ~ 250000 et continue de compter --- les paramètres d'optimisation Arduino ont dû l'amener à optimiser la récursivité ... ??? Oui, c'est le cas.
    • Ajoutez #pragma GCC optimize ("-O0")en haut du fichier et refaites:
  • 20180307-0910hrs Arduino Nano: Flash 32 Ko, SRAM 2 Ko, Processeur 16 MHz: valeur finale imprimée avant crash: 211 Here are the final print results: 209 210 211 ⸮ 9⸮ 3⸮
    • n'a pris qu'une fraction de seconde une fois qu'il a commencé à imprimer à 115200 bauds en série - peut-être 1/10 sec
    • 2 kiB = 2048 octets / 211 trames de pile = 9,7 octets / trame (en supposant que TOUTE votre RAM est utilisée par la pile - ce qui n'est pas le cas) - mais cela semble néanmoins très raisonnable.

Le code:

L'application PC:

/*
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);
}

Le programme Arduino "Sketch":

/*
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()
{
}

Les références:

  1. Sauter en C ++ par Alex Allain , Ch 16: Recursion, p.230
  2. http://www.electricrcaircraftguy.com/2014/01/the-power-of-arduino.html - littéralement: j'ai référencé mon propre site Web pendant ce "projet" pour me rappeler comment changer les niveaux d'optimisation du compilateur Arduino pour un fichier donné avec la #pragma GCC optimizecommande depuis que je savais que je l'avais documenté là-bas.
Gabriel Staples
la source
1
Notez que, selon les documents de avr-lib, vous ne devriez jamais compiler sans optimisation quoi que ce soit qui repose sur avr-libc, car certaines choses ne sont même pas garanties de fonctionner même avec l'optimisation désactivée. Je vous déconseille donc d' #pragmautiliser ce que vous y utilisez. Au lieu de cela, vous pouvez ajouter __attribute__((optimize("O0")))à la fonction unique que vous souhaitez désactiver.
Edgar Bonet
Merci, Edgar. Savez-vous où AVR libc a documenté cela?
Gabriel Staples
1
La documentation sur <util / delay.h> stipule: "Pour que ces fonctions fonctionnent comme prévu, les optimisations du compilateur doivent être activées [...]" (souligné dans l'original). Je ne sais pas trop si d'autres fonctions avr-libc ont cette exigence.
Edgar Bonet
1

J'ai écrit ce programme de test simple:

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);
}

Je l'ai compilé pour l'Uno, et au moment où j'écris, il s'est reproduit plus d'un million de fois! Je ne sais pas, mais le compilateur a peut-être optimisé ce programme

Le docteur
la source
Essayez de revenir après un nombre défini d'appels ~ 1000. Cela devrait alors créer un problème.
asheeshr
1
Le compilateur a astucieusement implémenté la récursion de queue sur votre croquis, comme vous le verrez si vous le démontez. Cela signifie qu'il remplace la séquence call xxx/ retpar jmp xxx. Cela revient au même, sauf que la méthode du compilateur ne consomme pas la pile. Ainsi, vous pourriez récuser des milliards de fois avec votre code (toutes choses étant égales par ailleurs).
Nick Gammon
Vous pouvez forcer le compilateur à ne pas optimiser la récursivité. Je reviendrai et posterai un exemple plus tard.
Gabriel Staples
Terminé! Exemple ici: arduino.stackexchange.com/a/51098/7727 . Le secret est d'empêcher l'optimisation en ajoutant #pragma GCC optimize ("-O0") en haut de votre programme Arduino. Je crois que vous devez le faire en haut de chaque dossier auquel vous souhaitez qu'il s'applique - mais je n'ai pas recherché cela depuis des années, alors recherchez-le par vous-même pour en être sûr.
Gabriel Staples