ClojureのSTMは使い物にならない

0x00. Clojureがいけてる件について


ここ数ヶ月でClojureをどんどん実戦投入してみているが、その成果は素晴らしいの一言に尽きる。Javaでは考えられなかったほどスマートかつ柔軟にデータ処理が可能であり、「あれ、こんなに短い記述でできちゃうのか!」と驚かされることが多い。そんなわけで、何でもかんでもJavaで片付けてきた筆者はここにきてClojureにかなり惚れ込んでおり、電子書籍やらウェブサイトやらで本格的に情報収集を進めているのだが…

0x01. Clojureの並列プログラミング


現時点では、Clojureを実戦投入したのは、ちょっとした処理に使うツール的なものだけである。理由は単に、筆者がまだClojureの初心者だからだ。しかしそろそろメインの仕事であるサーバアプリケーションやウェブアプリケーションでも使いたくてウズウズしてきており、そのような視点からさらに調査を進めている。

サーバアプリケーションやウェブアプリケーションでは並列プログラミング的なことをよくやるのだが、ClojureではこれはSTMを使って処理するのが王道のようだ。Clojureの解説を行う本などでは、STMは従来のJavaのロック地獄から解放してくれる救世主的な扱いをされており、筆者としては非常に期待していた。Javaでのマルチスレッドプログラミングは確かになかなか難しい部分があり、コードレビューなどで問題点を見つけ出す技術には経験に基づく勘が要求される。単に並列プログラミングを行いたいだけなのにメモリバリアーが〜とか言われるため、ある種バッドノウハウ的な側面がある(筆者は個人的に大好きだが)。

ClojureのSTMはぱっと見た感じでは拍子抜けするほどシンプルであり、「これで本当に動くなら、今までのJavaの並列プログラミングは何だったんだ…」と思う仕上がりになっている。

0x02. 遅いらしい


筆者の見落としである可能性もあるが、Clojureの解説を行う本(Programming ClojureとPractical Clojure。ついでに現在The Joy of Clojureを読んでいるところ)では、STMのパフォーマンスに関する記述はなかったように思う。そのため、普通に読んでいる読者は、間違いなく「並列プログラミングが必要とされる場面ではSTMを使えばよい」と考えるだろう。筆者もそう思っていたのだが、ある日Clojureに的を絞っているわけではない書籍である「Programming Concurrency on the JVM」を読んでいたところ、「STMはReadが多く、Writeが少ない場面だけにしておくべし」的な記述があって驚いた。Clojureでは基本的に並列プログラミングにはSTMしか選択肢がない(もちろんClojureからJavaのスレッドを生成したりすることもできるが、それならばsynchronized等の文法がサポートされている生のJavaを使った方が百倍開発しやすいため、却下)のに、書き込み競合が多い場面ではSTMが使えないのでは、開発が成り立たないのではと思ってしまうが…。この書籍内では実際にSTMが遅くて使えないケースをソースコード付きで掲載している。

そんなわけで、単純な例でベンチマークを取ってみることにした。

0x03. ベンチマークの内容


マップをひとつ生成する。このマップに対して多数のスレッドから書き込み競合が多く発生するようなアクセスを行う。具体的には、各スレッド内でランダムにキー(100種類のうちの1つ)を生成し、そのキーに対応する値を取得する。値は数値とする。この数値をひとつインクリメントし、再びマップにセットする。マップ内にキーが存在していない場合には1をセットする。スレッドは300個生成し、上記のインクリメント動作はそれぞれのスレッドで10万回ずつおこなう。これをJavaとClojureでそれぞれ記述したものが以下である。

Test2.java

package test;

import java.util.*;

public class Test2
{
public static final int _keyRange = 100;
public static final int _threadCount = 300;
public static final int _repeat = 100000;
//--------------------------------------------------------------------------------
public static void main( String[] args )
throws Exception
{
final long start = System.currentTimeMillis();
final Map map = new HashMap();

Runtime.getRuntime().addShutdownHook( new Thread( new Runnable()
  {
  public void run()
    {
    System.out.println( System.currentTimeMillis() - start );
    System.out.println( map );
    }
  } ) );

for( int i = 0; i < _threadCount; ++i )
  {
  new Thread( new Runnable()
    {
    public void run()
      {
      for( int k = 0; k < _repeat; ++k )
        {
        Random random = new Random();
        String key = "key" + random.nextInt( _keyRange );
        
        synchronized( map )
          {
          Integer value = ( Integer )map.get( key );
          if( value != null )
            {
            int oldValue = value.intValue();
            map.put( key, new Integer( oldValue + 1 ) );
            }
          else
            {
            map.put( key, new Integer( 1 ) );
            }
        
          }
        
        }
      }
    } ).start();
  }
}
//--------------------------------------------------------------------------------
}

