スタックとヒープを知る

2018/10/21

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

メモリについて

4つのメモリ領域

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

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

コンパイル時に決まるものを「静的」、実行時に決まるものを「動的」と区別します。

参考

https://www.includehelp.com/operating-systems/images/memory-layout-of-a-process-1.jpg https://www.includehelp.com/operating-systems/memory-layout-of-a-process.aspx

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

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

静的な領域

機械語に翻訳されたプログラムを置く

この命令が1行ずつ実行されることでプログラムが動く

グローバル変数など、実行中に変化がない静的な変数が置かれる場所

動的な領域

動的にサイズが確保されるデータを置く

関数の引数やローカル変数などの一時変数を置く

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

参考

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

イメージを掴むためにGoで簡単なプログラムを書いて実行してみました。

3つの変数を定義し、格納されているアドレスを出力しています。

code:go

package main

func main() {

a, b, c := 11, 12, 13

println(&a) // アドレスを出力

println(&b)

println(&c)

実行結果。

code:txt

$ go run address.go

0xc000040780

0xc000040778

0xc000040770 // 8bitずつ減っている

16進数のアドレス値が出力されました。

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

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

スタックについて

https://www.tutorialspoint.com/data_structures_algorithms/images/stack_representation.jpg https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm

概要

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

ちなみにLIFOはLast In First Outの略です。

通常の変数宣言などをするとコンパイラやOSが自動で割り当ててくれて、スコープを抜け寿命が終わると自動で解放もしてくれます。

なので、プログラマは特に気にすることなくコードを書いていくことができるので楽。

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

最初に決めるスタック領域のサイズを大きく取りすぎると 、使われていない部分が無駄になるのでそういうことはしたくありません。なのでスタックに入れるものには、比較的サイズが小さくて、特定の関数内でしか使わない変数などが向いています。

コードでの解釈

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

https://ufcpp.net/media/ufcpp2000/computer/fig/Essential/Stack.png

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

参考

ヒープについて

続いてヒープについて。

概要

ヒープは整然と積んでいくスタックとは違い、乱雑に物が積まれていく二次元の机の上のようなものです。

必要になったときにサイズを指定して自分自身でメモリの確保を行い、用が済んだときにプログラマが自分で解放処理を行う必要があります。

スタックと違い、複数のデータを確保したり、解放したりする順番は任意で、LIFOなどの制約もありません。

速度はスタックに比べると低速です。

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

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

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

参考

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

各言語での宣言の仕方

いくつかの言語でのヒープの扱い方を簡単に見てみます。

あまり厳密ではないので、イメージ程度に。

C言語では

以下のコードは何もしていないがこんなイメージ。

変数pは確保した領域の先頭のアドレスを返します。

code:c

p = (char*) malloc(100); // 100byteのchar型のメモリ領域を確保

free(p) // 解放

C++では

確保時はnew演算子、開放時はdelete演算子を使います。

参考

Rustでは

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

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

code:rs

let x: Box<i32> = Box::new(5)

ヒープに確保されているが、xがスコープが抜けるタイミングで解放されます。こここそがRustの特徴の一つだったりします。

他にも方法があるようです。

参考

Goでは

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

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

参考

気をつけること

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

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

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

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

https://chortle.ccsu.edu/assemblytutorial/chapter-33/fragmentation.gif

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

参考

まとめ

スタックとヒープは動的。

スタックは積み上げていくやつで、普通の変数宣言などに用いられる。順番が決まってる。

ヒープは任意のタイミングで使えるが、確保、解放は自分でやらないといけない。そして若干遅い。

長くなりました。

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