no-image

スタックとヒープを知る

Rustをやっていると、スタックとヒープの理解がないときついなという気分になったので少し調べてみた。

それを勉強会で発表したので、少しまとめる。

スライド: Jupyter Notebook Viewer

メモリについて

メモリとは一時的なデータを記憶する主記憶装置の一つだが、中身を見てみると1Byte(8bit)ごとにアドレスが振られているのがわかる。

ソースコードをコンパイルし実行ファイルが作られたときに、コード内の変数名などは全てメモリ上に格納されていく。
その格納する場所はどこでもいいわけではなく、ある程度決まった場所に置かれる。

4つのメモリ領域

プログラムのメモリ領域は、用途によっていくつかのセクションに分類される。
この分け方は、特に決まっているわけではなく増やしたり減らしたりもできるが、一般的には4分類されることが多いようである。

【参考】C++ – メモリ領域の区分の仕方の違い(4分類か5分類か)の理由|teratail

これらメモリ領域の「サイズ」はコンパイルやリンクの時点で決定される。
だが、中身の「データ」はコンパイル時に決まる部分と、実行時に決まる部分とがある。
コンパイル時に決まるものを「静的」、実行時に決まるものを「動的」と区別する。

【参考】OS – スタック領域は動的か静的か|teratail

【画像引用元】Memory layout of a process | Operating System

スタックとヒープは動的なので図を見ても分かるように、下2つを決めた残りの部分を両端から使っていく。

以下、簡単に4領域の概要。

静的な領域

  • テキスト領域(TEXT)
    • 機械語に翻訳されたプログラムを置く
    • この命令が1行ずつ実行されることでプログラムが動く
  • 静的領域(DATA)
    • グローバル変数など、実行中に変化がない静的な変数が置かれる場所

動的な領域

  • ヒープ領域(HEAP)
    • 動的にサイズが確保されるデータを置く
  • スタック領域(STACK)
    • 関数の引数やローカル変数などの一時変数を置く

また、5つに分類されているものを解説されている記事もあったので、合わせて参考にしてみるといいかも。

【参考】

アドレスをGoで確認してみる

イメージを掴むためにGoで簡単なプログラムを書いて実行してみた。
3つの変数を定義し、格納されているアドレスを出力している。

実行結果。

16進数のアドレス値が出力された。
これらはスタックを使っているが、上図で見たようにスタック領域は最初に宣言したもののアドレス値が大きいものになっていることと、8bitずつ使われていることがわかった。

なお、今回のように定義した変数がいつも連続したメモリ領域に格納されるわけではないが、今回の結果は直感的なものだった。

スタックについて

【画像引用元】Data Structures and Algorithms Stack

概要

スタック領域は、データを積み上げていき最後に積んだものから使っていくLIFO方式の領域である。

通常の変数宣言などをするとコンパイラやOSが自動で割り当ててくれ、スコープを抜け寿命が終わると自動で解放もしてくる。
なので、プログラマは特に気にすることなくコードを書いていくことができるので楽。

また、ローカル変数は全て事前にわかっているので一度で割り当てられることや、次の場所が自明なことで、確保、解放が高速であることも特徴。

最初に決めるスタック領域のサイズを大きく取りすぎると 、使われていない部分が無駄になるのでそういうことはしたくない。

なのでスタックに入れるものには、比較的サイズが小さくて、特定の関数内でしか使わない変数などが向いている。

コードでの解釈

このサイトにわかりやすい画像があったので少し引用させて頂く。

要は変数が宣言されたときにスタックに積まれ、スコープを抜けたときに自動的に取り除かれていくわけだ。

この辺の、コードと図でわかりやすく解説されている記事はいくつかあったので載せておく。

【参考】

気をつけること

スタックを扱う際にいくつか気を付ける点がある。

スタックオーバーフローエラー

技術系質問サイトの名前の由来にもなっているスタックオーバーフロー。
これはスタックに使うメモリのサイズを超えてpushしてしまうことである。

スタックアンダーフローエラー

これは逆に、スタックが空なのに、さらにpopしようと起こるエラー。
Cなど普通の言語で書いていると起こりえないが、アセンブリなどで書いていると起こりうるらしい。

