長旅の終わり

昨年の今頃から並列Lispの実装に取り組んでいました。当初、マルチスレッド方式で実装しましたが、期待した並列性能が出ませんでした。先日の記事でインタプリタでのマルチスレッド方式について改良したことをお話しました。そして、ついにコンパイルしたコードでもマルチスレッドによる並列性能を出すことができました。

原因

インタプリタにおいてはセル切り出しにおけるスレッドの競合が速度低下の原因でした。コンパイラにおいてはセルはそれほど多く消費しません。原因は何？　追求して遂に判明しました。L3キャッシュにおいてキャッシュミスがおきるような無駄なコードを生成していたのでした。

次のLispコードはフィボナッチ数を計算する再帰関数です。この＋関数を呼び出すときにGCが起動する可能性がありました。そこで第一引数をEvalしている間にGCが起動してもいいようにシェルターと呼ばれるスタックにその値を記憶しGCにより消失しないようなコードを生成していました。

(defun fib (n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (t (+ (fib (- n 1)) (fib (- n 2))))))

Easy-ISLispはLispコードを等価なCコードに変換しています。フィボナッチ数のLispコードは次のように変換していました。

static int FIB(int N, int th) {
    int res;
    
    if (CELLRANGE(N)) Fpshelterpush(N, th);
    Fcheckgbc();

    res = ({
        int res = NIL;
        if (fast_numeqp(N, fast_immediate(0)) != NIL) {
            res = fast_immediate(0);
        } else if (fast_numeqp(N, fast_immediate(1)) != NIL) {
            res = fast_immediate(1);
        } else {
            res = fast_plus(
                ({
                    int arg1, res;
                    arg1 = fast_minus(N, fast_immediate(1));
                    // Fpshelterpush(arg1, th);  // コメントアウト
                    res = FIB(arg1, th);
                    // arg1 = Fpshelterpop(th);  // コメントアウト
                    res;
                }),
                ({
                    int arg1, res;
                    arg1 = fast_minus(N, fast_immediate(2));
                    // Fpshelterpush(arg1, th);  // コメントアウト
                    res = FIB(arg1, th);
                    // arg1 = Fpshelterpop(th);  // コメントアウト
                    res;
                })
            );
        }
        res;
    });

    if (CELLRANGE(N)) N = Fpshelterpop(th);
    return res;
}

問題はコメントアウトした部分です。計算途中にGCが起動してもいいように挿入してあるコードです。このコードは動的リンクにより処理系本体にあるシェルターへのpush/popを呼び出しています。これはメモリ位地の離れた部分にアクセスしているのでしょう。異なるスレッドにおいてこのコードへのアクセスがL3キャッシュにおけるキャッシュミスを誘発していたものと思います。

改良

シェルターへのpush/popのコードを挿入しないようにコンパイラを改良しました。インタプリタは大量のセルを消費するので計算途中でGCが起動する可能性があります。しかし、コンパイルしたコードはそれほど大量のセルは消費しません。小整数は即値としていますのでフィボナッチのようなコードではほとんどセルを消費しません。リスト処理においても引数のevalの途中でGCが起動することはほぼ考えられません。カットすることとしました。

時間計測

mt-let、mt-callを利用した並列コードをコンパイルして実行時間を計測しました。

1.61倍程度高速化しました。黄金比に近いです。かなり良い計測結果が得られました。

目標達成

ver4.0にむけてマルチスレッド、マルチプロセスによる並列機能を追加することを目標としてきました。この楽しい旅は目的地に達したようです。さらに細かな改良、テストをした後にver4.0をリリースします。

Easy-ISLispはOSSです。BSD2ライセンスです。お気軽にご利用ください。
https://github.com/sasagawa888/eisl