DSAS開発者の部屋

Pythonの内包表記はなぜ速い?

「エキスパートPythonプログラミング」の発売が、Amazonや一部の書店で始まりました。

今回は、「エキスパートPythonプログラミング」の2章から、リスト内包表記について補足します。 本書で、リスト内方表記が速い理由について、次のような訳注を書きました。

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

今回はこの訳注の内容について、詳しく見ていきましょう。いきなりですが、内包表記を使う関数と使わない関数を用意して、実行速度とバイトコードを比較してみます。

In [1]: def sample_loop(n):
 ...: L = []
 ...: for i in xrange(n):
 ...: L.append(i)
 ...: return L
 ...:
In [2]: def sample_comprehension(n):
 ...: return [i for i in xrange(n)]
 ...:
In [3]: %timeit sample_loop(10000)
1000 loops, best of 3: 1.03 ms per loop
In [4]: %timeit sample_comprehension(10000)
1000 loops, best of 3: 497 us per loop
In [5]: from dis import dis
In [6]: dis(sample_loop)
 2 0 BUILD_LIST 0
 3 STORE_FAST 1 (L)
 3 6 SETUP_LOOP 33 (to 42)
 9 LOAD_GLOBAL 0 (xrange)
 12 LOAD_FAST 0 (n)
 15 CALL_FUNCTION 1
 18 GET_ITER
 >> 19 FOR_ITER 19 (to 41)
 22 STORE_FAST 2 (i)
 4 25 LOAD_FAST 1 (L)
 28 LOAD_ATTR 1 (append)
 31 LOAD_FAST 2 (i)
 34 CALL_FUNCTION 1
 37 POP_TOP
 38 JUMP_ABSOLUTE 19
 >> 41 POP_BLOCK
 5 >> 42 LOAD_FAST 1 (L)
 45 RETURN_VALUE
In [7]: dis(sample_comprehension)
 2 0 BUILD_LIST 0
 3 DUP_TOP
 4 STORE_FAST 1 (_[1])
 7 LOAD_GLOBAL 0 (xrange)
 10 LOAD_FAST 0 (n)
 13 CALL_FUNCTION 1
 16 GET_ITER
 >> 17 FOR_ITER 13 (to 33)
 20 STORE_FAST 2 (i)
 23 LOAD_FAST 1 (_[1])
 26 LOAD_FAST 2 (i)
 29 LIST_APPEND
 30 JUMP_ABSOLUTE 17
 >> 33 DELETE_FAST 1 (_[1])
 36 RETURN_VALUE

実行速度は、リスト内方表記の方が倍以上速いですね。 バイトコードについては詳しくは解説しませんが、 sample_loopは "19 FOR_ITER" から "38 JUMP_ABSOLUTE" までの8命令、sample_comprehensionは "17 FOR_ITER" から "30 JUMP_ABSOLUTE" までの6命令がループになっています。 インタプリタはこれらの命令を読み込んで実行というループを行っているので、まずは命令数の削減が高速化の理由の1つになります。 さらに、ループの中の処理について見ていきましょう。

1. append属性の取り出し

sample_loop のバイトコードで、 "23 LOAD_ATTR" という部分が、 "L" という変数からロードしたオブジェクトから "append" という属性を取り出しています。 属性の参照がどれくらい重い処理なのか、 属性の参照はそれなりに「重い」処理です。試しに、 append 属性の参照をループの外に追い出してみましょう。

In [19]: def sample_loop2(n):
 ....: L = []
 ....: append = L.append
 ....: for i in xrange(n):
 ....: append(i)
 ....: return L
 ....:
In [20]: %timeit sample_loop2(10000)
1000 loops, best of 3: 549 us per loop

リスト内方表記を利用した場合に比べて1割程度しか遅くありません。実は、元のコードのオーバーヘッドの大半は、append属性の参照にあったという事になります。

ちなみに、バイトコードは載せていませんが、LOAD_ATTRが無くなった分命令数も8命令から7命令に削減されています。

2. 関数の呼び出し

リスト内包表記が速い残り1割の理由は、 "29 LIST_APPEND" という命令にあります。

内包表記を使わない場合は、 "13 CALL_FUNCTION" によって、 append を「Pythonの関数として実行」する必要があります。この「Pythonの関数として実行」というのは、 スタックから引数リストを作成する必要があったり、呼び出される関数の方で引数のチェックをしていたり、関数の戻り値の処理("37 POP_BACK" など)が必要になります。

それに対して、 "LIST_APPEND" という命令はリストオブジェクトに要素を追加する専用の命令なので、内部ではリストへの要素の追加のみが行われるようになります。

まとめ

リスト内方表記を使うと速くなる仕組みを、バイトコードレベルで解説しました。もっと下まで知りたい方は、Pythonのソースコードの ceval.c というファイルから、 CALL_FUNCTION と LIST_APPEND の処理をしている部分を追ってみてください。

また、速くなる理由の大半は、属性の参照コストにありました。このコストは、内包表記を使わなくても、メソッドをループの手前でローカル変数に代入するというテクニックでも回避できます。このテクニックはリストのappendメソッド以外にも任意の属性に利用できるので、ボトルネックになるかもしれないループを書くときには積極的に利用しましょう。