Pythonコードのプロファイリング

普段、Pythonのコードは何となく速かろうという、言ってみれば勘で書いているのだけど、その勘とやらは往々にしてウンコードを生むものである。そこで、プロファイラを使っていきたいと思う。

使えそうなツール

そういうわけで、いくつか使えそうなツールをリストアップした。

経過時間のプロファイラ

ツール名 メモ
profile ビルトイン, ピュアPythonの決定論的プロファイラ
cProfile ビルトイン, C拡張の決定論的プロファイラ
line_profiler 行単位の決定論的プロファイラ
Plop 統計的プロファイラ, Dropboxの人が作ってる
statprof 統計的プロファイラ, 開発停止?
yep 拡張モジュール用の統計的プロファイラ, バックエンドにgoogle-perftools

メモリのプロファイラ

ツール名 メモ
memory_profiler 行単位でメモリ消費量の増減を記録
Heapy オブジェクトごとのメモリ消費量を記録
Pympler 同上, 新参プロジェクト

可視化ツール

ツール名 メモ
RunSnakeRun cProfile用の可視化ツール
Gprof2Dot.py cProfileの結果をGraphviz用のDOTファイルに変換
pycallgraph cProfileの結果からGraphvizを用いてコールグラフを作成


物は試しということで、ざっくり使ってみた。
使ってみた感じだと、cProfile, line_profiler, memory_profiler, pymplerあたりが良いかなーという感じがしている。

続きを読む

docopt

PyCon UK 2012の動画を見てたら面白いもの見つけたのでメモ。

docoptというもので、コマンドラインツールを作るときに、docstringを解析して引数をパースしてくれる優れもの。
http://docopt.org/

docstringのUsageセクションに用例を書いておくとそれを解析してくれる。例えば、

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""Test

Usage:
    test ship new <name>
    test ship <name> move <x> <y> [--speed=<kn>]
    test ship <name> (<from> <to>)...
    test ship shoot <x> <y>
    test mine (set|remove) <x> <y> [--moored|--drifting]
    test -h | --help
    test --version
Options:
    -h --help       Show this screen.
    --version       Show version.
    --speed=<kn>    Speed in knots [default: 10].
    --moored        Moored mine.
    --drifting      Drifting mine.

