Emacs の master ブランチに来たスレッド機能についての雑なまとめ

メモ的な感じ。

実装の概要

  • make-thread によってスレッド開始
  • thread-yield で別スレッドにスイッチ
  • thread-join で待ち合わせ

  • make-mutex で mutex 作成

  • with-mutex とかで排他制御
  • make-condition-variable で condvar 作成
  • condition-wait, condition-notify でスレッドの制御

  • グローバルの状態を共有

  • スレッドごとに local, dynamic variable, current buffer, match data は独立

  • GILがあって、同時にひとつしか動かない。

  • 基本はユーザーが thread-yield する協調スレッド動作で、thread-yieldかIOかイベント待ちでスレッド切り替え
  • ただし、fine-grained な制御を想定して設計しているので、現在の協調スレッドの動作に依存しないように注意すべしとのこと。

動作確認したいけど、ちょっと動かすとすぐ落ちるのでなかなか難しい。(追記 2016/12/18 の先端では落ちなくなった。まだいろいろ調整中の模様。)

後方互換性の問題

仕様や機能を追加した際に、既存のコードが壊れない方がうれしい。 特に、Emacsは長年の資産が重要なので、互換性を壊すコードにはそれなりの動機が必要なはず。 実際に、これまでも滅多なことでは過去の動作を変えていないし、大抵長期間の移行措置がある。cl-libとかいろいろ。

make-thread は既存のコードをカジュアルに並行化出来てしまう。 以下のマクロは実際にMLに投稿されたもので、既存の関数を別スレッドで動かそうというもの。gnusというニュースリーダーで使ったところ、UIが固まらなくて便利だったとのこと。 *1

この例のマクロでは、一見排他制御があるように見えるが、もともとの関数を呼ばれると2重に起動されてしまう。 グローバルの状態を共有するため、同時に動作しうる箇所にはもれなく排他制御などが必要。

何も触っていない既存のコードについても、IOがからむ箇所は同様に重複して呼ばれる可能性がある。 特に、上の例のようにIOで遅い箇所は積極的にスレッドで呼ばれる可能性があるため、呼ばれそうなところをもれなくチェックして、必要なら排他制御を入れる。 つまり、スレッドを使うと既存のコードが何もしなくても壊れる。

排他制御がないと、大体何となく動くけど、たまに落ちる、動いてるけどバッファとかが見えてないところで壊れるなどが起きる。 中途半端に動いてデータがこっそり壊れてたり、再現がなかなか出来ないバグがとにかくつらい。

問題を解決しない

現在の実装では同時に1スレッドしか動かないので、CPUが原因で固まる問題は解決できない。 複雑な構文解析や巨大なファイルのシンタクスハイライトで文字入力の度に固まるような問題は解決できない。

IOが原因でUIが固まる問題については解消される場合がある。上の例ではgnusがそうだった。

しかしながらスレッドが無い現状でも、IOで固まる問題は既存の非同期IOのインタフェースを使えば解決できる*2。 orgやgnusぐらいでかいと非同期プログラミングで書きなおすのは大変だけど、どうせ後方互換性が壊れるのであれば、既存のコードを書き直す方が良いかもしれない。フリーランチは無い。 *3

そもそも非同期プログラミングは、コールバックとかのプログラムの書き方が難しいのではない。 並行処理をまともに動かすことが難しいのであって、同期的に書けることはあまり解決になってない。 シングルスレッドな設計のまま安易に排他制御を入れると、ロックだらけになってロック漏れやデッドロックでつらいはず。 *4

あと、個人的には協調スレッド動作を止めれてもGILが外せるとは思えないので、完全なマルチスレッドは来ないのではないかと考えている。 *5

その他の問題

mutex でロックするにしても、知らない mutex ではロックできない。 複数の mutex が関わると容易にデッドロックする。mutex 一つでも間違えるとデッドロックする。 ロックを使うパッケージは自由に合成できない。別々なら正しくても、混ぜると壊れることがある。

他のスレッドAPIのある言語がそうであるように、各関数のドキュメントにスレッドセーフかどうか明記する必要がある。

