ゴルーチンによる Lisp Future 形式の実現

2013-04-19 (鈴)

1. はじめに

近年普及したマルチコア CPU の能力を活用するために,プログラムを手軽にコンカレント化できる仕組みが望まれている。 ここでは Go 言語による簡単な Lisp に対し,スペシャル・フォームとしてコンカレント化コンストラクト future を Go 言語のゴルーチン (goroutine) で実装する作例を示す。 future 形式の説明については future - Wikipedia [wikipedia.org] 等を参照されたい。

(setq a (future (+ 1 2 3)))

とすると式 (+ 1 2 3) が独立したスレッドでコンカレントに評価される。 その評価結果 6 は変数 a から取得できる。

(force a) ; => 6

もしも force 関数の適用時にまだスレッドでの式の評価が完了していなければ完了するまで待ち合わせる。

流儀によっては future ではなく promise と呼ばれることもあります。 promise という名前が暗示するように遅延評価 (lazy evaluation) と密接な関係があります。 典型的な Scheme 言語は delay 形式で遅延評価のためのオブジェクト (これも promise と呼ばれます) を作り,force 関数でその評価を強制します (R5RS [unixuser.org] §4.2.5)。
;; Scheme
(define a (delay (+ 1 2 3)))
(force a) ; => 6
こうした遅延評価は,最初に force された時はじめて式の評価を開始する単一スレッド版の future 呼び出しであると見ることができます。 future と遅延評価の関係は極めて初期の文献 H. G. Baker & C. Hewitt: The Incremental Garbage Collection of Processes (1977) [pipeline.com] から論じられています。

元々の future のアイディアでは,値が必要とされたとき (評価未完了ならば待ち合わせた後に) 自動的に値が取得される機構を仮定していたようです。 Multilisp - Computer Science - University of Massachusetts Amherst [umass.edu] (ppt) から Multilisp によるコード例を引用します:
(define fib 
  (lambda (x) 
    (if (= x 1) 1
      (if (= x 2) 2
        (+ (future (fib (- x 1))) 
           (future (fib (- x 2)))) ))))

(fib 10) => 89
同様のアイディアが Scheme では promise オブジェクトに対する implicit forcing として知られています (R5RS §6.4)。 implicit forcing の実装例は Let Little Lambda Lisp be a Little Lazy に見ることができます。 ここでは実装を簡単にするため,典型的な Scheme 言語の promise オブジェクトと同じく force されてはじめて値が取得されるように作ります。

ソースからのコンパイル&実行例を下記に示す。 コマンド行引数としてスクリプトのファイル名とハイフンを与えると,スクリプト (ここでは qsort.l) を実行した後そのまま対話セッションに入る。

