【技術本】オライリー・ハイパフォーマンスpython

https://amzn.to/3TGfPNL


【技術本】オライリー・ハイパフォーマンスpython

へポスト
Pythonの高速化における以下の考察と実例が述べられている。
・ボトルネック特定のためのプロファイリング方法
・データ型(リストとタプル、辞書と集合、イテレータとジェネレータ)
・ベクトル化
・Cコンパイル
・並行化
・並列化
・クラスタ化
・RAM消費量削減
紹介されるアルゴリズムは、数式や図解などで説明され実装も記載されているので、理解が及ばないという問題はほぼない。
ハードウェアのアーキテクチャの構造、言語仕様の特性、マルチコア～クラスタによる処理の分散方法の考察など、性能を引き出す論理思考のアプローチの過程は、Pythonに留まらず様々な高速化ケースの調査の足がかりにもなる参考書だと感じた。
翻訳においても、文章の癖は無く、流れるような日本語の表現で読みやすかった。
※一部、図表等で色分けを前提とした表示があり、黒の印刷では見にくい箇所もあり。
記載されているコードはUnix系でのPython 2.7がベース。
Windowsで動作させる場合で想定したパフォーマンスを出すにはOS依存処理部分に対処が必要な場合があったり、Python 3.xで動作させる場合は現行ではライブラリが対応していなかったりPython言語仕様やライブラリの仕様変更で想定したパフォーマンスが得られない可能性がある。

記載されている概要は以下の様です。

１章：高機能なPythonを理解する--------------------------------------
Pythonインタプリタは低水準の要素を抽象化しているが、それらを踏まえて性能を引き出す方法を以下に述べている。
・CPUのベクトル演算命令を活用した実装は、numpy(後述)などの外部ライブラリで解決可能。
・Pythonは動的型付け言語なので、コンパイラが行うコード最適化の恩恵を受けられない対策として、Cython(後述)での使用を検討すべき。
・マルチコアのボトルネック。アムダールの法則による障壁とも言えるPythonのGIL(グローバル・インタープリタ・ロック)。この問題はmultiprocessing標準ライブラリ(後述)、numexpr(後述)、Cython、分散モデル技術などで解決できる。
・CやFortranのライブラリを活用したPythonコードは、同等のCのコードと同じくらい高速になりうる。

２章：ボトルネック発見のためのプロファイリング--------------------------------------
Pythonによる処理時間やメモリ消費、処理詳細の調査と、ボトルネック特定のためのプロファイリング取得の方法を紹介。

３章：リストとタプル--------------------------------------
データ順序の格納に工夫しておけば高コストな線形探索を避ける事ができる。
線形の場合O(n)であり、ソートされていれば最良でもO(log n)
基本的に領域確保のメモリコピーコストは高い。
・リスト：動的配列。値を変更でき、サイズも変更できる。サイズ変更時に、将来の追加を見込んだ領域分も確保しているので領域再確保の回数を減らしている。
・タプル：静的配列。値を変更できない。生成されたら中のデータを変えられない。タプルの連結はできる。連結時に余剰領域は確保されない。静的データはタプルで扱うのが望ましい。リソースをキャッシュできる利点がある。小さなタプルはGC（ガーベージコレクション）後でも再利用のため保持される特性を利用できる。タプルの再生成などでリストより高速に生成できる。

４章：辞書と集合--------------------------------------
辞書と集合では任意のインデックスに対する探索計算量はO(1)で済む。
オープンアドレス型のハッシュ表を使う事で高速性を実現。検索するのでなくハッシュ値から計算されるメモリ上のデータの場所を直ちに求める。キーの衝突にはプローフ法アルゴリズムを採用。
ハッシュ表は、衝突を抑えるため、要素数がサイズの2/3を超えないようにしている。要素追加によるサイズ変更時には、領域確保と新しいハッシュ表への追加し直し、インデックス再計算などでコストが大きくかかる。
・辞書：探索が適す。
・集合：人数の計算が適す。集合は保持するキーのユニーク性を保証。
Pythonの変数、関数、モジュールを参照するときにの性能について。これらを検索する場合も、高速なローカル配列や、辞書を利用している。ループが始まる直前に、グローバルな参照をローカル変数にセットすることで高速化できる実例の紹介。

５章：イテレータとジェネレータ--------------------------------------
ジェネレータは複数の値をyieldで返す。ループなどで、１要素取り出すごとに処理して要素をジェネレートする。→遅延評価
従って、計算前に全ての事前生成などが必要になるrangeを使ったループや、リスト内包よりもメモリを節約する事ができる。メモリに乗り切らない処理も可能に。
早めに終了条件に到達すれば、総計算時間の節約もできる。→高速化