このAPIの上に行儀の良いラッパーをかぶせても解決できない。 グローバル共有なので全員がラッパーを使って、ルールを守ったプログラムにする必要があるが、恐らく不可能。 ドキュメントは読まれないし、ルールは守られない。

他の言語(JavaとかRubyとかPythonとか)ではプリミティブなスレッドAPIでも上手くやってるように見えるかもしれない。 これらの言語では、基本的にプロジェクトごとに並行系ライブラリを選ぶことが出来たり、マルチスレッドプログラミングの方針を統一できるので、ましな方法で統一させることが出来る。そもそも異なる制御方針のライブラリは無理やり混ぜても大体動かない。 Emacsでは、どのパッケージをまぜて使いたいかというのは開発者ではなくユーザーが選べるべきであるので、マルチスレッドの管理方針が違うくらいでパッケージが混ぜられないというのは避けたほうが良い。 だから、なるべくお互いに影響を与えないようなしくみが望ましい。

どうすればよかったか?

後方互換性が壊れず、問題も解決する(ちゃんと同時に複数実行が出来る)手法があると考えている。

ブラウザの WebWorker や、golang の goroutine/channel などがお手本になりそう。 グローバルやスレッドセーフでないオブジェクトを共有せず、完全に並行で動かして、通信(イベントやチャネル)でデータを共有する。 パフォーマンスの問題や、バッファの共有をどうするか、ライブラリはどうするかなどいろいろ考える必要はあるが、WebWorker の Transferable Object の仕組みのように、個別に対応して落とし所を探っていく進め方になると思う。 安全な仕組みをちゃんと作るのは大変そうだし、現在のEmacsの実装で可能かどうかはよく分からない。検討したけどやめたのかも知れない。 *6

この方法で上手く設計できればスレッド間の排他制御のためのロックが必要なくなるので、ロックなどの問題からも解消される。 メモリは独立なので後方互換性も壊れないし、独立して動くのでCPUで詰まる問題も解消出来る見込みが出来る。

時代遅れと指摘されているのは、すでにこのような仕組みが他の言語で取り入れられて実装されているにもかかわらず、問題が多いとわかっているメモリ共有で thread と mutex による制御を取り入れたこと。 *7

アクターモデルやイミュータブルデータモデルなど、マルチコアの時代になって、ロックを使わない並行プログラミングが広まっている。 ただし、シングルスレッドを前提にした単純なプログラミングモデルのまま移行は出来ないので、並行プログラミングの設計を身につける必要がある。

もちろん、プリミティブなthreadやロックによるプログラミングを全て否定するわけではない。 マルチコアを使い切るようなアプリケーションや、処理系の実装などの低レイヤーのプログラミングなど、それが必要とされる分野もある。 *8

大騒ぎするほどでもないのではないか

ちゃんと議論を全部追ったり、コードを全部見たわけではないので、自分が盛大に勘違いしてることがあるかも知れない。

また、現実的にはあまり make-thread するようなコードを書く人なんていなくて、全く問題が発生しない(報告されない)かも知れない。 実際、MLで「いやいや並行制御は大変なんですよ」って書いたら、Emacsでそんなガチ制御なんて必要ないと思うよと返ってきた。

あるいは、メインメンテナのみなさんによるスーパーテクノロジーで、今後なにかすごい進化が起きるのかも知れない。

とにかく、今は自分が本体に十分コミットできる状況ではないので、この流れを見守りたい。 *9

*1:そうとうやばいコードのはずなのに並行性について指摘がないことにびっくりしてたけど、あとで同様にびっくりした人から並行性についてのコメントが付いててちょっと安心した。

*2:同期的コードを非同期インタフェースで書き直す話 非同期と継続と私 - 技術日記@kiwanami

*3:フリーランチについて、例えば 後藤弘茂のWeekly海外ニュース など

*4:deferred.el について補足いろいろ - kiwanami の

*5:そもそも協調スレッドをやめるのなら、IO以外でも割り込まれるわけなので、そこら中に排他制御を入れる必要がある。つらそう。

