概要
原著者の許諾を得て翻訳・公開いたします。
- 英語記事: Lifelong Rubyist makes some Python code 5x Faster
- 原文公開日: 2017/10/02
- 著者: Richard Schneeman
ベテランRubyistがPythonコードを5倍速くした話（翻訳）
私はかれこれ10年以上Rubyコードを書きまくっていますが、最近は修士科目の関係でPythonコードも書きまくっています。RubyとPythonは多くの点で違っていますが、パフォーマンス上の特性やコードの最適化といった面では似ています。本記事では、私が最近最適化したPythonコード片を題材に、Rubyコードの場合の高速化手順と比較してみることにします。
本記事について「Pythonインタプリタの高速化かと思った」というご感想をいくつもいただきました。それはそれできっとクールだったでしょうが、この記事はそちらではなく、インタプリタ言語を使うコードの高速化を扱います。ここで学んだことは、PythonにもRubyにも通用します。
そのコードをご覧に入れる前に、ご存じない方のために一応私のパフォーマンス方面について書いておきます。私の趣味のひとつがRubyのパフォーマンスであり、Railsアプリのベンチマークに使われるderailed benchmarks gemのメンテナでもあり、多くのプロジェクトでパフォーマンス関連のプルリクを大量に送りました。Railsのend-to-endリクエストをほぼ12%高速化するプルリクを送った後、なりゆきで「すべての文字列をfreezeする」運動の促進担当者になったこともあります。パフォーマンス向上といっても、そのほとんどはhash（Pythonではdict）やarray（Pythonではlist）の代入の削減によって得られたものです。
警告: 私はlistとarrayを互いに交換可能なものとして用いる傾向があります。メソッドと関数についても同様です。これらが同じでないことも、これを見てカッとなって眼から血を吹く人がいることも承知していますので、どうかご容赦ください。
私にとってパフォーマンスの改善はこれが初めてではありません。
何かを高速化する前には、仕組みを理解しておかなければなりません。次の課題を設定します。
コードの仕組みについて関心のない方は、最適化でできることを解説する次節「ロジックをDRYにする」までスキップしていただいて結構です。
本記事で最適化するコードは、チェスに似たゲーム盤上でクイーンの移動方法をすべて特定する必要のあるゲームのプレイで用いられるものです。かつ、このゲーム盤の高さと幅は変更可能とします（実際のチェス盤とは異なることもある）。また、ゲーム盤のステートはlistのlist（Rubyではarrayのarray）で表現します。
空白は0で表します。ゲーム盤のステートは次のような感じになります。
height = 7
width = 7
board_spaces_occupied = [
[ 1, 0, 1, 1, 1, 0, 0],
[ 1, 1, 0, 1, 1, 0, 1],
[ 1, 1, 1, 1, 0, 0, 1],
[ 1, 0, 1, 0, 1, 1, 1],
[ 1, 0, 0, 1, 1, 1, 1],
[ 0, 0, 1, 0, 0, 1, 1],
[ 0, 1, 1, 0, 1, 1, 1],
]
詳細はもっと複雑ですが本記事とは無関係なので、さしあたってここまで理解できれば十分です。きっとRedditで「numpy使えばいいのに」とツッコミが入ることでしょう。numpyはこの特定の代入規則に合わなかったのです。
有効な移動先を特定するタスクを完了するため、次のPythonコードの変種を授業で与えられました。
BLANK = 0
def get_legal_moves_slow(move):
r, c = move
directions = [ (-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1)]
fringe = [((r+dr,c+dc), (dr,dc)) for dr, dc in directions
if move_is_legal(r+dr, c+dc)]
valid_moves = []
while fringe:
move, delta = fringe.pop()
r, c = move
dr, dc = delta
if move_is_legal(r,c):
new_move = ((r+dr, c+dc), (dr,dc))
fringe.append(new_move)
valid_moves.append(move)
return valid_moves
def move_is_legal(row, col):
return 0 <= row < height and\
0 <= col < width and\
board_spaces_occupied[row][col] == BLANK
元のコードは授業で使われたものですが、本記事に合わせて形式を少し簡単にしてあります。
heightとwidthとboard_spaces_occupiedはいずれもグローバルにアクセスできる変数です。
移動元として(5, 4)を渡すと、クイーンの移動先が2つしかないことが正しく示されるので、正常に動作していることがわかります。
print get_legal_moves_slow((5,4))
# => [(6, 3), (5, 3)]
Rubyistのために補足すると、このかっこは「タプル」であり、イミュータブルなarrayに含まれているとお考えください。Rubyならさしずめ
[[6, 3], [5, 3]]のような感じになるでしょう。
このコードを高速化するには、そこで行われていることを理解する必要があります。ロジックを追ってみることにします。
クイーンは、自分のいる場所から縦横斜めに移動できます。移動距離は、途中に遮るものがない限り盤上でいくつでも移動できます。この動作を表すために、クイーンのすぐ周りにある空き位置をすべて見つけたいと思います。空き位置は、横方向の（row）移動と縦方向（column）の移動で表します。
directions = [ (-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1)]
次に各空き位置を列挙して、クイーンがルールに違反せずにそこに移動できるかどうかをチェックします。
これを行うには、各移動方向をループして現在の横位置と縦位置に結合し、有効かどうかをそれぞれチェックします。
移動方向が有効な場合は、有効なマスの位置だけではなく、有効なマスへの到達方法（移動方向など）も保存します。この「移動方向」を繰り返しその先に展開して、他の有効な移動も見つけます。
fringe = [((r+dr,c+dc), (dr,dc)) for dr, dc in directions
if move_is_legal(r+dr, c+dc)]
注意:
rはrow（横方向）、cはcolumn（縦方向）を表します。drは横方向の差分、dcは縦方向の差分を表します。きれいな変数名は使われていません。なお文法をググりたいRubyist向けに補足すると、Pythonのこのようなlist列挙形式は「list comprehension」と呼ばれます。
これで、展開可能なfringe listを得ました。これをビジュアル表示する例を見てみることにします。
訳注: fringeは「付随」「メインでない」といったニュアンスです。コードと整合するよう英ママとしました。
完全に空になっているゲーム盤上に(3, 3)を置くと、そこから左斜め上のマスへの移動は(2, 2)になります。そこへの移動は、移動方向を表すarrayの最初の要素(-1, -1)を用います。これで、fringe listは次のようになります。
# [((row, column), (delta_row, delta_column))]
[((2, 2), (-1, -1))]
その先を展開したい場合は、現在の位置に同じ移動方向(-1, -1)を適用して(1, 1)を得ます。
これで、利用できないマスに到達するまで、空きマスの周囲にある展開の必要な位置を即座に得ることができます。
次のコードは、展開を最後まで行います。
valid_moves = []
while fringe:
move, delta = fringe.pop()
r, c = move
dr, dc = delta
if move_is_legal(r,c):
new_move = ((r+dr, c+dc), (dr,dc))
fringe.append(new_move)
valid_moves.append(move)
このコードでfringe listの各要素を列挙し、削除してから、移動が有効かどうかをチェックして、横方向の移動差分と縦方向の移動差分を適用して新しい位置を得ます。そしてこの新しい位置をfringe listに追加し、元の位置もvalid_moves listに追加し、後者が戻り値になります。
ここまでご理解いただけましたでしょうか。ここではループ内で同じゲーム盤に対してこのコードが何度も繰り返し呼び出されるので、ループの実行時間にまんべんなく影響します。
以上で、コードの動作と最適化方法について理解いただいたかと思います。
この後のセクションでは、RubyとPythonのどちらにも適用できたスクリプト言語の最適化手法のコンセプトについて解説します。Pythonコードを高速化する方法を理解できれば、任意のスクリプト言語を高速化できるようになります。最終的なコードやベンチマークは最後に示します。
ロジックをDRYにする
最適化の基本のひとつは、作業の重複を解消することです。ある要素をfringe listに1つ置くと、その位置はlist comprehensionで既に有効性がチェック済みになりますが、そのlistから他の要素を取り出すときに同じ要素について有効性を繰り返しチェックしてしまっています。つまり、8つのマスが有効な場合、各マスを2回ずつチェックしなければならなかったということです。
このチェックを1回に減らせば高速化できます。
オブジェクトよりロジックを優先する
スクリプト言語におけるオブジェクト作成は、メモリもCPUサイクルも消費します。このメモリを後でGC（ガベージコレクション）するときに、CPUサイクルを余分に消費してしまいます。
オブジェクトによっては、作成のコストが低いものがあります。複雑なオブジェクトは、その分作成やコピーに時間がかかります。list（Rubyで言うarray）やdict（Rubyで言うhash）は、stringよりもずっと作成コストが高くなります。同様に、stringよりもintegerの方が作成コストは低くなります。
このあたりの説明は難しいので、無理矢理な例を作りました。None（Rubyで言うnil）またはNoneでない値を1つ与えられ、これをlistに追加して後で処理するとします。次の例をご覧ください。
my_list = [value] # <== ここでlistに割り当てられる
if None in my_list:
return
# ...
上の例では、listと関係ない場合であってもlistの割り当てが発生してしまいます。そこで、次のようにarrayの割り当てが発生する前に値をチェックすればずっと高速になります。
if value is None:
return
my_list = [value]
# ...
もちろん、最初の例のようなコードを書く人はまずいないことは承知していますが、要点はご理解いただけると思います。
オブジェクトは遅く、ロジックは速い。これはRubyとPythonのどちらにも通用する真理です。
シリアライズ方法に注意
オブジェクト生成削減の際に考えておく点が2つあります。オブジェクト生成の実際のオーバーヘッドと、そのオブジェクトの参照方法や使用方法です。オブジェクトが割り当てられた後、どのように操作されるのでしょうか。
ここでは、データをシリアライズして内部から値を取り出し、タプルからの値の取り出しにコストがかかる様子を観察したいと思います。この例では、位置をタプルから展開しています。
move = (1, 0)
# ...
r, c = move
rやcの取り出しコストはゼロではありません。次のよく似た2つの関数をご覧ください。
def function_one(move):
r, c = move
return r + c
def function_two(r, c):
return r + c
タプルを渡すよりも、function_twoのように値をバラして渡す方がはるかに高速です。kernprofでベンチマークを取ってみたところ、function_oneではタプルから値を取り出さないと利用できないため、倍の時間がかかりました。
パフォーマンスを最大限に改善するためには、データ操作を可能な限り最小限に絞るのが理想的です。
ループ内のリテラルに注意
JITを持たないスクリプト言語で、次のコードが呼び出されるたびに何が起きるでしょうか。
valid_moves = []
呼び出しコストの非常に高いarrayが割り当てられます。コード例ではループ内でリテラルを明示的に使っていませんが、このコードがどのように実行されるかについても考慮が必要になることがあります。本記事のコード例では、このget_legal_moves_slow関数は何度も何度も繰り返し呼び出されます。上のコード例でforやwhileは使われていないからといって、このコードがループ内に置かれないとは言い切れません。
この場合、改変が発生してこの関数が呼び出されるたびにvalid_movesが必要になります。変更されない静的な値がいくつもあることにお気づきでしょうか。
次の場合で考えてみましょう。
directions = [ (-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1)]
比較的読みやすいこのちっぽけなコードが呼び出されるたびに、1つのlist、8つのタプル、16のinteger参照が割り当てられてしまいます。このlistは決して改変されないのですから、これを関数の外に追い出して、起動時に1回しか作成されないグローバル定数に保存すれば、割り当てを大幅に削減できます。
チェックせずにスキップせよ
同じチェックを2回繰り返さないことについては既に述べました。最も高速なコードは「コードを書かないこと」です。理想のチェック回数は、ずばりゼロ回です。
そのために安全でないコードを書けということではありません。しかし、絶対ありえないシナリオの存在に気づくことができれば、そのチェックは不要になります。
コード例のどこに適用すればよいでしょうか。次をご覧ください。
def move_is_legal(row, col):
return 0 <= row < height and
0 <= col < width and
board_spaces_occupied[row][col] == BLANK
ゲーム盤のマスが空いているかどうかをチェックする前に、ゲーム盤からはみ出していないかどうかをチェックしています。
どうすればこのチェックを削除できるでしょうか。1つの方法は、ゲーム盤の周りに境界を設定して、移動を展開したときにマスが空いていないことがわかるようにすることです。しかしこの方法では他の計算の難易度が上がってしまいます。
ロジックを曲げずに行う方法は1つありますが、それについては後述します。ここでのポイントは、チェックロジックを削除可能かどうかを検討することです。
メソッドがなければ問題もなくなる
メソッド呼び出し（Pythonでは関数呼び出し）のコストはゼロではありません。あるメソッドが呼び出されると、インタプリタはそのメソッドが存在する場所を探索してからコードを呼び出さなければなりません。
メソッドはコードをクリーンかつ理解しやすくするうえで有用ですし、ボトルネックの99%はメソッド呼び出しではないので、メソッドを削ってしまえと書くのはためらわれます。メソッドの削除は最適化としては非常に微細なものですが、それでも一片の真実はあります。
メソッド探索の回数についても考えてみましょう。Pythonの実装でlistのインデックスが何回探索されるのかは私も知りませんが、Rubyの場合はメソッドとして探索されます。
board_spaces_occupied[row][col] == BLANK
したがって、上のコードでは探索が1回ではなく2回実行されます。1回目はboard_spaces_occupied[row]にアクセスします。listが返されると、colを介して2つ目の要素にアクセスします。
メソッドを削除して操作の回数を削減できれば、1つのデータ構造に対して操作を実行することで高速化できるはずです。
ありがたいことに、メソッド呼び出し回数やarrayのインデックス参照などは、（言語の）コア開発者によって最適化されているので十分速いのが普通であり、したがって最適化する意味がありません。
言い換えると、プログラムを歪めてまで探索やメソッド呼び出しの回数を減らしてはいけません。（プログラムを歪めずに）探索を簡単に減らせるなら、ぜひそうしましょう。
ベンチマークを取る
パフォーマンス厨の皆さんに警告: コードのパフォーマンスをチューニングするときには、必ず変更前/変更中/変更後にベンチマークを取りましょう。本記事でのアドバイスはほとんどの場合一般的に通用しますが、特定のユースケースには適していないこともありえます。だからこそベンチマークは絶対省略しないでください。ベンチマークの正しい取り方はまったく別の問題なので、別の機会にしようと思います。
ときにはルールを完全無視
オブジェクトの数が多い方が有利な場合もあります。キャッシュを使えば、メモリと引き換えにCPUを節約できます。移動方向を保存するarrayを定数に移すことについては既に説明しましたが、それを微細なレベルで行います。つまり、コードをメモリ上に強制的に常駐させるのです。これと引き換えに、オブジェクト再構築のためのCPUサイクルをまったく消費せずに済みます。オブジェクトがキャッシュされるからです。
どんなものをキャッシュできるのでしょうか。高さと幅が固定であることと、移動のルールが変更される可能性がないことはわかっています。ゲーム盤上の位置は変更される可能性があります。ここを考慮して、位置ごとの有効なすべての移動のlistを事前に算出しておくという手が使えます。
ゲーム盤のステートが変更される可能性に注意しなければならないので、各展開方向のlistを作成するときにこの点を考慮します。たとえば、(3, 3)から右方向への移動は次のようになります。
[(3, 4), (3, 5), (3, 6)]
(3, 5)で何か変更が生じるとどうなるでしょうか。このマスが空かどうかをチェックして削除することはできますが、その場合(3, 6)も到達不能になります。移動方向ごとにlistが1つずつあるので、埋まったマスが最初に見つかった時点で列挙を中断すればよいのです。
ここまでの最適化をまとめて行う
まず、移動方向をarrayに保存します。
STAR_DIRECTIONS = [ (-1, 0), (1, 0), # 上下
(0, -1), (0, 1), # 左右
(1, -1), (1, 1), (-1, -1), (-1, 1)] # 斜め
移動の順序は重要ではありません。この後をご覧いただければわかります。
次にマスが空いているかどうかの探索を（2回ではなく）1回の呼び出しで行い、個別のrow/columnの組み合わせではなくタプルに基くようにしたいと思います。そこで、位置をインデックスとして持つdict（Rubyで言うhash）を1つ作成します。
def build_blank_space_dict():
blank_space_dict = {}
for c in range(0, height):
for r in range(0, width):
blank_space_dict[(c, r)] = (board_spaces_occupied[c][r] == BLANK)
return blank_space_dict
上を次のように使います。
def move_is_legal_from_dict(move):
return 0 <= move[0] < height and
0 <= move[1] < width and
blank_space_dict[move]
次が最もコストの高い部分です。ゲーム盤での有効な移動をすべて事前に算出してキャッシュしたいと思います。この作業のコストは高いのですが、起動時に1回行えば済むので、再計算が不要になります。
def calculate_first_move_guess_dict():
first_move_guess_dict = {}
for r in range(0, height):
for c in range(0, width):
rc_tuple = (r, c)
first_move_guess_dict[rc_tuple] = []
for delta_r, delta_c in STAR_DIRECTIONS:
valid_guesses = []
dr = delta_r
dc = delta_c
move = (r + dr, c + dc)
while move_is_legal_from_dict(move):
valid_guesses.append(move)
dr += delta_r
dc += delta_c
move = (r + dr, c + dc)
first_move_guess_dict[rc_tuple].append(valid_guesses)
return first_move_guess_dict
長くなりましたが、変更後のコードは上のようになります。ここで行っているのは、上述のget_legal_moves_slow()と基本的にまったく同じです。大きな違いは、rowやcolumnごとの可能な移動を二重ループの中でビルドしていることです。
move_is_legal_from_dict()で移動の有効性をチェックしてからlistに追加していますが、これに気づくことが重要です。これは位置がゲーム盤からはみ出しているかどうかのチェックなので、削除します。これで、後でゲーム盤のステートをチェックするときに同じチェックを繰り返さずに済みます（先ほど「後述する」と書いたのはこれです）。
お待ちかねの最終的なメソッドは次のようになります。
def get_legal_moves_fast(move):
valid_moves = []
for direction_list in first_move_guess_dict[move]:
for move in direction_list:
if blank_space_dict[move]:
valid_moves.append(move)
else:
break # そこから先の方向への移動はすべて無効
return valid_moves
有効な移動のarrayをfirst_move_guess_dict[move]で探索します。ゲーム盤が3x3の場合、位置(1, 1)の結果は次のようになります。
[[(0, 1)], [(2, 1)], [(1, 0)], [(1, 2)], [(2, 0)], [(2, 2)], [(0, 0)], [(0, 2)]]
サブarrayにある各要素をループで列挙し、blank_space_dict[move]でチェックします。有効な場合は有効な移動に追加し、無効な場合は内側のループをbreakします（その位置から先の方向はクイーンの移動ルール上無効であるため）。
最後に、有効な移動のタプルのlistを1つ返します。
パフォーマンスの比較はどのように行えばよいでしょうか。私はkernprofで確認しました。
$ kernprof -l -v perf.py
Wrote profile results to perf.py.lprof
Timer unit: 1e-06 s
Total time: 1.17439 s
File: perf.py
Function: get_legal_moves_fast at line 53
Line # Hits Time Per Hit % Time Line Contents
==============================================================
53 @profile
54 def get_legal_moves_fast(move):
55 100000 41991 0.4 3.6 valid_moves = []
56 900000 378690 0.4 32.2 for direction_list in first_move_guess_dict[move]:
57 1000000 491422 0.5 41.8 for move in direction_list:
58 200000 106333 0.5 9.1 if blank_space_dict[move]:
59 200000 116717 0.6 9.9 valid_moves.append(move)
60 else:
61 break # rest of direction is invalid
62
63 100000 39242 0.4 3.3 return valid_moves
Total time: 5.80368 s
File: perf.py
Function: get_legal_moves_slow at line 69
Line # Hits Time Per Hit % Time Line Contents
==============================================================
69 @profile
70 def get_legal_moves_slow(move):
71 100000 79230 0.8 1.4 r, c = move
72
73 100000 78106 0.8 1.3 directions = [ (-1, -1), (-1, 0), (-1, 1),
74 100000 75957 0.8 1.3 (0, -1), (0, 1),
75 100000 94609 0.9 1.6 (1, -1), (1, 0), (1, 1)]
76
77 900000 739500 0.8 12.7 fringe = [((r+dr,c+dc), (dr,dc)) for dr, dc in directions
78 800000 1704089 2.1 29.4 if move_is_legal(r+dr, c+dc)]
79
80 100000 79558 0.8 1.4 valid_moves = []
81
82 500000 406481 0.8 7.0 while fringe:
83 400000 471503 1.2 8.1 move, delta = fringe.pop()
84
85 400000 323095 0.8 5.6 r, c = move
86 400000 321289 0.8 5.5 dr, dc = delta
87
88 400000 736811 1.8 12.7 if move_is_legal(r,c):
89 200000 214678 1.1 3.7 new_move = ((r+dr, c+dc), (dr,dc))
90 200000 215883 1.1 3.7 fringe.append(new_move)
91 200000 189134 0.9 3.3 valid_moves.append(move)
92
93 100000 73752 0.7 1.3 return valid_moves
本記事をスマートフォンでお読みの方向けに、重要部分を以下に抜粋しました。
Total time: 1.17439 s
File: perf.py
Function: get_legal_moves_fast at line 53
Total time: 5.80368 s
File: perf.py
Function: get_legal_moves_slow at line 69
最適化前のメソッドの所要時間は5.80368秒、改善後のメソッドでは1.17439秒にまで短縮されました。パフォーマンスは約5倍向上しました。
これをさらに高速化することは可能でしょうか。
説明してませんでしたが、操作によってはコストの高いものがあります。私の見たところ、Pythonのlistに対するappend()は最適化があまり進んでいません。同じlistへのappend()を繰り返すのではなく、おそらく固定サイズのarrayを1つ初期化してそのインデックスに要素を追加し、続いてNone（Rubyで言うnil）をすべて削除してからarrayをリサイズする方法も考えられます。繰り返しになりますが、これが本当かどうかを確認するにはベンチマークをもれなく取ってください。
numpyが使えるのであれば、何か高速化の方法があるかもしれません。GVLを持たないプラットフォーム（RubyもPythonもこれには該当しません）であれば、移動方向ごとのループを並列化できるかもしれません。別のスレッドに置くためにスケジューリング時間を使う値打ちはおそらくありませんが。
また、私がPythonについて何か取りこぼしている点があるかもしれませんし、すべてを高速化できる方法を私が知らない言語もあります。これまで述べてきたのは、（Pythonの）itertoolsモジュール、functoolsモジュール、operatorモジュールについてです。
更に言うと、私のコードは元のものより複雑で、良くも悪くも凄いことになっています。作業内容も保存されるステートも多く、メモリ消費も増加しています。とは言うものの、私にとって重要なのは最後の「有効な移動を取得する」関数の呼び出し回数でした。この関数は読みにくいぐらい短く簡潔ですが、一方で各部分の協調動作について多くの知識を要求します。
私はコーディング時間のほとんどを、人間にとって読みやすいコードを書くことに費やしています。パフォーマンスが5倍アップするのは結構な話ですが、同僚のコードメンテ時間が10倍になったら何にもなりません。パフォーマンスではCPUやRAMを考慮しますが、同様に人間にとってのコストも考慮しましょう。私は普通、最初に遅いコードを書き、次にプロファイリングを行い、重要なホットスポットだけを最適化します。今回は、ここが私にとってのホットスポットでした。
お読みいただきありがとうございます。