Seberapa banyak saya bisa kambuh? Seberapa banyak saya bisa kambuh? Berapa banyak ca! @ # QFSD @ $ RFW

19

Papan Arduino Uno memiliki RAM terbatas yang berarti memiliki tumpukan panggilan terbatas. Terkadang, rekursi adalah satu-satunya pilihan cepat untuk mengimplementasikan algoritma tertentu. Jadi, mengingat bahwa tumpukan panggilan sangat terbatas, apa yang akan menjadi cara untuk mengetahui bahwa mengingat program tertentu berjalan di papan tulis, persis berapa banyak panggilan rekursif yang Anda mampu sebelum ada tumpukan melimpah (dan hal-hal buruk terjadi)?

asheeshr
sumber
2
Bisakah Anda memberikan contoh algoritma di mana pilihan antara solusi rekursif dan non-rekursif sangat jelas?
Cybergibbons
1
@ Cybergibbons Baru-baru ini, saya harus menulis dan menguji RDP dalam rentang waktu yang singkat, jadi saya melanjutkan implementasi rekursif. Saya tidak mengatakan bahwa iteratif tidak mungkin, hanya saja mungkin lebih mudah untuk melanjutkan dengan versi rekursif.
asheeshr
Apa artinya ini dalam judul pertanyaan: How much ca!@#QFSD@$RFW? Saya ingin tahu mengapa tidak ada yang mengedit itu menjadi sesuatu yang lebih bermakna (dalam 4 tahun terakhir).
Nick Gammon
Jawabannya adalah 211waktu (tergantung banyak faktor) :). Lihat jawaban saya di sini: arduino.stackexchange.com/a/51098/7727 . @NickGammon, dia berpura-pura "mengutuk", saya pikir. Ini adalah permainan kata untuk "recurse". Butuh waktu sebentar untuk memikirkannya juga. Awalnya cukup membingungkan.
Gabriel Staples
Oh begitu. Saya pikir server SE mungkin memiliki kesalahan :)
Nick Gammon

Jawaban:

15

Jika Anda benar-benar ingin muncul kembali (dan seperti yang dikatakan @jippie itu adalah ide yang buruk; pesan bawah sadar: jangan lakukan itu ) dan ingin tahu seberapa banyak Anda dapat berulang, maka Anda harus melakukan beberapa perhitungan dan percobaan; Anda juga biasanya hanya akan memiliki perkiraan karena tergantung banyak pada kondisi memori pada saat fungsi rekursif Anda akan dipanggil.

Untuk ini, Anda harus terlebih dahulu tahu bagaimana SRAM diatur dalam Arduino berbasis AVR (itu tidak akan berlaku untuk misalnya Arduino Galileo oleh Intel). Diagram berikut dari Adafruit menunjukkannya dengan jelas:

Organisasi SRAM

Maka Anda perlu mengetahui ukuran total SRAM Anda (tergantung pada Atmel MCU, maka jenis papan Arduino yang Anda miliki).

Pada diagram ini, mudah untuk mengetahui ukuran blok Data Statis seperti yang diketahui pada waktu kompilasi dan tidak akan berubah nanti.

The Heap Ukuran dapat lebih sulit untuk mengetahui karena dapat bervariasi pada saat runtime, tergantung pada alokasi memori dinamis ( mallocatau new) dilakukan oleh sketsa atau perpustakaan menggunakan. Menggunakan memori dinamis sangat jarang di Arduino, tetapi beberapa fungsi standar melakukannya ( Stringsaya pikir itu menggunakan tipe itu).

Untuk ukuran Stack , ini juga akan bervariasi selama runtime, berdasarkan pada kedalaman panggilan fungsi saat ini (setiap panggilan fungsi membutuhkan 2 byte pada Stack untuk menyimpan alamat pemanggil) dan jumlah dan ukuran variabel lokal termasuk argumen yang diteruskan ( yang juga disimpan di Stack ) untuk semua fungsi yang dipanggil sampai sekarang.

Jadi anggaplah recurse()fungsi Anda menggunakan 12 byte untuk variabel dan argumen lokalnya, maka setiap panggilan ke fungsi ini (yang pertama dari penelepon eksternal dan yang rekursif) akan menggunakan 12+2byte.

Jika kita mengira bahwa:

  • Anda berada di Arduino UNO (SRAM = 2K)
  • sketsa Anda tidak menggunakan alokasi memori dinamis (tidak ada tumpukan )
  • Anda tahu ukuran Data Statis Anda (katakanlah 132 byte)
  • ketika recurse()fungsi Anda dipanggil dari sketsa Anda, tumpukan saat ini adalah 128 byte

