Berapa banyak terlalu banyak panggilan fungsi bersarang?

15

Dikutip dari MSDN tentang StackOverflowException :

Pengecualian yang dilemparkan ketika tumpukan eksekusi melimpah karena mengandung terlalu banyak panggilan metode bersarang.

Too manycukup samar di sini. Bagaimana saya tahu kalau terlalu banyak benar-benar terlalu banyak? Ribuan panggilan fungsi? Jutaan? Saya berasumsi bahwa itu harus dikaitkan dengan beberapa cara dengan jumlah memori di komputer tetapi apakah mungkin untuk menghasilkan urutan besarnya kira-kira akurat?

Saya khawatir tentang ini karena saya mengembangkan sebuah proyek yang melibatkan banyak penggunaan struktur rekursif dan panggilan fungsi rekursif. Saya tidak ingin aplikasi gagal ketika saya mulai menggunakannya untuk lebih dari sekedar tes kecil.

.net exceptions recursion stackoverflow marco-fiset
sumber
4
Relatif mudah untuk mengubah fungsi rekursif menjadi fungsi non-rekursif. Cukup tempelkan data Anda di a Stack<T>.
Brian
1
Seberapa besar "terlalu banyak" sepenuhnya tergantung pada Anda untuk menentukan. Untuk .NET, gunakan editbin /stack:WHATEVER-NUMBER-YOU-LIKE yourexefile.exe.
SK-logic

Jawaban:

28

Saya khawatir tentang ini karena saya mengembangkan sebuah proyek yang melibatkan banyak penggunaan struktur rekursif dan panggilan fungsi rekursif. Saya tidak ingin aplikasi gagal ketika saya mulai menggunakannya untuk lebih dari sekedar tes kecil.

Kecuali jika lingkungan bahasa Anda mendukung pengoptimalan panggilan ekor (dan rekursi Anda adalah panggilan ekor), aturan dasar praktisnya adalah: kedalaman rekursi harus dijamin menjadi O (log n), yaitu menggunakan algoritme atau struktur data berdasarkan pembagian-dan- menaklukkan (seperti pohon, alogoritma penyortiran paling, dll) adalah OK, tapi apa pun linier (seperti implementasi rekursif penanganan daftar terkait) tidak.

Michael Borgwardt
sumber
3
+1. Jawaban yang sangat bagus, saya secara implisit menggunakan aturan ini tetapi saya tidak menyadarinya.
Giorgio
Di zaman sekarang ini, hampir semua kompiler berkualitas produksi yang layak dari kata sifat akan mendukung optimasi panggilan ekor.
John R. Strohm
1
@ JohnR.Strohm Namun OP telah menandai pertanyaan .NET, jadi AFAIK hanya 64-bit jitter yang melakukan optimasi panggilan ekor saat ini.
Mark Hurd
1
Agar tidak ada kebingungan, kedua x86 dan x64 selalu menghormati "ekor." instruksi awalan. Jadi untuk meringkas, di tanah NET., F # melakukan optimasi panggilan ekor lengkap, C # tidak, dan x64 jitter melakukannya jika itu "mudah" (tidak dapat diandalkan). Lihat blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11/…
Stephen Swensen
1
Benar, tetapi dalam beberapa kasus, seperti dalam ASP.NET hosting IIS yang terkenal, bahkan kedalaman rekursi O (log n) yang hanya mungkin gagal karena batas kedalaman stack stack kecil yang menyedihkan, tidak dibenarkan, menggelikan, yang membuat hampir semua rekursi (atau bahkan rantai panjang panggilan bersarang non-rekursif) tidak mungkin. Satu-satunya cara adalah mengedit biner iis itu sendiri.
SK-logic
17

Secara default, CLR mengalokasikan 1 MB ke stack untuk setiap utas (lihat artikel ini ). Jadi, bagaimanapun banyak panggilan yang diperlukan untuk melebihi jumlah ini. Itu akan bervariasi tergantung pada seberapa banyak ruang pada stack yang digunakan setiap panggilan untuk hal-hal seperti parameter dan variabel lokal.

Anda bahkan dapat membuatnya melempar StackOverflowExceptiondengan satu panggilan jika Anda ingin menjadi sedikit tidak ortodoks:

private static unsafe void BlowUpTheStack()
{
    var x = stackalloc byte[1000000000];
    Console.WriteLine("Oh no, I've blown up the stack!");
}
Cole Campbell
sumber
Sayangnya, default yang masuk akal ini sering dilanggar (misalnya, di asp.net).
SK-logic
2

Karena Cole Campbell mencatat ukuran memori dan Michael Borgwardt mencatat optimasi panggilan ekor, saya tidak akan membahasnya.

Hal lain yang perlu diperhatikan adalah CPS yang dapat digunakan untuk mengoptimalkan beberapa fungsi terjalin di mana optimasi panggilan ekor adalah untuk fungsi tunggal.

Anda dapat meningkatkan ukuran tumpukan seperti yang kami lakukan di sini , dan perhatikan bahwa kode 64-bit memakan tumpukan lebih cepat dari kode 32-bit.

Yang perlu diperhatikan adalah bahwa kami menjalankan salah satu contoh di bawah F # interaktif selama lebih dari 40 jam tanpa meniup tumpukan. Ya itu adalah salah satu panggilan fungsi yang berjalan dengan sendirinya terus menerus hingga berhasil diselesaikan.

Juga, jika Anda perlu melakukan cakupan kode untuk mencari tahu di mana masalah terjadi dan tidak memiliki cakupan kode dengan VS yang dapat Anda gunakan, TestDriven.NET

Guy Coder
sumber