並行並列言語Haskellの基本と特徴

並列並行言語Haskell

syocy氏：小山内と申します。『並列並行言語Haskell』ということで発表していきます。

まず、このスライドおよびソースコードはGitHubで管理しているので、そちらをご参照ください。PDFはGitHub Releasesの中に置いてあります。あと、スライド中のほとんどのソースコードはDoctestでテストされています。

このスライドの参考書というか種本みたいなものなんですけど、『Haskellによる並列・並行プログラミング』というすばらしい本があって。これはGHCの主要開発者のSimon Marlowさん自身が並列・並行Haskellの解説をした本になってます。

Haskellによる並列・並行プログラミング

単にHaskellのためだけのものというよりは並列・並行のさまざまなアイデアが紹介されていて、Haskellユーザー以外の方にもおすすめできる本なので、ぜひ（読んでください）って感じです。

並列・並行をやるモチベーション

本題です。まずプロセッサ性能トレンド。こちらの図はKarl Ruppさんという方がクリエイティブコモンズ（CC）で公開している最近のプロセッサ性能のトレンドなんですけど。

注目していただきたいのは青い丸い点です。Single-Thread Performanceというやつと、もう1つは黒い四角い1番下にある点、Number of Logical Coresというやつに注目してもらいたいです。

これを見るとシングルスレッド性能はもうだいぶ伸び悩んできている。その一方で論理コア数は順調に増えてきている。つまり現代のプロセッサの性能を引き出すにはコア数を活かすプログラミングが必要となってくるということです。

トレンドとか話しましたけどいまいち実感ないと思っていて、より身近な例で言うと10以上の物理コアを持つCPUがご家庭でも手に入れられるくらいのお値段になっております。

AMDのCPUだけ挙げてるのは別にIntelが嫌いってわけじゃないんですけど。

（会場笑）

こういうときにAMDのCPUとIntelのCPU並べると「その比べ方は適当ではない」みたいなことを言われると思うので、AMDのやつだけ置いています。

（会場笑）

まず1番上のRyzen TR 2990WXってやつはコアが32もあって、論理コアは64スレッドもあって、お値段が1799ドル。まあ買えなくもないかなくらいのお値段。

1番下のRyzen TR 1920Xというのは12コア24スレッドで400ドルくらい。これだったら普通に買えるくらいですね。

あと、適当にメニーコアという言葉を使っちゃいましたけど、けっこう定義があいまいな言葉なんです。100以上って言う人もいれば1,000以上って言う人もいるんですけど、とりあえずここでは物理10コア以上を「メニーコア」と呼ぶことにしておきます。7

並列並行言語の台頭。実際、本当にそうかって話なんですが、最近話題の言語って言語のコア機能的な部分に「並列並行機能」を備えているものが多いです。並列並行の重要性が世間的にも意識され始めたんだろうと言えます。

まずGo言語なんですけど、goroutineというコルーチンの1種みたいなものを持っています。ErlangとElixir、これは仮想マシンが軽量プロセスという実行単位を持っています。

Rust、Rustの特徴としてメモリー安全性ということが非常に強調されているんですけれども。Rustはそのメモリー安全性が並行性にも及ぶということを強調しています。Haskellはどうでしょうか？　

並列・並行とHaskell

並列・並行とHaskell。ここではHaskellのデファクトスタンダードのコンパイラであるGHCをイコールHaskellとして呼んでいきます。

Haskellは古くから並列・並行のことを考えて設計されてきた言語です。1997年にはライブラリとしてではなくて実行時システムとして並行性をサポートするということが決定されました。

2004年には実行時システムを共有メモリのマルチプロセッサ上で並列に動作させることが決定されました。共有メモリのマルチプロセッサというのはマルチコアCPUのこととイコールでいいと思います。

2009年の論文の『Runtime support for multicore Haskell』というのがあるんですけど、これくらいの時期にはもう、Haskellの並列並行機能は実用的な段階になっていたということですね。

実際Haskellは並列・並行のためのよい性質をたくさん持っています。Haskellは純粋なコードと副作用、入出力などですけどそれらを含むコードを分離できます。

その関係で並列性は決定的になります。決定的というのは、プログラムを動作させたときの並列度とか、実行環境が変わろうともその処理の結果は変わらないということです。

実行時システムが軽量スレッドというものをサポートしています。よく並行性の実現にはスレッドという概念が用いられるんですけれども、あたかも普通のOSのスレッドのように使えるものが普通のスレッドよりもはるかに軽く動作します。これはもうHaskell使うっきゃない！　ということですね。

並列・平行・分散のちがい

さて、今まで断りなく「並列・並行」という言葉を言ってきましたけれども、あと似た言葉に分散というのもありますが。

