コードを80倍高速化する方法

すべてビーバー！

Python Developerコースの3番目のセットを開始します。これは、オープンレッスンが予定されていることを意味します。これは、旧形式の公開日を部分的に置き換え、教師から興味深い資料を見つけることができます。 。 今回は、「スネーク」コードをスピードアップします。

行こう

PyPyはコードを2倍高速化でき、多くの人々を満足させます。 私は、PyPyがより多くの能力を持っていることを証明する短い個人的な物語を共有したいと思います。

免責事項：これはすべての場合の奇跡的な治療法ではありません。はい、この場合に特に効果がありましたが、他の多くの場合には効果的ではないかもしれません。 ただし、この方法は興味深いものです。 さらに、ここで説明する手順は、開発中に同じ順序で適用したため、この記事はPyPy最適化の命を救う例になります。

私は数ヶ月前に進化アルゴリズムで実験しました：計画は野心的でした-（シミュレートされた）クアドロコプター、つまりPIDコントローラーを制御できるロジックを自動的に開発する （ スポイラー ：飛行しません）



ランダムなクリーチャーの集団が存在する場合、各世代で最も適切なクリーチャーが生き残り、小さなランダムな変化で増殖するという考え方です。

ただし、この投稿のフレームワーク内では、最初のタスクはそれほど重要ではないため、コードに直接進みます。 quadrocopterを制御するために、クリーチャーは各delta_tで起動されるrun_stepメソッドを使用します（コードは完了しました）。

 class Creature(object): INPUTS = 2 # z_setpoint, current z position OUTPUTS = 1 # PWM for all 4 motors STATE_VARS = 1 ... def run_step(self, inputs): # state: [state_vars ... inputs] # out_values: [state_vars, ... outputs] self.state[self.STATE_VARS:] = inputs out_values = np.dot(self.matrix, self.state) + self.constant self.state[:self.STATE_VARS] = out_values[:self.STATE_VARS] outputs = out_values[self.STATE_VARS:] return outputs 

• 入力-Z軸に沿った最終点と現在位置が配置されているnumpy配列。
• 出力-モーターに伝達される推力が位置するnumpy配列。 まず、4つのモーターすべてが同じトラクションで制限されているため、クアドロコプターはZ軸に沿って上下に動きます。
• self.stateは、あるステップから別のステップに渡される未知のサイズの任意の値が含まれています。
• self.matrixとself.constantにはロジック自体が含まれています。 「正しい」値を送信すると、理論的には、完全に調整されたPIDコントローラーを取得できます。 彼らは世代間でランダムに変異します。

run_stepは（仮想シミュレーション時間間隔で）100 Hzで呼び出されます。 世代は500のクリーチャーで構成され、各クリーチャーは12秒間仮想テストされます。 したがって、各世代には600,000 run_step実行が含まれます。

まず、CPythonコードを実行してみました。 結果は次のとおりです。

 $ python -m ev.main Generation 1: ... [population = 500] [12.06 secs] Generation 2: ... [population = 500] [6.13 secs] Generation 3: ... [population = 500] [6.11 secs] Generation 4: ... [population = 500] [6.09 secs] Generation 5: ... [population = 500] [6.18 secs] Generation 6: ... [population = 500] [6.26 secs] 

最初の例外を除き、1世代あたり約6.15秒です。

次に、PyPy 5.9を試しました。

 $ pypy -m ev.main Generation 1: ... [population = 500] [63.90 secs] Generation 2: ... [population = 500] [33.92 secs] Generation 3: ... [population = 500] [34.21 secs] Generation 4: ... [population = 500] [33.75 secs] 

ああ！ CPythonの場合よりも5.5倍遅いことが判明しました。 これは部分的に予想されていました：nympyは、遅いことで知られるcpyextに基づいています。 （実際、私たちはこれに取り組んでいますcpyext-avoid-roundtripブランチでは、結果はすでにCPythonよりも優れていますが、これについては別の投稿で説明します）。

cpyextを避けましょう。 最初の明白なステップは、numpyの代わりにnumpypyを使用することです（micronumpyの一部のみを使用できるようにするハックです）。 速度が改善されたかどうかを確認します。

 $ pypy -m ev.main # using numpypy Generation 1: ... [population = 500] [5.60 secs] Generation 2: ... [population = 500] [2.90 secs] Generation 3: ... [population = 500] [2.78 secs] Generation 4: ... [population = 500] [2.69 secs] Generation 5: ... [population = 500] [2.72 secs] Generation 6: ... [population = 500] [2.73 secs] 

平均して、約2.7秒：PyPy + numpyの12倍、元のCPythonの2倍以上です。 すでに、多くの人がPyPyの素晴らしさを伝えようとしています。

しかし、結果を改善してください。 いつものように、最も時間がかかるものを正確に分析します。 vmprof プロファイルへのリンクを次に示します 。 numpypy内で多くの時間を費やし、さまざまな操作の結果を保存するために大量の一時配列を割り当てます。

さらに、jit トレースを見て、run関数を見つけましょう。これは、ほとんどの時間を費やすサイクルであり、1796の操作で構成されています。 行np.dot(...) + self.constantは、行1217と1456の間にあります。以下は、 np.dot(...)を呼び出す抜粋np.dot(...) 。 ほとんどのステートメントには何の価値もありませんが、1232行目にRPython関数descr_dotの呼び出しがあります。 実装により、結果を保存する新しいW_NDimArrayが作成されることがわかります。つまり、 malloc()を実行する必要があります。



