動機
ISLispの生みの親の一人である伊藤貴康先生の論文を読みました。並列マシンの製作、その上で走るPaiLispに興味を持ちました。その論文を参考にしてISLisp規格のEasy-ISLisp（以下「EISL」)に並列構文、pletとpcallを追加、並列Lispで何ができるのだろうか？と試行錯誤しています。
スレッドセーフ
インタプリタをスレッドセーフにするとともに、コンパイラが生成するLispオブジェクトもスレッドセーフにしました。EISLはLispコードをC言語にトランスパイルする方式です。スレッド番号を表す引数thを追加するようにしました。
int f_tarai(int x, int y, int z, int th){
tarai(x,y,z,th)
}
int tarai(int x, int y, int z, int th){
コード本体
}
C言語の引数はスレッドセーフですが、動的変数、シンボルや文字列を表すセルはスレッド間で共有していますので、これをスレッド番号ごとに管理するコードを生成するように変更しました。マーク＆スイープのGCスレッドごとに保護すべきセルなどのデータを保持し、スレッドセーフを実現しました。
C言語のPthreadライブラリを利用してスレッドに分割します。これによりマルチコアCPUであればそのスレッドが各コアで実行されるようになります。
並列構文
PaiLispの論文を参考にして次のように記述することとしました。
(defun ptarai (x y z)
(the <fixnum> x)(the <fixnum> y)(the <fixnum> z)
(if (<= x y)
y
(pcall ptarai (tarai (- x 1) y z)
(tarai (- y 1) z x)
(tarai (- z 1) x y))))
(defun pcount (n)
(plet ((a (count 1 (div n 2)))
(b (count (+ (div n 2) 1) n)))
t))
(defun count (m n)
(if (= m n)
t
(count (+ m 1) n)))
pcallは (pcall fn arg1 arg2 ...argn) という形式です。arg1,...argnをスレッドで起動、マルチコアで実行します。
pletはlet構文のマルチスレッド版です。式の部分をスレッドに分解して実行し、これをjoinで待機したのちにbody部を実行します。
余談ですが、EISLは型推論器をもっており、the構文により必要な情報を与えると最適化するようにしてあります。たらい回しのような単純な再帰コードの場合、C言語波の実行速度を出すことができます。
計測
インテルicore5で計測しました。Windows WSLで実行しています。
予想に反して並列のpfibの方が逐次のfibより若干遅いのでした。pthreadの設定の問題だろうか？などChatGPTに相手になってもらいかなり試行錯誤したのですが、残念ながら並列の方が遅くなっています。ARMラズパイ４００では並列の方が高速になっています。たらい回し、竹内関数の場合にはその再帰パターンは複雑なのでなかなか並列での性能が上げられないでいます。スレッドに分割するコストを考えても2倍くらいは高速になると予想していたのですが。ちょっとがっかり。
CPUによる違い
英語版Reddit/Lispには凄腕Lisperがた出入りしているように思いました。記事を投稿し、いくつか助言をいただきまいした。改良の余地はあるかもしれません。また、コンカレントGCと並列動作とかまだ共存できずにセグフォを起こしています。並列動作を理解しつつじっくりデバグしています。
インテル、AMD、ARM それぞれ設計方針が異なるようで並列動作したときのパフォーマンスが異なります。ARMの方が並列で効果を出せています。インテルicoreは単一スレッドの高速性を重視しているのかもしれません。
EISLはGithubにおいてります。よかったらお試しください。
https://github.com/sasagawa888/eisl