Hi、みんな。ここはPythonやPythonnoような言語の実装における、現時点のソフトウェアトランザクショナルメモリについての論文の短い要約（抽出物）です。
このブログ記事をより良くしてくれたIRCの人々(lucian, Alex Gaynor, rguillebert, timonator, Da_Blitz)に感謝します。
現在の議論の目的のために、私たちはPythonとJavaのマルチスレッド化を比べています。
複雑なハイレベル言語における問題
Javaのように、Python言語は保証します: Python仮想マシンはスレッドの誤った使用が原因でクラッシュすることは受け入れられません。
Javaのプリミティブ操作は、フィールドのオブジェクトフィールドを読み書きするようなものです; 対応する保証は、方針に沿っています。
プログラムがオブジェクトのフィールドを読み取り、別のスレッドが同じオブジェクトの同じフィールドに書き込む時、プログラムは、古い値または新しい値を参照するでしょう。
しかし、全く違った値ではなく、仮想マシンはクラッシュしません。Pythonのような高級言語は、"プリミティブな操作"は、はるかに複雑であるという事実があるため、Javaとは異なります。
それは例えば、いくつかのハッシュマップでおそらくアップデートを行って見られるかもしれません。
一般的には、それはすべての操作をシングルプロセッサの命令にアトミックに必ずし、完全にマップするのは不可能である。
JYTHON: きめ細かいロック
この問題はJavaの上で動作するJythonインタプリタでは"明示的に"解決されています。
解決策は次の文の通り明示的です：Jythonインタプリタ全体を通して、一つ一つの操作は、Javaレベルのロックメカニズムを慎重に利用しています。これは、"きめ細かいロック"のアプリケーションです。例えば、属性をハッシュマップの数だけ参照する操作はロック（__getattribute__における）の獲得と解放により保護されています。
このソリューションの引っ込めは、必要な細部へのこだわりです。一箇所でもロックをミスしたのであれば、いずれかのバグがあります。 --- このようなバグは、以前のバグが修正されているようにデバッグするため、ますますまれにしか起こらず困難なケースで発生します ---
また、私たちは"CPythonとの違い"のもとでそれを適正に保存します。しかしながら、二つのスレッドが異なる順序で同じオブジェクトをロックしようとすると、デッドロックの危険性があります。実際には、予想に反して私が手書きするほど悪い状態ではありません。Jythonにおけるロックの数は適切であり、そして、期待どおりに動作するすべての"一般的なケース"が可能になります。（稀なケースは、以下を参照してください。）
性能面では、Java仮想マシン自体は、長期間にわたって猛烈な最適化されているロックが付
属しています。
しかしながらCでコーディングされたソリューションの場合は、手動でロックを最適化するために余分な作業が多く必要になります（多くのバグを含んでしまうだろう）。
CPYTHON: きめのあらいロック
CPython、C言語によるPythonの標準実装では異なる単純なアプローチを取った：それはシングルグローバルロックを持ち、グローバルインタプリタロック（GIL）と呼ばれる。
それは"きめのあらいロック"を使用しています: ロックは、全体の実行であっちこっちにある1つのバイトコードが取得されて、リリースされます（実際に100のような少ない数のバイトコード）。それらを呼び出す複数バイトコードはGILで自分自身をシリアライズされるので、この解決策は、2つの操作が互いに競合しないことを保証するのに十分です。それは、インタプリタ全体にわたって慎重なロックを獲得するコードを書くのを避ける --- Jythonとは異なった ---解決策です。また、より強い保証を提供しています：すべてのバイトコードは、アトミックに完全に実行されます。
今日において、GILのアプローチの引き戻しは、マルチコアマシン上では明白です：複数のスレッドを開始し、バイトコードの実行をシリアル化することによって、実際には複数のコアのインタプリタの使用を許可しません。
PyPy、PythonによるPythonの実装では、これまでと同じアプローチを採用しています。
現在の処理
これまで見てきたように、我々は次のような解決策：既存のPython言語、CPython実装は、マルチスレッドの使用状況についての非常に強い保証を提供しています。
それは、ほとんどの既存のマルチスレッドのPythonプログラムが実際にそのような強い保証に頼ることは重要であると強調する。
これは、人口のリストを受け取り、いくつかのスレッドで行う問題の例で見ることができます:
next_item = global_list.pop()
これは、暗黙的にpop()がリストからアトミックの除去を実行するという事実を当てにしています。
二つのスレッドが同時に同じリストからポップしようとすると、2つの操作は、ある順序または別で発生します。
しかし、それらは例えば、両方のスレッドへ同じオブジェクトを返すか、リストオブジェクトの内部状態までぶち壊します。
このような例を念頭に置いて、私たちはこれらのマルチコア問題を含む強力な保証を落とす解決策を望んでいないことは明らかです。
しかしながらJythonがそうするように障壁を下げるのは、間違いありません; しかし、いくつかのPython実装は、いくつかの保証を提供しなくてはいけません、または、マルチスレッド化を全く提供してはいけません。
これは、組み込み型のメソッドの多くがアトミックであるという事実が含まれています。
(それは、全てにおいてマルチスレッドを提供していないことも実際にはまた、（部分的な）問題の解決策であることに留意すべきです。
最近、いくつかの"ハック"は、多かれ少なかれ透過的なアクセスし複数の独立したプロセス (e.g. multiprocessing).をプログラマに与えることが明らかです。
これらはいくつかのコンテキストで適切な解決策を提供するわけだが、マルチスレッドのように広く適用されません。
典型的な例として、それらは、複数のコアが、全くシリアライズできない情報を処理する必要があるとき適用しません。
--- いくつかのプロセス間における、いかなるデータ交換の要件。)
ここに、Jythonの一貫性がCPythonのGILよりどう弱いかの例があります。
それを示しているのに一般的でない例を要しており、CPythonのようなプログラマがそれらを予想するどんな仕事もせず、一般的に、実装の詳細として考えられている。
考察:
Thread 1: set1.update(set2)
Thread 2: set2.update(set3)
Thread 3: set3.update(set1)
各操作はCPythonの場合にはアトミックです。
しかし、Jythonの場合は、次の2つの手順（各々は、アトミックとみなすことができる）に分けられる：引数から読み取り、そして、対象のsetを更新する。
最初にset1 = {1}, set2 = {2}, set3 = {3} を行うとします。CPythonにおいて、独立したスレッドの実行順序の結果、最も小さなset {1, 2, 3} になります。
Jythonにおいて、すべての3つのsetが2つだけの要素を含むだけで終わっている可能性があります。
例は、少しこじつけですが、CPythonとの一貫性はJythonのより厳密に強くなって表示されるべきです。
PYPY
PyPyはCPythonやJythonに非常に似たPythonインタプリタです。しかし、生成方法は独特です。
それはPythonのサブセットであるRPythonで書かれたインタプリタであり、自動的に"翻訳"と呼ばれる段階で完全な仮想マシン（Cのコードを生成）になって手に入ります。
このコンテキストでは、CPythonとJythonのコンテキストはは異なります: PyPyではまったくもって簡単に、"翻訳時"にインタプリタへ任意のプログラム全体の変換を適用することが可能です。
この点を考慮し、インタプリタによってRPythonで操作の全オブジェクトにロックを追加し、プログラム全体の変換を想像することは可能です。
これはJythonと同様な状況として終わるでしょう。
しかしながら、それは慎重な手動配置でのロックがJythonの場合は回避され、デッドロックの問題が自動的に解決するとはなりません。
（実際には、デッドロックフリーであることは自動的に確保、検証できないグローバルプログラムのプロパティです;
いくらかのJythonの変更は、理論的にはこのプロパティを破るため、巧妙なデッドロックを導入することができます。
同じことが、ノンアトミックに適用されます。）
実際には、もし、インタプリタがスレッド1のバイトコードでAとB、およびスレッド2のバイトコードでBとA(反対の順序)に（読み取りおよび書き込みの両方の）アクセスした場合、私たちは簡単にそれを確認することができ、
--- また、あなたが2番目のオブジェクトにアクセスする必要がある、と決める前に最初のオブジェクトにアクセスしている必要があります。 ---
その時、アトミック性の強い保証を維持しながらデッドロックを（GILから離れて）回避する方法はありません。
確かに、両方のスレッドがそのバイトコードの実行の途中に進行した場合は、既にスレッド1によって変更されており、同様にBは既にスレッド2によって変更されています。
その場合、うまくスレッドを実行し続けるのは、可能ではありません。
USING SOFTWARE TRANSACTIONAL MEMORY
ソフトウェアトランザクショナルメモリ(STM)は、明らかに上述の問題に解決策をもたらすアプローチです。
実行し続けるどこのスレッドが間違った状況で終わった場合、私たちは、中断しロールバックすることができます。
これは、データベースのトランザクションの概念と似ています。
上述の例において、一方または両方のスレッドは、トラブルや中断を実行しようとしていることがわかります。
これは、彼らはこれまでに中止または単にまだコミットされていないものすべての副作用において、バイトコードの先頭で実行を再開する方法を持っている必要があることをより、具体的に意味しています。
私たちは、中断してロールバックする能力はPythonのマルチスレッド実装に欠けているパズルのピースだと考えています。
実際に、上記の問題のプレゼンテーションによれば、それはCPythonの一貫性とアトミック性の同じレベルを提供したすべての解決策は、中断とロールバックの容量を伴うことは避けられないです。--- これは正確にそのSTMを避けることができないことを意味します。
OK、しかしなぜJythonのアプローチで落ち着いて、インタプリタを通して左右の慎重なロックをかけないのか？
（1）私たちは、すべての操作のアトミック性を考慮し、決定を確認する（またはJythonのを盗む）必要がありますし、それらをここに文書化します;
（2）それはまた、これらのロックを最適化するために、本当に多くの作業となります。e.g. JITのみならずJVMが行うことと同様に;
（3）それは直交すべき機能のどこにでも手動で微調整するコードを必要とし、それはPyPyの方法ではありません;
（3）はおそらくここで最も重要です：あなたはPyPyで実装する言語ごとに作業をやり直す必要があります。
私自身もまたポイント（4）を意味する：それは楽いことではない :-)
詳細であるが、次のようにプロセスは働くだろう。
（これは、1つの可能なモデルの概要を説明します; 異なったモデルがより良くなることは確実です。）すべてのスレッドで:
- バイトコードの開始時に、私たちは"トランザクション"を起動します。これは、トランザクションで発生するログを記録するために、スレッドローカルなデータ構造を設定することを意味します。
- 私たちは、ログに読み込まれるすべてのオブジェクトを、行いたい変更と同様に記録します。
- この時間の間に、私たちは"読み取り"の不整合を検出し、現在のトランザクションの開始時間より遅いオブジェクトの"最終修正"タイムスタンプによって証明し、また中断する。
- これは、コードの残りの部分が矛盾した値とともに実行されるのを防ぐことができます。
- 私たちは"読み取り"矛盾なくバイトコードの最後に到達した場合は、私たちは、アトミックに"書き込み"の不整合を確認してください。
- これらは、他のスレッド内のオブジェクトへの同時更新から生じる矛盾です。---「書き込み」という私たちのオブジェクトか「読み込み」という私たちのオブジェクトのどちらか
- 不一致がまったく見つからない場合、私たちは、トランザクションを遅延をコピーすることによって、メインメモリにログから書き込み、"コミット"します。
どれの取引が始まるか、終わりがまさにポイントであるか指す、どれですか?
トランザクションが開始または終了するポイントは正確なポイントで、CPythonでは、グローバルインタプリタロックは、それぞれ取得され、解放されます。
私たちであれば(純粋に性能のために)CPythonがGILを取得して、Nバイトコードごとにリリースするという事実を無視してください。その時これを意味しています。
- 私たちは、任意のバイトコードの前にGILを（トランザクションを開始する）を取得し、バイトコードの後に私たちは、それ（トランザクションを終了する）を放します; そして
- CライブラリやOSへの外部呼び出しを行う前に、私たちは、GIL（トランザクションを終了する）を放し、その後のそれ（次のトランザクションを開始する）を再取得します
確かに、構造によって、CPythonではそれらはGILの解放で発生するため、これらのシステムコールはトランザクションの外で発生します。
PERFORMANCE
今のところ、多くの詳細な実装はまだ未解決です。
ユーザーの観点（i.e. Pythonを使用してプログラマ）から、最も関連しているものは総合的なパフォーマンスの影響です。
私たちは、これまで正確な数値を与えることはできず、また、初期性能がものすごく悪いと予想しています。（10倍遅いかもしれない）;
しかしながら、ロック機構、ロックを挿入するグルーバルプログラムの変換、ガーベージコレクション（GC）、ジャストインタイムコンパイラ（JIT）への連続な改善において、私たちはそれがほぼ妥当なパフォーマンス（たぶん、最大2倍遅い）を得ることが可能であると信じています。
例えば、GCは発生したスレッドから漏れることなくオブジェクト上のフラグを保持する。
私たちは、これらが多くの失われた性能を取り戻すことができる最適化の一種であると信じています。
THE STATE OF STM
トランザクショナルメモリは、Tom Knightにより1986年の論文で配信され、それ自体は比較的古い考え方です。
最初はハードウェアサポート、1995年に大衆化されたソフトウェアのみのトランザクショナルメモリ（STM）の考え方に基づいており、最近では集中的な研究の焦点となっています。
上記で説明したアプローチ --- 言語の実装の中核を形成するためにSTMを使用 --- は、私たちの知る限り、新しいです。
これまでのところ、ほとんどの実装ではライブラリの機能として、STMを提供しています。
それは明示的に使用する必要があります。多くの場合、オブジェクトは、STMによって保護されている必要があり、明示的に宣言の形態であってもよい（オブジェクトベースTSTMs）。
STMのネイティブサポートがClojure言語で特に現れ始めたのは最近のことです。
STMは、アプローチとして、Wikipediaに "大幅にマルチスレッドプログラムの概念的な理解を簡素化し、そのようなオブジェクトやモジュールなど既存の高レベルな抽象化と調和して働くことによって、プログラムのメンテナンス性の向上に役立ちます。" と記載されています。
私たちは実際に、これらの利点は、内部的に使用されているだけでなく、同様にPythonプログラマに公開されているほど重要であると考えています。
これは、Pythonプログラマは非常にシンプルなインターフェイスを与えるだろう:
with atomic:
<これらの操作はアトミックに実行されます>
（これは古い考え方です。私を含め2003人の人々はこれを面白いハックだと考えました。
いま私がブログ記事を書き、"それはハックではなかった、それは明確にハックされたロックを使用している。"と主張します。私は、composabilityのアイデアを買っています。）
実用的な観点から、私はロチェスター大学STM（RSTM）において、最近の研究の焦点となっているC++ライブラリ --- と結果のコレクション --- を真剣に探し始めた。
特に代表的な論文の一つが、Michael F. Spear、Luke Dalessandro、Virendra J. MaratheとMichael L. Scottによる
A Comprehensive Strategy for Contention Management in Software Transactional Memoryです。
CONCLUSION
これらのアイデアを取り、Pythonのような複雑な高水準言語の実装のコンテキストでこれらを適用すると、独自な難問が出てきます。
このコンテキストでは、PyPyを使用することは、実験プラットフォーム、また最近ではそのパフォーマンスのために注目されているプラットフォームにおいて道理にかなっています。
代替手段は興味ありません：例えばCPythonのでそれを行うと、グローバルインタプリタを書き換えることを意味します。
PyPyは代わりに、私たちは翻訳時に体系的に適用される変換としてそれを書きます。
また、PyPyは動的言語のために高速なインタプリタを生成するための一般的なプラットフォームです; PyPyにおいてSTMの実装だけではなく、同様にPython用だけではなく、他の言語の実装のために、Pythonの制約から抜け出して動作します。
Update:
これはほとんど私（Armin Rigo）が声を出して暴れる実験をしています; PyPyチーム全体が現在それに取り組むために、次の数年をフルタイムで費やすことを意味する記事と混同するべきではありません。
私が述べたようにそれは実際のPythonインタプリタに直交しており、それはいかなる場合でも、翻訳時にオンまたはオフにすることができる機能です;
私が知っている多くのまたはほとんどのユースケースでは、人々は2倍遅くしかしスケールするものより、むしろ速いPyPyに興味を持ち、手に入れたいと考えています。
私が言ったものはまったく本当に新しくありません。
証明のため、Riley and Zilles (2006)とTabba (2010) の両方は、私がここで説明したように、開始/終了のトランザクションにCPythonのかPyPyインタプリタのGILを回し、ハードウェアトランザクショナルメモリを試したので、参照して下さい。
（原文：Posted by Armin Rigo）
（翻訳：Tohru Ike）
0 件のコメント:
コメントを投稿