これらに違いはあるのか？　というのをまずいきたいと思います。

「並列と並行」なんですが、「並列」は英語で言うとparallelですかね。主眼としては、「同時に走らせることで処理を高速化したい」というときに、この言葉が使われます。

例えば「n並列」「並列ダウンロード」「GPU並列計算」とかいう言葉がよく使われると思います。これを「n『並行』」「『並行』ダウンロード」「GPU『並行』計算」というふうにはおそらく言わないかと思います。

「並行」は英単語ではconcurrentのことで、そもそも「同時にしたい」もしくは「同時であるかのように見せたい」処理があるときにこの言葉が使われます。

この同時性というのは擬似的でもよくて「本当に同時に動いているか」ということではないところに注意が必要です。

この並行性の表現にはよくスレッドの概念が用いられます。ここはちょっとややこしいところなんですけど、スレッドが本当に同時に動く実装になっている場合は並列のためにスレッドを使うということもあります。

「分散」、分散は並列・並行とはまた異なる特徴を持っています。英語ではdistributedですね。複数のマシンを使う処理のことを一般に分散と言います。

違う点としては、通信時間がかかるために共有メモリという単位を持たない、想定しないことが多いです。また複数のマシンで動いている処理ですけれども、一部のマシンだけダウンするみたいなことも考えなければいけません。

さらにマシンごとに性質が異なることが考えられます。例えばこのマシンはユーザーに近いとか、このマシンはデータベースに近いとか。そういう性質の違いがあることが考えられます。このスライドでは分散にはあまり触れないことになります。

並列・並行のコード

実際にどう書けばHaskellで並列になるんだよ？　という話をしていくんですが、「並列Haskell」というのはHaskell特有の性質を理解していないと把握しづらいところがあるので、まずは並行Haskellの軽量スレッドのやつから見ていきます。

スレッドという概念はわりとみなさんご存じかなと思います。こちらのコードなんですけど、helloworldという関数を定義しています。

何をするかと言うと、helloworldという文字を出力したあとに軽量スレッドで！（びっくり）という文字を100個出すという。こういうバカみたいなことをしています。

5行目がスレッド100個作っているもので、6行目と7行目が軽量スレッドの処理の中身です。

6行目が100マイクロセカンドスリープをして、7行目で！（びっくり）というのを出していると。

8行目が普通にhelloworldをメインスレッドで出しているところで、9行目がすべてのスレッドの終了を待つという処理をやっています。

10行目で改行して終わりみたいなプログラムです。

軽量スレッドを作る関数はasyncという関数があって、これはasyncパッケージに入っています。これは実は標準関数ではないんですけれども、標準関数forkIOの薄いラッパーになっています。

標準関数のforkIOはスレッドIDが漏洩する的な問題があってasyncのほうがより安全で便利になっていますので利用を推奨しています。

wait関数というのでスレッドの終了を待つことができます。cancel関数で軽量スレッドを外部からkillすることもできます。

どんな動きになるかと言うと、軽量スレッドに非同期例外が飛んでくるみたいなかたちになります。非同期例外というトピックは非常に難しいのでここではあまり触れません。

スレッド間通信

先ほどのコードでは単に文字を出すというだけのことだったんですけれども、実際の並行プログラムではスレッド間通信が必要だと思います。Haskellのスレッド間通信にはおおまかに2つの方法があります。

1つはMVarというのを使う方法。MVarというのは非常にシンプルな同期変数でして、アクセスの公平性が保証されているのが特徴です。

ここで言う「公平性」というのは、複数の軽量スレッドがMvarに参照を持つわけですが、その軽量スレッドによってアクセス頻度に偏りがないということを「アクセスの公平性」と呼んでいます。

このMVar自体は非常にシンプルなデータ構造なんですけど、それを使ったチャネルやセマフォなどの実装がありますのでそちらを使うこともできます。

MVarともう1つ、STM。Software Transactional Memoryという方法でもスレッド間通信はできます。これは共有状態の読み書きにトランザクションの概念を導入するもので、トランザクションというのは割り込まれない一連の読み書きブロックみたいな意味です。

これのすごいところは、途中で処理がブロックされたり失敗したりしたら、トランザクション全体、今までやってきたことをなかったことにしてリトライすることができるというのが特徴です。

これは単に1つの変数に対してだけじゃなくて、複数の変数が絡む処理でもトランザクションは作れます。そのため複雑な共有状態の処理をミスなく記述しやすいということになります。

STMもMVarと同じくいろんな実装に使われていて、チャネルとかキューとか、長さ制限付きのキューとか、セマフォなどの実装もあります。

こちらはSTMを使って共有カウンターを操作する例です。

