Q. なぜ’x’ in (‘x’,)が’x’ == ‘x’より速い?

質問 なぜ’x’ in (‘x’,)’x’ == ‘x’より速いのでしょう?

  1. >>> timeit.timeit("'x' in ('x',)")
  2. 0.04869917374131205
  3. >>> timeit.timeit("'x' == 'x'")
  4. 0.06144205736110564

条件を複雑にした場合も同様で、どちらも計算時間は線型的に増加するようです。

  1. >>> timeit.timeit("'x' in ('x', 'y')")
  2. 0.04866674801541748
  3. >>> timeit.timeit("'x' == 'x' or 'x' == 'y'")
  4. 0.06565782838087131
  5. >>> timeit.timeit("'x' in ('y', 'x')")
  6. 0.08975995576448526
  7. >>> timeit.timeit("'x' == 'y' or 'x' == 'y'")
  8. 0.12992391047427532

これを考慮すると、全ての場合において==よりもinを使うようにしたほうがいいと思うんです。


Answer(s)

David Woleverさんにも言いましたが、これには見かけ以上のものがあります。どちらもisにディスパッチされます。これは以下のようにすれば証明できます。

  1. min(Timer("x == x", setup="x = 'a' * 1000000").repeat(10, 10000))
  2. #>>> 0.00045456900261342525
  3.  
  4. min(Timer("x == y", setup="x = 'a' * 1000000; y = 'a' * 1000000").repeat(10, 10000))
  5. #>>> 0.5256857610074803

1つ目は、アイデンティティでチェックしているので速いというだけなのです。

片方のコードが他のコードより時間がかかる理由を知るために処理をトレースしてみましょう。

2つともceval.cCOMPARE_OPから始めているのは、それがこの問題に関係しているバイトコードだからです。

  1. TARGET(COMPARE_OP) {
  2. PyObject *right = POP();
  3. PyObject *left = TOP();
  4. PyObject *res = cmp_outcome(oparg, left, right);
  5. Py_DECREF(left);
  6. Py_DECREF(right);
  7. SET_TOP(res);
  8. if (res == NULL)
  9. goto error;
  10. PREDICT(POP_JUMP_IF_FALSE);
  11. PREDICT(POP_JUMP_IF_TRUE);
  12. DISPATCH();
  13. }

これでスタックから値をポップします(技術的には1つの値のみがポップされます)。

  1. PyObject *right = POP();
  2. PyObject *left = TOP();

そして、比較します。

  1. PyObject *res = cmp_outcome(oparg, left, right);

cmp_outcomeは以下です。

  1. cmp_outcome(int op, PyObject *v, PyObject *w)
  2. {
  3. int res = 0;
  4. switch (op) {
  5. case PyCmp_IS: ...
  6. case PyCmp_IS_NOT: ...
  7. case PyCmp_IN:
  8. res = PySequence_Contains(w, v);
  9. if (res < 0)
  10. return NULL;
  11. break;
  12. case PyCmp_NOT_IN: ...
  13. case PyCmp_EXC_MATCH: ...
  14. default:
  15. return PyObject_RichCompare(v, w, op);
  16. }
  17. v = res ? Py_True : Py_False;
  18. Py_INCREF(v);
  19. return v;
  20. }

