Pythonの四則演算とビット論理演算の速度を自分でも測ってみた
bit 単位でデータが詰め込まれているバイナリデータを眺める機会があったので、なんとなく「Python ビット演算」でググッてみた。そんな日のこと。
すると Python の int 型における各種演算速度を実測した人を発見。Pythonの四則演算とビット論理演算の速度 - yattの日記 。この記事の最初の１文を読んで、自分が思い浮かべた予想は「加減算とビット演算は同じくらいの速さ、乗算除算は少し劣る」というもの。しかし、その結果は、「ビット演算より加減算の方が早い」、とのこと。
ちなみに自分の持っていた前知識はこんな感じ。下に行くほど自信なし。
- Python の int はオブジェクト。不変型。
- Python で int 同士の演算を行うと新たな int オブジェクトが生成される。
- Python における int 同士のビット演算は Python の int オブジェクト２つを C の long 型に直すことから始まる。これらをビット演算。結果を元に Python の int オブジェクトを生成する。(Objects/intobject.c を昔、斜め読みした記憶より）
- Python における int 同士の加算は Python の int オブジェクト２つを C の long 型に直すことから始まる。これらを加算。結果を int の範囲内に収まっているかどうかをチェックする。収まっていれば Python の int オブジェクト、収まっていなければ Python の long オブジェクトを生成する。(Objects/intobject.c を昔、斜め読みした記憶より）
- CPython のオブジェクトの生成コストは C の long の加減算などとは比較にならないほど重い。もちろんビット演算より重い。
ビット演算も加減算も処理が似通っている上、その大半がオブジェクト生成処理のため、差はないと思っていたのだが。うん、コードの速さを推測しきろうとすることがいかに危険かを再認識。短いコード片の速度は推測したら実測もすべし。もう何回目だろう。
反省をさっそく生かすべく、うちの環境でも測ってみる。
- 環境
- Intel Core2 Quad Q6600 2.40GHz
- Windows XP Pro SP2
- Python 2.5.2
> func_call_time.py op all[sec] per call[sec] ------------------------------------------------------------ add 2.340e-001 5.584e-008 sub 2.350e-001 5.608e-008 mul 3.280e-001 7.828e-008 div 3.910e-001 9.331e-008 mod 3.430e-001 8.186e-008 logand 2.820e-001 6.730e-008 logor 2.960e-001 7.064e-008 logxor 2.970e-001 7.088e-008 結果をソートしたもの add 2.340e-001 5.584e-008 sub 2.350e-001 5.608e-008 logand 2.820e-001 6.730e-008 logor 2.960e-001 7.064e-008 logxor 2.970e-001 7.088e-008 mul 3.280e-001 7.828e-008 mod 3.430e-001 8.186e-008 div 3.910e-001 9.331e-008
コードをすこしいじって timeit 使用に。再挑戦。
> intcalctime.py -n 10 op all[sec] per calc[sec] ------------------------------------------------------------ add 2.376e+000 5.669e-008 sub 2.393e+000 5.712e-008 logand 2.899e+000 6.918e-008 logor 2.922e+000 6.973e-008 logxor 2.940e+000 7.016e-008 mul 3.372e+000 8.048e-008 mod 3.445e+000 8.221e-008 div 4.088e+000 9.756e-008
たしかに。うちの環境でも logand らビット演算より add, sub のほうが早い。しかし実装 Objects\intobject.c を読み直すと以下のようになっていて、 and のほうがシンプル。ナゾが残った。このナゾ、解ける人求む？
static PyObject * int_add(PyIntObject *v, PyIntObject *w) { register long a, b, x; CONVERT_TO_LONG(v, a); CONVERT_TO_LONG(w, b); x = a + b; if ((x^a) >= 0 || (x^b) >= 0) return PyInt_FromLong(x); return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w); } /* 中略 */ static PyObject * int_and(PyIntObject *v, PyIntObject *w) { register long a, b; CONVERT_TO_LONG(v, a); CONVERT_TO_LONG(w, b); return PyInt_FromLong(a & b); }
検証に用いた func_call_time.py コードは Pythonの四則演算とビット論理演算の速度 - yattの日記 より。intcalctime.py コードはこちら。
#! /bin/env python # coding: utf-8 # intcalctime.py u"""int 型同士の各種演算の速度計測 original yatt の日記 http://d.hatena.ne.jp/yatt/20080904 """ import timeit import optparse MAX_VALUE = 2048 NAMES = ("add", "sub", "mul", "div", "mod", "logand", "logor", "logxor") OPS = ("+", "-", "*", "/", "%", "&", "|", "^") def make_testcode(op): u"""テストコード生成""" return """for i in xrange(1, %d): for j in xrange(1, %d): i %s j """ % (MAX_VALUE, MAX_VALUE, op) def count_time(op, repeat_num=1): u"""op 演算子によるテストコードを repeat_num 回実行し、速度計測する""" timer = timeit.Timer(make_testcode(op)) return timer.timeit(repeat_num) def main(): usage = '%prog [-n repeat_num]' parser = optparse.OptionParser(usage=usage) parser.add_option('-n', '--repeat_num', action='store', type='int') parser.set_defaults(repeat_num=1) options, args = parser.parse_args() repeat_num = options.repeat_num results = [] for name, op in zip(NAMES, OPS): time = count_time(op, repeat_num) results.append((time, name, op)) results.sort() print "op\tall[sec]\tper calc[sec]" print "-" * 60 format = "%s\t%.3e\t%.3e" for time, name, op in results: print format % (name, time, time / repeat_num / (MAX_VALUE-1)**2) if __name__ == '__main__': main()