６章：行列とベクトルの計算--------------------------------------
行列、２次元拡散の処理を実例として紹介。
以下の問題をnumpyで解決している。
・メモリ確保のコストや、確保したリストがPythonの特性によりポインタ参照のうえメモリ上で断片化している（位置特定のコスト高）。→重要なメモリ使用を局所化
・バイトコードがfor文のベクトル化に最適されていない。→CPUのベクトル演算命令の使用

Linuxのperfを利用してPython実行時の状況をプロファイリングして高速化を証明。（高速化の主要因はベクトル演算命令でなく、メモリの局所化と断片化の減少であった。）

以下のnumpyを使用した更なる高速化の紹介。
・インプレース演算によるメモリ確保の削減。
・汎用関数はメモリ使用量が大きいので特化した関数を実装して代替し命令数(IPC:Instructions Per Cycle)の削減。
・インプレース演算を簡潔に高速化するnumexprモジュール。ただし、計算式をコンパイルするオーバヘッドがあるため、小さな行列計算などではそれが大きなオーバヘッドとなって全体の性能に影響する場合があるので、状況を見てのトレードオフ。

７章：Cにコンパイルする--------------------------------------
コンパイルによる高速化は、数学的な処理で同じ演算を多数繰り返すループや、ループ内で一時的なオブジェクトが多数生成されている場合に有効。
外部ライブラリ参照（前述のnumpy利用含む）や、I/Oバウンドのものは高速化できない。
Pythonは動的型付け語であり、仮想マシンはどの型でも対応できるように関数などが汎用化されているが、実行時に変数の型を決定するコストが特にループ時には累積する。変数の型を確定できれば、それを静的コンパイル時に解決すれば高速化できる。→高水準のPythonオブジェクトを必要としなければ、低水準の機械語に下って、機械語とメモリを直接操作して高速化できる。
・Cython
型注釈のあるPythonをコンパイルされた拡張モジュールに変換するコンパイラ。OpenMP（並列化モジュール） やmultiprocessing対応モジュールで並列化も可能。GCは参照カウント法。setup.pyスクリプト経由でモジュールをコンパイル。ブラウザで見れるHTMLファイルを出力する注釈オプションがあり、それを基に性能処理を解析して高速化施策を検討できる。高速化に着目する要点コツを踏まえながら、CPUバウンドの処理をモジュール化し、それに型の注釈の記述や、ネイティブで提供されない関数を独自実装による強度低減や、リストの境界チェック無効のテクニックなどで性能向上する例を紹介。外部関数インタフェースも紹介。
・Shed Skin
PythonからC++へのコンパイラ。型推論を用いている。標準ライブラリは別途実装したものを利用する必要あり。生成するコードは独立実行可能→Pythonプロセスとメモリが共有されない。Pythonプロセスからメモリコピーされ、結果もコピーして返されるので巨大なメモリーブロックを用いるとメモリコピーによるコスト増大。
・Numba
numpyに特化したJITコンパイラ(一回目でコンパイルするので２回目以降から高速)。
LLVMコンパイラを使用。
・Pythran
PythonからC++へのコンパイラ。型注釈を記入する方式。部分的にnumpyサポート。OpenMPサポート。
・PyPy
JITコンパイラ。すべての組み込みモジュールをサポート。変更の手間が全くかからない。GCはマーク＆スイープ法。RAMの使用量は多い。

GC特性による未使用オブジェクトの回収タイミング、ファイル参照処理の挙動についての説明あり。
Pythonが開発されているのと同じ方法でコードを書きCPythonモジュールの作成例の紹介。

８章：並行処理--------------------------------------
I/O待ちが含まれる処理を、非同期ノンブロッキングで並行化をサポートするライブラリを使用して高速化する実例を紹介。
・gevent
高水準非同期I/O インタフェース提供
・tornado
イベントループの実行を手動制御が必要。
・AsyncIO
Python3.4以降で可能な非同期I/O制御ライブラリ

