C++のスタックメモリと動的メモリの上限値調査

#C++のプログラミングにて
　以下のようなコードはコンパイルは出来ますが、実行すると「Segmentation fault: 11」になりした。なお、コンパイラはg++、version 10.1.0、Macです。

```c++:main.cpp
#include <iostream>
int main(){
  //ローカル変数の定義
  char field[2000][2000]={};
  int type[2000][2000]={};

  for (int i = 0; i < 2000; i++) {
    for (int k = 0; k < 2000; k++) {
      std::cin >> field[i][k];
    }
  }

  //以降省略

  return 0;
}
```


#Segmentation faultの理由
　ズバリ、「__メモリ不足__」です。
　ローカル変数に大きすぎる配列を用意すると実行できないことは知っていたのですが、自分が思っているよりも上限が小さかったようです。
　そもそもローカル変数はスタックメモリに配置されますが、スタックメモリの容量はあまり大きくありません。
[参考）　モノづくりC言語塾　C言語 スタックメモリ](https://monozukuri-c.com/langc-stack-memory/)
　そこで、スタックメモリの容量について調査してみることにしました。

#スタックメモリの上限調査
　まずは、上述のmain.cppのデータサイズを計算します。

　char field[2000][2000]={};
　　char型は1byteより1*2000*2000=4000000(byte)=4(MB)
　int type[2000][2000]={};
　　int型は4byteより4*2000*2000=16000000(byte)=16(MB)

 上限は少なくとも20MB以下のようです。

以下のようなtest.cppで上限値を調査したところ、8384464バイト(__およそ8.3MB__)が上限値でした。
(スタックメモリの容量は環境等によって異なるようですので、参考程度に「この人の場合は10MBも無いんだな」と思って頂ければ幸いです。)

```c++:test.cpp
#include <iostream>
#define MB 8
#define KB 384
#define Byte 464
int main(){
  char mega_byte[1000][1000][MB]={};//サイズはMB[メガバイト]
  char kilo_byte[1000][KB]={};//サイズはKB[キロバイト]
  char byte[Byte]={};//サイズはByte[バイト]
  return 0;
}
```

私のPCでは二次元配列であれば
int array[1447][1447]={};//およそ8.3MB
long long a[1023][1023]={};//およそ8.3MB
あたりが限界となるようで、1000*1000を超えるような場合はローカル変数にしないほうが無難なようです。

#動的メモリの上限調査
 スタックメモリはおよそ8.3MBが限界という結果が出ましたが、動的メモリの上限値はどの程度なのか調べてみます。
 実行中に動的メモリが確保できず停止したことがないので、1byteからスタートして確保するサイズを10倍づつ増加させてみます。

```c++:test2.cpp
#include <iostream>
#include <vector>
#include <stdio.h>
#include <time.h>
int main(){
  //カーネルがkillしてくれるのを待ちます
  for (long long byte = 1; ; byte*=10) {
    clock_t start = clock();
    std::cout << byte<<"[byte]" << '\n';
    std::vector<char> v(byte,'a');
    clock_t end = clock();
    const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0;
    printf("time %lf[ms]\n", time);
  }
  return 0;
}
```

下記のようになりました。

| 確保するサイズ[byte] | 確保できたか | 実行時間[ms] |
|:-----------|------------:|:------------:|
| 1      | Yes        | 0.145000         |
| 10      | Yes   | 0.005000         |
| 100      | Yes        | 0.005000         |
| 1000(=1KB)     | Yes       | 0.003000         |
| 10000     | Yes        | 0.014000         |
| 100000     | Yes        | 0.08100         |
| 1000000(=1MB)     | Yes        | 0.61100         |
| 10000000     | Yes        | 5.207000         |
| 100000000     | Yes        | 49.044000         |
| 1000000000(=1GB)     | Yes        | 542.140000         |
| 10000000000     | Yes        | 6715.737000         |
| 100000000000(=100GB)     | No        |(killed :9にて終了)|

　10MBあたりまでは高速に動作し、10GBまではなんとか確保しました。
100GBの確保にてkilled:9で強制終了しましたが、そもそも利用しているPCの物理メモリ8GBです。killされる直前にアクティビティモニタを確認したところ

* メモリ　57GB
* メモリ圧縮　55.82GB

となっており、メモリ圧縮でなんとか確保した（圧縮してるなら出来てない気もする）ようで、100GB確保出来る筈もなく妥当な結果です。
　私個人はGBのオーダでメモリを確保することはないので、動的メモリの上限値はあまり気にしなくて良いようです。
　これだけ見ると動的メモリは空きメモリと時間があるなら際限なく確保できそうでしたが、1e18(=1000000000000000000)など明らかに大きすぎるサイズのメモリを確保しようとすると以下のようなエラーが発生しました。

```
terminate called after throwing an instance of 'std::length_error'
  what():  cannot create std::vector larger than max_size()
Abort trap: 6
```
 [max_size()](https://cpprefjp.github.io/reference/vector/vector/max_size.html)という関数があり、コンテナに格納可能な最大数を取得出来るようです。
試しに、最大数を出力し、上限数でメモリを確保してみます。

```c++:test3.cpp
#include <iostream>
#include <vector>
#include <stdio.h>
#include <time.h>
int main(){
  std::vector<char> v;
  std::cout <<"最大数:"<<v.max_size() << '\n';

  clock_t start = clock();
  
  //最大数で確保する
  v.resize(v.max_size());

  clock_t end = clock();
  const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0;
  printf("time %lf[ms]\n", time);
  return 0;
}
```

結果は以下のようになりました。

```
最大数:9223372036854775807
test(49061,0x7fff95f95380) malloc: *** mach_vm_map(size=9223372036854775808) failed (error code=3)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
Abort trap: 6
```

char型のvectorの場合、コンテナの最大数は9223372036854775807だそうです。およそ9エクサバイトの容量を確保しようとしてエラーが出ました。
v.max_size()で取得できる値は理論値であって、実際に実行出来る上限値はPCに依存するということのようです。
　念のためにメモリ不足で実行出来なかったmain.cppを動的に確保して実行してみます。

```c++:main2.cpp
#include <iostream>
#include <vector>
#include <stdio.h>
#include <time.h>
int main(){
  clock_t start = clock();
  std::vector<std::vector<char> > field(2000,std::vector<char>(2000));
  std::vector<std::vector<int> > type(2000,std::vector<int>(2000));

  clock_t end = clock();
  const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0;
  printf("time %lf[ms]\n", time);
  return 0;
}
```

　無事に14[ms]で実行できました。

　次にnewを使ってメモリ確保の実験をしてみます。

```c++:test4.cpp
#include <iostream>
#include <vector>
#include <stdio.h>
#include <time.h>
int main(){
  long long size=1e11;
  clock_t start = clock();
  char * a = new char[size];//1e11Byte=100GBのメモリを確保する
  clock_t end = clock();
  const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0;
  printf("time %lf[ms]\n", time);
  delete[] a;
  return 0;
}
```

実行結果は

```
time 0.226000[ms]
```

　メモリが確保出来たようです。[new演算子例外の実験](https://www.asahi-net.or.jp/~uc3k-ymd/Lesson/Section02/except.html)を参考に例外が発生しているかどうかも確かめてみましたが、例外は発生していませんでした。しかし、sizeを1e11から1e13にすると、vectorでの実験と同様にbad_allocの例外が発生しました。
　実行中にアクテビティモニタを確認したところ、

* 実メモリサイズ　1.3MB
* 仮装メモリサイズ　935.41GB

となっていました。どうやら、仮想メモリを使って900GB程度まで確保したようです。
test2.cppでのVectorのテストでは要素を'a'にて初期化しており、仮想メモリを利用出来なかった（？）ようですが、今回のテストは領域を割り当てるだけで利用していない為仮想メモリを利用したようです。
　仮想メモリやメモリ圧縮について疎いので勉強しようと思います。。
　
#まとめ
* 関数内で定義する変数はスタックメモリが利用され、上限値__8MB__程度(上限を越えると実行時にSegmentation fault) 
* 目安としては、二次元配列なら1000*1000を超えるなら動的に確保したほうが良い。
* 動的にメモリを確保する場合は__10MB__程度までは1秒未満で確保できる。動的メモリサイズの上限はPCの物理メモリサイズや、割り当て可能な仮想メモリサイズ、メモリ圧縮など依存する（模様）。