Tech Sketch Bucket of Technical Chips by TIS Inc.

マルチコア時代のプログラマは関数脳になろう〜Scala・Clojure〜

Pocket

前回 の記事では、関数型プログラミングの概念とJava8による実装例を示しました。しかしJava8のリリースは来年まで延期されてしまったため、今すぐ試してみるには少しハードルが高いかもしれません。
そこで今回は、Java7のJVM上で動作する代表的な関数型プログラミング言語、 ScalaClojure を紹介します。

Scalaとは

では、 Scala から紹介しましょう。
scala.png

ScalaはJVM上で動作するプログラミング言語で、関数型の特徴とオブジェクト指向の特徴を合わせ持った、欲張りな言語です。

JVM上で動作するため、既存の膨大なJavaライブラリをそのまま流用でき、JVMのパフォーマンスチューニングノウハウを最大限活用することができます。またJavaよりも豊富な記述形式を持ちながらもJavaオブジェクトをそのまま扱え、強力な型推論を持った静的型付け言語でもあるため、定型的で冗長な記述を省略できる上にコンパイル時のチェックが強力な「Better Java」として利用することも可能です。

一方でScalaは、「不変なコレクションや再代入を禁じる変数宣言valのみ利用する」など、 参照透過性を保つための一定の紳士協定 に従っている限り、関数型プログラミング言語として振る舞うこともできます。このあたりは「関数型プログラミング」しかできない Haskell などの純粋関数型プログラミング言語とは対照的です。
それ以外にもActorによる並列処理や、暗黙の型変換による既存クラスの拡張(に見える記法)など、Scalaはとても大きな言語仕様とAPIを提供しています。

Scalaでの実装

では、 前回 Java8で実装したお題をScalaで実装してみましょう。Java8と同様、簡単に並列化できるでしょうか。

お題(再掲)

  1. ファイルシステムからテキストファイルを読み込む
  2. 形態素解析を行う
  3. 名詞・動詞・形容詞・副詞以外の単語を排除する
  4. 単語を辞書上の基本形に変換する(辞書に無い単語はそのまま)
    • 例えば「走れ」「メロス」は、「走る」「メロス」になります
  5. 単語の出現頻度を数える
  6. 出現頻度が高い順にソートして出力する

環境

CPU AMD Phenom™ II X6 1065T Processor (6コア 2.9GHz)
memory 16GB
OS Ubuntu 12.04.2 LTS (64bit) 3.5.0-36-generic
形態素解析エンジン Kuromoji 0.7.7
ビルドツール sbt 0.12.4
Java7 ORACLE Java SE 7u25 1.7.0_25-b15
Scala 2.10.2

ソースコードの公開

前回 と同様に、github の ココ で公開しています。

Scalaコード(非並列化)

並列化を指示していないScalaコードは、下記のようになります。

ソースコード(のコア部分)

完全なソースコード

前回 紹介したJava8のコードと見比べていただくとわかりますが、コアな処理部分は驚くほどJava8の関数型スタイルと同じです。一方try-catchや型宣言、コンテナクラスの宣言などが簡略化されており、Java8に比べてコード量がずいぶんと減っていることもわかります。

ビルドと実行

Scala(Java PJでも使えますが)用のビルドツール sbt を用い、以下のコマンドで単独で実行可能なjarを作ります。(具体的なPJ定義は、githubの build.sbtplugin.sbt を参照してください)

実際に実行してみると、以下のような結果が得られました。

scala_nonpar_8192.png

Java8の場合とは異なり、そのままでも何らかの処理が並列化されていることがわかります。ScalaコードをScalaコンパイラが解釈してJavaクラスを生成する際に、何らかの最適化と並列化が行われているのだと考えられます。

Scalaコード(並列化)

ではJava8と同様、Listを並列コレクション化してみます。

ソースコード(のコア部分)

完全なソースコード

Scalaの並列化も、Java8と同様、コレクションにpar関数を適用し並列コレクション化することで実現できます。
ただし(少なくとも2.10.2の)Scalaの場合、sortWith高階関数が並列コレクションには定義されていないため、sortWithを行う前に通常のシーケンシャルなコレクションに戻さなければなりません。

ビルドと実行