5行目でSTMのTVarという種類の変数を作っていて、0で値を初期化していると。また6行目でスレッドを1000個作って、7行目と8行目でその共有カウンターをインプリメントしています。

9行目ですべてのスレッドの終了を待って、10行目で最終的なカウンターの値を呼び出して出力するということをやっています。

このatomicallyという関数がありますが、7行目と10行目ですね。atomicallyという関数がトランザクションを作る関数です。atomicallyの下にあるブロックが1つのトランザクションになるという感じです。

先ほども言ったようにここでは単にCounterという1つの変数しか見てませんけれども、複数のSTM変数からの処理を1つのatomicallyの下に書くことができます。

A Tour of Go in Haskell

並行Haskellのまとめですけど、Haskellは実行時システムが軽量スレッドをサポートしています。

軽量スレッドの構文みたいなのもけっこう軽くて、asyncという関数を呼ぶだけで軽量スレッドができます。またSTMによって複雑な共有状態の処理が記述できるという特徴もあります。

ちょっとここで宣伝なんですけど、去年くらいに『A Tour of Go in Haskell』というものを作りました。これはGo言語の公式チュートリアルの『A Tour of Go』というのがあって、その並行性の章をHaskellで書いてみたという内容になります。

結論としては、並行構文の軽さはGoとHaskellで同じくらいで、STMがある分Haskellのほうがうまく書ける例もあります。もしご興味があれば見ていただければと思います。

実は英語版も一緒に作ったんですけど、英語版を公開したら添削してくれて、怒涛の勢いでプルリクエストが飛んできて、ありがたかったですね。（笑）。

評価順序を改変する

並行Haskellが終わったので、並列Haskellのほうにいきます。よく「遅延評価」という言葉を聞いたことがあると思うんですけど、簡単に言うとHaskellは必要になってから式を順番に評価していく評価方法を取っています。

たとえ並列オプションを有効にしたコンパイラで並列オプションを有効にしたとしてもデフォルトでガベージコレクション以外が自動的に並列化されることはありません。

しかし、並列に評価してほしい箇所を指示するということができます。下のコードを見ていただきたいんですが、これはmutualPowという関数を定義していて、何をやるかと言うと「Intの値を2つ受け取って相互に累乗を取って、その2つの累乗の結果を返す」みたいなコードになっています。

このz1とz2を並列に計算したいというときにどうするか？　はい、こうします。

6行目だけが変わっています。z1par z2 pseq、あとは (z1, z2) 、タプルという感じです。par関数というのが第一引数の評価を並列化する関数で、pseq関数というのがここではここで直列化するという指示になります。

関数をバッククオートで囲っている記法をちょっと見慣れない方もいるかと思うんですけど、Haskellの場合関数をバッククオートで囲うと、二引数の関数がなんだろう二項演算子みたいな扱いをされます。

なので、ここでz1とz2が並列化されて両方が終わったタイミングで、両方が終わったらpseqってことで直列化されて、z1z2が返ってくるという感じです。

しかし、典型的なデータ構造にいちいち並列化を指示していくのはけっこう面倒です。なので評価戦略というかたちで並列化の指示だけ処理の本体から分離することができます。

下のコードを見ていただければわかると思うんですけれども。mutualPowStという関数を定義しています。Stはストラテジーの意味ですね。

1番最初に作ったmutualPowという関数をそのまま使って、その次の5行目、using (parTuple2 rseq rseq)というところで評価戦略を指示しています。usingというのが評価戦略を適応するみたいな関数で、parTuple2というのがタプルの評価を並列化するという評価戦略になります。

並列Haskellのまとめです。

Haskellは式の評価方法を指示することで並列を実現できます。評価方法の指示は評価戦略というかたちで処理の本体から分離することができます。

より高レイヤーのツール

さてここまでHaskellのプリミティブな並列・並行機能、軽量スレッドと評価戦略を見てきました。ここからはより高レイヤーの並列・並行ツールを簡単に紹介していきます。

まず自動的な並列化。Par モナドというのがあって、データフロー並列とパイプライン並列というのがこれによってできるようになります。

データフロー並列というのはデータの流れのグラフみたいなのをDSL的に書くと分岐する点は並列にできるわけなので、そこを勝手に並列化するみたいな処理ができます。

パイプライン並列はシェルのパイプラインみたいな。順々に処理をしていくパイプラインを作ると各段の処理を並列化するということをします。

またHaxlというのがあって、これはデータソースへのクエリを自動的に並列化するライブラリになっています。これはFacebookのシグマというスパムフィルタがFacebook社内にあるらしいんですけど、それで使われているということらしいです。

行列計算の並列化。repaというのは行列計算について自動並列の一種であるデータ並列というのを導入します。行列の掛け算ってここが並列にできるよというのが決まったようなものなので、ここを並列化するというわけですね。

