Quanto posso pagar? Quanto posso pagar? Quanto ca! @ # QFSD @ $ RFW

19

A placa do Arduino Uno possui RAM limitada, o que significa que possui uma pilha de chamadas limitada disponível. Às vezes, a recursão é a única opção rápida para implementar um determinado algoritmo. Portanto, considerando que a pilha de chamadas é severamente limitada, qual seria a maneira de descobrir que, dado um determinado programa em execução no quadro, exatamente quantas chamadas recursivas você pode pagar antes que haja um estouro de pilha (e coisas ruins acontecem)?

asheeshr
fonte
2
Você pode dar um exemplo de algoritmo em que a escolha entre uma solução recursiva e não recursiva é tão clara?
Cybergibbons
1
@ Cyybibbons Mais recentemente, eu tive que escrever e testar o RDP em um curto espaço de tempo, então continuei com a implementação recursiva. Não estou dizendo que iterativo não é possível, apenas que pode ser mais fácil prosseguir com a versão recursiva.
asheeshr
O que isso significa no título da pergunta How much ca!@#QFSD@$RFW:? Estou curioso para saber por que ninguém editou isso como algo mais significativo (nos últimos 4 anos).
Nick Gammon
A resposta é 211vezes (dependendo de muitos fatores) :). Veja minha resposta aqui: arduino.stackexchange.com/a/51098/7727 . @NickGammon, ele finge "xingar", eu acho. É um jogo de palavras para "recursão". Levei um minuto para descobrir isso também. Foi bastante confuso no começo.
Gabriel Staples
Ah eu vejo. Eu pensei que os servidores SE poderia ter tido uma falha :)
Nick Gammon

Respostas:

15

Se você realmente deseja se retribuir (e como @jippie disse que é uma péssima idéia; mensagem subliminar: não faça isso ) e quer saber o quanto você pode retribuir, será necessário realizar alguns cálculos e experimentos; Além disso, você geralmente terá apenas uma aproximação, pois depende muito do estado da memória no momento em que sua função recursiva será chamada.

Para isso, você deve primeiro saber como a SRAM é organizada no Arduino baseado no AVR (não se aplica, por exemplo, ao Arduino Galileo da Intel). O diagrama a seguir da Adafruit mostra claramente:

Organização SRAM

Então você precisa saber o tamanho total da sua SRAM (depende do Atmel MCU, portanto, que tipo de placa Arduino você possui).

Neste diagrama, é fácil descobrir esse tamanho do bloco Static Data , pois é conhecido em tempo de compilação e não será alterado posteriormente.

O tamanho da pilha pode ser mais difícil de saber, pois pode variar em tempo de execução, dependendo das alocações de memória dinâmica ( mallocou new) executadas pelo seu esboço ou pelas bibliotecas que ele usa. O uso de memória dinâmica é bastante raro no Arduino, mas algumas funções padrão o fazem (o tipo Stringusa, eu acho).

Para o tamanho da pilha , ele também varia durante o tempo de execução, com base na profundidade atual das chamadas de função (cada chamada de função ocupa 2 bytes na pilha para armazenar o endereço do chamador) e o número e tamanho das variáveis ​​locais, incluindo argumentos passados ​​( que também são armazenados na pilha ) para todas as funções chamadas até agora.

Então, vamos supor que sua recurse()função use 12 bytes para suas variáveis ​​e argumentos locais, então cada chamada para essa função (a primeira de um chamador externo e a recursiva) usará 12+2bytes.

Se supusermos que:

  • você está no Arduino UNO (SRAM = 2K)
  • seu sketch não usa alocação dinâmica de memória (sem Heap )
  • você sabe o tamanho dos seus dados estáticos (digamos 132 bytes)
  • quando sua recurse()função é chamada do esboço, a pilha atual tem 128 bytes

Então você fica com 2048 - 132 - 128 = 1788os bytes disponíveis na pilha . O número de chamadas recursivas para sua função é 1788 / 14 = 127, portanto , incluindo a chamada inicial (que não é recursiva).

Como você pode ver, isso é muito difícil, mas não impossível de encontrar o que você deseja.

Uma maneira mais simples de obter o tamanho da pilha disponível antes da recurse()chamada seria usar a seguinte função (encontrada no Adafruit learning center; eu mesmo não testei):

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

É altamente recomendável que você leia este artigo no Adafruit learning center.

jfpoilpret
fonte
Vejo Peter-Bloomfield postou sua resposta enquanto escrevia a minha; sua resposta parece melhor, pois descreve completamente o conteúdo da pilha após uma chamada (eu havia esquecido o estado dos registradores).
Jfpoilpret
Ambas as respostas de qualidade muito boa.
Cybergibbons
Dados estáticos = .bss + .data, e é o que é relatado pelo Arduino como "RAM ocupada por variáveis ​​globais" ou o que for, correto?
Gabriel Staples
1
@GabrielStaples sim exatamente. Mais detalhadamente .bssrepresenta as variáveis ​​globais sem valor inicial no seu código, enquanto que dataé para variáveis ​​globais com um valor inicial. Mas, no final, eles usam o mesmo espaço: Dados estáticos no diagrama.
Jfpoilpret 24/0318
1
@GabrielStaples esqueceu uma coisa: tecnicamente, essas não são apenas variáveis ​​globais, mas também há variáveis ​​declaradas staticem uma função.
Jfpoilpret 24/0318
8