ビルド方法も実行方法も、非並列化バージョンと同じです。実行時にフラグを付けたりする必要はありません。

scala_par_8192.png

通常のシーケンシャルなコレクションの場合に比べ、より適切に並列化が行われていることがわかります。
並列コレクションを用いることで、シーケンシャルなコレクションの場合に比べて実処理時間(real)は1/3になり、CPUのユーザモード処理時間(user)も半減しました。

一方Java8とは異なり、シーケンシャルなListと並列Listで結果の順序が一致しています。Scalaの並列コレクションは一般的に、「並列化された個々のパーツの実行順序」は保証されないものの、結果を合成するときには順序通りに再合成されるためです。
(ただし、"副作用を伴う演算"や"結合則が成立しない演算"の場合、並列コレクション化した際に異なる結果になってしまう場合があります。詳細は Scalaのマニュアル を参照してください)

Clojureとは

次に Clojure を見てみましょう。
clojure.png

ClojureもJVM上で動作するプログラム言語です。そのためScalaと同様、既存のJava資産やチューニングノウハウを活用することができます。

ただしClojureは関数型プログラミング言語の親である LISP の流れを汲んでおり、基本的に関数型プログラミングのスタイルでしかプログラムが書けません。また関数も演算子も区別なく前置記法であり、プログラムそのものもデータも区別なく S式 と呼ばれる括弧を多用した記法で表現されます。
そのためC言語やJava、Rubyなどに慣れ親しんだプログラマにとっては、そもそもClojureプログラムを読み解くことさえも難しいのが現実でしょう。

一方、前置記法なS式で表現されるClojureの文法は極めて小さくシンプルで、(開眼したプログラマなら)プログラムの内容を直感的に正確に読み解くことができます。STMと呼ばれる並行処理制御機構を内蔵しており、またマクロ機構によって処理系が実行する前にS式を別のS式に変換することもできるため、問題領域専用の高度なDSLを容易に構築することができます(例えばWebアプリケーションフレームワークの Compojure や、リアルタイム分散処理エンジンの Twitter Storm などが有名です)。

Clojureでの実装

では、お題をClojureで実装してみます。

環境

CPU AMD Phenom™ II X6 1065T Processor (6コア 2.9GHz)
memory 16GB
OS Ubuntu 12.04.2 LTS (64bit) 3.5.0-36-generic
形態素解析エンジン Kuromoji 0.7.7
ビルドツール Leiningen 2.1.3
Java7 ORACLE Java SE 7u25 1.7.0_25-b15
Clojure 1.5.1

Clojureコード(非並列化)

並列化を指示していないClojureコードは、下記のようになります。
一つの関数で全て実装するとさすがに読みづらかったため、複数の関数に分割しています。

ソースコード(のコア部分)

完全なソースコード

S式で書かれているため読み解き難いですが、4つの関数から構成されています。

readFile [file enc]

readFileは、エンコードを指定してテキストファイルを読み込む関数です。with-openマクロでopenしたファイルハンドルに対して、line-seq関数で各行の遅延シーケンスを得ます。
(「シーケンス」とは、リスト構造を抽象化したものです。伝統的なLISPにはデータ構造として「リスト」しかありませんが、Clojureはlist/vector/map/set等のデータ構造を持ち、それらはすべて「シーケンス」として抽象化されています)

readFileは副作用を伴うファイルI/Oを行うため、そのままでは状況によって関数の結果が異なってしまいます(関数内であれば各行にアクセスできるが、関数の評価が完了しファイルハンドルがcloseした後に行にアクセスすると例外が発生する)。そのためline-seqにdoallマクロを適用して各行を全て評価してメモリ上にシーケンスとして展開することで、ファイルI/Oの副作用をreadFile関数内に閉じ込めています。

morphological [lines]

morphologicalは、引数として渡された行の形態素解析を行い、名詞、動詞、形容詞、副詞のみでフィルターした後に、各単語を、辞書にあれば基本形、なければ字句そのままに変換した単語のシーケンスを返します。

wordCount [words]

wordCountは、引数として渡された単語シーケンスを同じ単語でグループ化し、各単語の出現頻度をカウントした後に降順ソートした結果を返す関数です。

