Haskell(GHC)での軽量ユーザスレッドの実装方法

命令型言語の Java や Ruby がユーザスレッドからカーネルスレッドに移行したのとは対照的に、関数型言語の Erlang や Haskell では軽量なユーザスレッドを提供することに成功しています。僕は、この違いが何から生じているのか理解したいと思っています。この記事では、これまで調べたことをまとめます。

軽量なユーザスレッドは Erlang が有名ですが、Haskell (GHC)でも利用できることを重ねて強調しておきます。Haskell の方が Erlang よりも速いようです。追記：フェアな比較ではないようなので、話半分で参照して下さい。

Rubyの場合

Ruby 1.8 まで提供されていたユーザスレッドは、軽量とは言えませんでした。その理由は、ユーザスレッドをコンテキストスイッチさせる際にスタックをコピーしていたからです。Ruby ソースコード完全解説の第19章スレッドによれば、これは移植性を高めるための選択だそうです。

CPU のスタックポインターを書き換えればスタックのコピーは不要ですが、CPU のアーキテクチャごとにアセンブラを書く必要があります。Ruby 1.8 までは、スタックポインターの書き換えをせずに、スタックの内容を差し替えることで、アセンブラを書くことを回避していました。このため、ユーザスレッドが遅かったのです。

GHCの場合

GHCのユーザスレッドが軽いのはどうしてでしょうか？ 2種類の答えが予想できます。

破壊的な代入がないという関数型言語の特徴から来ている
スタックポインターを書き換えるアセンブラを頑張って書いている

というわけで、ソースを読んでみましょう。ユーザスレッドのスケジュールを担当しているのは、rts/Schedule.c の schedule() です。GHC Commentaryにアルゴリズムが載っています。

scheduler(cap)
{
  for (;;) {
    yieldCapability(cap);  /* give cap to anybody wanting in from outside */
    tso = popRunQueue(cap);
    result = StgRun(tso);
    case result of
      out of heap -> re-enqueue tso; call GC;
      out of stack -> enlarge tso; re-enqueue tso;
      time expired -> put tso on end of queue; /* round robin */
      finished -> 
        if (tso is a bound thread)
          return;
        else
          continue;
    }
}

StgRun がスレッドを走らせるようです。(Stg は Spain-less Tag-less G マシンの略。G は Graph の略。ラムダ計算とは結局グラフ簡約のことで、グラフ簡約のための仮想マシンが STG。) 実際のコードはこうなっています。

r = StgRun((StgFunPtr) stg_returnToStackTop, &cap->r);

StgRun はレジスタを退避し、第一引数の stg_returnToStackTop を呼び出します。stg_returnToStackTopは以下のように定義されています。

stg_returnToStackTop
{
  LOAD_THREAD_STATE();
  CHECK_SENSIBLE_REGS();
  jump %ENTRY_CODE(Sp(0));
}

LOAD_THREAD_STATE は、とても探しにくいのですが、compiler/cmm/CmmParse.yの中で、emitLoadThreadState に変換されているようです。

  ( fsLit "LOAD_THREAD_STATE", \[] -> emitLoadThreadState ),

compiler/codeGen/StgCmmForeign.hs を見ると、emitLoadThreadState の実体は loadThreadState で、これは以下のように定義されています。

loadThreadState :: LocalReg -> LocalReg -> CmmAGraph
loadThreadState tso stack = do
  -- tso <- newTemp gcWord -- TODO FIXME NOW
  -- stack <- newTemp gcWord -- TODO FIXME NOW
  catAGraphs [
        -- tso = CurrentTSO;
        mkAssign (CmmLocal tso) stgCurrentTSO,
        -- stack = tso->stackobj;
        mkAssign (CmmLocal stack) (CmmLoad (cmmOffset (CmmReg (CmmLocal tso)) ts
o_stackobj) bWord),
        -- Sp = stack->sp;
        mkAssign sp (CmmLoad (cmmOffset (CmmReg (CmmLocal stack)) stack_SP) bWor
d),
        -- SpLim = stack->stack + RESERVED_STACK_WORDS;
        mkAssign spLim (cmmOffsetW (cmmOffset (CmmReg (CmmLocal stack)) stack_ST
ACK)
                                    rESERVED_STACK_WORDS),
        openNursery,
        -- and load the current cost centre stack from the TSO when profiling:
        if opt_SccProfilingOn then
          mkStore curCCSAddr
                  (CmmLoad (cmmOffset (CmmReg (CmmLocal tso)) tso_CCCS) ccsType)

        else mkNop]

という訳で、Cmm(C--) レベルのスタックポインターが書き換えられていることが分かりました。Cmm とは汎用アセンブラです。

結局、GHC はもともと Cmm という汎用アセンブラを用意しており、その中でスタックポンターを書き換える手段が提供されていたので、軽量なユーザスレッドをサポートできたといえそうです。(つまり、違いは頑張ってたくさんのCPUアーキテクチャをサポートしたかどうか。)

なお GHC では、以下のような中間言語を作ります。

Core -- 拡張ラムダ式 (-ddump-simpl で見れる)
STG -- Graph 簡約マシンのコード (-ddump-core で見れる)
Cmm -- 汎用アセンブラのコード (-ddump-cmm で見れる)
アセンブラ/C/LLVM

GHC のソースを読むにあたって、NaOHaq さんにお世話になりました。ありがとうございます。

不正確な記述もあると思うので、突っ込みを歓迎します。

あどけない話

Internet technologies

Haskell(GHC)での軽量ユーザスレッドの実装方法

Rubyの場合

GHCの場合