ここで経路が分岐します。PyCmp_INのブランチが以下です。

  1. int
  2. PySequence_Contains(PyObject *seq, PyObject *ob)
  3. {
  4. Py_ssize_t result;
  5. PySequenceMethods *sqm = seq->ob_type->tp_as_sequence;
  6. if (sqm != NULL && sqm->sq_contains != NULL)
  7. return (*sqm->sq_contains)(seq, ob);
  8. result = _PySequence_IterSearch(seq, ob, PY_ITERSEARCH_CONTAINS);
  9. return Py_SAFE_DOWNCAST(result, Py_ssize_t, int);

注意すべきはタプルが以下のように定義されることです。

  1. static PySequenceMethods tuple_as_sequence = {
  2. ...
  3. (objobjproc)tuplecontains, /* sq_contains */
  4. };
  5.  
  6. PyTypeObject PyTuple_Type = {
  7. ...
  8. &tuple_as_sequence, /* tp_as_sequence */
  9. ...
  10. };

だから分岐の、

  1. if (sqm != NULL && sqm->sq_contains != NULL)

が当てはまり、関数(objobjproc)tuplecontainsである*sqm->sq_containsになります。

この関数は以下です。

  1. static int
  2. tuplecontains(PyTupleObject *a, PyObject *el)
  3. {
  4. Py_ssize_t i;
  5. int cmp;
  6.  
  7. for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
  8. cmp = PyObject_RichCompareBool(el, PyTuple_GET_ITEM(a, i),
  9. Py_EQ);
  10. return cmp;
  11. }

ちょっと待ってください、PyObject_RichCompareBoolは別の分岐のものではないのでしょうか? いいえ、違います。それはPyObject_RichCompareです。

このコードの経路は短いので、結局のところ速度はこの2つの関数の速度によって決まるようになります。では2つを比較しましょう。

  1. PyObject_RichCompareBool(PyObject *v, PyObject *w, int op)
  2. {
  3. PyObject *res;
  4. int ok;
  5.  
  6. /* Quick result when objects are the same.
  7. Guarantees that identity implies equality. */
  8. if (v == w) {
  9. if (op == Py_EQ)
  10. return 1;
  11. else if (op == Py_NE)
  12. return 0;
  13. }
  14.  
  15. ...
  16. }

PyObject_RichCompareBoolのコード経路は、比較的すぐに終了します。PyObject_RichCompareでは以下のようになります。

  1. PyObject *
  2. PyObject_RichCompare(PyObject *v, PyObject *w, int op)
  3. {
  4. PyObject *res;
  5.  
  6. assert(Py_LT <= op && op <= Py_GE);
  7. if (v == NULL || w == NULL) { ... }
  8. if (Py_EnterRecursiveCall(" in comparison"))
  9. return NULL;
  10. res = do_richcompare(v, w, op);
  11. Py_LeaveRecursiveCall();
  12. return res;
  13. }

Py_EnterRecursiveCallPy_LeaveRecursiveCallの組み合わせは、先ほどの経路には現れません。しかし、いくつかのグローバル変数の増分と減分の後で簡略化させる、比較的速いマクロがあります。

do_richcompareは、次のようなことを行います。

  1. static PyObject *
  2. do_richcompare(PyObject *v, PyObject *w, int op)
  3. {
  4. richcmpfunc f;
  5. PyObject *res;
  6. int checked_reverse_op = 0;
  7.  
  8. if (v->ob_type != w->ob_type && ...) { ... }
  9. if ((f = v->ob_type->tp_richcompare) != NULL) {
  10. res = (*f)(v, w, op);
  11. if (res != Py_NotImplemented)
  12. return res;
  13. ...
  14. }
  15. ...
  16. }

これはv->ob_type->tp_richcompareを呼び出すための簡単なチェックを行います。それは、

  1. PyTypeObject PyUnicode_Type = {
  2. ...
  3. PyUnicode_RichCompare, /* tp_richcompare */
  4. ...
  5. };

これが行うのは、

  1. PyObject *
  2. PyUnicode_RichCompare(PyObject *left, PyObject *right, int op)
  3. {
  4. int result;
  5. PyObject *v;
  6.  
  7. if (!PyUnicode_Check(left) || !PyUnicode_Check(right))
  8. Py_RETURN_NOTIMPLEMENTED;
  9.  
  10. if (PyUnicode_READY(left) == -1 ||
  11. PyUnicode_READY(right) == -1)
  12. return NULL;
  13.  
  14. if (left == right) {
  15. switch (op) {
  16. case Py_EQ:
  17. case Py_LE:
  18. case Py_GE:
  19. /* a string is equal to itself */
  20. v = Py_True;
  21. break;
  22. case Py_NE:
  23. case Py_LT:
  24. case Py_GT:
  25. v = Py_False;
  26. break;
  27. default:
  28. ...
  29. }
  30. }
  31. else if (...) { ... }
  32. else { ...}
  33. Py_INCREF(v);
  34. return v;
  35. }

すなわちこれがleft == rightをショートカットするのです。ただし、以下のことを行った後に限られています。

  1. if (!PyUnicode_Check(left) || !PyUnicode_Check(right))
  2.  
  3. if (PyUnicode_READY(left) == -1 ||
  4. PyUnicode_READY(right) == -1)

全体的に見ると、これらの経路はこのように表すことができるでしょう(分かっている分岐を手動で再帰的に、直線的に並べて明らかにし簡潔化しました)。

  1. POP() # Stack stuff
  2. TOP() #
  3. #
  4. case PyCmp_IN: # Dispatch on operation
  5. #
  6. sqm != NULL # Dispatch to builtin op
  7. sqm->sq_contains != NULL #
  8. *sqm->sq_contains #
  9. #
  10. cmp == 0 # Do comparison in loop
  11. i < Py_SIZE(a) #
  12. v == w #
  13. op == Py_EQ #
  14. ++i #
  15. cmp == 0 #
  16. #
  17. res < 0 # Convert to Python-space
  18. res ? Py_True : Py_False #
  19. Py_INCREF(v) #
  20. #
  21. Py_DECREF(left) # Stack stuff
  22. Py_DECREF(right) #
  23. SET_TOP(res) #
  24. res == NULL #
  25. DISPATCH() #

これに対して、

  1. POP() # Stack stuff
  2. TOP() #
  3. #
  4. default: # Dispatch on operation
  5. #
  6. Py_LT <= op # Checking operation
  7. op <= Py_GE #
  8. v == NULL #
  9. w == NULL #
  10. Py_EnterRecursiveCall(...) # Recursive check
  11. #
  12. v->ob_type != w->ob_type # More operation checks
  13. f = v->ob_type->tp_richcompare # Dispatch to builtin op
  14. f != NULL #
  15. #
  16. !PyUnicode_Check(left) # ...More checks
  17. !PyUnicode_Check(right)) #
  18. PyUnicode_READY(left) == -1 #
  19. PyUnicode_READY(right) == -1 #
  20. left == right # Finally, doing comparison
  21. case Py_EQ: # Immediately short circuit
  22. Py_INCREF(v); #
  23. #
  24. res != Py_NotImplemented #
  25. #
  26. Py_LeaveRecursiveCall() # Recursive check
  27. #
  28. Py_DECREF(left) # Stack stuff
  29. Py_DECREF(right) #
  30. SET_TOP(res) #
  31. res == NULL #
  32. DISPATCH() #