スタックオーバーフローを起こしてみる

Pythonでスタックオーバーフローエラーを起こしてみるコードを書いてみた。

try-exception文でRecursionErrorが出てもとにかく再帰しまくる関数を実行する。

すると、以下のようにスタックオーバーフローが起きたのが確認できた。

ヒープについて

続いてヒープについて。

概要

ヒープは整然と積んでいくスタックとは違い、乱雑に山積みしていくイメージのもの。

【画像引用元】Memory in C – the stack, the heap, and static – The Craft of Coding

必要になったときにサイズを指定して自分自身でメモリの確保を行い、用が済んだときに自分で開放処理を行う。

確保、解放する順番は任意で、LIFOなどの制約もない。

速度はスタックに比べると低速で、これは、確保時は空いている領域を検索する必要があったり、読み込み時も一度ポインタアドレスを読んでからデータの場所を見に行ったりするから。

スタックとは逆に、大規模なデータを置くのに向いている。

確保、開放する様子は先ほども載せたが以下のサイトがわかりやすかった。

【参考】

用途としては、データを必要とするスコープがはっきりせず、いろいろな場所から参照されるものを置くときや、事前にサイズのわからないファイルを読むこむときなどに使われる。

各言語での宣言のしかた

いくつかの言語でのヒープの扱い方を簡単に見てみる。
あまり厳密ではないので、イメージ程度に。

C言語では

確保時はmalloc()関数を用いる。「メモリアロケーション」の略。
void*型のポインタを返すのでキャストして使うことが多い。

開放時はfree()関数を用いる。

以下のコードは何もしていないがこんなイメージ。
変数pは確保した領域の先頭のアドレスを返す。

 

C++では

確保時はnew演算子、開放時はdelete演算子を使う。
Cと似ているが、コンストラクタやデストラクタがあるところなどが異なるらしい。

【参考】

Rustでは

Rustでは、Box<T>型を使うとヒープ上に確保できる。

以下はi32型の値5をxに格納している。

ヒープに確保されているが、xがスコープが抜けるタイミングで解放される。

他にも方法があるようだ。

【参考】rustで動的にバッファを確保する方法 – 睡分不足

Goでは

Goではスタックとヒープを気にする必要がないようだ。

どこに確保するかはコンパイラがよしなに行ってくれるので、たとえnewしたとしても必要がなければスタック上に置かれる。

【参考】golangではスタックとヒープを気にする必要が無い – Qiita

気をつけること

任意のタイミングで確保、解放ができるヒープだが、頻繁にやりすぎるとフラグメンテーションの原因になる。

確保時に、塊で空いている場所を探すわけだが、必要なサイズがいつも同じ大きさとは限らないので、前回解放したサイズが今回確保するサイズよりも小さい場合は、また別の場所を探して確保することになる。

すると、使用中の部分と未使用の部分が飛び飛びになってしまい、確保時に参照の局所性が失われやッシュのヒット率低下が起こり、処理性能が悪化してしまう。

文字で書いてもわかりにくと思うので、図を見てもらったほうがわかりやすい。

【画像引用元】Dynamic Memory Allocation

GCなどがある言語では、GC後にコンパクションという処理を行って、使用部分と未使用部分をそれぞれ一塊になるように整理する操作もある。

他の注意点としては、ヒープへの確保は失敗することもあるということだ。
物理的なメモリが足りないときや、アドレス空間に空きがないときはエラーが生じる(こともある)。

【参考】IPA ISEC セキュア・プログラミング講座:C/C++言語編 第1章 総論:C/C++がもたらす問題

まとめ

  • スタックとヒープは動的。
  • スタックは積み上げていくやつで、普通の変数宣言などに用いられる。順番が決まってる。
  • ヒープは任意のタイミングで使えるが、確保、解放は自分でやらないといけない。そして若干遅い。

長くなった。
PythonやJavaScriptなど裏で勝手に色々やってくれる言語ばかりやっていたので、これまで意識することなくプログラミングできていたが、いい機会にしれて良かった。