01:~/tmp$ tar xvf lisp-25-04-01.tar.bz2
lisp-25-04-16/
lisp-25-04-16/8queens.l
lisp-25-04-16/qsort-pi-seq.l
lisp-25-04-16/qsort-pi.l
lisp-25-04-16/qsort.l
lisp-25-04-16/README.txt
lisp-25-04-16/src/
lisp-25-04-16/tiny-lisp-prof.go
lisp-25-04-16/tiny-lisp.go
lisp-25-04-16/src/arith/
lisp-25-04-16/src/lisp/
lisp-25-04-16/src/lisp/data.go
lisp-25-04-16/src/lisp/env.go
lisp-25-04-16/src/lisp/globals.go
lisp-25-04-16/src/lisp/interp.go
lisp-25-04-16/src/lisp/lex.go
lisp-25-04-16/src/arith/num.go
lisp-25-04-16/src/arith/num_test.go
01:~/tmp$ cd lisp-25-04-16
01:~/tmp/lisp-25-04-16$ GOPATH=`cygwin -w -a .` go build tiny-lisp.go
01:~/tmp/lisp-25-04-16$ ./tiny-lisp qsort.l -
> (qsort '(3 1 4 1 5 9 2 6 5))
(qsort '(3 1 4 1 5 9 2 6 5)) => (1 1 2 3 4 5 5 6 9)
> (+ 7 8 9)
(+ 7 8 9) => 24
> (/ 7 8 9)
(/ 7 8 9) => 7/72 /*~0.09722222222222222*/
> (setq a (future (+ 7 8 9)))
(setq a (future (+ 7 8 9))) => &{0x123aa390 <nil> {0 0}}
> (force a)
(force a) => 24
> a
a => &{<nil> 24 {0 0}}
> Control-C で中断
1301:~/tmp/lisp-25-04-16$  
Windows の Cygwin では上記のとおりにできますが, Linux や Mac OS X など普通の Unix 類では GOPATH=`cygpath -w -a .` のかわりに GOPATH=`pwd` としてください。 Cygwin では止むを得ませんが Control-C による中断は乱暴な方法ですから,普通の Unix 類では Control-D による終了を試してください。

2. インタープリタのスレッド・セーフ化

Lisp インタープリタに future 形式を実装するには,まずインタープリタをスレッド・セーフにしなければならない。 複数のスレッド (厳密に言えば,ここでは Go 言語で実装するからゴルーチン) から同時に改変されるデータ構造には,名前に対するシンボルの一意性を保つためのマップと,束縛変数からその変数値へのマップがある。 これらの操作を排他ロックで保護する。

名前に対するシンボルの一意性を保つためのマップ (symbols 変数) については,次のように保護する。

 var symbols = make(map[string]*Symbol)
+var lock sync.Mutex
 
 // 文字列からシンボルを作る。
 func NewSymbol(name string) *Symbol {
+   lock.Lock()
    sym, ok := symbols[name]
    if !ok {
        sym = &Symbol{name}
        symbols[name] = sym
    }
+   lock.Unlock()
    return sym
 }

束縛変数からその変数値へのマップ (Env 構造体の Table フィールド) については,次のように保護する。

 // 環境. 現在の束縛変数に対する Table と自由変数に対する Next からなる。
+// Table を参照するときは Lock で排他すること。
 type Env struct {
    Table map[*Symbol]Any
    Next  *Env
+   Lock  sync.Mutex
 }
 func (env *Env) Get(sym *Symbol) Any {
    for ; env != nil; env = env.Next {
+       env.Lock.Lock()
        val, ok := env.Table[sym]
+       env.Lock.Unlock()
        if ok {
            return val
        }
 func (env *Env) Set(sym *Symbol, val Any) {
    for ev := env; ev != nil; ev = ev.Next {
+       ev.Lock.Lock()
        _, ok := ev.Table[sym]
        if ok {
            ev.Table[sym] = val
+           ev.Lock.Unlock()
            return
        }
+       ev.Lock.Unlock()
    }
    if env.Next == nil { // トップレベルの環境ならば
+       env.Lock.Lock()
        env.Table[sym] = val
+       env.Lock.Unlock()
        return
    }

排他ロックで保護したこれらの操作はどれも短時間で終了すると期待されるから,コンカレント性に対して目立った悪影響はないと考えてよい。 排他ロックとして使う sync.Mutex 構造体は軽量なオブジェクトだから,環境を実現する連結リストの各 Table にそれぞれ設けても差し支えない。 下記に Go 1.0.3 の go/src/pkg/sync/mutex.go から sync.Mutex の定義を引用する (Go 1.1beta2 も同様である)。

// A Mutex is a mutual exclusion lock.
// Mutexes can be created as part of other structures;
// the zero value for a Mutex is an unlocked mutex.
type Mutex struct {
    state int32
    sema  uint32
}

このように排他ロックの実体は二つの整数からなる構造体にすぎない。

3. Future 形式と Force 関数の実装

Go 言語のゴルーチンとチャネルのおかげで future 形式と force 関数の実装は単純である。

future 形式を実装する Go の futureForm 関数を示す。

// (future expession)
func futureForm(x *Cell, env *Env) (Any, *Env) {
    a := CheckForUnary(x)
    ch := make(chan Any)
    go futureTask(a, env, ch)
    return &Future{ch, nil, sync.Mutex{}}, nil
}

CheckForUnary(x)x が長さ1のリストであることを確認して x.Car を返す。 これがコンカレントに評価すべき式である。 評価結果を送受するためにキャパシティ 0 のチャンネル ch を作り,式 a,環境 env ともに futureTask に渡してゴルーチンとしてコンカレントに実行する。

func futureTask(a Any, env *Env, ch chan<- Any) {
    ch <- env.Eval(a)
    close(ch)
}

futureTask 関数は式 a を環境 env で評価し,その結果をチャネル ch で送信してから,ch を閉じる。

一方,futureForm 関数はゴルーチンを分岐させた後,チャネルを含んだ Future 構造体を構築し,そのアドレスを返す。

type Future struct {
    Ch     <-chan Any
    Result Any
    Lock   sync.Mutex
}
ゴルーチンでコンカレントに実行される futureTask 関数では仮引数 ch が送信用チャネル chan<- Any として宣言される一方で,結果を受け取る Future 構造体ではフィールド Ch が受信用チャネル <-chan Any として宣言されていることに注意してください。

force 関数を実装する Go の forceFunc 関数を示す。

// (force expession)
func forceFunc(a []Any) Any {
    CheckArity(1, a)
    if fu, ok := a[0].(*Future); ok {
        fu.Lock.Lock()
        if fu.Ch != nil {
            fu.Result = <-fu.Ch
            fu.Ch = nil
        }
        fu.Lock.Unlock()
        return fu.Result
    }
    return a[0]
}

もしも与えられた引数が Future 構造体へのポインタならば,構造体の受信用チャネル・フィールド Ch から評価結果を1回だけ受け取る。 このときゴルーチンがまだ結果をチャネルに送信していなければ待ち合わせる。 得られた結果を構造体の Result フィールドに格納し,次回以降の force 関数の呼び出しでは単に Result フィールドの値を返す。

futureForm 関数が Future 構造体そのものではなくそのアドレスを返したのは,コピーされてもフィールドを共有するためです。 1回の future 呼び出しの結果に対して force での受信が2回以上あってはいけません。

4. 4 コア CPU での高速化の実験

コンカレント化の効果を見るため 5001 個の整数をクイックソートする qsort-pi.l と,その非コンカレント版である対照用の qsort-pi-seq.l を用意した。 qsort-pi.l の内容を下記に示す。 クイックソートのピボットによるリストの2分割の後,右半分のソート処理を future 形式で別のゴルーチンに任せる。 再帰的な2分割のたびに次々とゴルーチンが作り出される。 必要になったとき,その結果を force 関数で取り出す。 非コンカレント版の qsort-pi-seq.l(force right-sorted)right-sorted に,(future (cons …))(cons …) に置き換えた以外は同一である。

(defun qsort (seq) (_qsort seq nil))

(defun 1st (list) (car list))
(defun 2nd (list) (car (cdr list)))

(defun _qsort (left-seq right-sorted)
  (if (null left-seq)
      (force right-sorted)
    (let ((pivot (car left-seq))
          (tail (cdr left-seq)))
      (let ((pair (_split pivot tail)))
        (let ((left (1st pair))
              (right (future
                      (cons pivot
                            (_qsort (2nd pair) right-sorted)))))
          (_qsort left right))))))

(defun _split (pivot seq)               ; => (left-seq right-seq)
  (if (null seq)
      (list nil nil)
    (let ((x (car seq))
          (tail-pair (_split pivot (cdr seq))))
      (if (< x pivot)
          (list (cons x (1st tail-pair))
                (2nd tail-pair))
        (list (1st tail-pair)
              (cons x (2nd tail-pair)))))))

(print (qsort '(3
1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3
……略……
2 9 8 6 0 8 0 9 9 8 8 8 6 8 7 4 1 3 2 6 0 4 7 2 1
)))

この処理では多数のゴルーチンが作られるが,これらはいわば仮想的なスレッドである。 実際のスレッド数は環境変数 GOMAXPROCS で指定できる。 下図は 4 コア 4 スレッド CPU である Core i5-3470 3.20GHz 上の Windows 7 Professional SP1 (32ビット) で Go 1.1beta2 を使ってコンパイルした Lisp インタープリタを GOMAXPROCS=10 で実行した様子である。



同じマシンで環境変数 GOMAXPROCS を 1 から 10 まで変化させたときの実行時間 (time 出力の real 値) は次のとおりである。 一つの環境変数値に対してそれぞれ2回試行し,短い方の時間を採った。

GOMAXPROCS qsort-pi.l [s] qsort-pi-seq.l [s]
1 13.1 11.8
2 10.3 12.3
3 8.6 12.1
4 7.8 12.0
5 7.4 11.9
6 7.2 11.9
7 7.1 11.9
8 7.0 11.9
9 6.9 11.9
10 6.8 11.9

スレッド数が 1 のときは非コンカレント版である qsort-pi-seq.l が速いが,2 以上では future を利用した qsort-pi.l が速くなる。 スレッド数を増やすごとに速くなり,10 スレッドでは 1.75 倍ほどに高速になる。

奇妙なのは CPU のコア数である 4 を超えてスレッド数を増やしても,なおわずかずつ速くなることである。 おそらく排他ロックやチャネルの待ち合わせで遊休している間の CPU を,他のスレッドが利用できるようになるためであろう。

5. おわりに

Go 言語による簡単な Lisp インタープリタに Go 言語のゴルーチンを使って future 形式を実装し,Lisp 上でのコンカレントな計算を実現した。 こうすることでマルチコア CPU の能力を活用した高速な処理を,高い CPU 使用率のもとで達成できる。 実装のためのコード量の少なさから,この作例をコンカレントなシステムを構築するための Go 言語の表現力の高さを示す実例と見ることもできるだろう。 この分野にどれほどの可能性があるだろうかと期待される。


Copyright (c) 2013 OKI Software Co., Ltd.