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]])

リスト内包表記ステキ!