Kemudian Anda dibiarkan dengan 2048 - 132 - 128 = 1788byte yang tersedia di Stack . Dengan demikian, jumlah panggilan rekursif ke fungsi Anda 1788 / 14 = 127, termasuk panggilan awal (yang bukan merupakan panggilan rekursif).

Seperti yang Anda lihat, ini sangat sulit, tetapi bukan tidak mungkin untuk menemukan apa yang Anda inginkan.

Cara yang lebih sederhana untuk mendapatkan ukuran tumpukan tersedia sebelum recurse()dipanggil adalah dengan menggunakan fungsi berikut (ditemukan di pusat pembelajaran Adafruit; saya belum mengujinya sendiri):

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

Saya sangat menyarankan Anda untuk membaca artikel ini di pusat pembelajaran Adafruit.

jfpoilpret
sumber
Saya melihat peter-r-bloomfield memposting jawabannya ketika saya sedang menulis jawaban saya; jawabannya tampak lebih baik karena sepenuhnya menggambarkan isi stack setelah panggilan (saya lupa negara register).
jfpoilpret
Keduanya jawaban kualitas yang sangat baik.
Cybergibbons
Data statis = .bss + .data, dan apakah yang dilaporkan oleh Arduino sebagai "RAM yang diambil oleh variabel global" atau apa pun, yang benar?
Gabriel Staples
1
@GabrielStaples ya persisnya. Secara lebih rinci .bssmewakili variabel global tanpa nilai awal dalam kode Anda, sedangkan datauntuk variabel global dengan nilai awal. Tetapi pada akhirnya mereka menggunakan ruang yang sama: Data Statis dalam diagram.
jfpoilpret
1
@GabrielStaples lupa satu hal, secara teknis ini bukan hanya variabel global yang terjadi di sana, Anda juga memiliki variabel yang dideklarasikan staticdalam suatu fungsi.
jfpoilpret
8

Rekursi adalah praktik buruk pada mikrokontroler karena Anda telah menyatakan diri Anda dan Anda mungkin ingin menghindarinya kapan pun memungkinkan. Di situs Arduino ada beberapa contoh dan perpustakaan yang tersedia untuk memeriksa ukuran RAM gratis . Misalnya Anda dapat menggunakan ini untuk mencari tahu kapan harus istirahat rekursi atau sedikit rumit / berisiko untuk profil sketsa Anda dan kode keras batas di dalamnya. Profil ini diperlukan untuk setiap perubahan dalam program Anda dan untuk setiap perubahan dalam rantai alat Arduino.

jippie
sumber
Beberapa kompiler kelas atas, seperti IAR (yang mendukung AVR) dan Keil (yang tidak mendukung AVR) memiliki alat untuk membantu Anda memantau dan mengelola ruang stack. Ini benar-benar tidak dianjurkan pada sesuatu yang sekecil ATmega328.
Cybergibbons
7

Tergantung fungsinya.

Setiap kali fungsi dipanggil, bingkai baru didorong ke tumpukan. Biasanya akan berisi berbagai item penting, berpotensi termasuk:

  • Alamat pengirim (titik pada kode dari mana fungsi dipanggil).
  • Pointer instance lokal ( this) jika memanggil fungsi anggota.
  • Parameter masuk ke fungsi.
  • Daftarkan nilai yang perlu dipulihkan saat fungsi berakhir.
  • Ruang untuk variabel lokal di dalam fungsi yang dipanggil.

Seperti yang Anda lihat, ruang tumpukan yang diperlukan untuk panggilan yang diberikan tergantung pada fungsinya. Misalnya, jika Anda menulis fungsi rekursif yang hanya mengambil intparameter dan tidak menggunakan variabel lokal, itu tidak akan membutuhkan lebih dari beberapa byte pada stack. Itu berarti Anda dapat menyebutnya secara rekursif lebih dari fungsi yang mengambil beberapa parameter dan menggunakan banyak variabel lokal (yang akan memakan tumpukan lebih cepat).

Jelas keadaan tumpukan tergantung pada apa lagi yang terjadi dalam kode. Jika Anda memulai rekursi langsung di dalam loop()fungsi standar , maka kemungkinan tidak akan ada banyak pada stack. Namun, jika Anda memulainya bersarang beberapa level dalam fungsi lain, maka tidak akan ada banyak ruang. Itu akan mempengaruhi berapa kali Anda bisa kambuh tanpa menguras tumpukan.