+ self.constant部分の興味深い実装は、 + self.constant呼び出しがJITによって組み込まれているため、何が起こっているかを理解しやすくなることです。 特に、結果にW_NDimArrayを割り当てる__0_alloc_with_del____の呼び出しと、配列自体を割り当てるaw_mallocがあります。 次に、結果の配列のフィールドを設定し、イテレータを作成し、最後にacall_assembler呼び出す149の簡単な操作の長いリストがあります。これは、JITまたは個別の追加の実際のロジックです。 call_assembler 、JITからJITへの呼び出しを行うための操作の1つです。



これはすべて最適ではありません：私たちの場合、 self.matrixのサイズself.matrix常に（ self.matrix等しいことがわかっています-これは、一時配列のmalloc() 2回の呼び出しを含む多くの作業を行うことを意味します。合計6回の乗算と6回の加算。 これはJITのせいではないことに注意してください。CPython+ numpyは同じことをしなければなりませんが、Cへの非表示の呼び出しでは。

よく知られているコンパイラーの最適化、ループの反転は、おそらくこの問題の解決に役立つでしょう。 コンパイラーの観点からは、ループの反転には常にリスクが伴います。マトリックスが大きすぎると、配列のサイズが絶えず変化する場合は役に立たない大きな形状のないコードの塊が最終的に残されます。 これが、この場合のPyPy JITがそうしようとさえしない主な理由の1つです。

ただし、マトリックスは小さく、常に同じサイズであることがわかっています。 したがって、ループを手動で展開します。

 class SpecializedCreature(Creature): def __init__(self, *args, **kwargs): Creature.__init__(self, *args, **kwargs) # store the data in a plain Python list self.data = list(self.matrix.ravel()) + list(self.constant) self.data_state = [0.0] assert self.matrix.shape == (2, 3) assert len(self.data) == 8 def run_step(self, inputs): # state: [state_vars ... inputs] # out_values: [state_vars, ... outputs] k0, k1, k2, q0, q1, q2, c0, c1 = self.data s0 = self.data_state[0] z_sp, z = inputs # # compute the output out0 = s0*k0 + z_sp*k1 + z*k2 + c0 out1 = s0*q0 + z_sp*q1 + z*q2 + c1 # self.data_state[0] = out0 outputs = [out1] return outputs 

このコードには、値がCreature.run_stepで発行された値と等しいことを確認するためのヘルスチェックが追加されています。

仕組みを確認しましょう。 最初にCPythonを使用：

 $ python -m ev.main Generation 1: ... [population = 500] [7.61 secs] Generation 2: ... [population = 500] [3.96 secs] Generation 3: ... [population = 500] [3.79 secs] Generation 4: ... [population = 500] [3.74 secs] Generation 5: ... [population = 500] [3.84 secs] Generation 6: ... [population = 500] [3.69 secs] 

良さそう-CPython + numpyの元の実装よりも60％高速です。 PyPyを確認します。

 Generation 1: ... [population = 500] [0.39 secs] Generation 2: ... [population = 500] [0.10 secs] Generation 3: ... [population = 500] [0.11 secs] Generation 4: ... [population = 500] [0.09 secs] Generation 5: ... [population = 500] [0.08 secs] Generation 6: ... [population = 500] [0.12 secs] Generation 7: ... [population = 500] [0.09 secs] Generation 8: ... [population = 500] [0.08 secs] Generation 9: ... [population = 500] [0.08 secs] Generation 10: ... [population = 500] [0.08 secs] Generation 11: ... [population = 500] [0.08 secs] Generation 12: ... [population = 500] [0.07 secs] Generation 13: ... [population = 500] [0.07 secs] Generation 14: ... [population = 500] [0.08 secs] Generation 15: ... [population = 500] [0.07 secs] 

はい、これは間違いではありません。 数世代後、時間は1世代あたり約0.07〜0.08秒の範囲で安定します。 これは、CPython + numpyの実装よりも約80（80）倍、素朴なPyPy + numpyよりも35〜40倍高速です。

もう一度トレースを見てみましょう：高価な呼び出しがなくなり、一時的なmalloc（）が絶対にありません。 ロジックのルートは行386〜416で、Cレベルの高速な乗算と加算の実行が確認できます。float_mulとfloat_addは、mulsdコマンドとaddsdx86コマンドに直接変換されます。

前述したように、これは非常に具体的な例であり、そのような方法は普遍的ではありません。残念ながら、任意のコードの80倍の高速化を待つべきではありません。 ただし、これは、高速コンピューティングにおけるPyPyの可能性を明確に示しています。 そして最も重要なことは、これはPyPyがうまく機能するように特別に設計されたトライアルベンチマークではないことです。例は小さいですが現実的です。

結果を再現する方法

 $ git clone https://github.com/antocuni/evolvingcopter $ cd evolvingcopter $ {python,pypy} -m ev.main --no-specialized --no-numpypy $ {python,pypy} -m ev.main --no-specialized $ {python,pypy} -m ev.main 

終わり

どちらかといえば、ここまたは公開レッスンで質問を待っています 。