似たようなものとしてaccelerateというのもあります。これも行列計算の並列化をサポートするんですが、repaと違ってできるのはHaskellコードじゃなくてHaskell以外のコード生成をするみたいなパッケージになっています。例えばGPUとか、LLVM IRのコードを生成できます。

分散プログラミング

分散プログラミングについて。今まで並列・並行の話をしてきましたが、分散プログラミングをするためのフレームワームもあります。distributed-processあるいはCloud Haskellと呼ばれるものがあります。

これはいまいち関係がわからないんですけど、厳密に言うとCloud Haskellプロジェクトの下で開発されているdistributed-processフレームワークみたいになるっぽいです。

これはHaskellに分散プログラミングを導入するフレームワークです。実行モデルは軽量スレッドではなくて、ErlangとかElixirの軽量プロセスに近い感じの実行モデルになります。これのすごい点としては、とある暗号通貨の実装に使われているらしいです。

今までいろいろ並列化するためのものを紹介してきましたが、もちろんプロファイリングすることもできます。

ThreadScopeというプロファイラツールがありまして、これはHaskellの実行時システムのログを可視化してくれるツールになります。各OS向けにバイナリ配布されているので非常に導入しやすいです。

この下の画像はThreadScopeで自作の適当な並列処理を表示してみたものなんですけど、横軸が時間軸で縦に並んでいるのがそれぞれCPUコアみたいな単位です。

最初はそれぞれのスレッドがあまり動いてないというか、1番上のスレッドしか動いてないんですけど。最後に全部のスレッドが動いて集計処理をするみたいなプログラムになっています。このオレンジのラインはガベージコレクションの実行です。緑色のやつが実際の処理が動いているよということです。

まとめです。

CPUの性能を引き出すには並列・並行が必要になってくる時代であろうと思います。現在のHaskellには並列・並行が得意とされる言語と同等以上の並列・並行の道具がそろっているよということです。

Haskellの並列・並行関連のニュース

一応、時間が余ったとき用に補遺を用意してきたんですけど。最近のHaskellの並列・並行関連のニュースを軽く説明していきたいと思います。そんなにニュースってほど新しくもないんですけど。

最初に1番上のやつ、ApplicativeDoというのがGHC8.0で追加されました。今までDo記法というのはモナドにしか使えなかったんですけど、それをApplicativeにも使えるようにしようというものです。

それ自体は並列に関係しているわけではないんですけど、Applicativeの中には自動的に並列にできるようなものがあるので、そういう並列なものが書きやすくなるというメリットがあります。先ほど軽く紹介したFacebookのHaxlというやつではApplicativeDoが使われているらしいです。

2番目、Facebookの話が続くんですけれども、今Facebookには、最初に紹介した本の著者のSimon Marlowさんがいるらしくて。そのへんの成果としてqnオプションというのがGHC8.2で追加されました。

これはガベージコレクターの並列性を処理の本体に並列性とは別に表現できるようにするためのオプションです。環境によっては処理本体の並列性よりガベージコレクションの並列性を下げるほうがパフォーマンスが出るみたいなことがあって、こういうオプションが追加されました。

3番目がGHCのNUMAサポート。これもGHC8.2ですね。最近のCPUってマルチコアになってきていますけど、その中でもとくにたくさんコアがあるGPUってコアへのアクセス速度というかアクセスレイテンシーがコアによって異なるみたいなアーキテクチャになっていることがあります。NUMAというのはそういうアーキテクチャのことで、GHCは最近それをサポートしたと。

4番目、暗号通貨CardanoはCloud Haskellを使っているという話があります。これは先ほどちょっと説明したんですけど、IOHKという会社が作っている暗号通過のCardanoはCloud Haskellで実装されているらしいです。これは公式サイトにも書いてあったのでたぶん正しいと思います。

軽量スレッドの消費メモリ

これが最後かな。軽量スレッドって今までさんざん言ってきましたが、どのくらい軽いのかみたいな話をしたいと思います。

これはtakenobuさんという方が作られたスライドから引用させてもらったんですけど、TSOというデータ構造があります。これはThread State Objectの略で、これがHaskellの実行形で軽量スレッドを1つにつきTSOが1つみたいな感じで作られるオブジェクトになります。

TSOのデータの構造体はこんな感じになっていて、スタックを除くと18ワード。Haskellのデフォルト標準スタックサイズが1キロバイトからなので、つまり1キロバイトプラス18ワードから軽量スレッドが作られると。軽いよねってことですね。

つまり軽量スレッドを1,000個立ち上げたとしても1メガバイトしか本体だけでは使わないということなので、軽いよねって感じです。以上です。

（会場拍手）