asked by Markus Meskanen
2015年10月22日
Q. なぜ’x’ in (‘x’,)が’x’ == ‘x’より速い？
Why is 'x' in ('x',) faster than 'x' == 'x'?
(2015-03-05)by Markus Meskanen
本記事は、原著者の許諾の もとに翻訳・掲載しております。
質問 なぜ ’x’ in (‘x’,) が ’x’ == ‘x’ より速いのでしょう？
>>> timeit.timeit("'x' in ('x',)")0.04869917374131205>>> timeit.timeit("'x' == 'x'")0.06144205736110564条件を複雑にした場合も同様で、どちらも計算時間は線型的に増加するようです。
>>> timeit.timeit("'x' in ('x', 'y')")0.04866674801541748>>> timeit.timeit("'x' == 'x' or 'x' == 'y'")0.06565782838087131>>> timeit.timeit("'x' in ('y', 'x')")0.08975995576448526>>> timeit.timeit("'x' == 'y' or 'x' == 'y'")0.12992391047427532これを考慮すると、全ての場合において == よりも in を使うようにしたほうがいいと思うんです。
Answer(s)
David Woleverさんにも言いましたが、これには見かけ以上のものがあります。どちらも is にディスパッチされます。これは以下のようにすれば証明できます。
min(Timer("x == x", setup="x = 'a' * 1000000").repeat(10, 10000))#>>> 0.00045456900261342525 min(Timer("x == y", setup="x = 'a' * 1000000; y = 'a' * 1000000").repeat(10, 10000))#>>> 0.52568576100748031つ目は、アイデンティティでチェックしているので速いというだけなのです。
片方のコードが他のコードより時間がかかる理由を知るために処理をトレースしてみましょう。
2つとも ceval.c で COMPARE_OP から始めているのは、それがこの問題に関係しているバイトコードだからです。
TARGET(COMPARE_OP) { PyObject *right = POP(); PyObject *left = TOP(); PyObject *res = cmp_outcome(oparg, left, right); Py_DECREF(left); Py_DECREF(right); SET_TOP(res); if (res == NULL) goto error; PREDICT(POP_JUMP_IF_FALSE); PREDICT(POP_JUMP_IF_TRUE); DISPATCH();}これでスタックから値をポップします（技術的には1つの値のみがポップされます）。
PyObject *right = POP();PyObject *left = TOP();そして、比較します。
PyObject *res = cmp_outcome(oparg, left, right); cmp_outcome は以下です。
cmp_outcome(int op, PyObject *v, PyObject *w){ int res = 0; switch (op) { case PyCmp_IS: ... case PyCmp_IS_NOT: ... case PyCmp_IN: res = PySequence_Contains(w, v); if (res < 0) return NULL; break; case PyCmp_NOT_IN: ... case PyCmp_EXC_MATCH: ... default: return PyObject_RichCompare(v, w, op); } v = res ? Py_True : Py_False; Py_INCREF(v); return v;}ここで経路が分岐します。 PyCmp_IN のブランチが以下です。
intPySequence_Contains(PyObject *seq, PyObject *ob){ Py_ssize_t result; PySequenceMethods *sqm = seq->ob_type->tp_as_sequence; if (sqm != NULL && sqm->sq_contains != NULL) return (*sqm->sq_contains)(seq, ob); result = _PySequence_IterSearch(seq, ob, PY_ITERSEARCH_CONTAINS); return Py_SAFE_DOWNCAST(result, Py_ssize_t, int);注意すべきはタプルが以下のように定義されることです。
static PySequenceMethods tuple_as_sequence = { ... (objobjproc)tuplecontains, /* sq_contains */}; PyTypeObject PyTuple_Type = { ... &tuple_as_sequence, /* tp_as_sequence */ ...};だから分岐の、
if (sqm != NULL && sqm->sq_contains != NULL)が当てはまり、関数(objobjproc)tuplecontainsである*sqm->sq_containsになります。
この関数は以下です。
static inttuplecontains(PyTupleObject *a, PyObject *el){ Py_ssize_t i; int cmp; for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i) cmp = PyObject_RichCompareBool(el, PyTuple_GET_ITEM(a, i), Py_EQ); return cmp;}ちょっと待ってください、 PyObject_RichCompareBool は別の分岐のものではないのでしょうか？ いいえ、違います。それは PyObject_RichCompare です。
このコードの経路は短いので、結局のところ速度はこの2つの関数の速度によって決まるようになります。では2つを比較しましょう。
PyObject_RichCompareBool(PyObject *v, PyObject *w, int op){ PyObject *res; int ok; /* Quick result when objects are the same. Guarantees that identity implies equality. */ if (v == w) { if (op == Py_EQ) return 1; else if (op == Py_NE) return 0; } ...} PyObject_RichCompareBool のコード経路は、比較的すぐに終了します。 PyObject_RichCompare では以下のようになります。
PyObject *PyObject_RichCompare(PyObject *v, PyObject *w, int op){ PyObject *res; assert(Py_LT <= op && op <= Py_GE); if (v == NULL || w == NULL) { ... } if (Py_EnterRecursiveCall(" in comparison")) return NULL; res = do_richcompare(v, w, op); Py_LeaveRecursiveCall(); return res;} Py_EnterRecursiveCall と Py_LeaveRecursiveCall の組み合わせは、先ほどの経路には現れません。しかし、いくつかのグローバル変数の増分と減分の後で簡略化させる、比較的速いマクロがあります。
do_richcompare は、次のようなことを行います。
static PyObject *do_richcompare(PyObject *v, PyObject *w, int op){ richcmpfunc f; PyObject *res; int checked_reverse_op = 0; if (v->ob_type != w->ob_type && ...) { ... } if ((f = v->ob_type->tp_richcompare) != NULL) { res = (*f)(v, w, op); if (res != Py_NotImplemented) return res; ... } ...}これは v->ob_type->tp_richcompare を呼び出すための簡単なチェックを行います。それは、
PyTypeObject PyUnicode_Type = { ... PyUnicode_RichCompare, /* tp_richcompare */ ...};これが行うのは、
PyObject *PyUnicode_RichCompare(PyObject *left, PyObject *right, int op){ int result; PyObject *v; if (!PyUnicode_Check(left) || !PyUnicode_Check(right)) Py_RETURN_NOTIMPLEMENTED; if (PyUnicode_READY(left) == -1 || PyUnicode_READY(right) == -1) return NULL; if (left == right) { switch (op) { case Py_EQ: case Py_LE: case Py_GE: /* a string is equal to itself */ v = Py_True; break; case Py_NE: case Py_LT: case Py_GT: v = Py_False; break; default: ... } } else if (...) { ... } else { ...} Py_INCREF(v); return v;}すなわちこれが left == right をショートカットするのです。ただし、以下のことを行った後に限られています。
if (!PyUnicode_Check(left) || !PyUnicode_Check(right)) if (PyUnicode_READY(left) == -1 || PyUnicode_READY(right) == -1)全体的に見ると、これらの経路はこのように表すことができるでしょう（分かっている分岐を手動で再帰的に、直線的に並べて明らかにし簡潔化しました）。
POP() # Stack stuffTOP() # #case PyCmp_IN: # Dispatch on operation #sqm != NULL # Dispatch to builtin opsqm->sq_contains != NULL #*sqm->sq_contains # #cmp == 0 # Do comparison in loopi < Py_SIZE(a) #v == w #op == Py_EQ #++i # cmp == 0 # #res < 0 # Convert to Python-spaceres ? Py_True : Py_False #Py_INCREF(v) # #Py_DECREF(left) # Stack stuffPy_DECREF(right) #SET_TOP(res) #res == NULL #DISPATCH() #これに対して、
POP() # Stack stuffTOP() # #default: # Dispatch on operation #Py_LT <= op # Checking operationop <= Py_GE #v == NULL #w == NULL #Py_EnterRecursiveCall(...) # Recursive check #v->ob_type != w->ob_type # More operation checksf = v->ob_type->tp_richcompare # Dispatch to builtin opf != NULL # #!PyUnicode_Check(left) # ...More checks!PyUnicode_Check(right)) #PyUnicode_READY(left) == -1 #PyUnicode_READY(right) == -1 #left == right # Finally, doing comparisoncase Py_EQ: # Immediately short circuitPy_INCREF(v); # #res != Py_NotImplemented # #Py_LeaveRecursiveCall() # Recursive check #Py_DECREF(left) # Stack stuffPy_DECREF(right) #SET_TOP(res) #res == NULL #DISPATCH() # PyUnicode_Check と PyUnicode_READY はそれぞれ2個のフィールドしかチェックしないので、かなりコストが低いと言えるでしょう。しかし明らかなのは、上にあるものはコードの経路がより短く、関数の呼び出しも1つのスイッチステートメントだけで、処理もやや少ないということです。
要約
どちらも if (left_pointer == right_pointer) にディスパッチします。違いは、そこにたどり着くまでの処理量だけで、 in を使えば処理が少ないというだけのことです。
この驚くべき動作は、以下の3つの要素が組み合わせられることで生じます。
1つ目： in 演算子はショートカットをとり、等価性のチェック（ x == y ）を行う前に、アイデンティティのチェック（ x is y ）を行います。
>>> n = float('nan')>>> n in (n, )True>>> n == nFalse>>> n is nTrue2つ目：Pythonでの文字列のインターンにより、 "x" in ("x", ) にある2つの "x" は同一になります。
>>> "x" is "x"True（特に注意しなくてはならないのは、これは実装に特異的な動作であるということです。 is は 決して 文字列の比較に使ってはいけません。なぜなら、信じられないような結果（例えば "x" * 100 is "x" * 100 ==> False ）が出てしまう可能性が 常に あるからです）。
3つ目：■Veedracさんの素晴らしい回答■で詳しく説明されているように、 tuple.contains__ （ x in (y, ) は (y, ).__contains (x) と おおよそ 等価）は、 str.eq__ （また、 x == y は x.__eq (y) と おおよそ 等価）よりも、アイデンティティのチェックを実行する段階に速く達することです。
この証拠として、 x in (y, ) は、論理上等価な x == y よりもはるかに時間がかかります。
In [18]: %timeit 'x' in ('x', )10000000 loops, best of 3: 65.2 ns per loop In [19]: %timeit 'x' == 'x' 10000000 loops, best of 3: 68 ns per loop In [20]: %timeit 'x' in ('y', ) 10000000 loops, best of 3: 73.4 ns per loop In [21]: %timeit 'x' == 'y' 10000000 loops, best of 3: 56.2 ns per loop x in (y, ) の場合に時間がかかる原因は、 is の比較が失敗した後、 in 演算子が通常の等価性のチェックに戻るので（すなわち == を使用）、比較には == と同じ時間がかかり、タプルを生成したりメンバをたどったりするオーバーヘッドのために全体の演算が遅くなることです。
a in (b, ) のほうが速くなるのは a is b の場合に 限られる ことにも注意してください。
In [48]: a = 1 In [49]: b = 2 In [50]: %timeit a is a or a == a10000000 loops, best of 3: 95.1 ns per loop In [51]: %timeit a in (a, ) 10000000 loops, best of 3: 140 ns per loop In [52]: %timeit a is b or a == b10000000 loops, best of 3: 177 ns per loop In [53]: %timeit a in (b, ) 10000000 loops, best of 3: 169 ns per loop（なぜ a in (b, ) は a is b or a == b よりも速いのでしょうか？ おそらく、仮想マシンの命令数が少ないためではないかと思います。つまり、 a in (b, ) の命令数は3つぐらいしかありませんが、 a is b or a == b は仮想マシンの命令数がもっと多くなるからです）
■Veedracさんの回答■では、特に == と in のそれぞれで起こることについてさらに詳しく説明されているので、ぜひ読んでみるといいでしょう。
監修者
古川陽介
株式会社リクルート プロダクト統括本部 プロダクト開発統括室 グループマネジャー 株式会社ニジボックス デベロップメント室 室長 Node.js 日本ユーザーグループ代表
株式会社リクルート プロダクト統括本部 プロダクト開発統括室 グループマネジャー 株式会社ニジボックス デベロップメント室 室長 Node.js 日本ユーザーグループ代表
複合機メーカー、ゲーム会社を経て、2016年に株式会社リクルートテクノロジーズ(現リクルート)入社。
現在はAPソリューショングループのマネジャーとしてアプリ基盤の改善や運用、各種開発支援ツールの開発、またテックリードとしてエンジニアチームの支援や育成までを担う。
2019年より株式会社ニジボックスを兼務し、室長としてエンジニア育成基盤の設計、技術指南も遂行。
Node.js 日本ユーザーグループの代表を務め、Node学園祭などを主宰。
- Twitter: @yosuke_furukawa
- Github: yosuke-furukawa
関連記事
