Pythonでメモリを食い過ぎた時に見直すポイント
ちょっと複雑なアルゴリズムをPythonで実装してみて、自分の予想以上にメモリを食ってしまったので何が原因なのかプロファイルしてみた。
辞書を大量に使ってはいけない
指摘されてみれば当たり前のことなんだけども、辞書はハッシュテーブルなのでメモリをたくさん使う。「グラフの頂点ごとに整数→整数のマッピングを持ちたいな」と思って、うっかり辞書を使ってしまったのだが、エントリー数が6個でも 1048バイト×頂点数 のメモリが吹っ飛んでいく。いくらハッシュのアクセスがO(1)だからといって、1048バイトmallocしてスラッシング起こしてんだったら全然安くない。エントリの個数とアクセス頻度によってはO(n)で線形探索したほうがよっぽどよい。
エントリーの個数が5件までならハッシュテーブルではないコンパクトな持ち方をするので280バイト。それでもでかい。
自作クラスのインスタンスも辞書を持っている
Cのstructみたいなものだと思ったら大間違いで、オブジェクトのメンバ変数は辞書に格納されている。だから「この頂点クラスは整数を3つ持っているだけだ」と思っていても、さらに辞書の280バイトを支払っている。
__slots__を使う、という解決策を提案する人もいるかもしれないが次の項目も参照。
そもそもオブジェクトをたくさん作ってはいけない
そもそも整数オブジェクトって何バイト?
正解は値(long)が8バイト、に加えて型オブジェクトへのポインタ(8バイト)と、参照カウンタ(ssize_t: 8バイト)がついて全部で24バイトだ。
(注: もちろん環境やコンパイルオプションに影響されるのでここでは筆者の環境での例をあげている)
というわけで大量の整数の集まりを、計算の途中で一時的にPythonのオブジェクトとして扱うならまだしも、その形のまま大量に貯めこむのは筋が悪い。標準ライブラリにはarrayやstructといったコンパクトに値を持つためのクラスが用意されているのでそれを使うべき。
結論
オブジェクトは使うな、ベタな配列で値をもて…それって素直にCで書いたほうがよかったんじゃないか?