{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# スタックとヒープを知る\n",
    "\n",
    "- 2018/10/11 勉強会"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# アジェンダ\n",
    "\n",
    "1. 調べようと思ったきっかけ\n",
    "1. メモリ領域概観\n",
    "2. スタックについて\n",
    "3. ヒープについて\n",
    "4. まとめ\n",
    "5. 参考"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# 調べようと思ったきっかけ\n",
    "\n",
    "- スタックとヒープわかってないとRustわけわかめになる"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# メモリについて\n",
    "\n",
    "- メモリは1Byte(8bit)ごとにアドレスが振られている\n",
    "- 実行ファイルにコンパイルすると変数名は16進数のアドレス値に変換される\n",
    "- 1つのプロセスは1つのメモリ空間と複数のスレッドを持つ\n",
    "    - 1つのスレッドは1つの連続したメモリ領域のスタックを持つ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# メモリ領域概観\n",
    "\n",
    "- メモリ領域の「サイズ」はビルド時に決定する\n",
    "- スタックとヒープに格納されるデータは動的に決まる\n",
    "    - ので、実行するまでどこを使うか決まらない\n",
    "    - だから、下3つ以外の部分を上下両端から使っていく\n",
    "\n",
    "![](https://he-s3.s3.amazonaws.com/media/uploads/383f472.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 5つのメモリ領域\n",
    "\n",
    "- 置かれるアドレスが\n",
    "    - 実行時に決まるものが「動的」\n",
    "    - コンパイル時に決まるものが「静的」\n",
    "\n",
    "---\n",
    "### 静的な領域\n",
    "- text\n",
    "    - プログラムの内、機械語の部分を置く\n",
    "- data\n",
    "    - 初期値のあるグローバル変数を置く\n",
    "- bss\n",
    "    - 初期値のないグローバル変数を置く\n",
    "    - Block Started by Symbolの略\n",
    "    - [参考リンク](http://www.ertl.jp/~takayuki/readings/info/no03.html)\n",
    "    \n",
    "### 動的な領域\n",
    "- heap\n",
    "    - プログラムのデータを置く\n",
    "    - 動的にサイズが確保されるものを置く\n",
    "- stack\n",
    "    - 関数の引数やローカル変数を置く\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## アドレスをGoで確認してみる\n",
    "\n",
    "#### 複数の変数を宣言してアドレスを出力する\n",
    "\n",
    "- これらの値はスタック領域に入る\n",
    "\n",
    "```\n",
    "package main\n",
    "\n",
    "func main() {\n",
    "\ta, b, c := 11, 12, 13\n",
    "\tprintln(&a) // アドレスを出力\n",
    "\tprintln(&b)\n",
    "\tprintln(&c)\n",
    "}\n",
    "\n",
    "```\n",
    "\n",
    "#### 出力結果\n",
    "```\n",
    "> go run address.go\n",
    "0xc000040780\n",
    "0xc000040778\n",
    "0xc000040770 // 8bitずつ減っている\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# スタックについて\n",
    "\n",
    "- 積み上げる、堆積物という意味\n",
    "    - きれいに整然と積み上げていくイメージ\n",
    "- LIFO\n",
    "\n",
    "![](https://www.tutorialspoint.com/data_structures_algorithms/images/stack_representation.jpg)\n",
    "\n",
    "- 【画像引用元】[Data Structures and Algorithms Stack](https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## スタックについて\n",
    "\n",
    "- コンパイラやOSが自動で割り当てる領域\n",
    "    - 領域の解放も自動的にやってくれる\n",
    "    - 楽\n",
    "- メモリ割り当てが高速\n",
    "    - ローカル変数は全て事前にわかるので一度で割り当てられる\n",
    "    - ヒープ割り当てより2~3桁速い(要出典)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## コードでの解釈\n",
    "\n",
    "- スコープが入れ子になっているとき、内側のスコープで使うデータ領域は後から確保し、先に解放される\n",
    "    \n",
    "![](https://ufcpp.net/media/ufcpp2000/computer/fig/Essential/Stack.png)\n",
    "\n",
    "- わかりやすい図解\n",
    "    - [スタックメモリとヒープメモリ](http://article.higlabo.com/ja/stack_and_heap.html)\n",
    "    - 【画像引用元】[メモリ管理 - コンピュータの基礎知識 | ++C++; // 未確認飛行 C](https://ufcpp.net/study/computer/MemoryManagement.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 気をつけること\n",
    "\n",
    "- スタックオーバーフロー\n",
    "    - スタックのメモリのサイズを超えてpushすること\n",
    "- スタックアンダーフロー\n",
    "    - スタックが空の状態でさらにpopしようとすること\n",
    "- スコープを抜ければスタック領域が強制的に解放される\n",
    "    - ポインタがスタック領域を指すときは解放後にアクセスしないようにする\n",
    "    \n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# ヒープについて\n",
    "\n",
    "- 塊、山積みという意味\n",
    "    - 乱雑に山積みするイメージ\n",
    "\n",
    "![](https://craftofcoding.files.wordpress.com/2015/12/stackmemory4.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## ヒープについて\n",
    "\n",
    "- 動的に割り当てたり、解放できる領域\n",
    "- メモリの確保と解放を自分自身で行う必要がある\n",
    "    - サイズは動的に指定できる\n",
    "    - 確保、解放する順番は任意\n",
    "- 低速\n",
    "    - アロケート時は空いている領域を検索する\n",
    "    - 読み込み時もポインタアドレスから参照する"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 用途\n",
    "\n",
    "- データを必要とするスコープがはっきりしないとき\n",
    "    - さまざまな箇所から参照される場合など\n",
    "- ファイルを読み込むとき\n",
    "    - ファイルサイズがわからないから"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## C言語では\n",
    "\n",
    "- malloc()でメモリアロケーション\n",
    "- free()で解放\n",
    "\n",
    "------\n",
    "\n",
    "- 擬似コード\n",
    "    - 【参考】[ヒープとスタック | 学校では教えてくれないこと | [技術コラム集]組込みの門 | ユークエスト株式会社](https://www.uquest.co.jp/embedded/learning/lecture16.html)\n",
    "\n",
    "```\n",
    "ファイルオープン;\n",
    "file_sizeを取得;\n",
    "buf = malloc(file_size);\n",
    "bufにファイル内容を読み出し;\n",
    "free(buf);\n",
    "```\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## C++では\n",
    "\n",
    "- new演算子でメモリアロケーション\n",
    "- delete演算子で解放\n",
    "- コンストラクタ、デストラクタがある辺りが若干違う\n",
    "    - http://book.geocities.jp/muu5muu/doc1/sample6.html\n",
    "    - https://brain.cc.kogakuin.ac.jp/~kanamaru/lecture/C++2/09/09-02.html\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Rustでは\n",
    "\n",
    "- `Box<T>型`をつかうとヒープ上にアロケートできる\n",
    "    - `i32`型の値5をxに格納\n",
    "    - `let x: Box<i32> = Box::new(5)`\n",
    "- [他の方法](http://mmi.hatenablog.com/entry/2017/08/06/230823)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## ちなみにGoでは\n",
    "\n",
    "- スタックとヒープを気にする必要がない\n",
    "    - コンパイラがよしなに行ってくれる\n",
    "    - newしても必要がなければスタックにアロケートする\n",
    "    - 【参考】[golangではスタックとヒープを気にする必要が無い - Qiita](https://qiita.com/rookx/items/a1e3d057a0ed71424094)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 気をつけること\n",
    "\n",
    "- 確保、解放を頻繁にやりすぎるとフラグメンテーションの原因になる\n",
    "    - 参照の局所性が失われ、キャッシュのヒット率低下が起こり、処理性能が悪化する\n",
    "    - GC後、使用領域を一箇所にまとめるコンパクションという処理を行うこともある\n",
    "- 確保に失敗することもある\n",
    "    - 物理的な空きメモリがないとき\n",
    "    - アドレス空間に空きがないとき"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# まとめ\n",
    "\n",
    "- メモリにはいくつかの領域がある\n",
    "- スタックはLIFOでスコープが寿命\n",
    "- ヒープは自分で確保と解放を行う"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# 参考\n",
    "\n",
    "- [ヒープとスタック | 学校では教えてくれないこと | [技術コラム集]組込みの門 | ユークエスト株式会社](https://www.uquest.co.jp/embedded/learning/lecture16.html)\n",
    "- [スタックメモリとヒープメモリ](http://article.higlabo.com/ja/stack_and_heap.html)\n",
    "- [メモリ管理 - コンピュータの基礎知識 | ++C++; // 未確認飛行 C](https://ufcpp.net/study/computer/MemoryManagement.html)\n",
    "- [メモリとスタックとヒープとプログラミング言語 | κeenのHappy Hacκing Blog](https://keens.github.io/blog/2017/04/30/memoritosutakkutohi_puto/)\n",
    "- [malloc ライブラリのメモリ管理構造 | 技術文書 | 技術情報 | VA Linux Systems Japan株式会社](https://www.valinux.co.jp/technologylibrary/document/linux/malloc0001/)(未読)\n",
    "- [ポインタと配列 - A Day In The Life](http://glassonion.hatenablog.com/entry/20090414/1239716083)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": "block",
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}