PyUnicode_CheckPyUnicode_READYはそれぞれ2個のフィールドしかチェックしないので、かなりコストが低いと言えるでしょう。しかし明らかなのは、上にあるものはコードの経路がより短く、関数の呼び出しも1つのスイッチステートメントだけで、処理もやや少ないということです。

要約

どちらもif (left_pointer == right_pointer)にディスパッチします。違いは、そこにたどり着くまでの処理量だけで、inを使えば処理が少ないというだけのことです。

answered by Veedrac

この驚くべき動作は、以下の3つの要素が組み合わせられることで生じます。

1つ目:in演算子はショートカットをとり、等価性のチェック(x == y)を行う前に、アイデンティティのチェック(x is y)を行います。

  1. >>> n = float('nan')
  2. >>> n in (n, )
  3. True
  4. >>> n == n
  5. False
  6. >>> n is n
  7. True

2つ目:Pythonでの文字列のインターンにより、"x" in ("x", )にある2つの"x"は同一になります。

  1. >>> "x" is "x"
  2. True

(特に注意しなくてはならないのは、これは実装に特異的な動作であるということです。is決して文字列の比較に使ってはいけません。なぜなら、信じられないような結果(例えば"x" * 100 is "x" * 100 ==> False)が出てしまう可能性が常にあるからです)。

3つ目:■Veedracさんの素晴らしい回答■で詳しく説明されているように、tuple.contains__x in (y, )(y, ).__contains(x)おおよそ等価)は、str.eq__(また、x == yx.__eq(y)おおよそ等価)よりも、アイデンティティのチェックを実行する段階に速く達することです。

この証拠として、x in (y, )は、論理上等価なx == yよりもはるかに時間がかかります。

  1. In [18]: %timeit 'x' in ('x', )
  2. 10000000 loops, best of 3: 65.2 ns per loop
  3.  
  4. In [19]: %timeit 'x' == 'x'
  5. 10000000 loops, best of 3: 68 ns per loop
  6.  
  7. In [20]: %timeit 'x' in ('y', )
  8. 10000000 loops, best of 3: 73.4 ns per loop
  9.  
  10. In [21]: %timeit 'x' == 'y'
  11. 10000000 loops, best of 3: 56.2 ns per loop

x in (y, )の場合に時間がかかる原因は、isの比較が失敗した後、in演算子が通常の等価性のチェックに戻るので(すなわち==を使用)、比較には==と同じ時間がかかり、タプルを生成したりメンバをたどったりするオーバーヘッドのために全体の演算が遅くなることです。

a in (b, )のほうが速くなるのはa is bの場合に限られることにも注意してください。

  1. In [48]: a = 1
  2.  
  3. In [49]: b = 2
  4.  
  5. In [50]: %timeit a is a or a == a
  6. 10000000 loops, best of 3: 95.1 ns per loop
  7.  
  8. In [51]: %timeit a in (a, )
  9. 10000000 loops, best of 3: 140 ns per loop
  10.  
  11. In [52]: %timeit a is b or a == b
  12. 10000000 loops, best of 3: 177 ns per loop
  13.  
  14. In [53]: %timeit a in (b, )
  15. 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のそれぞれで起こることについてさらに詳しく説明されているので、ぜひ読んでみるといいでしょう。

answered by David Wolever