C++ 大きな配列をmain関数内で宣言するとsegmentation faultとなる

Question

#大きな配列をmain関数内で宣言するとsegmentation faultとなる

以下はナップザック問題に関する実装です。
main関数内でdp[110][100005]を宣言するとsegmentation faultとなります。
グローバルに宣言すれば問題は解決するのですが、これはどういった理由なのでしょうか？

main関数内とグローバルでの宣言ではメモリへの保存のされ方が異なるということなのでしょうか？
ご存知のかたがいましたら教えていただけると幸いです。

#include<iostream>
#include<vector>
using namespace std;

void chmax(long long &a, long long b) {
    if(a < b) a = b;
}

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> w(n), v(n);
    for(int i=0; i<n; i++) cin >> w[i] >> v[i];

    // main関数内でdpの２次元配列を宣言
    long long dp[110][100005] = {};

    for(int i=0; i<n; i++) {
        for(int sum_w = 0; sum_w <= W; sum_w++) {
            // i番目の商品を選ぶ
            if(sum_w - w[i] >= 0) {
                chmax(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i]);
            }
            // i番目の品物を選ばない
            chmax(dp[i+1][sum_w], dp[i][sum_w]);
        }
    }
    cout << dp[n][W] << endl;
}

Answer 1

メモリ管理のメカニズムは実行環境によるので詳細を説明するのは難しいのですが Linux だと大抵のディストリビューションではデフォルトでのスタックの上限は 8MB に設定されていると思います。 ulimit -s とコマンド入力すればどういう設定になっているか見れます。

Windows だと実行ファイルにスタックの上限を設定できる (リンクオプションとして指定できる) ようですがデフォルトだとたった 1MB ということになっています。

必要に応じて制限を緩和する設定をすることは可能とはいえ、これらのデフォルト設定におけるスタックの上限はおそらく想像以上に小さいように感じるのではないでしょうか。 要するに普通はこれらの範囲に収まるように書くものだということであり、自動変数として巨大な配列を確保しようとするべきではないという習慣はあります。

Answer 2

一般的に、Cの関数内で定義された変数のためのメモリはスタックから確保されます。
ですのであまり巨大なデータは定義できません。

Answer 3

皆さんの回答の通りです。グローバル変数はヒープ、ローカル変数はスタック領域に割り当てられることが多いです（規則ではないので、必ずとは言い切れない）。

このため、グローバル変数のみに配置できる大きな配列というケースがありえます。これは単に変数定義を関数外に書くだけで解決することができます。

ただし、グローバル変数は名前範囲が大きく、語の重複やデバッグを困難にしてしまうことがあります。

グローバル変数化以外の解決策として静的変数とする(static化する)という方法があります。これならば外部と変数名重複を起こすことがありえません。もちろん、別にstatic化できない理由がある（再帰関数とかの場合）は例外です。

Answer 4

ココで答えました。

※ 領域確保のためにグローバル変数使うのはお行儀が悪いと思ってるので、↑ではmalloc/free使ってます。
※ C++なら new/delete あるいは vector 使いますかねぇ...

Comments

[HogeAnimalLover]

グローバル変数以外の簡単な代案として、static化するという方法があります。もちろん、再帰関数等では無理の場合もありますが、static化が手っ取り早いです（もっとも、再帰関数ならばグローバル変数でも駄目ですが）。動的メモリ確保だとリークの危険ですし、デバッグもしずらいので。

[episteme]

leakが怖いなら unique_ptr/shared_ptr, vector 選びます。
static/global だとre-entrant性をぶち壊すのでthreadが絡んだときに厄介だし。
static/globalはメモリ不足対処の1'st-choiceにはならんと思ってます(いくら手っ取り早くとも)。

[HogeAnimalLover]

もちろん1'st-choiceではありません。「グローバル変数よりはstaticの方がマシ」程度の意見です。「お行儀について」という記述があったのでコメントした次第です。

Answer 5

このあたり見てください
メモリの 4 領域
c++で配列のサイズが大きく多くて実行時にエラーが起こる場合の対応

Answer 6

＞main関数内とグローバルでの宣言ではメモリへの保存のされ方が異なるということなのでしょうか？

はい。