builderscon tokyo 2019 - Elixir: Under the Hood

2019年8月31日、[builderscon tokyo 2019](https://builderscon.io/tokyo/2019) にて「[Elixir を支える技術 -「落ちない」システムの秘密に迫る](https://builderscon.io/builderscon/tokyo/2019/session/5e4eb13c-4efd-42ee-b22c-5ccb37c0854e)」というセッションで発表してきました。この記事では、発表で使ったスライドと台本を公開します。時間的制約で当日喋れなかった部分や参考リンクもつけているので、当日聴かれた方は差分を楽しんでみてください。

builderscon は参加するのも初めてで、もともとは、[Erlang & Elixir Fest 2019]([https://elixir-fest.jp](https://elixir-fest.jp/)) の懇親会で元同僚から勧められた勢いで CfP を送ったのがキッカケでした。3日前になっても台本すら出来ていなかったときはさすがに後悔しましたが、当日は予想以上に多い聴衆と質問で非常に楽しいセッションでした。すべて運営スタッフと温かい聴衆のみなさんのおかげです。ありがとうございました。

また、ぼくがいま勤めている株式会社 ABEJA でも、Elixir を運用中のシステムで使っています（具体的にどういうところで使っているかは、この記事で載せている登壇の台本を読んでみてください）。[エンジニアを積極採用中](https://hrmos.co/pages/abeja/jobs/11797333)なので、Elixir が大好きでプロダクションのコードを書きたい人はぜひ一緒に働きましょう。

------

_ここから、登壇内容の台本とスライドです。スライド本体の PDF は[こちら](https://speakerdeck.com/ishikawa/elixir-under-the-hood)です。_
![Elixir_Under_Hood_JPEG_Min.002.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/fb6b4fbc-5fdc-016f-0187-4b03d44f5a29.jpeg)

## Introduction

![Elixir_Under_Hood_JPEG_Min.003.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/ee1616a8-039a-8dcb-a30d-14f8a45ea496.jpeg)

みなさま、はじめまして。セッションのスピーカーを務めさせていただく石川尊教（いしかわ・たかのり）です。Twitter のアカウントは [@takanori_is](https://twitter.com/takanori_is) で、ときどき思い出したように技術の話をしたりします。それ以外では映画やアニメといったサブカルチャー、または猫かお酒の話をしているので興味がある方はフォローしてください。

プログラマとしての職歴はごらんのとおりです。古の「Web 2.0 時代」に株式会社ドリコムでデビューしてからは、株式会社ミクシィで SNS とゲームのプラットフォーム事業に関わっていました。現在は株式会社 ABEJA で機械学習エンジニア向けの開発プラットフォームを作っています。

今回のセッションでは Elixir というプログラミング言語について話をするわけですが、ぼく自身が Elixir という言語を使いはじめたのは前職のミクシィで新規事業のプラットフォームを開発するときに採用したのが馴れ初めです。約4年間の付き合いになります。

そのあいだ、実運用環境で Elixir のシステムを動かしており、前職ではゲームユーザー向けのアプリのバックエンド、**現職の ABEJA では社内外で使われている[機械学習向け開発プラットフォーム](https://abejainc.com/platform/ja/)において API Gateway を Elixir で作ったシステムで運用しています。すべての API や Jupyter ノートブックへのリクエストの認証・ルーティングを請け負っており、また、カメラなどのデバイスから送られてくるデータの受け口でもあります。**

つまり、いずれもライブな環境で稼働しつづける必要があるシステムであるわけですが、これまでシステムが完全に落ちたのは自分が仕込んだバグでメモリが枯渇したときくらいです。それくらい、Elixir で作ったシステムは安定しています。

## Summary

![Elixir_Under_Hood.004.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/012b95ae-1c66-a7da-9632-f72a4a9f39b2.jpeg)
では、セッションの本編に入る前に、今回のセッションでお話しすることをまとめたいと思います。

まず、Elixir という言語の簡単な紹介をしたいと思います。日本でも採用事例が増えてきたとはいえ、まだまだマイナーな言語なので、会場にお越しの方でも知っている人は少ないかと思います。また、Elixir は Erlang（あーらん）という別の言語の Virtual Machine（ばーちゃる・ましん）とランタイムで実行されます。Erlang は歴史の長い言語ですが、こちらはさらにマイナーかもしれません。ちょっとアンケートを採ってみましょうか。

Elixir または Erlang という言語を、名前だけでも聞いたことがある人は挙手をお願いします。（挙手をうながす）

では、Elixir または Erlang について、少なくとも何かのチュートリアルくらいはやったことがある...つまり「完全に理解した」人はどれくらいいますか？（挙手をうながす）

では、「完全に理解して」いる方でも何も知らない方でも、できるだけ Elixir と Erlang のエッセンスが伝わるように、このセッションでは言語の特徴やデザイン、その魅力を紹介できればと思います。

それから、一応、今回のセッションは「落ちないシステムの秘密に迫る」という煽り文句で採択してもらっているので、このへんについても喋りたいと思います。そもそも「落ちないシステム」ってどういうことなの、とか、そのために Elixir というより Erlang が採用しているアプローチについても説明します。「Elixir は並行処理に強い」とか「スケールしやすい」という話、あるいは「Ruby に似た文法」などの噂を聞いたことがあるかもしれませんが、だいたい、そういう話をします。

とまあ、このへんまでがイントロダクション、概念とか紹介記事的な内容でして、そのあとはもうすこし技術的な詳細の話をしたいと思います。前半で紹介した特徴や機能が VM やランタイムでどのように実装されているのか。特に、並行処理にスポットライトを当てて話したいとは思います。

最後に、個人的にホットなトピックとして実行コードの最適化についても簡単にご紹介できればと思います。Erlang は比較的「遅い」と言われる言語ですが、開発チームによって最近取り組まれている最適化についてご紹介します。

明らかに時間が足りないというか詰め込みすぎ感が凄いので、基礎的なところや概要的なところは適度に端折りつつ、スピーカーの独断と偏見で面白いと思うトピックについて、時間の許すかぎりお話しさせていただければと思います。

## Erlang
![Elixir_Under_Hood_JPEG_Min.006.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/ae8df8e9-66f2-b99f-88eb-31ea538520f0.jpeg)
いよいよセッションの本編です。

まずは Erlang の話をしましょう。はじめに Erlang ありきです。Erlang は、スウェーデンの通信機器メーカーであるエリクソン社によって、1980年代に開発された言語です。[^1] 電話交換機のプログラム開発のために、多くの既存言語を試したのち、自分たちの求める要件（並行性とエラーリカバリー、プロセス）を満たすために開発されました。1987 年ごろから社内で使われていたようですが、1998 年にオープンソースで公開され、実に 30 年以上の歴史を持っています。

言語の具体的な話に入る前に、採用事例について話しましょう。たぶん、もっとも身近なところでは今年2月の [Erlang&Elixir Fest 2019]([https://elixir-fest.jp](https://elixir-fest.jp/)) で発表された任天堂さんの事例じゃないでしょうか。家庭用ゲーム機 Nintendo Switch (TM) 向けに、プッシュ通知のシステムを Erlang で開発、運用しているそうです。[^2] この発表はぼくも聞いていたのですが、「1億接続に備える」というのが印象的でした。

また、同じくゲーム分野の League of Legends というオンラインゲームのチャットシステム[^3] で採用された事例や、あるいはメッセージングアプリの WhatsApp [^4] や Heroku の一部でも使われています。[^5]

```erlang
-module(listsort).

-export([by_length/1]).

by_length(Lists) ->
    qsort(Lists, fun (A, B) -> length(A) < length(B) end).

qsort([], _) -> [];
qsort([Pivot | Rest], Smaller) ->
    qsort([X || X <- Rest, Smaller(X, Pivot)], Smaller) ++
      [Pivot] ++
	qsort([Y || Y <- Rest, not Smaller(Y, Pivot)], Smaller).
```

さて、百聞は一見にしかず、ということで Erlang プログラムの例を見てみましょう。Erlang は当初、Prolog という言語をベースに開発されたので、文法の多くを Prolog 言語から借りています。[^6] パターンマッチは柔軟で便利ですし、また、クロージャやすべての値が immutable であることなど、関数型っぽい側面もあります。

![Elixir_Under_Hood_JPEG_Min.008.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/d7e7838b-7cf6-89e4-7315-381d93716a95.jpeg)
しかし、Erlang を特徴づけるもっとも重要なデザインは「プロセス」の導入でしょう。

Erlang ではすべての処理はプロセスに分離されています。Erlang プロセスは分離されたヒープ、スタック、プログラムカウンターを持つのは OS のプロセスと同じですが、Erlang のプロセスは非常に「軽量」です。プロセスの生成/破棄は高速で、非常にたくさんのプロセスを起動することができます。

![Elixir_Under_Hood_JPEG_Min.009.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/5b1b9639-60a5-e725-c3d3-467288f1fce2.jpeg)
単に Erlang シェルを起動した直後の状態でもこれだけのプロセスが起動しています（`i().` の出力）ひとつのプロセスが消費するメモリは、たとえばぼくの Macbook だと 2704 バイトでした。とても小さいですね。

プロセス間は一部の例外を除いてメモリを共有しておらず、コミュニケーションが必要な場合は「メッセージ」を使います。メッセージ、というのは Erlang のデータ型、たとえば数値や文字列、タプルなどを別のプロセスに非同期で送信することができます。

また、Erlang では複数のランタイムに分散したプロセスも透過的に扱うことができます。

これらのプロセスは同じマシンに存在するかもしれませんし、ネットワークで接続された別々のマシンに存在するかもしれません。しかし、プログラマはローカルで実行するメッセージングと全く同じ仕組みで、ローカルのプロセスから別のマシンのプロセスにメッセージを送ることができます。ここまで簡単に分散コンピューティングができるのは、一度体験してみると感動的ですらあります。

[^1]: [History of Erlang - Erlang Programming Language](https://www.erlang.org/course/history) ちなみに、同年代の他言語としては Perl や Objective-C, Eiffel といった言語があります。
[^2]: [Erlang/OTP と ejabberd を活用した Nintendo Switch(TM)向け プッシュ通知システム 「NPNS」の 開発事例 - Speaker Deck](https://speakerdeck.com/elixirfest/otp-to-ejabberd-wohuo-yong-sita-nintendo-switch-tm-xiang-ke-hutusiyutong-zhi-sisutemu-npns-false-kai-fa-shi-li)
[^3]: [How League of Legends Scaled Chat to 70 million Players - It takes Lots of minions. - High Scalability -](http://highscalability.com/blog/2014/10/13/how-league-of-legends-scaled-chat-to-70-million-players-it-t.html)
[^4]: [Why WhatsApp Only Needs 50 Engineers for Its 900M Users | WIRED](https://www.wired.com/2015/09/whatsapp-serves-900-million-users-50-engineers/)
[^5]: [Stuff Goes Bad | Heroku](https://blog.heroku.com/erlang-in-anger)
[^6]: [Erlang -- Academic and Historical Questions](http://erlang.org/faq/academic.html), 実際に、最初期の処理系は Prolog で実装されていたそうです。 [A Brief History of the BEAM Compiler – A Blog from the Erlang/OTP team – The Erlang/OTP team at Ericsson, the implementors and maintainers of Erlang/OTP.](http://blog.erlang.org/beam-compiler-history/)

## Elixir

![Elixir_Under_Hood_JPEG_Min.011.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/f527d18f-0b1e-cd5c-86cf-4551329dc9b5.jpeg)
やっと、Elixir について紹介できます。しかし、Elixir については、これ以上あまり説明することがありません。というのも、Elixir はシンタックスと一部の拡張を除くと、ほぼ Erlang そのものだからです。もうすこし詳しく説明します。

まず、Elixir は Rails の core committer でもあった José Valim（ジョゼ・ヴァリム）によって 2012 年に公開されました。一番の特徴は Erlang との相互運用性 (Interoperability) を確保しつつ、言語をより使いやすいものにし、拡張性も追加していることです。[^7]

まずはマクロを導入することで、実行前の構文木の操作ができるようになっています。これによって DSL や独自の構文を追加したり、関数ではできないことが可能になっています。

![Elixir_Under_Hood_JPEG_Min.012.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/ff73edd8-c410-2a3d-561e-2a8fbf823554.jpeg)
たとえば、Elixir のユニットテストライブラリが提供する `assert` はマクロで実装されているため、ひとつの `assert` だけでアサート対象の「式」に応じた適切な結果を出すことができます。JS では [power-assert](https://github.com/power-assert-js/power-assert) というライブラリがありますが、あれと同じです。

![Elixir_Under_Hood_JPEG_Min.013.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/c5d8c387-71fd-45ce-f3b3-b5a6213731d3.jpeg)
こちらがテストの実行結果です。assert の対象になっていた式 `1 + 2 == 4` の内容に即したエラーメッセージが出力されていることがお分かりになるでしょうか？　これはマクロが、引数に渡された「抽象構文木」を直接操作できるからこそ可能になっています。

もうひとつ。Elixir の Web フレームワーク、Phoenix でのルーティングを見てみましょう。Rails などでも一般的な DSL によって、マッチするパスのパターンとコントローラーを指定できます。

```elixir
scope "/", SampleWeb do
  pipe_through :browser
  get "/", PageController, :index
end
```

これもマクロなので、展開すると、だいたい以下のようなコードに変換されます。[^8] DSL が関数と引数のパターンマッチに展開されているのが分かると思います。このようにマクロは、boilerplate なコードの自動生成にも役立ちます。

```elixir
def __match_route__(conn, "GET", [], _) do
  conn = __pipe_through0__(conn)
  mod = SampleWeb.PageController
  params = mod.init(:index)
  mod.call(conn, params)
end
```

また、マクロによって言語のシンタックスが拡張可能になり、言語のコアのシンタックスを最小限にとどめ、残りは Elixir 自身で実装できるようにしています。もちろん、プログラマもマクロでシンタックスを拡張できます。たとえば、多くの言語では組み込みの、[if もマクロで実装](https://github.com/elixir-lang/elixir/blob/v1.9.1/lib/elixir/lib/kernel.ex#L3085)されています。

```elixir
defmacro if(condition, clauses) do
  build_if(condition, clauses)
end

defp build_if(condition, do: do_clause) do
  build_if(condition, do: do_clause, else: nil)
end

defp build_if(condition, do: do_clause, else: else_clause) do
  optimize_boolean(
    quote do
      case unquote(condition) do
        x when :"Elixir.Kernel".in(x, [false, nil]) -> unquote(else_clause)
        _ -> unquote(do_clause)
      end
    end
  )
end

defp build_if(_condition, _arguments) do
  raise ArgumentError,
        "invalid or duplicate keys for if, only \"do\" and an optional \"else\" are permitted"
end
```

言語のコアのシンタックスを最小限にするという思想は、Elixir のシンタックスの進化の過程にも現れています。マクロを提供するということは構文木をプログラム可能にする、ということですから、構文は Elixir 組み込みのデータ構造で表現できる必要がありました。

最初期のバージョンはこんな感じでした。

```elixir
defmodule(Hello, do: (
  def(calculate(a, b, c), do: (
    =(temp, *(a, b))
    +(temp, c)
  ))
))
```

二項演算子が追加されました。

```elixir
defmodule(Hello, do: (
  def(calculate(a, b, c), do: (
    temp = a * b
    temp + c
  ))
))
```

次に括弧を少なくして、

```elixir
defmodule Hello, do: (
  def calculate(a, b, c), do: (
    temp = a * b
    temp + c
  )
)
```

`do..end` が追加されて現在の形になりました。

```elixir
defmodule Hello do
  def calculate(a, b, c) do
    temp = a * b
    temp + c
  end
end
```

この他にも、ポリモーフィズムを実現するための仕組みとして Protocol というものも導入されていたり、注意深く設計された標準ライブラリも魅力的ですが、逆に言うと、Erlang に足されている要素はこれだけだ、とも言えます。

![Elixir_Under_Hood_JPEG_Min.017.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/116064e8-8a15-040b-680b-d9f2339943e5.jpeg)
これ以外は Erlang なので、プログラム実行時のランタイム・スタックも Erlang と Elixir でほとんど変わりません（実行時スタックの図）。左が Erlang で、右が Elixir です。<sup>2</sup> Elixir の標準ライブラリが乗っかってる以外は同じですね。

[^7]: [Elixir Design Goals - Elixir](https://elixir-lang.org/blog/2013/08/08/elixir-design-goals/)
[^8]: コンパイル結果の .beam ファイルをディスアセンブルすると、割と読みやすい Erlang コードが取得できます [Disassemble Elixir code - Learn Elixir - Medium](https://medium.com/learn-elixir/disassemble-elixir-code-1bca5fe15dd1)

## 落ちないシステム

さて、そろそろ「落ちないシステム」の話をしましょう。「落ちないシステム」とは何でしょうか？

![Elixir_Under_Hood_JPEG_Min.019.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/eeeaaabc-b293-fd43-3624-660b4351476d.jpeg)
「100% バグがないシステムを作れば落ちない！」...もちろん、そんなわけはないですよね？

そもそも、「100% バグがないシステム」が非現実的ですし、実運用しているシステムでは大なり小なり何かしらの障害が起こるものです。特に多いのが一時的なネットワークエラーや外部システムのエラーでしょう。現実世界ではエラーは避けようがありません。

![Elixir_Under_Hood_JPEG_Min.020.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/bae96be0-e142-6c72-80af-0c3211947577.jpeg)
では、落ちないシステムとはなんでしょうか？　それはエラーが起こっても回復できるシステム、いつまでも稼働しつづけるシステムです。ここでも、Erlang のプロセスが活きてきます。まず、Erlang ではプロセス同士はメモリ空間からして完全に独立しているため、あるプロセスで起こったエラーが他のプロセスに影響することがありません。エラーは局所的に分離されています。[^9]

また、プロセスが終了したときに他のプロセスが検知する仕組みが用意されており、「プロセスが異常終了したときにエラー処理を行うプロセス」という仕組みを構築することができます。

たとえば、あるプロセスが異常終了したときに仕事を引き継ぐための別のプロセスを起動したり、単にそのプロセスを再起動したりする監視プロセスを作ることができます。こうした監視プロセスは Supervisor (スーパーバイザー) と呼ばれます。Erlang と一緒に配布されている OTP というフレームワークでは、Supervisor を使ってプロセスの監視ツリーを簡単に構築するためのライブラリが用意されています。分散処理の仕組みを使って、Supervisor プロセスと Worker プロセスを別々のマシンに配置することも可能です。

概念的には、これが Erlang の「落ちないシステムの秘密」になります。

[^9]: Erlang の作者 Joe Armstrong による講演 [Systems that Run Forever Self-heal and Scale](https://www.infoq.com/presentations/self-heal-scalable-system/)

## BEAM Virtual Machine (6min)

さて、ここからは Erlang の Virtual Machine、通称 BEAM とランタイムの話をしながら、プログラムが実際にどのように実行されるのか見ていきたいと思います。ちなみに BEAM やランタイムは C 言語で実装されているため、これ以降は随所に C のコードが出てきます。C 言語なんて知らないよ、という方は雰囲気だけでも感じていただければと思います。

Erlang や Elixir のソースコードは、コンパイラによって BEAM で実行可能な形式に変換されます。ソースコードはプリプロセッサや Parse Transform という変換を経て、抽象構文木という木構造のデータに変換されます。そのあと、いくつかの中間表現を経て、BEAM で実行可能な形式 (BEAM Code) に変換されます。

たとえば、以下のようなモジュールをコンパイルすると

```erlang
-module(add).
-export([add/2]).

add(A,B) -> A + B.
```

関数 `add` の定義は以下のような BEAM Code に変換されます。

```erlang
{function, add, 2, 2}.
  {label,1}.
    {line,[{location,"sample.erl",4}]}.
    {func_info,{atom,add},{atom,add},2}.
  {label,2}.
    {line,[{location,"sample.erl",4}]}.
    {gc_bif,'+',{f,0},2,[{x,0},{x,1}],{x,0}}.
    return.
```

インデントされていますが、これは直列的な命令列になっています。BEAM は、こうした命令列を順番に実行していくことでプログラムを実行します。

BEAM の他の特徴としては以下の通りです。

- BEAM (Bogumil’s/Björn’s Abstract Machine)
- **garbage collecting**
- **reduction counting**
- non-preemptive
- Interpreter loop: directly threaded
- register machine

このうち、太字のものについては、このあと、折を見て説明していきます。

さて、次に、BEAM の中で Erlang のデータがどのように扱われているか簡単に見ていきましょう。まず、Erlang のすべての値、たとえば数値、真偽値、プロセスなどはすべて、**Term** という固定長のデータで表現されています。

Term が具体的に何か、というとマシンのワード長の整数です。[^10] 一般的に、ポインタと同じ長さ、32bit マシンなら 4 バイト整数、64 bit マシンなら 8 バイト整数です。

```c
typedef unsigned long Eterm;
```

言語処理系の実装に不慣れな方は奇妙に思われるかもしれませんが、この整数をそのまま使うわけではなく、整数のビット列に情報を詰め込んで使います。特に、ビット列の一部がタグとして使われており、ここの値を見れば、その Term がどのデータ型かわかるようになっています。[^11]

たとえば、簡単な例として小さな整数はタグの 4 ビットを `1111` にし、残りのビットがそのまま整数の値になります。もちろん、多くのデータはひとつのワードに収まらないので、その場合はヒープ領域に実際のデータを確保して、Term はその領域へのポインタになります。

ここまでは他の言語の Virtual Machine とあまり変わりません。では、そろそろ、Erlang をもっとも特徴づけている「プロセス」を見ていきます。

プロセスも BEAM から見れば、データ型のひとつ、C 言語的にはプログラムの実行中に必要になる情報をまとめた構造体になります。[^12]

```c
struct process {
    ErtsPTabElementCommon common; /* *Need* to be first in struct */
    Eterm* htop;		/* Heap top */
    Eterm* stop;		/* Stack top */
    Eterm* heap;		/* Heap start */
    Eterm* hend;		/* Heap end */
...
```

この構造体ではさまざまな情報が管理されていますが、大雑把にいうと以下の4つです。

- ヒープ領域
- スタック領域
- メールボックス
- PCB

PCB 以外は動的に確保されますが、PCB は構造体に埋め込まれた固定長データで、プロセスを管理するための情報を格納しています。プロセスの ID やのちほどスケジューリングのときにお話しする reduction もここに格納されています。メールボックスは、前半でお話ししたプロセス間のメッセージ・パッシングで、メッセージが格納されるキューになります。

ただし、これは非常に単純化したものです。実際には、他にもいくつかのメモリ領域がプロセス内には存在します。たとえば、Erlang の GC は世代別ガベージ・コレクタなので、古い世代のオブジェクトを移動するための「Old Heap」がありますし、GC を遅延させたり、ロックを取得できなかったときのメッセージの一時的な退避場所として Heap Fragments という領域があったりします。[^13]

Erlang でプロセスを作成する、ということは、これらの必要なメモリ領域を確保したのちに構造体を初期化し、それを実行キューに追加するだけです。Erlang のプロセスは気軽に作れる、というのも頷けますね。

![Elixir_Under_Hood_JPEG_Min.028.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/a29844be-a026-b7be-13c8-a6754564b22c.jpeg)
さて、実行キューの話が出ましたので、次はプロセスのスケジューリングについて話します。せっかく作ったプロセスが「いつ」実行されるか、は重要ですよね。これをコントロールしているのがスケジューラーです。

通常、CPU コアと同じ数のスケジューラーが存在し、それぞれが実行キューを持ち、個別の OS スレッドで実行されます。できるだけ均等な負荷がかかるように、ランタイムが頑張ってロードバランシングしています。

さて、スケジューラーは実行キューにあるプロセスを素早く「すこしずつ」実行することで、それぞれのプロセスが並行に動くようにします。このとき「すこしずつ」の長さを決めるのが、さきほどプロセスの PCB に格納されていた **reduction** というカウンターです。

reduction は関数呼び出しで増えていき、最大 reduction 数を超えたらプロセスが切り替わります。ちなみに、Erlang にはループがなく、関数の再帰呼び出しをするしかないので、Erlang レベルで何かしようとするとすぐに reduction は最大数に達してコンテキストスイッチが起こります。

このようにして、Erlang の並行プログラミングは実現されています。スケジューラーがこのような構成になるまではいくつかの変遷があったり、Dirty Scheduler という怖い名前のスケジューラーもあるので、興味のある方は調べてみてください。[^14]

![Elixir_Under_Hood_JPEG_Min.029.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/993c5535-843c-179c-ce5f-e17d43fe7fe2.jpeg)
さて、BEAM の最後の締めくくりとして、ガベージ・コレクションの話をしましょう。とはいえ、GC も詳しく話しているとキリがないので、軽く触りだけ紹介します。

まず、アルゴリズムとしては世代別コピー GC です。[^15] これもすごーくざっくり説明すると、ヒープ領域が足りなくなったら、オブジェクトのうち使われてるものだけを別のヒープ領域にコピーして、古いヒープ領域は破棄することでメモリを空ける GC です。コピーするのでコピーGCですね。

このとき、すべてのオブジェクトをスキャンするのではなく、新しく作られたオブジェクトのみスキャンし、それでも生き残ったオブジェクトは「旧世代」として別のメモリ領域 Old Heap に移動してしまうのが世代別GCです。[^16]

アルゴリズムとしては特に目新しいものではないと思います。ただ、Erlang らしい特徴としてはふたつ。まず、世代別GCは余分にメモリを消費してGCの性能を上げる手法ですが、Erlang ではすべての値が Immutable なので、短命なオブジェクトが比較的多く、Old Heap をあまり圧迫しません。

また、プロセスごとにヒープ領域が分かれており、GC のあいだはそのプロセスのみが停止するのと、短命なプロセスであることが多いので、GC によってシステムが停止することがありません。GC もプロセスで分離されてるわけです。

[^10]: https://github.com/erlang/otp/blob/6f0ad85853f4ee441fdbddb446a0b2cf79bee082/erts/emulator/beam/sys.h#L352
[^11]: [A staged tag scheme for Erlang](https://www.it.uu.se/research/publications/reports/2000-029/2000-029-nc.pdf)
[^12]: https://github.com/erlang/otp/blob/6f0ad85853f4ee441fdbddb446a0b2cf79bee082/erts/emulator/beam/erl_process.h#L938
[^13]: [Processes - The Erlang Runtime System](https://blog.stenmans.org/theBeamBook/#CH-Processes)
[^14]: [Erlang Scheduler Details and Why It Matters - Hamidreza Soleimani's Blog](https://hamidreza-s.github.io/erlang/scheduling/real-time/preemptive/migration/2016/02/09/erlang-scheduler-details.html)
[^15]: 大きなバイナリデータはまた扱いが異なります。[Erlang -- Constructing and Matching Binaries](http://erlang.org/doc/efficiency_guide/binaryhandling.html)
[^16]: [Erlang Garbage Collector | Erlang Solution blog](https://www.erlang-solutions.com/blog/erlang-garbage-collector.html)

## Optimization

いよいよ終盤です。最後に、Erlang の最適化について最近の動向含めて紹介したいと思います。

![Elixir_Under_Hood_JPEG_Min.031.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/9d6372dc-4ee8-c38f-a45a-de7c5c7abb12.jpeg)
まず、古くからあるものとして HiPE、High Permance Erlang という、BEAM Code を OS のネイティブ・コードにコンパイルするプロジェクトがあり、Erlang と一緒に配布されています。[^17] LLVM のバックエンドも持っていたりするのですが、残念ながら最新のバージョンでは BEAM に追加された新しい命令列に対応できていません。

![Elixir_Under_Hood_JPEG_Min.032.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/80f0ec15-d698-93c8-3730-cf09773fd226.jpeg)
次に、少なくとも 2014 年から開発が進められている BEAMJIT というプロジェクトがあります。[^18] これはその名の通り、BEAM に JIT コンパイルを追加する試みです。JIT は Java などで有名ですが、一応説明すると、Virtual Machine 用のコードを実行時に OS のネイティブ・コードにコンパイルする技術です。Just-In-Time でコンパイルするから JIT ですね。

事前にすべてのプログラムをネイティブ・コードに変換する AOT, Ahead-of-Time なコンパイルと比べて「実行時にしか分からない情報」特に「頻繁に実行されるコードのみをコンパイル」することができるアドバンテージがあります。

このとき、頻繁に実行されるコードを判定するための戦略として、BEAMJIT では Tracing JIT という手法を使っています。関数ボディの最初など特定のポイントに実行回数を記録する命令を挿入し「頻繁に実行されるコードパス」を見極めます。ネイティブ・コードの生成には LLVM を使っているそうです。

![Elixir_Under_Hood_JPEG_Min.033.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/44940871-0f35-f4cd-352a-c7a6e1193949.jpeg)
さて、最後に BEAM 自身の最適化についても話したいと思います。実は、BEAM でも古くからいくつかの最適化は行われてきました。たとえば、BEAM Code をロードするときに、いくつかの命令列をまとめてひとつの命令列に置き換えたり、決して実行されないコードの除去などをしていました。

さらに、最近のバージョンでは BEAM のインタプリタが、BEAMJIT の開発経験で得られた知見をもとに大幅に書き換えられました。これによって BEAM 命令のサイズが 20% ほど削減され、CPU のキャッシュに収まりやすくなったため結果的に実行速度も上がりました。

![Elixir_Under_Hood_JPEG_Min.034.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/682f419f-e971-a63a-18d3-e440a97f0a72.jpeg)
また、コンパイル時の新しい中間表現として Static Single Assignment (SSA) フォーマットの中間表現が追加されました。SSA が何か、は例を見てもらうのが分かりやすいと思います。

```
@ssa_bool:6 = bif:is_tuple _0
```

これは右辺の結果を左辺に代入ですね。`_0` は実行中の関数に渡された引数、`bif:is_tuple` はタプルかどうかを判定する関数です。左辺は変数っぽいですが、ちょっと変わってますね。末尾に `:6` という添字がついています。SSA では、すべての変数は一度だけ代入されます。そして、変数の添字がそれぞれの代入をユニークにしています。このあと、次のような命令があったとします。

```
br @ssa_bool:6, label 7, label 3
```

これは条件つきジャンプで、`@ssa_bool:6` 変数が true なら `label 7`, そうでなければ `label 3` にジャンプします。

実はこのように、変数への再代入がなくなることで、多くの最適化が簡単になります。実際に、SSA の導入によっていくつかの最適化が追加されたり、既存の最適化が改良されたりしました。[^19]

[^17]: [Erlang -- HiPE](http://erlang.org/doc/man/HiPE_app.html)
[^18]: [Tracing JIT Compiler - Lukas Larsson - YouTube](https://www.youtube.com/watch?v=PtgD5WRzcy4)
[^19]: [Introduction to SSA – A Blog from the Erlang/OTP team – The Erlang/OTP team at Ericsson, the implementors and maintainers of Erlang/OTP.](http://blog.erlang.org/introducing-ssa/)

## Conclusion

![Elixir_Under_Hood.038.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/461f2c26-3a5a-817f-243b-fca0e4d05cd4.jpeg)
さて、駆け足でしたが、これでおしまいです。このセッションでは、Erlang と Elixir のデザインと特徴についてお話しし、どのようにして Erlang の並行性が実現されているのか、処理系の観点からお話ししました。また、最適化について最近の動向を含めて簡単にご紹介させていただきました。

今日来られたみなさんが少しでも、Erlang と Elixir というプログラミング言語や言語処理系の内部について興味をもっていただければ幸いです。ご静聴ありがとうございました。

![Elixir_Under_Hood_JPEG_Min.039.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/2181c9b5-bead-6518-715f-b70e72729be1.jpeg)

## Q&A

今まで何度か登壇した中で一番多くの質問をもらったのですが、その中で「お薦めの本」の質問があったのでリンクを張っておきます。大変申し訳ないのですが、いずれも Erlang の本です。

Elixir についてはあまり本を読んでないのですが、本家の[チュートリアル](https://elixir-lang.org/getting-started/introduction.html)と[標準ライブラリのドキュメント](https://elixir-lang.org/docs.html)が充実しているので、まずはそちらを読むのがいいと思います。

### プログラミング Erlang  ([Amazon](https://www.amazon.co.jp/dp/B079YZC22H/))

![2_プログラミングErlang.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/573eb227-f626-4ce5-7f55-9621be302f9c.jpeg)
Erlang の作者 Joe Armstrong による入門書です。Erlang を触ったことがない、興味がある、という人向けに設計思想から学べるオーソドックスなプログラミング本です。

### すごいErlangゆかいに学ぼう！ ([Amazon](https://www.amazon.co.jp/dp/B00MLUGZIS/))

![2_すごいErlangゆかいに学ぼう!.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/67e67a1d-9119-32a5-f258-0d78e569f7c3.jpeg)
**可愛くないですか！？**

イラストとユーモアに溢れた、でも、その内容は Erlang の基礎からはじめて、プロセス監視、OTP、リリース、Dyalizer と盛りだくさん。およそ、プロダクションレベルのコードを開発するために必要な知識がすべて詰め込まれています。書籍版は残念ながら白黒印刷でイラストの魅力が半減しているので、電子書籍がお薦めです。少しバージョンが古いですが、[オンライン版](https://learnyousomeerlang.com/content)（[日本語](https://www.ymotongpoo.com/works/lyse-ja/index.html)）もあるので中身を知りたい人はどうぞ。

ちなみに、[すごい Haskell](https://www.amazon.co.jp/dp/B009RO80XY/) もあります。こっちのイラストも良い。

### Erlang in Anger ([Web]([https://www.erlang-in-anger.com](https://www.erlang-in-anger.com/)))

![2_Erlang_in_Anger.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/18990/8da372de-2750-3f60-ac91-c394b02aefcc.jpeg)
「すごい Erlang」がプロダクションコードの開発に必要な本だとすれば、こちらはプロダクションの運用には欠かせない本です。Erlang/OTPで構築したシステムの運用や調査に役立つ情報が網羅されています。最初に読む本ではないのですが、とりあえず手元に置いて目次だけでも把握しておけば、いざというときに役立ちます。

Heroku で Erlang をどう使ってるかの話もちょっとあるので、そのへんに興味がある人もどうぞ