bench.clj(注:間違いあり。修正版は0x06項目を参照)

(ns bench)
(import '(java.util Random))

(def _keyRange 100)
(def _threadCount 300)
(def _repeat 100000)
(def mapref1 (ref {}))
(def _start (System/currentTimeMillis))
(def _agents (seq (repeat _threadCount (agent nil))))

(defn fn1 []
  (let
    [
     _random (new Random )
     _key (str "key" (.nextInt _random _keyRange))
    ]
    
    (dosync
      (let [ _oldValue (get @mapref1 _key) ]
        (if (nil? _oldValue)
          (alter mapref1 assoc _key 1)
          (alter mapref1 assoc _key (+ 1 _oldValue))
        )
      )
    )
  )
)

(defn fn2 [ dummy ]
  (dotimes [ _index _repeat ]
    (fn1)
  )
)

(doseq [ _agent _agents ]
  (send-off _agent fn2)
)

(defn fn3 []
  (println (- (System/currentTimeMillis) _start))
  (println @mapref1)
)

(doseq [ _agent _agents ]
  (await _agent)
)

(fn3)
(shutdown-agents)
(System/exit 0)

0x04. ベンチマーク結果


この2つのプログラムを実行してみると、Java版は6〜7秒程度で終わるが、Clojure版は60秒程度かかる。Clojure版はざっと10倍程度遅いことになる。(これは書き込み競合が極端に多い例であり、ClojureのSTMが最も苦手とするケースではあることに注意が必要だ。Writeが少なく、Readが多いケースでは、Javaより速い場合もあるかもしれない。)

0x05. STMは使えないと思う理由


筆者はこの結果を受けて、「ClojureのSTMは使えない」と判断した。

「Readが多いケースならば、STMもよいのでは」という意見もあるかもしれない。しかし開発している最中に、いちいち「この部分の競合ではReadが多いか?」などと考えるのはナンセンスだ。

また、サーバアプリケーションに予想以上のアクセスが集中するなどのケースで、「読み込みが大部分だろう」と思っていた箇所で書き込み競合が多く発生してしまったら悲惨なことになってしまうかもしれない。そして、そもそも書き込み競合が多い場面で使えないのでは、別の技術も勉強する必要があり、無駄である。

さらにもう一つの理由として、「正しいコードかどうか」の判断を付けることができないという点があげられる。Javaのロックベースのマルチスレッドプログラミングは、確かに落とし穴が多い。しかしFindBugsのようなツールやコードレビューなどによって、デッドロック等の問題が発生する可能性などを見つけることができる。また、実際にデッドロックが起こってしまった場合などにも、問題点がはっきりする。問題点が見つかれば、それを修正していくことで、「正しいコード」に近づく。そしてある時点で、ほぼ確実に正しく動作するコードになった、と自信を持つことができるようになる。そしてそのコードは速い。

ClojureのSTMでは、実際にアプリケーションを完成させてテストするまで、「性能がでるかどうか」つまり「正しいコードかどうか」を判断することができない。サーバアプリケーションではしばしばテスト時点では想像もできない複雑なパターンのアクセス集中が発生することが予想されるため、いつまでたっても「このコードでいける!」と自信を持つことができなくなるだろう。また、問題があった場合の修正はアプリケーションの作り自体の変更になる可能性があり、Javaでのデッドロックの修正よりもよほど大がかりになる可能性がある。これはかなりの茨の道になるだろう。

この筆者の判断は現時点でのものなので、数年後にSTMが爆速になっていたりすれば、もちろん使ってみるつもりだ。また、性能が問題にならないようなちょっとした処理であればもちろんSTMは便利に使えるだろう。

0x06. 追記(コードのミスを修正)


コメント欄でTakahiro Hozumiさんより非常に有意義なコメントをいただいた(ありがとうございます!)。やはりSTMのパフォーマンスには問題があるらしい。また、上記の筆者のClojureコードにはミスがあり、実際には300スレッドを生成できていないことがわかった。

修正版を作成したので以下に掲載する。

bench.fixed.clj

29行目をコメントアウトすると、確かに300スレッド生成できていることが確認できる(また、ps -eLf等のコマンドでも確認済み)。

問題のパフォーマンスだが、修正後のコードを使って300スレッド生成してみるとさらに遅くなることがわかり、Javaより10倍どころではなく、恐ろしく遅くなることがわかった。そのため、0x05で示した本稿の結論的なものは変わらない形となる。

0x07. さらに追記


Clojureでは(今回のテストのように)単純に多くのスレッドを生成したいだけの場合にはagentの使用は不適切であるとコメント欄で指摘していただいた。このような場合にはagentの使用には大きなオーバーヘッドがあるようだ。The Joy of Clojureの11章がこのあたりに触れた説明となっており、とても参考になる。

本稿で目的としているテストを正しく行うためのコードはTakahiro Hozumiさんが作成してくれたhttps://gist.github.com/3048d90328d3118583a4の(ref-bench)であり、パフォーマンスはJavaの10倍程度遅いということになるようだ。

少し話題が反れるが、Programming ClojureやPractical Clojureを読んだ印象はまさに「Clojure=シンプル」であったのだが、The Joy of Clojureの11章の印象は(悪い意味で)かなり違う。現実的にはそれほどシンプルな記述で並行プログラミングを実現できる、というわけではなさそうだ。lockingなどは普通にデッドロックを起こす可能性があるように思えるためClojureらしくないと感じる。

0x08. またまた追記


詳しくはコメント欄を参照していただきたいが、最終的には以下のようなことになるようだ。

  • Agentを使ってスレッドを作ること自体のオーバーヘッドはそれほど大きくない
  • (書き込み競合が多い場合の)STMは非常に重く、Javaの10倍どころではない時間を要する
  • Advertisements

    14 Comments on “ClojureのSTMは使い物にならない”

    1. Takahiro Hozumi says:

      こんにちは。
      スレッド数(n)とSTMのリトライ数が線形( O(n) )関係じゃないのは本にはほとんど書かれてないですが注意が必要ですよね。
      成功したスレッド以外が毎回必ずリトライするという極端な例を考えると多分 O(n!) でしょうか。
      現実的な対応としては
      ・大きなスレッド数を避ける
      ・処理対象のデータを分割する
      ・dosyncの外でできる計算は外でやる
      ・STMを使わない
      ぐらいだと思います。
      Making an RPG in Clojure (part one of many?)
      http://briancarper.net/blog/520/making-an-rpg-in-clojure-part-one-of-many
      この方もスレッド数が多いとリトライがばかにならないということで、シングルスレッドに書き直してるみたいです。
      今回のようにI/Oがない(ブロックする可能性がない)関数をagent に使用するのであれば、
      send-off ではなく send を使用すると固定サイズのスレッドプールで処理が実行されるので、リトライに上限ができると思います。
      send-off は必要に応じて伸び縮みするスレッドプールが使用されます。
      またはpmap, pcall, pvalues のどれかを使っても同じように、一度に実行するスレッド数を調整してくれるので同じ効果があると思います。

      • Takahiro Hozumi says:

        > (repeat _threadCount (agent nil))
        すみませんよく見てなかったのですが
        repeat は 毎回同じ値を返すのでこれは agent が指定回数分作られるわけではないです。
        repeatedly は指定回数、関数を実行したシーケンスを作ります。

    2. kanatoko says:

      コメントありがとうございます。リンク先のRPGすごいですねw。コメント欄も含め読むのには少し時間がかかりそうです。

      agentはご指摘通り生成できていませんでした。非常に助かりました。ありがとうございます。

      スレッド数が多くなるとこれだけ(Javaより)遅くなるっていうのはちょっと残念です。改良に期待して待つことにします。

    3. Takahiro Hozumi says:

      追記に付いて

      今回の例のように、スレッドを作るために Agent を使うというのは適切ではないです。
      The Joy Of Clojure の Chapter11に Agent をいつ使うか、いつ使うべきでないかが記載されていますが、
      Ref や Atom と同じく、時と共に値が変わっていく Identity に対して使用するべきです。
      今回の例では、普通に.run や future でスレッドを作る方がいいです。
      Agentだと劇的にパフォーマンスが悪いのは300のスレッドセーフなキューを作って
      それにアクションを出し入れするという余計な処理が加わるからかな。
      ↑でリンクしたRPGの例でも各キャラに割り当てた Agent を経由して Ref を操作していたと
      書いてあったので、よく考えたらあまり意図がわからないですね。
      STM は2個以上の変数の協調的な変更が必要なときに初めて嬉しいものなので、
      今回のように、1つの独立に更新できる変数には Atom を使うのが自然だと思います。
      こちらでも測定してみました。

      Refだと50秒、Atomだと17秒ですね。futureを使っても同じでした。
      プログラミング Clojure にも載っていますが、2個以上の変数の協調的な変更が必要な時でも
      全部を一つの Atom に突っ込むという技もあります。

      >スレッド数が多くなるとこれだけ(Javaより)遅くなるっていうのはちょっと残念です。改良に期待して待つことにします。
      私は今のSTMの実装はかなり実用十分だと思いますよ。
      今回のとても極端な競合状態が起きるケースが Java の10倍で済むという事は
      平均的には数倍で済むということであり、
      それでパッチワークだらけの船にならないなら見合うと思います。
      Clojureの並行処理のツールボックスにはいくつもの洗練された道具が入ってて、場面場面で好きに選べるのが好きです。

      • Takahiro Hozumi says:

        あと、最初にpmap 使ったらいいかもと書きましたが、それは全然駄目で遅かったです。

    4. kanatoko says:

      Takahiro Hozumiさん

      ありがとうございます。洗練されたClojureコードで非常に勉強になります。
      (lockingの存在なんて、知りませんでした…)

      >私は今のSTMの実装はかなり実用十分だと思いますよ。
      >今回のとても極端な競合状態が起きるケースが Java の10倍で済むという事は
      >平均的には数倍で済むということであり、
      >それでパッチワークだらけの船にならないなら見合うと思います。

      この部分は、どのようなアプリケーションの開発を想定しているかによって意見が異なるでしょうね。
      私が作っているサーバアプリケーションなどでは数千スレッド〜1万スレッドくらいの規模でもきちんと動いてくれるものが要求されるのでダメなのですが、おっしゃるとおりで平均的にはすっきりプログラミングできる利点が勝る場面は多々あるだろうと思います。

      Agentのオーバーヘッドには気がつきませんでした。テスト目的に沿っていなかったですね。こちらのご指摘も大変助かります。ありがとうございます。

      >STM は2個以上の変数の協調的な変更が必要なときに初めて嬉しいものなので、
      >今回のように、1つの独立に更新できる変数には Atom を使うのが自然だと思います。

      今回のテストはあくまでもSTMの書き込み競合が多いケースでのパフォーマンスを測定するのが目的で、単に1つのHashMapを使っただけです。実際のケースでは2つどころかもっと多くの変数に対してがっつりdosyncすることを考えていました(パフォーマンスがダメそうなのでやらなさそうですが)。

      >Clojureの並行処理のツールボックスにはいくつもの洗練された道具が入ってて、場面場面で好きに選べるのが好きです。

      Clojureでは何も考えずに全部STMでやればよいのかと思っていたのですが、場面に併せて適切な解を選ぶ必要があるのであれば、少し面倒であると捕らえる人もいるかもしれません。私はちょっとそのような超シンプルなやり方でいけることを期待していたので、ちょっとがっかりしているところです。

    5. kanatoko says:

      The Joy of Clojure読んできました。まさにWhen not to use Agentsでした(;´Д`)

    6. kanatoko says:

      さらに追記しました。

      http://clojure.org/rationale
      に↓とあるように

      Clojure’s software transactional memory and agent systems do the hard part

      STMとAgentでさっくり解決!というのを期待していたのですが…

    7. Takahiro Hozumi says:

      こちらもコードが間違っていましたw すみません。
      関数に .run を読んだだけで別スレッドで走るわけではありませんでした。

      結果、Ref は 8分程度待っても結果返ってこず、Atom は 27秒、HashMap&ロック は48秒でした。
      一転しますが、競合が激しい部分は素直にJavaにしておいた方がいいですね。

    8. kanatoko says:

      引き続きありがとうございます。なるほど.runだとカレントスレッドで走るだけなんですね。

    9. kanatoko says:

      頂いた結果を踏まえて、こちらでも再度テストしてみました。同じ結果で、非常に遅くなりますね。

      STMが遅いのか、Clojureそのもののオーバーヘッドがかなりあるのか、微妙な感じかもしれません。

      Agentについてです。(Agentの使用が適切なケースかどうかはさておき)Agent版と生スレッド生成版のパフォーマンスはほとんど差がないようなので、Agentを使うことが劇的な遅さに繋がるというわけではなさそうです。

      HashMap&ロックがJavaと同じくらいの速さを出してくれればうれしいところなのですが…

    10. […] Clojureの並行プログラミングモデルはSTMとagentを中心とした非常に洗練されたものだとされていることがある。Javaでスレッドを生で扱う場合の危険性と対比され、Clojureは開発効率がよく危険性が少ない、と思っているユーザも多いだろう。しかし実際にはClojureのSTMは書き込み競合が発生した場合に非常に遅く、また実際の並行プログラミングのためにはSTMとagentだけではなく他の方法も覚える必要があり、それほどシンプルなものではない。 […]

    11. omasanori says:

      nのスレッドに対するリトライ回数はたかだかn!ではなくたかだかn^2程度ではないでしょうか?
      いずれにしても、トランザクションで(ロックを使って自分以外をブロックするよりも)全体的な計算量が増えるのは確かです。

      あと、これはClojureとは関係のない質問ですが、数千スレッド~1万スレッド規模が適正なハードウェアを使っているのでしょうか?
      そうでなければどちらにしても性能的には正しくないことが起こるのではないかという不安があります。


    Leave a Reply

    Fill in your details below or click an icon to log in:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out / Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out / Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out / Change )

    Google+ photo

    You are commenting using your Google+ account. Log Out / Change )

    Connecting to %s