Perlu dicatat bahwa optimasi rekursi ekor ada pada beberapa kompiler (walaupun saya tidak yakin apakah avr-gcc mendukungnya). Jika panggilan rekursif adalah hal terakhir dalam suatu fungsi, itu berarti kadang-kadang mungkin untuk menghindari mengubah bingkai tumpukan sama sekali. Compiler hanya dapat menggunakan kembali bingkai yang ada, karena panggilan 'induk' (jadi untuk berbicara) selesai menggunakannya. Itu berarti Anda secara teoritis dapat terus berulang sebanyak yang Anda suka, selama fungsi Anda tidak memanggil yang lain.

Peter Bloomfield
sumber
1
avr-gcc tidak mendukung rekursi ekor.
asheeshr
@AsheeshR - Senang tahu. Terima kasih. Saya pikir itu mungkin tidak mungkin.
Peter Bloomfield
Anda dapat melakukan eliminasi / optimasi panggilan ekor dengan refactoring kode Anda alih-alih berharap kompiler akan melakukannya. Selama panggilan rekursif ada di akhir metode rekursif, Anda dapat dengan aman menulis ulang metode untuk menggunakan pengulangan while / for.
abasterfield
1
Posting oleh @TheDoctor bertentangan dengan "avr-gcc tidak mendukung rekursi ekor", seperti halnya pengujian kodenya. Kompilator memang menerapkan rekursi ekor, yang merupakan cara dia mendapatkan hingga jutaan rekursi. Peter benar - adalah mungkin bagi kompiler untuk mengganti panggilan / kembali (sebagai panggilan terakhir dalam suatu fungsi) hanya dengan melompat . Ini memiliki hasil akhir yang sama dan tidak mengkonsumsi ruang stack.
Nick Gammon
2

Saya memiliki pertanyaan yang sama persis seperti saya membaca Jumping into C ++ oleh Alex Allain , Bab 16: Rekursi, hal.230, jadi saya menjalankan beberapa tes.

TLDR;

Arduino Nano saya (ATmega328 mcu) dapat melakukan 211 panggilan fungsi rekursif (untuk kode yang diberikan di bawah ini) sebelum memiliki stack overflow dan crash.

Pertama, izinkan saya menangani klaim ini:

Terkadang, rekursi adalah satu-satunya pilihan cepat untuk mengimplementasikan algoritma tertentu.

[Pembaruan: ah, saya membaca sepintas kata "cepat". Dalam hal ini Anda memiliki validitas. Namun demikian, saya pikir ada baiknya mengatakan hal berikut.]

Tidak, saya tidak berpikir itu pernyataan yang benar. Saya cukup yakin semua algoritma memiliki solusi rekursif dan non-rekursif, tanpa kecuali. Hanya saja kadang-kadang jauh lebih mudahuntuk menggunakan algoritma rekursif. Karena itu, rekursi sangat disukai untuk digunakan pada mikrokontroler dan mungkin tidak akan pernah diizinkan dalam kode keamanan kritis. Meskipun demikian, tentu saja dimungkinkan untuk melakukannya pada mikrokontroler. Untuk mengetahui seberapa "dalam" Anda bisa masuk ke fungsi rekursif yang diberikan, cukup mengujinya! Jalankan dalam aplikasi kehidupan nyata Anda dalam test case kehidupan nyata, dan lepaskan kondisi dasar Anda sehingga akan terulang kembali. Cetak penghitung dan lihat sendiri seberapa "dalam" Anda sehingga Anda tahu apakah algoritma rekursif Anda mendorong batas RAM Anda terlalu dekat untuk digunakan secara praktis. Berikut adalah contoh di bawah ini untuk memaksa stack overflow pada Arduino.

Sekarang, beberapa catatan:

Berapa banyak panggilan rekursif, atau "stack frames" yang bisa Anda dapatkan ditentukan oleh sejumlah faktor, termasuk:

  • Ukuran RAM Anda
  • Berapa banyak barang yang sudah ada di tumpukan Anda atau diambil di tumpukan Anda (yaitu: RAM Anda penting;, free_RAM = total_RAM - stack_used - heap_usedatau Anda mungkin mengatakan free_RAM = stack_size_allocated - stack_size_used)
  • Ukuran setiap "stack frame" baru yang akan ditempatkan ke stack untuk setiap panggilan fungsi rekursif baru. Ini akan tergantung pada fungsi yang dipanggil dan variabel dan persyaratan memori, dll.