A recursão é uma má prática em um microcontrolador, como você já se declarou e provavelmente deseja evitá-la sempre que possível. No site do Arduino, existem alguns exemplos e bibliotecas disponíveis para verificar o tamanho da RAM livre . Você pode, por exemplo, usar isso para descobrir quando interromper a recursão ou um pouco mais complicado / arriscado para criar um perfil do seu esboço e codificar o limite nele. Esse perfil seria necessário para todas as alterações no seu programa e para todas as alterações na cadeia de ferramentas do Arduino.

jippie
fonte
Alguns dos compiladores mais avançados, como o IAR (que oferece suporte ao AVR) e o Keil (que não oferecem suporte ao AVR) possuem ferramentas para ajudá-lo a monitorar e gerenciar o espaço de pilha. Não é realmente aconselhável algo tão pequeno quanto um ATmega328.
Cybergibbons
7

Depende da função.

Toda vez que uma função é chamada, um novo quadro é empurrado para a pilha. Geralmente, ele contém vários itens críticos, incluindo potencialmente:

  • Endereço de retorno (o ponto no código a partir do qual a função foi chamada).
  • O ponteiro da instância local ( this) se estiver chamando uma função de membro.
  • Parâmetros passados ​​para a função
  • Registre valores que precisam ser restaurados quando a função termina.
  • Espaço para variáveis ​​locais dentro da função chamada.

Como você pode ver, o espaço de pilha necessário para uma determinada chamada depende da função. Por exemplo, se você escrever uma função recursiva que usa apenas um intparâmetro e não usa variáveis ​​locais, ela não precisará de muito mais do que alguns bytes na pilha. Isso significa que você pode chamá-lo recursivamente muito mais do que uma função que usa vários parâmetros e usa muitas variáveis ​​locais (que consumirão a pilha muito mais rapidamente).

Obviamente, o estado da pilha depende do que mais está acontecendo no código. Se você iniciar uma recursão diretamente na loop()função padrão , provavelmente não haverá muito na pilha. No entanto, se você o iniciar aninhar vários níveis em outras funções, não haverá muito espaço. Isso afetará quantas vezes você pode se recuperar sem esgotar a pilha.

Vale a pena notar que a otimização da recursão da cauda existe em alguns compiladores (embora não tenha certeza se o avr-gcc a suporta). Se a chamada recursiva é a última coisa em uma função, significa que às vezes é possível evitar alterar o quadro da pilha. O compilador pode apenas reutilizar o quadro existente, já que a chamada 'pai' (por assim dizer) terminou de usá-lo. Isso significa que, teoricamente, você pode continuar recorrendo o quanto quiser, desde que sua função não chame mais nada.

Peter Bloomfield
fonte
1
O avr-gcc não suporta recursão de cauda.
asheeshr
@AsheeshR - É bom saber. Obrigado. Achei que provavelmente era improvável.
Peter Bloomfield
Você pode fazer uma eliminação / otimização da chamada final refatorando seu código, em vez de esperar que o compilador faça isso. Enquanto a chamada recursiva estiver no final do método recursivo, você poderá reescrever o método com segurança para usar um loop while / for.
abasterfield
1
A postagem de @TheDoctor contradiz "o avr-gcc não suporta recursão de cauda", assim como meu teste do código dele. O compilador realmente implementou a recursão da cauda, ​​e foi assim que ele conseguiu um milhão de recursões. Peter está correto - é possível que o compilador substitua a chamada / retorno (como a última chamada em uma função) por simplesmente pular . Ele tem o mesmo resultado final e não consome espaço na pilha.
Nick Gammon
2

Eu tinha exatamente a mesma pergunta que estava lendo Jumping into C ++, de Alex Allain , Capítulo 16: Recursão, p.230, então fiz alguns testes.

TLDR;

Meu Nano do Arduino (ATmega328 mcu) pode fazer 211 chamadas de função recursivas (para o código fornecido abaixo) antes que o estouro da pilha seja interrompido.

Primeiro, deixe-me abordar esta reivindicação:

Às vezes, a recursão é a única opção rápida para implementar um determinado algoritmo.

[Atualização: ah, eu deslizei a palavra "rápido". Nesse caso, você tem alguma validade. No entanto, acho que vale a pena dizer o seguinte.]

Não, não acho que seja uma afirmação verdadeira. Estou certo de que todos os algoritmos têm uma solução recursiva e não recursiva, sem exceção. Às vezes é bem mais fácilpara usar um algoritmo recursivo. Dito isto, a recursão é muito desaprovada para uso em microcontroladores e provavelmente nunca seria permitida em códigos críticos de segurança. No entanto, é possível, é claro, fazê-lo em microcontroladores. Para saber o quão "profundo" você pode entrar em qualquer função recursiva, basta testá-lo! Execute-o em seu aplicativo da vida real em um caso de teste da vida real e remova sua condição de base para que ela se recupere infinitamente. Imprima um contador e veja você mesmo o quão "profundo" você pode ir para saber se o seu algoritmo recursivo está pressionando demais os limites da sua RAM para ser usado na prática. Aqui está um exemplo abaixo para forçar o estouro de pilha em um Arduino.

