massa142's blog

くり返す このポリリズム

「ハイパフォーマンスPython」を読んだ

ハイパフォーマンスPython

ハイパフォーマンスPython

Pythonの高速化技法について一歩踏み込んだプロユースの解説書。ボトルネックの測定方法から、最適なデータ構造の使い分け、CythonやPyPyなどのコンパイラの比較、numpyなどのパッケージの使い方、マルチコアCPUの活用法、メモリ効率を劇的に改善するトライ構造や近似計算まで、シンプルな実例プログラムを用いながらわかりやすく説明します。高性能なプログラムの書き方だけでなく、高性能なシステムの作り方を総合的に学ぶことができるPythonエキスパート必携の一冊です。

https://www.oreilly.co.jp/books/9784873117409/

ここにも書いてあるように、プロファイリングのやり方からデータ構造、Cコンパイル・並列並行処理など幅広い内容が扱われていた。CPython以外の実装について勉強しようと思ってこの本を読み始めたので、個人的には「7章 Cにコンパイルする」が特に面白かった。

また普段はI/Oバウンドなプログラムを書くことが多いので、RAM使用量の削減とかそのためのプロファイリングなどCPUバウンドなプログラムについての知見が得られてよい。

時間ができたら次は積ん読になってるCythonのやつを読もう。

Cython ―Cとの融合によるPythonの高速化

Cython ―Cとの融合によるPythonの高速化

読書メモ

3章 リストとタプル

  • リストは動的な配列
  • タプルは静的な配列
  • サイズが1~20の小さなタプルについては、使われなくなってもメモリがOSに返却されず、将来の再利用のために保持される
>>> %timeit l = [0, 1, 2, 3, 4, 5 ,6, 7, 8 ,9]
96.8 ns ± 1.22 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
>>> %timeit t = (0, 1, 2, 3, 4, 5 ,6, 7, 8 ,9)
16.4 ns ± 0.205 ns per loop (mean ± std. dev. of 7 runs, 100000000 loops each)

4章 辞書と集合

5章 イテレータとジェネレータ

def fibonacci():
    i, j = 0, 1
    while True:
        yield j
        i, j = j, i +j
def fibonacci_succinct():
    is_odd = lambda x: x % 2
    first_5000 = islice(fibonacci(), 0, 5000)
    return sum(1 for x in first_5000 if is_odd(x))
  • ジェネレータで省メモリで高速な処理が可能
    • 遅延評価

6章 行列とベクトルの計算

  • メモリ断片化

    • リストはデータそのものではなくポインタを保持している
      • どんな型でも格納できるのでたいていの場合では便利
      • ベクトルや行列の演算においては、著しい性能劣化の原因に
      • データをメモリ上の連続した１つのブロックとして扱うことができれば、データ全体を一回の操作で移動できる
      • データが断片化されていると、ブロック全体を移動できず、各位要素をばらばらに移動する必要がある
    • ループがベクトル化に対応していない
      • 一度に1つの要素を演算するループを、ひとまとまりのデータに対して同時に処理したい

  • numpy導入

    • 効率のよいベクトル化演算パッケージ
    • データを連続的なメモリ領域に保持し、ベクトル演算命令をサポート
    • +=や*=などのインプレース演算は、入力の1つを出力として も使うから、計算結果を格納するための領域を確保する必要がない
    • numexpr

7章 Cにコンパイルする

  • AOTコンパイラ

    • Cython
    • Shed Skin
    • Pythran

  • JITコンパイラ

    • Numba
      • Continuum(Anaconda)謹製
      • @jitデコレータを付けるだけ
    • PyPy
      • GCのやり方が違う
        • CPythonは参照カウント法/PyPyはマーク&スイープ法
      • Cによる拡張ライブラリには効果がない
        • Pythonのコードを高速化するのが仕事
      • RAMの使用量が多い
  • CPython Compiler Tools
    • ここに色々まとまってる
  • PyPyはPython3・Numpy対応できるように進化しててすごい
  • ctypes
    • 外部関数インターフェース
    • 引数をCの型へキャストする必要あり
    • 複雑でメンテナンスが大変になりやすい
  • cffi
  • f2py

8章 並行処理

  • イベントループで並行処理を実現
    • 2つの考え方
      • コールバック
      • Future
  • gevent
    • http://www.gevent.org/
    • 標準 I/O 関数を非同期に変えるモンキーパッチ
    • 軽量スレッドで並行処理ができるGreenlet
      • 複数のCPUを使わずに、イベントループを使うことによって I/O 待ちの間にgeventのスケジューラがGreenletを切り替える
    • grequests知らなかった
  • tornado
    • http://www.tornadoweb.org/en/stable/
    • コールバックの方法を採用していたけど、バージョン3.xからは、互換性を保ったまま、コルーチ 風の処理が追加された
    • イベントループは全体で動作していて、非同期I/Oにかぎらず プログラムの実行の流れを制御している
    • geventはiwait関数が実行している間だけイベントループが動作
  • asyncio
    • asyncioライブラリは、tornadoやgeventのようなモジュールと組み合わせて、同じイベントループで動作させることも可能
  • やっぱり標準ライブラリがいいよね

9章 multiprocessingモジュール

  • embarrassingly parallel問題(あきれるほど 簡単に並列化可能な問題)
    • ジョブを互いに独立な単位に分割する
    • ワーカーによって計算時間にばらつきがあるのなら、処理の順序をランダム化することを検討する
    • 処理の遅い順に並べて、もっとも遅い処理から先に片づける
    • 検証された理由がないかぎり、デフォルトのchunksizeを用いる
    • チャンク数を物理コア数の倍数にすること
  • 可能なら自前で非同期システムを作るのは避ける
    • geventのような成熟したライブラリがbetter
    • 外部のキュー管理システムについてもCeleryとかを使おう

10章 クラスタとジョブキュー

11章 RAM使用量を削減する

  • テキスト処理アルゴリズム
    • トライ
    • DAWG(有向無閉路文字列グラフ)
  • RAM使用量を削減するコツ
    • 数値データを扱うならnumpy
    • ジェネレータを使う(Python2.x: xrange/Python3.x: range)
    • 大量のUnicodeオブジェクトを使うならPython3.3+
    • ビット列を太陽に使うならnumpy/bitarray
  • 確率的データ構造
    • 精度を犠牲にしてメモリの使用量を膨大に削減