*6:2014年の段階ではブランチを作った本人は非共有状態でメッセージパッシングがいいという議論をしていたという話がある。concurrency and emacs - a surprising next step

*7:A Blast From The Past: The Tale Of Concurrency In Emacs - Sebastian Wiesner

*8:O'Reilly Japan - 並行コンピューティング技法

*9:でも、こういう問題を見ると、それ cc:semaphore で…とかすでにcacoo.el で通ったしとか、いちいち思ったりする。

deferred.el について補足いろいろ

こちらの記事:deferred.elでHTTP通信を非同期化する やこちらの記事:Org-modeとToodledoを連携させるorg-toodledo.elを非同期実行に対応させましたを見て大変感動いたしまして、deferred.el 作った人としていくつか補足したいと思い、この記事を書きました。

deferred.el 情報、サンプルコード

まず、ドキュメントやサンプルコードが少ないという問題ですが、自分の力不足で申し訳ありません。今のところ、まとまっている情報は以下です。

あとは、MELPAで deferred.el への依存を調べてコードを読むというのもあります。

非同期/同期コードの分離、デバッグ

deferred.el は async.el のような一箇所だけ非同期で動かすようなツールと違って、小さな非同期タスクをつなげて大きな処理を組み立てるという目的のライブラリです。 そのため、書いてるうちに非同期タスク連鎖が長くなってしまって、さらにエラーのわかりにくさと合わさってデバッグが大変になることがあります。

そこで、ぜひおすすめしたいのは、deferred関数による非同期タスクの連結部分と、同期的な実務処理を分けることです。具体的には以下のようです。

;; 同期処理の関数を定義
(defun some_task_function_1 (arg)
    :
    result
)

(defun some_task_function_2 (arg)
    :
    result
)

;; 非同期処理をつなぐ部分
(deferred:$
  (deferred:process "some_command")
  (deferred:nextc it some_task_function_1)
  (deferred:nextc it some_task_function_2)
    :
)

some_task_function_1some_task_function_2 は、前の結果を受け取って何か処理を行う同期的な関数です。普通の関数ですので、通常のテストを書いたり scratch バッファで試すことも出来ます。また、 edebugブレークポイントを仕掛けてデバッグすることも出来ます。

このように分離しておくことで、deferredの連鎖は制御構造に集中できますし、見通しも良くなります。

concurrent.el の利用を検討する

deferred.el を使うことで、同期で書いていた処理を非同期な処理に機械的に書き換えることが出来ます。多くの問題はこれでほとんど解決します。

しかしながら、非同期の処理流れが並行して動いて、しかも協調的に動作(いわゆるマルチスレッド)することが求められる場合、このやり方では解決できなくなります。同期的なプログラミングスタイルのまま、安直な協調の方式としてグローバル変数を使ったフラグ制御をやりだすと、各地の処理がグローバルな状態に依存してしまうため、大きな処理を書くとすぐに破綻します。

そういうケースでは並行プログラミングの設計を行う必要があるのですが、大抵の場合、並行動作を想定せずに書いた既存のコードは大幅な書き直しになります。並行プログラミングについて復習してがんばりましょう。

並行処理の設計を行うと、並行プログラミング特有の汎用的な部品が欲しくなります。いくつかの部品を concurrent.el に用意しました。例えば、golangのchannelに対応するものとして cc:signal があったり、外部プロセス数の制御用として cc:semaphore があります。あとはqueueとかあると良さそうですよね。

設計のポイントとしては、処理の流れでプログラムを組み立てるのではなくて、データの流れを考えてその通り道を並行プログラミングの部品でつなげていくという感じになります。

評価タイミングの意識

deferred.el を使うと、実行タイミングの意識が大事になって来ます。具体的には以下のタイミングがあります。

  • コンパイル時(マクロ展開のタイミング)
  • 関数実行時
  • deferredタスク実行時

コンパイルはあんまり気にしなくても大丈夫だと思いますが、deferred関数と一緒に独自マクロを使いたい場合は評価順序に気をつける必要があります。

