C / C ++ ukuran tumpukan maksimum program

Saya ingin melakukan DFS pada array 100 X 100. (Katakanlah elemen array mewakili node grafik) Jadi dengan asumsi kasus terburuk, kedalaman panggilan fungsi rekursif bisa naik hingga 10000 dengan setiap panggilan mengambil katakanlah 20 byte. Jadi apakah itu layak berarti apakah ada kemungkinan stackoverflow?

Berapa ukuran maksimum tumpukan di C / C ++?

Tentukan gcc untuk
1) cygwin di Windows
2) Unix

Apa batasan umumnya?

Dalam Visual Studio ukuran tumpukan default adalah 1 MB saya pikir, jadi dengan kedalaman rekursi 10.000 setiap bingkai tumpukan dapat paling banyak ~ 100 byte yang seharusnya cukup untuk algoritma DFS.

Kebanyakan kompiler termasuk Visual Studio memungkinkan Anda menentukan ukuran tumpukan. Pada beberapa (semua?) Linux rasa ukuran tumpukan bukan bagian dari yang dapat dieksekusi tetapi variabel lingkungan di OS. Anda kemudian dapat memeriksa ukuran tumpukan dengan ulimit -sdan mengaturnya ke nilai baru dengan misalnya ulimit -s 16384.

Berikut link dengan ukuran tumpukan default untuk gcc.

DFS tanpa rekursi:

std::stack<Node> dfs;
dfs.push(start);
do {
    Node top = dfs.top();
    if (top is what we are looking for) {
       break;
    }
    dfs.pop();
    for (outgoing nodes from top) {
        dfs.push(outgoing node);
    }
} while (!dfs.empty())

tumpukan benang seringkali lebih kecil. Anda dapat mengubah default pada waktu tautan, atau mengubah pada waktu berjalan juga. Sebagai referensi, beberapa default adalah:

• glibc i386, x86_64 7,4 MB
• Tru64 5.1 5.2 MB
• Cygwin 1,8 MB
• Solaris 7..10 1 MB
• MacOS X 10.5 460 KB
• AIX 5 98 KB
• OpenBSD 4.0 64 KB
• HP-UX 11 16 KB

Tergantung platform, bergantung pada toolchain, bergantung pada ulimit, bergantung pada parameter .... Ini sama sekali tidak ditentukan, dan ada banyak properti statis dan dinamis yang dapat mempengaruhinya.

Ya, ada kemungkinan tumpukan meluap. Standar C dan C ++ tidak mendikte hal-hal seperti kedalaman tumpukan, yang umumnya merupakan masalah lingkungan.

Sebagian besar lingkungan pengembangan dan / atau sistem operasi yang layak akan memungkinkan Anda menyesuaikan ukuran tumpukan suatu proses, baik pada saat tautan atau waktu muat.

Anda harus menentukan OS dan lingkungan pengembangan yang Anda gunakan untuk bantuan yang lebih bertarget.

Misalnya, di Ubuntu Karmic Koala, default untuk gcc adalah 2M dicadangkan dan 4K berkomitmen tetapi ini dapat diubah saat Anda menautkan program. Gunakan --stackopsi lduntuk melakukan itu.

Saya baru saja kehabisan tumpukan di tempat kerja, itu adalah database dan menjalankan beberapa utas, pada dasarnya pengembang sebelumnya telah melemparkan array besar ke tumpukan, dan tumpukan itu tetap rendah. Perangkat lunak ini disusun menggunakan Microsoft Visual Studio 2015.

Meskipun utas kehabisan tumpukan, utas gagal dan berlanjut secara diam-diam, itu hanya tumpukan meluap ketika datang untuk mengakses konten data di tumpukan.

Saran terbaik yang bisa saya berikan adalah untuk tidak mendeklarasikan array di stack - terutama dalam aplikasi yang kompleks dan terutama di thread, sebagai gantinya gunakan heap. Untuk itulah itu ada;)

Juga perlu diingat bahwa ini mungkin tidak langsung gagal saat mendeklarasikan tumpukan, tetapi hanya pada akses. Dugaan saya adalah bahwa kompiler menyatakan tumpukan di bawah jendela "secara optimis", yaitu akan menganggap bahwa tumpukan telah dideklarasikan dan berukuran cukup sampai digunakan dan kemudian menemukan bahwa tumpukan tidak ada.

Sistem operasi yang berbeda mungkin memiliki kebijakan deklarasi stack yang berbeda. Silakan tinggalkan komentar jika Anda tahu apa kebijakan ini.

Saya tidak yakin apa yang Anda maksud dengan melakukan pencarian pertama yang mendalam pada array persegi panjang, tetapi saya berasumsi Anda tahu apa yang Anda lakukan.

Jika batas tumpukan adalah masalah, Anda harus dapat mengubah solusi rekursif Anda menjadi solusi berulang yang mendorong nilai antara ke tumpukan yang dialokasikan dari heap.