C/C++ gooseのドキュメントが示すヒープ管理のコスト問題と対策について

まえふり

最近、goose言語が話題になっている。

この言語はC/C++に似た言語であるが、C/C++におけるヒープ管理のコストがないことによってベンチマークによっては3.3倍の性能が出て、メモリーの消費も抑えられるというものである。

Faster than C++ and than safe Rust, while memory safe. Over sixteen benchmarks Goose runs at 3.3x the speed of idiomatic C++, 1.16x hand-optimized C++ and 1.12x the best safe Rust, and uses 1.9x, 1.3x and 1.2x less memory (results). These gains come from Goose's data layouts and memory model.

似た機能をC/C++で無理矢理実現する

堅牢性を完全に無視した乱暴な方法であれば、C/C＋＋のヒープ管理のコストをゼロにすることは簡単である。

#define malloc(x) alloca(x)
#define free(x) /**/

必要に応じて領域を広げて、その先頭のアドレスを取って来る。不要になっても即時に開放はしないので空き領域の管理も断片化も発生しない。そして、関数の終了時に獲得した領域をそのまま丸ごと開放する。

gooseはこのような処理を安全に行うためにわざわざ言語をまるごと作り直している。
ただ、ヒープ管理のコストが重く響くケースというのは限定的なのでここまでやる人が今までいなかったのだろう。

コストの発生源:ヒープのおさらい

計算機関係の教科書に出てくると思うが、ヒープ管理の古典的な実装は以下のようなものである。

1. スタックセグメントの末端の空き領域に反対方向に成長する第二のスタックを作る(このセグメントは実メモリーのサイズを超える広さを持つ仮想記憶領域であり、二つのスタックは衝突しないようになっている)。そしてこの第二のスタックをヒープと呼び、2つのスタックの隙間をモートと呼ぶ。
2. malloc or newが呼び出されるたびに必要なサイズだけ領域を切り分け、線形のリンクを張っていく。これはストレージのファイルシステムのように動作する。この時、空きがない場合はOSの機能を使用してヒープを延長する。
3. free or deleteが呼び出されるたびに切り分けた領域を空き領域に戻し、隣接した空き領域があれば一つの空き領域として結合する。

この辺の処理を雑にコーディングしてみると以下のようになる。ヒープとバイト数を指定して領域を確保して、確保した領域の位置(ヒープの先頭からのバイトオフセット)を獲得または返却をする処理である。

typedef struct { size_t size, next; } MBLOCK;

size_t xmalloc(void *heap, size_t bytes) {
  MBLOCK *mb = (MBLOCK *)heap;
  size_t prev, next, need;
  need = (bytes + sizeof (MBLOCK) - 1) / sizeof (MBLOCK) + 1;
  for (prev = 0; next = mb[prev].next; prev = next) {
    if (mb[next].size > need) {
      mb[next + need].next = mb[next].next;
      mb[next + need].size = mb[next].size - need;
      mb[prev].next = next + need;
      mb[next].size = need;
      break;
    } else if (mb[next].size == need) {
      mb[prev].next = mb[next].next;
      break;
    }
  }
  return next ? (char *)&(mb[next + 1]) - (char *)&(mb[0]) : next;
}

size_t xfree(void *heap, size_t boff) {
  MBLOCK *mb = (MBLOCK *)heap;
  size_t prev, next, mark, nelm;
  mark = (boff / sizeof (MBLOCK)) - 1;
  for (prev = 0; (prev < mark) && (next = mb[prev].next); prev = next) {
    if (next > mark) {
      mb[prev].next = mark;
      mb[mark].next = next;
      if ((prev + mb[prev].size) == mark) {
	    mb[prev].size += mb[mark].size;
	    mb[prev].next  = mb[mark].next;
	    mark = prev;
      } 
      if ((mark + mb[mark].size) == next) {
	    mb[mark].size += mb[next].size;
	    mb[mark].next  = mb[next].next;
      }
      return 0;
    }
  }
  return !0;
}

安全性を配慮したヒープ管理のコスト対策

要するに、free or deleteを使用しないというルールを設定するならば、管理コストは発生しない。だが、標準のmalloc or newの仕様ではランタイムライブラリと共有されるので、ユーザーの意図しないfree or deleteは陰で実行されている。これによってヒープ領域は断片化されコストが発生する。

C/C++でこの問題を解決するには非標準のmallocを作成し、必要に応じて領域をまるごと破棄または作り直すのがよい。

ヒープの管理コストが重要になる限られたケースにおいてはこの手が有効になる。