９章：multiprocessingモジュール--------------------------------------
一台のマシンでマルチコア並列処理をするのに注力するモジュール。
プロセス間ではGILの問題が起こらない。ただし、プロセスを追加すると、通信のオーバヘッド（IPC:Inter-Process Communication）が増え、利用可能なRAMが減るので、プロセス分倍速になる事はない。RAMを使い尽くすとスワップにより性能劣化するので注意が必要。
numpyでforkしたプロセスで乱数生成器の初期化を忘れると同じ乱数列が発生する注意点。
モテンカルロ法の円周率推定計算をmultiprocessingで実装した例を紹介。
以下のIPCを利用した並列処理を素数判定処理の実例を踏まえて性能測定。
・改良版単純Pool法：multiprocessing.Poolを使用する。小さな約数判定は逐次処理で行い（IPC削減）、約数が見つからなければ並列処理にする。
・Redis：インメモリデータベースを使用した場合
・RawValueフラグ：multiprocessing.RawValueを使用。ロック機構がないが高速。本検証ではフラグが素数未発見→素数発見の一方向のみにしか変わらないのでロックを考慮しないで使用できている。
・mmapフラグ版：mmapモジュールを使ったメモリマップによる解法。
・mmapフラグ改良版：mmapフラグ版のカウンタロジックを改良したもの

multiprocessing.Arrayを用いてnumpy配列に置換してデータ共有をする方法の紹介。ただし、プロセス間で領域を分担して並列処理する手法。同じデータを同時にアクセスする場合は注意。
並列処理でのファイルのロックにlockfileモジュールを使用した紹介。
multiprocessingモジュールによるプロセス間でPythonオブジェクトの共有（値ロック）方法の紹介。

１０章：クラスタとジョブキュー--------------------------------------
複数の計算機をまとめて一つの共通タスクを解く方法について。
・Parallel Pythonモジュール
multiprocessingに似たインタフェースを持つ。分散処理をしてもらいたいリモートPC群でParallel Pythonのサーバを起動して、メインのプログラムから振り分ける方式。
・IPython Parallel
PyPyと組み合わせる事ができる。SSH通信も可能。
クラスタ構成設定ファイルをリモートに配布してから、該当プロセスを立ち上げてクラスタを構成する。
・NSQ
Queue方式。
Go言語で書かれたデータ形式やプログラミング言語に依存しないメッセージング基盤。
障害に堅牢。pub/sub/consumerによる考え方で実装されており、ノード障害やサービス負荷などでのノード切り離しや追加が可能。Queueの潜在的問題はメッセージの消失だが、メッセージが増えて来たらディスクに保持することで解決している。
HTTP経由で出力の様子もプロファイリング可能。

１１章：RAM使用量を削減する--------------------------------------
Pythonは整数型のような基本データ型のオブジェクトをキャッシュする特性がある。→RAMに制約のあるシステムでは注意が必要。
外部の処理にデータを渡すだけであったり、データの一部を使うだけならlistよりarrayが有効。※array の中身を処理すると基本データ型が一時的なオブジェクトに変換されてしまうのでコストがかかる。
numpyを使用した効率的なメモリ管理の紹介。
sys.getsizeof()とmemitによるメモリ使用量プロファイリングの紹介。※memitのほうが正確に調べられる。
Python3.3以降でのUnicodeオブジェクトのメモリ効率が改善。均一に４バイト必要だったものが、ASCIIには1バイト、出現頻度が低い文字には複数バイト割り当てるように改善された。
RAMに効率よく大量のテキストを記憶する手法として、木構造を利用したトライとDAWGを紹介。利点として共通接頭辞検索もできる。
・DAWGモジュール
初期化が必要。構築後に変更はできない。
・Marisaトライモジュール
構築後に変更できない。
・HATトライ
キャッシュを有効活用した構成。構築後に変更可能だが、APIは最小限。

メモリマップトファイルの使用や、ジェネレータを使用して、データの必要な部分だけを読み込むようにする方法の紹介。ビットを大量に使うならnumpyとbitarray。CPythonよりPyPyの方がRAM使用量は少ない。

以下の確率的データ構造による精度を犠牲にしているがメモリ使用量を削減して高速な処理の紹介。
・Morrisカウンタ
近似値の数え上げ。
・K-最小値
数え上げた要素の重複をカウントできるようにしたもの。
・Bloomフィルタ
要素が集合に含まれているかの検索。偽陰性がなく陰陽性の確率を制御できる。
・LogLogカウンタ
ハッシュ値の各ビットがランダムであるという確率を利用して、先頭に0が続くハッシュ値を記録していき要素数を推定する。初期にカウンタを増やすハッシュ値にでくわすと推定値に大きな影響を与えてしまう欠点がある。

１２章：現場に学ぶ--------------------------------------
現場でのPythonを活用したシステム開発での高速化の事例を紹介。

以上。

へポスト