"""

from docopt import docopt

print docopt(__doc__, version="0.1.0")

を実行すると

% ./test ship new hoge
{'--drifting': False,
 '--help': 0,
 '--moored': False,
 '--speed': '10',
 '--version': 0,
 '.': False,
 '10': False,
 '<from>': [],
 '<name>': 'pig',
 '<to>': [],
 '<x>': None,
 '<y>': None,
 'Drifting': False,
 'Moored': False,
 'Options:': False,
 'Show': 0,
 'Speed': False,
 'default:': False,
 'in': False,
 'knots': False,
 'mine': False,
 'mine.': 0,
 'move': False,
 'new': True,
 'remove': False,
 'screen.': False,
 'set': False,
 'ship': True,
 'shoot': False,
 'this': False,
 'version.': False}

みたいにディクショナリを返してくれる。

間違った使い方をして、解析できなかったら、docstringを表示する

% ./test sleep
Usage:
    test ship new <name>
    test ship <name> move <x> <y> [--speed=<kn>]
    test ship <name> (<from> <to>)...
    test ship shoot <x> <y>
    test mine (set|remove) <x> <y> [--moored|--drifting]
    test -h | --help
    test --version
Options:
    -h --help       Show this screen.
    --version       Show version.
    --speed=<kn>    Speed in knots [default: 10].
    --moored        Moored mine.
    --drifting      Drifting mine.

便利っぽいですね。

簡単に表記について説明すると、

  • "< >" で囲んだものは、必須の引数とみなす。上で言うと、ship の後ろの は必須だから、指定しないとdocscringを表示する。
  • "[ ]" で囲んだものは、任意の引数とみなす。上で言うと、--speed とかは指定しなくても良い。
  • "( )" はグルーピングするために使う。上で言うと、from と to を両方指定しないといけない。
  • "..." は前の引数を複数個指定するときに使う。上で言うと、from と to のペアを複数個指定することが出来る。
  • "[default: val]" を、Optionsセクションで指定すると、任意の引数にデフォルト値を設定することが出来る。上で言うと、--speed を省略した時に、デフォルト値の10が返される。

という感じ。それからオプションにはショートオプション( "-" )とロングオプション( "--" )があって、ショートオプションは連続指定できる。例えば、"-abc" は "-a -b -c" と等価に扱われる。

API

docopt(doc, argv=None, help=True, version=None, options_first=False)

だけ。

  • argv は、引数のリストで、デフォルトで sys.argv[1:] が渡される。
  • help は、False にすると、-h あるいは --help に手動で対応できる。デフォルトでは True で、docstring を表示して終了する。
  • version は、--version が渡された時に表示するバージョンを指定できる。
  • options_first は、True にすると、最初にオプションの指定をすることを強制できる。というか後ろに渡された場合は必須引数とみなされる。

詳しい説明は、http://docopt.org/ へ。Rubyとかの実装もあるらしい。

Pythonのリスト内包表記をdisる

 Pythonにはリスト内包表記という可読性を著しく損なう記法がある。でも、リスト内包表記は何故か速くて、for文を書く前にそれがリスト内包表記で書けないか考えることになっている。

どれくらい速いのか。普通のforループと比較してみる。

#普通のループ
def loop(i):
    result = []
    for x in range(i):
        result.append(x)
    return result

#リスト内包表記
def compre(i):
    return [x for x in range(i)]

以下は100ループを100万回行った時の実行時間

>>import timeit
>>timeit.__dict__.update(loop=loop, compre=compre)
>>timeit.Timer('loop(100)').timeit()
16.42305278778076
>>timeit.Timer('compre(100)').timeit()
8.095446825027466

速い!やばい!100万回だから1回あたりの差は殆どないけど、ネストとかめちゃくちゃしたら意味のある差になると思う。

 確かに速いんだけど、リスト内包表記がPythonの哲学に沿ってないという意見がある。でも正直、その辺は僕には分からない。いわゆるPythonistaな人たちが大切にしているPEPという文書があって、Pythonに関する重要なことが詰まっている。有名なのは「PEP 20 - The Zen of Python」と「PEP 8 - Style Guide for Python Code」で、みんな読むらしい。このPEP20に、可読性が大事とか、複雑なのは駄目とか書いてある。

 というのは置いておいて、大事なのはリスト内包表記はとにかく速いってこと。じゃあ、なんで速いのかってことを書きたい。このことについて、エキPyを読んでいると、ちょうど記述が見つかって、

リストに要素を append() する場合、インタプリタは「リストから append 属性を取り出してそれを関数として呼び出す」という処理をしなければなりません。 それに対して、リスト内包表記を使うと、インタプリタに直接「リストに要素を追加する」という処理をさせることができます。インタプリタが解釈する命令数が減る、属性の取り出しが不要になる、関数呼び出しが不要になる、という3つの理由で、リスト内包表記を使うと速くなります。

とある。ふむふむ。分からん。この本、エキスパートじゃないと理解できない仕様みたいです。

 これを脚注に入れた稲田さん(@)という凄い人が、その内容を以下の記事で解説している。

DSAS開発者の部屋:Pythonの内包表記はなぜ速い?

この記事によれば、リスト内包表記が、for文でappendするより速い理由は

  1. listオブジェクトからappend属性を取り出さなくて良い
  2. 関数呼び出しがない

の2点らしい。後者はappendを呼びださなくて良いということ。とくに前者の、属性の取り出しが不要であることが、大きく貢献しているらしい。

 そこで、理解のためにまず上の記事を再現してみる。内部でどんな処理になっているのか確かめるために、Pythonのバイドコートを逆アセンブルするdisというモジュールを使う。比較するのは上の2つの関数(loopとcompre)

>>import dis
>>dis.dis(loop) #普通のループ
  2           0 BUILD_LIST               0
              3 STORE_FAST               1 (result)

  3           6 SETUP_LOOP              33 (to 42)
              9 LOAD_GLOBAL              0 (range)
             12 LOAD_FAST                0 (i)
             15 CALL_FUNCTION            1
             18 GET_ITER            
        >>   19 FOR_ITER                19 (to 41)
             22 STORE_FAST               2 (x)

  4          25 LOAD_FAST                1 (result)
             28 LOAD_ATTR               1 (append)
             31 LOAD_FAST                2 (x)
             34 CALL_FUNCTION            1
             37 POP_TOP             
             38 JUMP_ABSOLUTE           19
        >>   41 POP_BLOCK           

  5     >>   42 LOAD_FAST                1 (result)
             45 RETURN_VALUE    
>>  
>>dis.dis(compre) #リスト内包表記
  2           0 BUILD_LIST               0
              3 LOAD_GLOBAL              0 (range)
              6 LOAD_FAST                0 (i)
              9 CALL_FUNCTION            1
             12 GET_ITER            
        >>   13 FOR_ITER                12 (to 28)
             16 STORE_FAST               1 (x)
             19 LOAD_FAST                1 (x)
             22 LIST_APPEND              2
             25 JUMP_ABSOLUTE           13
        >>   28 RETURN_VALUE   

命令コードの一覧は 31.12. dis — Python バイトコードの逆アセンブラ — Python 2.7ja1 documentation にある。結果を見るとリスト内包表記も、forでゴリゴリ回すというのは同じらしい。注目すべきは、上の記事で言われている、append属性の取得と関数呼び出しの部分がどうなっているかだ。
 普通のループの方を見ると、loop関数の4行目を実行する段階でLOAD_ATTRを実行している。そしてその後に、CALL_FUNCで関数を呼び出している。一方で、リスト内包表記の方を見ると、LIST_APPENDを実行しているだけだ。

 ここで、属性の取得がどれだけ重いのか見るために、以下の関数を使う。

def appnd(i):
    l = []
    for x in range(i):
        a = l.append

append属性をひたすら取得している。これを先ほどのloop関数と実行時間を比較する。

>>timeit.Timer('loop(100)').timeit() #リストのappendを行うループ
16.42305278778076
>>timeit.Timer('appnd(100)').timeit() #append属性の取得だけを行うループ
9.775523900985718

実行時間の大体6割くらいが、append属性の取得によるものだった。確かにこの部分がなければ速くなりそう。

 属性の取得が重い処理だということは分かったけど、どうして重いのか。その点に少し触れている論文があった。

Type Resolution and Access consumes a significant fraction of time. For most benchmarks, this classes of bytecodes takes more than 20% of the time. In the CPython implementation, subsequent executions of the same LOAD_ATTR, say in a loop, causes the type resolution to be redone even in cases when invariance of the outcome is guaranteed. CPython does no effort to optimize this save for caching of bound methods by the type they are bounded to and the method name. This cache, however, is referenced late in the bytecode handler, making it inefficient.
http://www.cs.ucsb.edu/research/tech_reports/reports/2010-14.pdf

 それから稲田さんの記事によれば、この辺の実装はceval.cになるので、少し覗いてみた。Pythonでは、属性の取得をするとき、オブジェクトと属性名が渡される。そこでまず、オブジェクトの型を解決する必要がある。そして、オブジェクトの型が分かると、今度は属性を探す。まず、クラスの属性を見て、見つかればスタックに追加する。そのあと、インスタンスの属性を見て、見つかればスタックに追加する。これをループの中でぐるぐる回して、見つからなくなればbreakする。最後に、スタックからpopして属性を取得する、という流れになる。ここで取得した属性を、キャッシュせずにループの中で毎回行なっているそうな。これは、ループの中で属性が変更されたり、参照先のオブジェクトが変わったりするから。
 というわけで、普通にループで回すときは、LOAD_ATTRで属性を取得して、取得した属性をCALL_FUNCで呼び出すという処理を毎回行なっている。一方で、リスト内包表記はリストにappendすることが分かっているので、直にLIST_APPENDを実行できるということ。だから速い。

まとめ
 リスト内包表記は、append属性の取得がない分、forループでappendするより速い。つまり、稲田さんの記事にもある通り、属性の取得がなければforループもそこそこ速い。ただ、mapとかで書ける場合、たとえば

def mapstr(i):
    return map(str, range(i))

のような処理は、リスト内包表記より速い場合が多い。それにリスト内包表記より読みやすい。そこで、なんとなく以下のような基準で書けば良い気がする。

  • mapやfilterが使える場合は使う
  • それ以外で、リスト内包表記で簡単に書ける場合はリスト内包表記を使う
  • もし複雑になるときは可読性のためにforループを使う
  • forループを使うとき、入力サイズが大きければ属性の取得をループから掃き出す

つまり実行速度も大切だけど、Pythonなんだから可読性も大切にしたいよね。ってことが言いたかった。というわけで、disモジュールを使ってリスト内包表記をdisってみたのだった。

おまけ
クイックソートです

def qs(l):
    if len(l) == 0: return l
    return qs([x for x in l[1:] if x < l[0]]) + [l[0]] + qs([x for x in l[1:] if x >= l[0]])

リスト内包表記ステキ!