SyntaxHighlighter

2017年4月23日日曜日

Pausable Unittest その2 (開発の経緯)

Pausable Unittest その2 (開発の経緯)

概要

今回は、なぜ Pausable Unittest を Stackless Python のライブラリとして作成したかについて書いておこうと思います。

なお、ここで言及している Python は、基本的には Python 2.7 での話です。
最新の Python 3.5, 3.6 系列ではやや異なっているかもしれません。

Pausable Unittest 実現に必要な機能

Pausable Unittest では、以下のようなスクリプトを書くことを目的としています。

この中で重要なのは、(*1) の部分で Python インタプリタを終了し、システムを再起動した後で、続きを実行できるところです。

これを実現するためには、「関数の実行の中断と、その状態の保存/復元」が必要になります。
self.reboot() では、実行中の関数 test_check_reg を中断し、そのローカル変数の状態やどこまで実行したかの状態を含めて保存し、再起動後に復元する必要があります。

generator, fiber, coroutine, continuation

そこで、この機能を実現するために必要な要素技術は何か、について、検討をしました。
その結果、ジェネレータファイバーコルーチン継続などを、ファイルに保存し、あとで復元できればよいという考えに至りました。

ジェネレータ、ファイバー、コルーチン、継続は、いずれも「関数のようなものを途中で中断し、他に制御を移すことができる」という機能を持っています。

例えば、 JavaScript で書いたジェネレータでは、下記のようになります。

上記の例では、1, 2, 3, ..., 5 の順で数字が出力されます。
つまり、g.next() でジェネレータ gen に制御を移し、 yield で制御を戻す、といった流れになります。

これは、関数のような genyield によって中断できていることになります。

なお、 JavaScript ではジェネレータを定義する際には通常の関数と異なり function* を用いますが、 Python では「関数の中に yield があればジェネレータ」となっています。

参考までに Ruby のファイバーは下記のようになります。

こちらも同様に、1, 2, 3, ..., 5 の順で数字が出力されます。

このように、ジェネレータやファイバー (やコルーチン) には、「処理を中断し、処理を他に移すことができる」という特徴があります。

あとは、途中まで実行したジェネレータやファイバーを、ファイルに保存できればよいことになります。
先に挙げた Ruby の例では、下記のようなことができるとよいわけです。

しかし、これは Marshal.dump に失敗し、例外が送出され、うまく動作しません。

通常の Python でジェネレータを使って同様なことを書くと、やはりジェネレータを pickle できず、同様にうまく動作しません。

Stackless Python を選んだ経緯

通常の Python や Ruby で実現できない理由

通常の Python や Ruby で実現できないのは、もちろん「ジェネレータやファイバーをファイルに保存できないから」です。
これは、ただ未実装なわけではなく、技術的に実装が困難だからです。

Python や Ruby でのメソッドの呼び出され方

通常の Python や Ruby では、メソッドの呼び出し時にスタックが消費されます。
例えば、下記のような Python のスクリプトを考えます。

この関数 foo は、バイトコンパイルの結果、以下のようなバイトコードに変換されます。

Python は、与えられたソースコードを上記のようなバイトコードの変換した後、実際に処理を行います。
このとき、各行の命令を実行していくわけですが、ここで関数呼び出しの OpCode である CALL_FUNCTION がどのように処理されるかに注目してみます。

Python での CALL_FUNCTION の処理

現在の Python や Ruby では、ソースコードをバイトコードにコンパイルした後で、それを仮想マシン上で実行するようになっています。
Python の場合、上記のようなバイトコードに変換した後で、実行していきます。

「関数の呼び出し」の場合、通常は CALL_FUNCTION という OpCode に変換されます。
その後、実行時に ceval.cPyEval_EvalFrameEx 関数の中の switch 文で解釈されて実行されます。
Python 2.7.10 のコードを一部だけ抜き出すと、下記のようになっています。

このように、関数の実行そのものは call_function に委ねられ、処理が続けられます。

call_function では、いくつかの条件によって処理が分岐していきますが、間接的に PyEval_EvalFrameEx 関数が呼ばれます。
たとえば、ある条件下では fast_function が呼ばれますが、その中を追っていくと、条件に応じて PyEval_EvalFrameEx が呼ばれるのが分かります。

つまり、 Python インタプリタでは、 Python の関数呼び出しを Python 仮想マシンが実行する際に、 PyEval_EvalFrameEx の再帰呼び出しが発生し、その結果、スタックが消費されていることが分かります。

スタックが消費されることによる影響

スタックが消費される実装になっている場合、関数の状態を復帰させるのが非常に困難になります。

C 言語でのスタックの使い方は完全にコンパイラに依存しています。
例えば、スタック上には種々のローカル変数が配置されますが、それらをダンプしたり、復旧させたりする手段は、 C 言語には提供されていません。
もちろん、環境や OS 依存な方法を使ってスタックをダンプすることはできますが、ダンプしたスタックをそのまま復旧しても、状態が正しく復元されるわけではありません。
スタック上には種々の変数のアドレスなどがある場合もありますが、スタックがダンプされたときと復旧させた時で同じアドレスが使われるとは限らないからです。

そのため、スタックがある程度消費された状態を復元するのは、困難なものになります。

Stackless Python での CALL_FUNCTION の処理

一方で、 Stackless Python では、以下のようにやや処理が異なっています。

このように、 STACKLESS マクロに応じて、goto によるジャンプなどがはさまっています。

Stackless Python では、 call_function の中では、 Python の関数呼び出しは行わず、すべての処理が PyEval_EvalFrameEx のループに戻ってから行われるように工夫されています。
俗に「トランポリン呼び出し」と呼ばれるような方法に近い実装がされています。

その結果、 Stackless Python では、(一部の例外はありますが) Python の関数呼び出し時に、原則として再帰呼び出しが行われません。

こうした実装上の工夫や、 prickelpit.c などで追加されている pickle に関する処理により、 Stackless Python ではジェネレータを pickle することが可能となっているようです。

Stackless Python を選択する

主に、これらの技術的な理由により、個人的に好みの Ruby ではなく、 Stackless Python を選ぶことにしました。
また、 PyPy でも、同様にジェネレータを保存できるので、 Python を選んでおけば、仮に将来的に Stackless Python の開発が止まっても、ある程度の代替案が確保できるだろうという目論見がありました。

おそらく、 Scheme や Lua などでも同様のことができるのかもしれませんが、こういった理由により、 Pausable Unittest を実装する言語として、 Python を選択しました。