目次


魅力的なPython: Pythonジェネレーターで「無重量スレッド」を実装する

マイクロスレッドのパワー

Comments

マイクロスレッドの領域というのは、少なくともPythonでは、Stackless Pythonのための一風変わった拡張でありました。Stacklessの話題およびStacklessが近年経てきた変遷は、おそらくそれだけで1つのコラムにすることができることでしょう。ただ早い話、「新生Stackless」では、「継続」は明らかに関心外であり、マイクロスレッドこそが、このプロジェクトの存在意義(raison d'être) となっています。分かりにくい話なのですが。

とはいっても、まずは少し話をさかのぼってみることにしましょう。マイクロスレッドとは何物なのでしょうか。マイクロスレッドとは、基本的に、固有のごくわずかなリソースを使って実行可能なプロセスのことで、Pythonインタプリターの単一インスタンスの中で実行されます(共通メモリー空間などの中で)。マイクロスレッドの場合、現在の中程度の性能のPCでプロセスを並行して何万個も実行することができ、1秒に何十万回もコンテキストの切り替えを行うことができます。これは、fork() 呼び出しやOSの標準的なスレッド生成呼び出しでは、及びもつかない数字です。「軽量」と言われているスレッド生成ライブラリーでも、ここに掲げた数字よりも何桁も重いスレッドになります。

このコラムで私が紹介する無重量スレッドは、OSのスレッドとは少しの意味合いが異なります。また、無重量スレッドは、Stacklessによって実現されるものとまったく同じだということでもありません。無重量スレッドは、ほとんどの点で、同様のたいていの仕組みよりもかなり単純化されており、セマフォー、ロックなど、ほとんどの問題は姿を消しています。この簡潔さの代価が、私が「協調的マルチスレッド化」という形式で提示するものです。標準的なPythonのフレームワークの中で強制排除 (preemption) を追加するというのは、私には実現できないように思われます (少なくともStackless Python 2.2以外では。__future__ が何をもたらすかは、誰にもわからないことです)。

ある意味では、無重量スレッドは、WindowsやMacOSのかつてのバージョンにあった(1個のアプリケーションの中での) 協調的マルチタスキングを思い出させます。しかし、他方で、無重量スレッドは、プログラムの流れを表現する別の方法にすぎません。無重量スレッドが行うことは、すべて、少なくとも原理的には「ものすごく大きなif/elifブロック」の技法を使って実現可能なことです(これは力づくのプログラマーの最後の砦ですが)。

コルーチンのおさらい

以前このコラムで、簡単なジェネレーターでコルーチンをシミュレートするメカニズムを紹介したことがありました。その中心部分のメカニズムは、いたって単純なものです。1群のジェネレーター・オブジェクトが、制御の流れを適当な分岐へ委譲することを制御する関数、scheduler() 、の中にラップされているというものでした。scheduler() 関数との間でしか分岐の制御を行わないという意味では、これらは本当のコルーチンではありません。しかしながら、実用上は、余分なコードをほとんど追加することなく同じことを実現できます。scheduler() は、以下のようなコードとなります。

リスト1. コルーチンをシミュレートするためのscheduler()
def scheduler(gendct, start):
    global cargo
    coroutine = start
    while 1:
        (coroutine, cargo) = gendct[coroutine].next()

このラッパーで注目すべき点は、それぞれのジェネレーター / コルーチンが、ブランチ先としたいアドレスと合わせて1個の組 (tuple) を形成しているという点です。基本的に、ジェネレーター / コルーチンは、GOTOターゲットを伴います。私は、便宜上、コルーチン間で受け渡されるデータを形式化するための1つの方法として、ジェネレーターでcargo という標準的なコンテナーも作成するようにしていますが、合意の上で使用されるグローバル変数やsetter/getterというようなコールバック関数を使ってデータの受け渡しを行ってもかまわないでしょう。Raymond Hettingerは、受け渡しされるデータを効率よくカプセル化できるようにすることを意図してPython Enhancement Proposal (PEP) というものを記述しており、ひょっとすると、将来のPythonは、そうした機能を備えるようになるかもしれません。

新しいスケジューラー

無重量スレッドに対する要求仕様は、コルーチンのものとは少し異なりますが、それでも中心部分にscheduler() 関数を使用することができます。異なる点は、ジェネレーター / コルーチンからブランチ・ターゲットを受け取るのではなく、スケジューラー自身がブランチ・ターゲットを決定しなければならないという点です。完全なテスト・プログラムとサンプルは、以下のようなものとなります。

リスト2. サンプル・スクリプトmicrothreads.py
from __future__import generators
import sys, time
threads = []
TOTALSWITCHES =10**6
NUMTHREADS    =10**5
def null_factory():
def empty():
while1:yield None
return empty()
def quitter():
for nin xrange(TOTALSWITCHES/NUMTHREADS):
 yield None
def scheduler():
 global threads
 try:
 while1:
for threadin threads: thread.next()
except StopIteration:
 pass
if __name__ =="__main__":
for iin range(NUMTHREADS):
         threads.append(null_factory())
    threads.append(quitter())
    starttime = time.clock()
    scheduler()
print"TOTAL TIME:    ", time.clock()-starttime
print"TOTAL SWITCHES:", TOTALSWITCHES
print"TOTAL THREADS: ", NUMTHREADS

これは、考え得る無重量スレッド・スケジューラーの中で、ほとんど最も簡単なものでしょう。すべてのスレッドが、固定した順に登録され、まったく同じ優先順位をもっています。次に、この込み入ったからくりを解き明かしてみましょう。以前の回で解説したコルーチンの場合と同様、無重量スレッドを記述するときは、いくつかの約束ごとに従う必要があります。

複雑な話

ほとんどの間、無重量スレッドのジェネレーターは、while 1: ループの中を走っているはずです。このリストのようなスケジューラーの構成方法では、1個のスレッドが停止すると、スケジューラー全体が停止することになります。これは、ある意味では、OSのスレッドよりも「堅固」でないことになりますが、scheduler() のループの中で例外をキャッチするほうが、ループの外でキャッチする場合よりも、余分な仕掛けをたくさん必要としません。さらに、スレッドが (自分自身で終了するか、別のスレッドによって終了させられるかして) 終了しなくても、そのスレッドをthreads リストから削除することができます。実際には、スレッドの削除を簡単に行うための管理は行っていませんが、これを素直に拡張するなら、スレッドを、リストではなく、ディクショナリーか何かのデータ構造に保存することになるでしょう。

上の例は、スケジューラーのループを最終的に終了するための1つの合理的な技法を示しています。特別なジェネレーター / スレッドであるquitter() が何らかの条件 (上の場合、コンテキスト・スイッチの回数) を監視し、その条件に合致したときにStopIteration をスローします (この例では、他の例外はキャッチされません)。終了後も、他のジェネレーターは、すべて、まだ生きており、必要なら、後で (マイクロスレッド・スケジューラーか何かで) 再開させることもできます。もちろん、必要なら、これらのジェネレーター / スレッドを削除することもできます。

上記の例では、とくに意味のないスレッドを使用しています。これらのスレッドは何もしません。何もしないことで、最小限の形式にしています。上の例をこのように組み立てているのは、要点、すなわち無重量スレッド自体のオーバーヘッドが非常に小さいということを説明するためです。64 Mバイトのメモリーしか搭載していない昔のPentium IIのWindows 98ラップトップ・マシンで無重量スレッドを10万個生成しても何の問題もありません (100万個のスレッドを生成すると、ディスクが長い時間激しく揺れ動くようになる)。OSのスレッドでこれを試してみてください。また、このかなり遅い366 MHzのチップで、100万回のコンテキスト・スイッチを約10秒で実行することができます (コンテキスト・スイッチに関与するスレッドの数が、この時間にとくに重要な意味をもつわけではない)。当然ながら、実際の無重量スレッドは、何らかの仕事をするわけですので、そのタスクに応じて、もっと多くの資源を使用することになるでしょう。しかし、スレッド生成自体は「無重量」と形容できます。

スイッチングのオーバーヘッド

無重量スレッド間のスイッチングは低コストですが、それでもまったく無料というわけにはいきません。この問題をテストするために、ある程度の仕事を実行するサンプル・コードを作成してみました。ある程度の仕事とはいってもスレッドで実行させるのにふさわしい程度の最小限に近い仕事です。スレッド・スケジューラーは、実際には「do A, then do B, then do C ...」といった命令になるわけですので、メイン関数の中で全体が並行動作する例を作成するのは難しいことではありませんでした。

リスト3. サンプル・スクリプトoverhead.py
from __future__ import generators
import time

TIMES = 100000
def stringops(): for n in xrange(TIMES): s = "Mary had a little lamb" s = s.upper() s = "Mary had a little lamb" s = s.lower() s = "Mary had a little lamb" s = s.replace('a','A') def scheduler(): for n in xrange(TIMES): for thread in threads: thread.next() def upper(): while1: s = "Mary had a little lamb" s = s.upper() yield None def lower(): while1: s = "Mary had a little lamb" s = s.lower() yield None def replace(): while1: s = "Mary had a little lamb" s = s.replace('a','A') yield None if __name__=='__main__': start = time.clock() stringops() looptime = time.clock()-start print"LOOP TIME:", looptime global threads threads.append(upper()) threads.append(lower()) threads.append(replace()) start = time.clock() scheduler() threadtime = time.clock()-start print"THREAD TIME:", threadtime

無重量スレッド版は、直線的なループ版の2倍強の時間実行されること、すなわち上記のマシンで3秒弱対6秒強という値になることが判明しました。もちろん、それぞれの作業単位が、文字列1個のメソッド呼び出しの2倍とか10倍とか100倍だったとすると、スレッドのオーバーヘッドに費やされる時間の割合は、作業の大きさに応じて小さいものになります。

スレッドの設計

無重量スレッドは、1個の概念的な処理よりも大きな規模のものにすることが可能であり、またそうするのが普通です。どんな種類のものであれ、スレッドは、1個のタスクまたは活動を表すのに必要なフロー・コンテキストの分量を表すのに使用されます。しかしながら、タスクは、1個のスレッド・コンテキストの中で費やしたい時間やサイズよりも大きくなりえます。この問題は、アプリケーション開発者がとくに何か介入しなくても、優先順位設定 (preemption) によって自動的に処理されます。残念ながら、無重量スレッドの場合、ユーザーが、他のスレッドと「うまく協調する」ことに注意を払う必要があります。

最低限、無重量スレッドは、概念的な処理を1つ完了したら必ずyield する (制御を譲る) だけの思いやりがなければなりません。スケジューラーは、またそのスレッドに戻ってきて、次の段階の処理を行えるようにします。たとえば、以下のようにです。

リスト4. 擬似コード - フレンドリーな無重量スレッド
def nicethread():
    while 1:
        ...operation A...
        yield None
        ...operation B...
        yield None
        ...operation C...
        yield None

良く設計されたスレッドは、しばしば、基本的な処理の区切りでだけでなく、もっと頻繁にyield するようにします。概念的に「基本的」だとされる処理には、よく、大きなコレクションに対するループが含まれます。そのような場合 (そのループ構文がどの程度時間を消費するかによりますが)、たぶんそのループ構文の中にyield を1個か2個入れる (おそらくループの繰り返しが一定回数実行されるつど入れる) のがよいでしょう。プリエンプティブ・スレッドの場合と異なり、行儀の悪い無重量スレッドは、無制限にプロセッサーを独り占めすることが可能です。

残りのスケジュール

これまでの例は、スレッド・スケジューラーの最も基本的なスタイルを示すものばかりでした。スレッドでは、もっといろいろなことができそうです (これは、良いジェネレーター / スレッドを設計することとは、まったく独立した問題です)。ついでに、拡張できそうなことをいくつか示してみたいと思います。

スレッド管理の改良

簡単なthreads のリストを設けることで、スケジューラーで処理されるジェネレーター / スレッドの追加が簡単になります。しかし、このデータ構造は、実行する必要のなくなったスレッドの削除や停止 (suspend) を簡単化するようなことは何もやってくれません。スレッド管理用のデータ構造には、ディクショナリーやクラスのほうが適しています。簡単な例として、これまでのサンプル・コードのthreads リストの代わりとして (ほぼ) ぴったりのクラスを以下に示します。

リスト5. スレッド管理を行うPythonのクラスの例
class ThreadPool:
"""Enhanced threads list as class
    threads = ThreadPool()
    threads.append(threadfunc)  # not generator object
    if threads.query(num) <<has some property>>:
        threads.remove(num)
    """
    def __init__(self):
          self.threadlist = []
          self.threaddict = {}
          self.avail =1
    def __getitem__(self, n):
return self.threadlist[n]
def append(self, threadfunc, docstring=None):
# Argument is the generator func, not the gen object# Every threadfunc should contain a docstring
          docstring = docstringor threadfunc.__doc__
          self.threaddict[self.avail] = (docstring, threadfunc())
          self.avail +=1
          self.threadlist = [p[1]for pin self.threaddict.values()]
return self.avail-1 # return the threadID
    def remove(self, threadID):
del self.threaddict[threadID]
          self.threadlist = [p[1]for pin self.threaddict.values()]
def query(self, threadID):
"Information on thread,if it exists (otherwise None)"return self.threaddict.get(threadID,[None])[0]

もっといろいろなことができるでしょうが、手始めとしては、こんなものでしょう。

スレッドの優先順位

これまでの簡単なサンプル・コードでは、すべてのスレッドが、スケジューラーから同じ数のアテンションを入手していました。スレッドの優先順位システムにさらに細かい調整を施すには、少なくとも2通りの一般的な手法があります。優先順位が1種類だけのシステムでは、「高い優先順位」のスレッドに低い優先順位のスレッドよりも、多くアテンションを上げることしかできません。これを素直に実現するとすれば、PriorityThreadPool(ThreadPool) という新しいクラスを作成し、スレッドの反復 (iteration) の際に、重要なスレッドのほうを多く返してもらうようにするということになるでしょう。このような非常に単純な方法を用いる場合、その.__getitem__() メソッドで、いくつかのスレッドを連続的に複数回返すことになるかもしれません。したがって、優先順位の高いスレッドは、「タイム・スライス」を単に1回受けるのではなく、2回とか10回とか100回とか連続的に受けることになるでしょう。これを (ほんの少しながら) ひねった「リアルタイム」バージョンとしては、スレッド・リストの随所に重要なスレッドのコピーを多数登録しておいて、それを返すという手もあるかもしれません。この方法だと、優先順位の高いスレッドに対するアテンションの全体の回数を増やすだけでなく、それらのスレッドに対して行う実際のサービスの回数を増やすことになるでしょう。

スレッドの優先順位を扱うための、もっと洗練されていると思われるもう1つの方法があるのですが、この方法は、純粋なPythonでは簡単に利用することはできません (特定のOSやプロセッサーに対応したサード・パーティのライブラリーを使えば可能)。スケジューラーは、単に優先順位の高いスレッドにタイム・スライス数を整数値として指定するのではなく、各無重量スレッドで消費された時間を測定し、スレッドのスケジューリングを動的に調整して、過少にサービスを受けているスレッドをもっと公平に扱うようにすることも可能です (公平さというのは、スレッドの優先順位と関係してくるでしょう)。残念ながら、Pythonのtime.clock() およびそのファミリー関数は、この方法を有効に利用できるだけの充分高い分解能のタイマーとはなっていません。他方、「複数タイム・スライス」法で過小評価されているスレッドが自分自身の優先順位を動的に高くするのを防ぐ手立てもありません。

マイクロスレッドとコルーチンとの組み合わせ

無重量スレッド (マイクロスレッド) のスケジューラーを作成するために、私は、コルーチンの「ここにブランチしてきてください」というロジックを除外しました。実際には、そうする必要もありませんでした。これまでのサンプル・コードに出てきた無重量スレッドは、ジャンプ・ターゲットにではなく、必ずNone に制御を移していました。しかし、この2つの考え方を組み合わせてはならない理由はありません。コルーチン / スレッドがジャンプ・ターゲットに制御を移すなら、スケジューラーは、必要な箇所にジャンプできるわけです (おそらく、スレッドの優先順位によってオーバーライドされないかぎり)。ただし、コルーチン / スレッドが単にNone に制御を移すだけなら、スケジューラーは、次にアテンションを与えるべきスレッドがどれであるかを自分自身で決定できるでしょう。任意にジャンプすることと直線的なスレッド・キューとの間の相互関係を決定し (プログラミングする) には、少し工夫が必要になります。といっても、何か難解な工夫が必要だというわけではありません。

高速かつ安価 -- 使わない手はない

マイクロスレッドのパターン (すなわち「無重量スレッド」) は、結局のところ、Pythonでのフロー制御の (もともとの機能とは別に設けた) 特別なスタイルの1つであると言うことができます。このコラムでは、これまでの回で、そうしたスタイルについていくつか取り上げました。制御メカニズムにいろいろなものが利用できることの素晴らしさは、開発者がコードの機能を論理的なコンポーネントの単位で分離できるということ、およびコンテキストにしたがってコードをできるだけ関係付けることができるという点にあります。

実際のところ、可能であるもの(ループや if )全てを実際にやる、ということの可能性を実現するのは、大した手間ではありません。数多くの小さな「エージェント」や「サーバー」や「プロセス」に簡単に分解できるような類の問題であれば、アプリケーションの根底にある「ビジネス・ロジック」を表現するのに、無重量スレッドが最も簡明なモデルとなるかもしれません。もちろん、これによって、無重量スレッドが、もっとよく知られたフロー・メカニズムに比べ、猛烈に高速に処理できる可能性をもっているという点を損なうこともありません。


ダウンロード可能なリソース


関連トピック

  • 以前このコラムでDavidは、さまざまな種類のステート・マシンを実現するためのPythonによる抽象パターン紹介しました。そのときの記事「魅力的なPython: ステート・マシンの使い方 (2000/12/15)」(developerWorks、2000年8月) が、今回の記事で新しい概念を説明するための足がかりとなっています。
  • Davidの魅惑的なPython: Python実装に駆り立てたもの (2001/02/09) (developerWorks、2000年10月) で、マイクロスレッドのことが、継続 (continuations)、コルーチン、ジェネレーターなどの他の (もともとの機能とは別に設けた) フロー構造とともに簡単に触れられています。この記事では、Python 2.2にジェネレーターが導入される以前にあったさまざまな問題の中のいくつかについて言及しています。
  • もっと最近では、Davidは、Python 2.2のアルファ期間中に、魅力的なPython:イテレーターとシンプル・ジェネレーター (2001/12/07) (developerWorks、2001年9月) という記事を発表しています。
  • マイクロスレッドに興味のある方、あるいはStackless Pythonの複雑な変遷に興味のある方は、Stackless PythonのWebサイト を訪問するとよいでしょう。Davidの意見は、Stacklessの概念的な空間にまで入り込んでいるかもしれませんが、Stacklessは、Davidのフレームワークで実現されないことをいろいろと実現し続けるだろうとDavidは考えています (標準的なPythonのフォークにパッチを当てる必要があるにせよ)。
  • developerWorks のLinuxゾーンには、他にもLinux関係の記事が多数掲載されています。

コメント

コメントを登録するにはサインインあるいは登録してください。

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=230460
ArticleTitle=魅力的なPython: Pythonジェネレーターで「無重量スレッド」を実装する
publish-date=06012002