関数実行時が通常意識する実行タイミングです。静的なdeferredの連結はこのタイミングで行われます。

deferredタスク実行時は、deferredで作ったタスクが実際に実行されるタイミングで、上の関数実行時とは別のタイミングです。

はまりどころとしては、非レキシカルスコープ変数を参照しようとして未定義変数アクセスでエラーになるとか、実行時に評価されるはずが間違ってdeferredタスク実行時に評価されていたとか、カレントバッファとかポイント位置が実行時とdeferredタスク実行時で違うとかがあります。

レキシカルスコープ問題

実行時の値をdeferredタスクに透過的に渡したい場合は、レキシカルスコープ変数を使います。

Emacs 24 以上であれば、ファイル先頭の lexical-binding: t で有効になります。Emacs 23 以下で動かす必要がある場合は (require 'cl) して lexical-let を使います。

deferred.el本体は lexical-let で書いているのですが、clライブラリは Emacs 24 ぐらいから非推奨になっているので、今後どこかのタイミングで本体最新版をlexical-bindingで書き換えて、Emacs 23 以下のサポートを切り離す計画があります。

再利用問題

JavaScript の Promise は resolve複数回呼ぶことが出来ませんが、値を先に resolve した後からでも then をつなげることが出来ます。

deferred.el が参考にした JSDeferredcall (Promiseのresolveに相当) を何度も呼ぶことが出来ますが、next で先にタスクをつなげておかないと、値が流れて無くなってしまいます。

これは設計の違いですので、どちらが正しいというものではないと思います。

deferred.el は、 deferred:callback-post (Promiseのresolveに相当) を何度も呼ぶことが出来ますし、後から deferred:nextc でタスクをつなげることも出来ます。ただし、2度目以降の deferred:callback-post によって初回の値が上書きされますので、基本的にはdeferredタスクが何度も呼ばれないような作りにしておくのが安全です。

キャンセル問題

deferred:cancel は、意図通りに動かない場合があります。

実際にキャンセルの処理が動くのは deferred:wait などのタイマー、 deferred:processなどの外部プロセス、 deferred:url-retrieveなどで直接返ってきたdeferredオブジェクトだけです。

他の一般のdeferredオブジェクトのcancelは、呼ばれたdeferredオブジェクトより下流に値が伝搬しないように、タスクの連鎖を切るという実装になっています。ですので、deferredタスクの連鎖の仕方とcancelを呼ぶ対象によっては、cancelを呼んでも副作用が止まらない場合があります。

確実に副作用をキャンセルさせたい時は、プログラマが自分でキャンセル処理を書く必要があります。

deferred:do マクロの予定

JSだとメソッドチェーンで非同期タスクを楽につなげていけるのですが、 deferred.el ではメソッドチェーンが使えないので deferred:$deferred:nextc でタスクをつなげていく方法にしました。

ClojureのThreadマクロのように書けるとかっこ良かったのですが、タスクを入れ子にするなどの複雑な構造が扱いづらかったり、また見た目的にタスク間のつながりが把握しづらいように思ったので、当時は採用しませんでした。そこで、itを毎回書くことでタスクの接続位置を明確にできる(と思った)現在の方法を採用しました。

この方法は冗長なのでもっと短く書ける方法を試行錯誤した結果、edbi.elで使ったedbi:seqが良かったので、このマクロを deferred:do として採用するつもりでいます。

deferred:doの例:

;; シェルを順番に実行して結果を加工して、最終的にエコー領域に表示する。
;; (※deferred:doはまだありませんが、edbi:seqと同じです)
(lexical-let (aa bb)
  (deferred:do
   (aa <- (deferred:process-shell "ls /var | wc -l"))
   (bb <- (deferred:liftd length (deferred:process-shell "ls /lib")))
   (lambda (x) 
     (message "var: %s / lib: %s" aa bb))))

おわりに

とりあえず、ざっくばらんに書きました。 皆様の deferred.el ライフ向上の参考になれば幸いです。