-main [file enc]

-mainはjavaコマンドから実行する場合のエントリポイントとなります。readFile関数、morphological関数、wordCount関数を組み合わせて単語数をカウントし、結果を表示します。

ビルドと実行

Clojure用のビルドツール Leiningen を用い、以下のコマンドで単独で実行可能なjarを作ります。(具体的なPJ定義は、githubの project.clj を参照してください)

実際に実行してみると、以下のような結果が得られました。

clojure_nonpa_8192.png

1スレッドしか動作していないことがわかります。

Clojureコード(pmapによる並列化)

Clojureの場合、Java8やScalaのような「並列化されたコレクション」という操作は準備されていませんが、「与えられたシーケンスの各要素に対して関数を並列に適用する"並列map関数(pmap)"」が提供されています。まずはこのpmap関数を用いて並列処理化してみましょう。

ソースコード(のコア部分)

完全なソースコード

ビルドと実行

mapを単純にpmapに置き換えてビルドし実行してみると、予想に反して下記のような結果になりました。

clojure_par1_8192.png

pmapを用いた場合、CPUのユーザモード処理時間(user)が2倍以上になっているのに対し、実処理時間(real)は短くなるどころか若干伸びています。複数コア上で複数スレッドが並列処理されていますが、各コアは50%前後しか使われていません。

これはClojureのpmapが、「与えられたシーケンスの要素全てにスレッドを割り当て、CPUの物理コア数+2個のスレッドプールでそれらを非同期実行する」ような実装になっているため、大量の要素数(今回の例では、ファイル内の行は10万行以上あり、各行に形態素解析を行うとTokenは全部で600万個以上も生成される)に対してはスレッドのコンテキストスイッチのオーバーヘッドが大きすぎ、CPUの能力が使い切れないためではないかと考えられます。

残念ながらClojure 1.5.1では、今回の状況では並列化されても高速化にはつながりませんでした。

Clojureコード(futureを用いた明示的な並列化)

このままではナニカに負けている気がするので、適切な並列化処理を明示的に実装し、並列化と共に高速化してみます。

ソースコード(のコア部分)

完全なソースコード

並列化処理を明示的に実装しているため、一気に複雑になりました。

「future」はClojureの並列処理機構の一つで、futureが評価されるとfutureに束縛された関数を別スレッドで実行します。futureにderefを適用することで、別スレッドで実行した計算結果を得ることができます。

-main関数ではファイルの各行を物理コア数で等分に分割し、各々の断片に対して「形態素解析 & 単語のグループ化とカウント」を行うfutureを定義しています。(doall futures)することで各断片の処理が別スレッドで実行され、その結果をwordCount関数でderef futureしてconcatで集約し、結果を表示しています。

ちょうどHadoopの「mapper - combiner - reducer」と同じような処理をclojureで実装した形になりますね。

ビルドと実行

実行させてみると、下記の結果を得ました。

clojure_par3_8192.png

全てのコアなCPUを使い切り、並列化と高速化が果たされたことがわかります。

まとめ

前回 今回と、JVM上で動作する関数型プログラミングについて、Java8、Scala、Clojureを例にとってさわりの部分を紹介しました。

今回のお題の場合、Java8とScalaは関数型スタイルでの実装がほぼ同じような記法になり、並列化も簡単で効果が高いのが特徴的でした。一方Clojureはプログラムの見た目が全く異なり、並列化の効果を出すためにも一工夫が必要でした。Clojureのパワーを最大限に引き出すためには、今回のお題や例示した実装方法は適切ではなかったようです。

  Java7 Java8 Scala Clojure
非並列処理 実時間 0m32.304s 0m32.511s 0m50.478s 1m38.138s
CPU時間 0m33.730s 0m35.842s 2m12.208s 1m44.675s
並列処理 実時間 0m10.826s 0m17.546s 1m53.819s(0m30.442s)
CPU時間 0m50.107s 1m09.556s 4m6.439s(2m35.974s)

さてみなさん、関数脳は近づいて来ましたか?
マルチコア時代のプログラマとして、関数型プログラミングに少しでも親しみを持つきっかけとなれば幸いです。

エンジニア採用中!私たちと一緒に働いてみませんか?