Agora, algumas notas:

Quantas chamadas recursivas ou "empilhamento de quadros" você pode receber são determinadas por vários fatores, incluindo:

  • O tamanho da sua RAM
  • Quantas coisas já estão na sua pilha ou ocupadas na sua pilha (por exemplo: sua RAM livre importa; free_RAM = total_RAM - stack_used - heap_usedou você pode dizer free_RAM = stack_size_allocated - stack_size_used)
  • O tamanho de cada novo "quadro de pilha" que será colocado na pilha para cada nova chamada de função recursiva. Isso dependerá da função que está sendo chamada e de suas variáveis ​​e requisitos de memória, etc.

Meus resultados:

  • 20171106-2054hrs - Toshiba Satellite com 16 GB de RAM; quad-core, Windows 8.1: valor final impresso antes da falha: 43166
    • levou alguns segundos para travar - talvez 5 a 10?
  • 20180306-1913hrs Laptop de ponta da Dell com 64 GB de RAM; 8-core, Linux Ubuntu 14.04 LTS: valor final impresso antes da falha: 261752
    • seguido pela frase Segmentation fault (core dumped)
    • levou apenas ~ 4 ~ 5 segundos ou mais para travar
  • 20180306-1930hrs Arduino Nano: TBD --- está em ~ 250000 e continua contando --- as configurações de otimização do Arduino devem ter feito com que ele otimizasse a recursão ... ??? Sim, é esse o caso.
    • Adicione #pragma GCC optimize ("-O0")ao topo do arquivo e refaça:
  • 20180307-0910hrs Arduino Nano: flash de 32 kB, SRAM de 2 kB, 16 MHz de processamento: valor final impresso antes da falha: 211 Here are the final print results: 209 210 211 ⸮ 9⸮ 3⸮
    • demorou apenas uma fração de segundo depois que começou a imprimir a uma taxa de transmissão serial de 115200 - talvez 1/10 s
    • 2 kiB = 2048 bytes / 211 quadros de pilha = 9,7 bytes / quadro (supondo que TODA a sua RAM esteja sendo usada pela pilha - o que realmente não é o caso) -, mas isso parece bastante razoável.

O código:

A aplicação para 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);
}

O programa "Sketch" do Arduino:

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

Referências:

  1. Saltando para C ++ por Alex Allain , Ch 16: Recursão, p.230
  2. http://www.electricrcaircraftguy.com/2014/01/the-power-of-arduino.html - literalmente: referenciei meu próprio site durante este "projeto" para me lembrar de como alterar os níveis de otimização do compilador Arduino para um determinado arquivo com o #pragma GCC optimizecomando desde que eu sabia que tinha documentado lá.
Gabriel Staples
fonte
1
Observe que, de acordo com os documentos da avr-lib, você nunca deve compilar sem otimização nada que dependa da avr-libc, pois não há garantia de que alguma coisa funcione com a otimização desativada. Por isso, aconselho a #pragmanão usar o que está usando lá. Em vez disso, você pode adicionar __attribute__((optimize("O0")))à única função que deseja desativar.
Edgar Bonet
Obrigado, Edgar. Você sabe onde o AVR libc está documentado?
Gabriel Staples
1
A documentação em <util / delay.h> declara: "Para que essas funções funcionem conforme o esperado , as otimizações do compilador devem ser ativadas [...]" (ênfase no original). Não tenho certeza se outras funções do avr-libc têm esse requisito.
Edgar Bonet
1

Eu escrevi este programa de teste simples:

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

Eu o compilei para o Uno e, enquanto escrevo, ele se repetiu mais de um milhão de vezes! Não sei, mas o compilador pode ter otimizado este programa

O médico
fonte
Tente retornar após um número definido de chamadas ~ 1000. Deve criar um problema então.
asheeshr
1
O compilador implementou astutamente a recursão da cauda no seu esboço, como você verá se o desmontar. O que isto significa é que substitui a sequência call xxx/ retpor jmp xxx. Isso equivale à mesma coisa, exceto que o método do compilador não consome a pilha. Assim, você pode receber bilhões de vezes com seu código (outras coisas são iguais).
Nick Gammon
Você pode forçar o compilador a não otimizar a recursão. Voltarei e postarei um exemplo mais tarde.
Gabriel Staples
Feito! Exemplo aqui: arduino.stackexchange.com/a/51098/7727 . O segredo é impedir a otimização adicionando #pragma GCC optimize ("-O0") ao topo do seu programa Arduino. Acredito que você precise fazer isso na parte superior de cada arquivo ao qual deseja aplicar - mas eu não procuro isso há anos, então pesquise-o para ter certeza.
Gabriel Staples