Hasil saya:

  • 20171106-2054hrs - Toshiba Satellite dengan 16 GB RAM; quad-core, Windows 8.1: nilai akhir yang dicetak sebelum crash: 43166
    • butuh beberapa detik untuk crash - mungkin 5 ~ 10?
  • 20180306-1913hrs Laptop high-end Dell dengan RAM 64 GB; 8-core, Linux Ubuntu 14.04 LTS: nilai akhir dicetak sebelum crash: 261752
    • diikuti oleh frasa Segmentation fault (core dumped)
    • hanya butuh ~ 4 ~ 5 detik untuk crash
  • 20180306-1930hrs Arduino Nano: TBD --- ada di ~ 250000 dan masih menghitung --- pengaturan optimasi Arduino pasti menyebabkannya mengoptimalkan rekursi ... ??? Ya itu masalahnya.
    • Tambahkan #pragma GCC optimize ("-O0")ke bagian atas file dan ulangi:
  • 20180307-0910hrs Arduino Nano: 32 kB flash, 2 kB SRAM, proses 16 MHz atau lebih: nilai akhir dicetak sebelum mogok: 211 Here are the final print results: 209 210 211 ⸮ 9⸮ 3⸮
    • hanya membutuhkan sepersekian detik setelah mulai mencetak pada 115200 serial baud-rate - mungkin 1/10 detik
    • 2 kiB = 2048 bytes / 211 stack frames = 9,7 bytes / frame (dengan asumsi SEMUA RAM Anda sedang digunakan oleh stack - yang sebenarnya tidak demikian) - tetapi ini tampaknya masih sangat masuk akal.

Kode:

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

Program "Sketsa" 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()
{
}

Referensi:

  1. Jumping into C ++ oleh Alex Allain , Bab 16: Rekursi, hal.230
  2. http://www.electricrcaircraftguy.com/2014/01/the-power-of-arduino.html - secara harfiah: Saya mereferensikan situs web saya sendiri selama "proyek" ini untuk mengingatkan diri saya bagaimana mengubah tingkat optimisasi kompilator Arduino untuk file yang diberikan dengan #pragma GCC optimizeperintah karena saya tahu saya sudah didokumentasikan di sana.
Gabriel Staples
sumber
1
Perhatikan bahwa, menurut dokumen avr-lib, Anda tidak boleh mengkompilasi tanpa optimasi apa pun yang bergantung pada avr-libc, karena ada hal-hal yang tidak dijamin bahkan bekerja dengan optimasi yang dimatikan. Karena itu saya menyarankan Anda untuk #pragmatidak menggunakannya di sana. Sebagai gantinya, Anda dapat menambahkan __attribute__((optimize("O0")))ke fungsi tunggal yang ingin Anda optimalkan.
Edgar Bonet
Terima kasih, Edgar. Apakah Anda tahu di mana AVR libc mendokumentasikan ini?
Gabriel Staples
1
The dokumentasi di <util / delay.h> negara: “Agar fungsi-fungsi ini bekerja sebagaimana dimaksud, optimasi kompilator harus diaktifkan [...]” (penekanan dalam aslinya). Saya tidak yakin apakah ada fungsi avr-libc lain yang memiliki persyaratan ini.
Edgar Bonet
1

Saya menulis program tes sederhana ini:

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

Saya mengkompilasinya untuk Uno, dan ketika saya menulisnya telah berulang lebih dari 1 juta kali! Saya tidak tahu, tetapi kompiler mungkin telah mengoptimalkan program ini

Dokter
sumber
Cobalah untuk kembali setelah sejumlah panggilan yang ditetapkan ~ 1000. Seharusnya itu menciptakan masalah.
asheeshr
1
Kompiler secara cerdik telah mengimplementasikan rekursi ekor pada sketsa Anda, karena Anda akan melihat apakah Anda membongkar itu. Apakah ini berarti bahwa ia menggantikan urutan call xxx/ retoleh jmp xxx. Ini sama dengan jumlah yang sama, kecuali bahwa metode kompiler tidak mengkonsumsi stack. Dengan demikian Anda dapat kambuh miliaran kali dengan kode Anda (hal lain dianggap sama).
Nick Gammon
Anda dapat memaksa kompiler untuk tidak mengoptimalkan rekursi. Saya akan kembali dan mengirim contoh nanti.
Gabriel Staples
Selesai! Contoh di sini: arduino.stackexchange.com/a/51098/7727 . Rahasianya adalah mencegah pengoptimalan dengan menambahkan #pragma GCC optimize ("-O0") bagian atas program Arduino Anda. Saya percaya Anda harus melakukan ini di bagian atas setiap file yang Anda inginkan untuk diterapkan - tetapi saya belum melihat itu selama bertahun-tahun jadi riset untuk Anda sendiri untuk memastikan.
Gabriel Staples