スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

--.--.-- | スポンサー広告

[Lua] スタックレスってどういうこと?

eguoさんの日記(無断でアンテナ捕捉させて頂いてます m(_ _;m )でstackless pythonに触れているのを見て、そういえばスタックレスって何だっけな、と思って再度調査。まとめることにしました。

MLなどを見ていると、Lua5.0(5.1)はスタックレス(stackless)であるそうです。Lua4.0はスタックレスではなく、Lua5.0でコルーチンを実装するためにスタックレスにしたのだそうな。参考までに、pythonは公式のものはスタックレスではなく、傍流であるstackless pythonはその名の通りスタックレスのようです。

そんでそんで、スタックレスって結局何よ、というわけです。
おおよそLua-MLとstackless pythonから知恵を拝借しています。

一番最初に・・・スタックレスかそうでないか、というのはスクリプト言語のVMの内部実装に関する話です。ユーザーとしては特に必要な場合意外、意識しなくても良かったりします。

「スタックレス」の「スタック」とは、いわゆるC言語・アセンブラで言うスタックであって、C言語で関数コールをするとスタックにプログラムカウンタが積まれる、C言語では一時変数はスタック上に確保される、というような話で言う場合のスタックです。他のスタックと区別するため、ここでは「Cスタック」と呼びます。

ではまず、スタックレスじゃない場合というのはどういった状況なのかということについて。
この場合、スクリプト言語で関数を多重に呼んだ場合に、関数呼び出しのネスト状況がガンガンCスタックに積まれていく、そういう実装になります。これはC言語での関数呼び出しと同様です。スクリプトで、関数A呼び出し→関数A内で関数B呼び出し→関数B内で関数C呼び出し といったように、関数呼び出しがネストしている場合に、それをそのままC言語における関数呼び出しで実装すると、これはスタックレスではなく、Cスタックを使う実装になります。C言語での機能をスクリプトに置き換えたと考えれば、きわめてストレートな実装といえます。

ではスタックレスな場合はどうかというと、Cスタックを使わず、スクリプト言語側で自前で用意したスタック構造を使います。結局スタックがCスタックであるのか、自前であるのか、という違いであって、スタック構造を使わないわけではありません。ただし自前のスタックでは格納する情報が違います。Cスタックを使った場合、スタックに積まれるのはCPUのレジスタ値であったり、プログラムカウンタであったりしますが、自前スタックの場合は、その言語特有の実行情報を持つデータを積むことになります。関数呼び出しがいくらネストしていても、VM内部ではネストした呼び出しにならず、Cスタックでのレベルはずっと同じ位置にとどまります。

なんとなくスタックレスの意味がつかめたでしょうか?
簡単にまとめますと、「自前のスタックは使うけどCスタックは使わないよ」ということです。


じゃあスタックレスにしたら何が良いの?ということですが、


・自前スタックのデータが取りやすい
実行時のCスタックの構造はCPUやコンパイラによって違いが出るため、Cスタックの状況をスクリプト側から「調べる」とするとやや難しい話になってしまいますが、自前スタックであれば簡単に調べられます。2つ上の呼び出し元の実行位置、といったような情報が簡単に取れるわけです。

・コルーチンを実装しやすい。高速になる。
(ここでの「コルーチン」とは、マイクロスレッドなどを含む広義の意味とします)
コルーチンを実装するには、関数呼び出しのネスト状態を無視したジャンプを行う必要があります。このジャンプを実装するには2種類の方法があり、1つ目はVMをスタックレスな構造にした上で自前のスタックを調整する方法。2つ目はCスタックのデータをコピーする、またはCスタックを別アドレスにスイッチするなどして、Cスタックの状況をを再現する方法です。2つ目の方法ではメモリコピーまたはスイッチの負荷がそれなりにあるので、1つ目のほうが高速に実装できる可能性が高いです。またCスタックのコピー・スイッチというのはC++の例外処理などで不用意な問題を起こす可能性があるといわれますし、移植性にも疑問があります。なお、後述の話もご参考に。

・実行状態の保存・再開などがしやすい
スタックレスでない場合は、ネストされた関数の途中から再開、というようなことをするためにはCスタックの状態を再現しなければならず、プラットフォームによらない実装なども極めて難しいものになりますが、スタックレスであれば自前のデータ構造のため、簡単に再現することができます。
(stackless pythonではこれを「継続(continuation)」といい、コルーチンなどもcontinuationによって実装しているようです。残念ながらLuaではこれに該当する機能はないようです)

・深い再帰構造に耐えうる
Cスタックには限界があるため、あまり再帰が深いと復帰不可能なエラーになってしまいますが、自前のスタックであればヒープのメモリがある限り再帰を行うことができます。


などなどのため、スタックレスにするといろいろ良いことはあるようです。


・スクリプト・C境界を越えてのyield問題
なお、気になる点としては、コルーチンについて、コルーチン呼び出し(スクリプト言語関数)→C言語ユーザー定義関数→スクリプト言語関数 というような呼び出し構造がある場合に、その先からyieldすることが可能か?という問題があります。Lua5.0/5.1ではこれは禁止されています。
結局のところ、スタックレスなのはVM内部のみですから、間にC言語のユーザー定義関数が挟まれたら結局Cスタックを使ってしまいます。Cスタックをコピーまたはスイッチし、再現する方法を取らなければ、上記のようなyieldは実現できません。なお、Lua5.0/5.1では"COCO" (LuaJITで使用されている)を使うとこれが実現されます。これはLua内に閉じたコルーチンではなく、C言語の領域でのコルーチンを使用する実装です。

COCO
http://luajit.luaforge.net/coco.html

(ちなみに"COCO"では、実装として、Windows環境ではOSで用意されたマイクロスレッド機能であるfiberを使い、その他では主にsetjmpもしくはアセンブラによってCスタックのスイッチを実現しています。)

これを考えると、

スクリプト言語→C言語ユーザー定義関数

で止まってくれる場合に限り、スタックレスの意味があるのかもしれません(もっともCスタックの消費が減るメリットはあります)。
Luaでは、

スクリプト言語→C言語ユーザー定義関数→スクリプト言語関数→C言語ユーザー定義関数→スクリプト言語関数→・・・

というようなネストが可能なだけに、やや歯がゆいところですが、標準で使う限りはコルーチンではこのようなネスト構造の先でのyieldは諦めることになりそうです。嫌ならば"COCO"を使いましょう。

"COCO"を使うとそれぞれのコルーチンにCスタック領域を取るようになり、スタックレスの意味がなくなってしまうようにも思えますが、"COCO"では、スタックサイズを自由に設定でき、サイズを0に設定すれば元のコルーチンとほぼ同じ動作になるため、良いとこ取りが可能です。Cスタックがあるほうが良いか、ないほうが良いかというのは使い道による、というわけです。

・pcall - yield問題
あと現状のLuaではpcall(エラー時にちゃんと戻ってくるよう保護された関数コール)の中からのyieldもできないようです。これはpcallの実装にsetjmpが使われているためですが、これも"COCO"で解決されるとか。


ちなみに、Cスタックを使用するコルーチン実装は別に"COCO"に限りませんが、現状ではもっとも安定していそうなのでこれを挙げさせて頂きました。ここまで書いてくると、"COCO"が万能かのように見えますが、"COCO"はLua本来の移植性をやや損ないますので、この点は注意が必要です。

私が理解している限りの、Luaとスタックレスをめぐる状況はこんな感じです。なにか間違ったことを言っている可能性もありますので、ぜひツッコミをお願いいたします。
(それ以前に興味ある方がどれだけいるか疑問な罠・・・)

スポンサーサイト

テーマ:プログラミング - ジャンル:コンピュータ

2006.04.10 | Comments(5) | Trackback(0) | Lua

コメント

stackeless について

stackless python を調べていて、立ち寄りました。

「ではスタックレスな場合はどうかというと、Cスタックを使わず、スクリプト言語側で自前で用意したスタック構造を使います。」


からすると、はむ!さんは python の関数が Cスタック上で動いていると誤解しているように思えます。

Python の関数も「heap 領域から確保した」すなわち「自前で用意した」、関数ごとの Frame 上で動いています。その証拠に generator や closure といった、、呼び出し側のコンテキストとは独立した、関数側のローカル変数を保持し続ける関数オブジェクトのインスタンスを python では扱えます。実際 python の generator を利用すれば 軽量な thread を実装できます。

下に python の virtual machine の動き(関数呼び出しも含みます)を書いてあるので一度読んでもらえればと思います。

http://www.nasuinfo.or.jp/FreeSpace/kenji/sf/python/virtualMachine/PyVM.htm

しかし stackless python の説明は、前置きが長いばかりで、なぜ stackless なのかの説明を的確に答えないものばかりに思えます。途中で真面目に読めなくなるものしか web では見つけられませんでした。Python を知っている読者ならば当然持つはずの疑問には無頓着な説明ばかりだと感じます。

Web では下の説明を途中まで読んだのですが、全部途中で読む意味無しと判断しました。

http://www.onlamp.com/pub/a/python/2000/10/04/stackless-intro.html?page=2
http://www.onlamp.com/pub/a/python/2000/08/23/pythonnews.html
http://www.informit.com/articles/article.aspx?p=23294
PEP219 stackless;;http://www.python.org/dev/peps/pep-0219/

どこかに stackless python の stackless の意味:CPython との違いを短く・的確に説明した文章がないでしょうか。

2008-04-24 木 14:05:37 | URL | 小林@那須 #JalddpaA [ 編集]

小林@那須様

ご指摘ありがとうございます。
pythonについて、また、多数の言語についてそれほど詳しいともいえませんので、ご指摘について感謝いたします。

たしかに公式のpythonでもヒープから確保した独自フレームを利用しているようですね。
そういう意味では、記事中で触れたいくつかの特徴は既に備えているといえそうです。
とはいえ、実装面でCスタックのレベルが変化しないわけではないようです。

これを簡単に調査する方法は、デバッグバージョンのpythonを実行させ、スクリプト上で関数コールが多数ネストをした状態でブレークさせてみることです。

コールスタックを見れば、Cスタック上で関数コールがネストしている様子がわかります。具体的には、以下のスクリプトを実行して、sleep中にデバッガからブレークしてみました。(VC++2005使用)

import time
def f1(a):
 if a > 100:
  time.sleep(100)
 print "before:",a
 f1(a+1)
 print "after:",a

f1(0)

※ネストは都合上全角スペースで表現していますが、半角に置き換えてくださいm(__)m

Cのコールスタック中に、call_functionとPyEval_EvalFrameEx(これはVMのメインループ関数です)が交互に現れます。
また、上のスクリプトを、ネストが1000回までできるように修正して実行すると、スタックオーバーフローとなりました。
このことから、関数コールにCスタックを利用しているVMであることが確認できました。

なお、コルーチン機能(generator)については、必ずしもstacklessでなければ実現できないものではありません。
WindowsNT系で実装されているfiberはCのスタックを切り替えますし、RubyのVMもstacklessではありません。

あとstacklessの説明についてですが、上の記事中でリンクしていますが、こちらの5章がわかりやすいと感じました。
http://www.stackless.com/spcpaper.htm

ご参考になれば幸いです。

2008-04-24 木 19:34:58 | URL | はむ! #sqCyeZqA [ 編集]

stackless python について 2

挨拶が遅れました。小林と申します。Python の generator を使った light weight co-operative な multi thread module を作っています。その兼ね合いで stackless python を調べています。

>こちらの5章がわかりやすいと感じました。

逆に この 5 章:What does it mean to be stackless の部分を読んで、私は この資料は読む価値が無いと判断しちゃいました。だって 5 章は、既存の CPython の stack frame を説明しているのですから。章の題とは違って stackless について書いていないのですから、「そんなことは知っとるわい。ここでも能書きばかりで stackless の意味についての説明は避けるのかよ。」と それ以上読むのを止めてしまいました。

はむ!さんの指摘で再度資料を読み直してみたら、stackless については 6 章以下に書いてありました。やっと stackless python での stackless の意味を理解できました。末尾再帰が可能になっていることには驚かされました。たしかに context switch 動作も速くなりそうです。

でも、stackless python では既存の C 拡張あたりが危なそうだと感じます。既存の CPython グループから受け入れられていないのも納得できる気がします。

Multi thread と stackless python の視点から見たとき、この資料は stackless python が multi thread に適していることことの説明にはなっていないと考えます。Stackless python の context switch が早くなっても、ユーザーが書く python thread コードは遅いままだからです。実用的な意味のある、少し規模の大きな multi thread python code では stackless python の context switch の早さなど、埋もれてしまうプログラムも多いと思います。既存の python を捨ててまで stackless python に移るだけの強い根拠を、この資料は提示していない思います。

私は既存の thread/threading による multi thread よりも stackless python による multi thread のほうが優れている理由は、 stackless python が co-operative な multi thread 機能を提供している点にあると考えています。Native OS の thread を使った thread/threading の pre-emptive な multi thread で発生する test and set のクリティカル・タイミングにおける誤動作を防げることが stacklss python の有利さだと思っています。

でも、それぐらいならば既存の python と整合性を持つ generator を使った co-operative な multi thread の方が優れているとも考えます。

はむ!さんは どのように考えますでしょうか。御意見を伺えたら幸いです。

2008-04-24 木 23:08:23 | URL | 小林@那須 #JalddpaA [ 編集]

小林様

pythonとして、generatorが良いか、stackless pythonによるcoroutineが良いかという点に関しては、特にどちらにすべきという意見は持っておりません。また、別途greenletという実装もあるようですね。

言えることは、python本流の人たちはstackless pythonを見た上でgeneratorを選択し、一方stackless pythonはEVE Onlineという大規模ネットワークゲームの開発者に、「stackless pythonがなければこのゲームは実現不可能だった」と言わせるだけの、ある環境における利点を持っているということです。

それと、私の認識が間違ってなければですが、pythonでのgenerator実装では、「yieldを含む関数は自動的にgeneratorになる」という文法的制約を通じて、スタックフレームのレベルを飛びこすようなyieldを禁止しています。(これがpythonがCスタックの入替えを伴わずにgeneratorを実装できている理由かと)

この実装はかなり興味深い実装なのですが、これによって、yieldをサブルーチンの中で使うといった用途が実現できない・もしくはしづらくなっていますので、対象となるアプリケーションでそういった使い方をする必要があるかどうか、というのも1つの判断理由になるかと思います。

他の一般的なcoroutine実装では、(制約はあれど)スタックフレームのレベルを飛びこすことができ、それをCスタックの入替え(setjmp/longjmp)やstackless化によって実装しているかと思います。

一般的なOSのマルチスレッドは、コンテキストスイッチが重いという点、排他制御が難しい点、逆に、プリエンプティブであるがゆえに1つのスレッドが止まっても他が動き続けるという点など、ここでお話しているようなgeneratorやcoroutineとは似ているようで、かなり用途の違う技術というように思います。作成するスレッドが10~100であればOSスレッドでも良いかもしれませんが、もっと多い場合(~数万レベル)などはcoroutine系の技術の出番かなと思うところです。OSスレッドに比べると安全で、偶然による動作がない分書きやすいのも違う点ですね。

もっとも、OSによるブロックを伴うAPIを使いたい(ブロック中に他のことをさせたい)場合はOSスレッドを使うより他はないでしょう。coroutineからOSによるブロックを伴うAPIを実行すると(当然のように)VM上の全部のcoroutineが止まりますので。
ただし、非同期動作可能なAPIを使っていけば、coroutineによる同時通信処理などを実現可能と思われます。

ついでですが、Rubyの場合は現状プリエンプティブなソフトウェアスレッドを実装しているようですが、Ruby2.0に向けてネイティブスレッドとFiberの併用の方向性のようですね。

決め手にはならないかもしれませんが、ご参考になれば。

2008-04-25 金 13:58:15 | URL | はむ! #sqCyeZqA [ 編集]

stackless python について 3

はむ!さん 御意見ありがとうございます。小林です。

>、「yieldを含む関数は自動的にgeneratorになる」という文法的制約を通じて、スタックフレームのレベルを飛びこすようなyieldを禁止しています。(これがpythonがCスタックの入替えを伴わずにgeneratorを実装できている理由かと)

私の言葉で言い直させてもらうと、generator 関数と普通の関数では、文法的に関数の呼び出し方を変えることを強制しています。

そのため、generator でスレッド制御を行っている下の SimPy ではスレッドから別のコンテキスト・スイッチを含むサブルーチン・スレッドの呼び出しができません。
SimPy;;http://simpy.sourceforge.net/


>別途greenletという実装もあるようですね。
greenlet については知りませんでした。検索して下を見てきました。
http://codespeak.net/py/dist/greenlet.html

Fiber に良く似ていると感じました。意識してなのか、fiber と同様に wait/sleep 機能を持たせていません。Fiber や greenlet が wait/sleep 機能を持っていれば、それだけで co-operative な thread と使えるのに。


>もっとも、OSによるブロックを伴うAPIを使いたい(ブロック中に他のことをさせたい)場合はOSスレッドを使うより他はないでしょう。

同意します。同時に大部分のモジュールが thread safe を保障していない python では、 pre-emptive な multi thread 制御なんて、怖くて使えません。なんらかの手段で pre-emptive な thread 部分を隔離しておく必要があります。OSによるブロックを伴うAPIを並列に動かす必要にせまられたら、その部分を別プロセスで動かすことさえ考えるかもしれません。まだ そのような経験はありませんが。

-----------

色々と教えてくださり、ありがとうございました。ずっと stackless の意味が解らなかったのですが、今回やっと理解できました。はむ!さんの指摘がなかったら「Continuations and Stackless Python」の論文を気を入れて読み直すこともなかったと思います。こちらに書き込んでみて良かったと喜んでいます。

2008-04-26 土 14:04:18 | URL | 小林@那須 #JalddpaA [ 編集]

コメントの投稿


秘密にする

新しい記事へ <<  | HOME |  >> 古い記事へ

広告:

FC2Ad

カテゴリ展開メニュー

  • 未分類(13)
  • Lua(38)
  • プログラミング(11)
  • 食べ物(3)
  • SPAM(2)
  • ゲーム開発(4)
  • GIS/GPS/GoogleMaps(2)
  • スポーツ(1)
  • Skype API(1)
  • AR(1)

はてブ ランキング

ブログ全体: このWikiのはてなブックマーク数

プロフィール

はむ!

Author:はむ!
よく使う言語・環境:
C++,C,Lua,java,VBA,DB
たまにPHPとかjavascript
血液型:O型

メール: lua%ham.nifty.jp
(%を@に変えてください)
ついったー: @hammmm

Lua関連アンテナ

ブロとも申請フォーム

この人とブロともになる

全記事表示リンク

全ての記事を表示する

ブログ内検索


上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。