なぜ中間変数を使ったコードは、使っていないコードより速いのか？

疑問点

私はこの奇妙な動作に遭遇し、それを説明することができませんでした。これらはベンチマークです。

py -3 -m timeit "tuple(range(2000)) == tuple(range(2000))"
10000 loops, best of 3: 97.7 usec per loop
py -3 -m timeit "a = tuple(range(2000));  b = tuple(range(2000)); a==b"
10000 loops, best of 3: 70.7 usec per loop

変数代入による比較は、一時変数によるワンライナーより27%以上速いのはなぜですか？

Pythonのドキュメントによると、timeitの間はガベージコレクションが無効になっているので、そのようなことはありえません。ある種の最適化なのでしょうか？

Python2.xでも再現性は低いですが、再現する場合があります。

Windows 7/10, CPython 3.5.1 から 3.10.1, Intel i7 3.40 GHz, OS と Python の両方が 64 ビットで実行されています。私が Intel i7 3.60 GHz で Python 3.5.0 を実行してみた別のマシンは、この結果を再現しないようです。

同じPythonのプロセスを使用して実行すると timeit.timeit() で実行すると、それぞれ 0.703 と 0.804 が得られました。程度は低いですが、まだ示しています。(~12.5%)

どのように解決するのですか？

私の結果はあなたと同様でした。中間変数を使用するコードは、Python 3.4 では一貫して少なくとも 10-20 % 速かったのです。しかし、まったく同じ Python 3.4 インタプリタ上で IPython を使用した場合、このような結果になりました。

In [1]: %timeit -n10000 -r20 tuple(range(2000)) == tuple(range(2000))
10000 loops, best of 20: 74.2 µs per loop

In [2]: %timeit -n10000 -r20 a = tuple(range(2000));  b = tuple(range(2000)); a==b
10000 loops, best of 20: 75.7 µs per loop

注目すべきは、前者の74.2μsに近づくことができなかったのは -mtimeit をコマンド ラインから使用した場合、前者の 74.2 μs に近づくことさえできませんでした。

というわけで、このHeisenbugはなかなか面白いことが判明しました。私はコマンドを実行する際に strace で実行してみたところ、確かに何か怪しげなことが起こっています。

% strace -o withoutvars python3 -m timeit "tuple(range(2000)) == tuple(range(2000))"
10000 loops, best of 3: 134 usec per loop
% strace -o withvars python3 -mtimeit "a = tuple(range(2000));  b = tuple(range(2000)); a==b"
10000 loops, best of 3: 75.8 usec per loop
% grep mmap withvars|wc -l
46
% grep mmap withoutvars|wc -l
41149

さて、これが違いの理由です。変数を使用しないコードでは mmap システムコールが中間変数を使用するものに比べてほぼ1000倍多く呼び出されます。

は withoutvars がいっぱいで mmap / munmap のように、256kの領域では、これらの同じ行が何度も何度も繰り返されます。

mmap(NULL, 262144, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f32e56de000
munmap(0x7f32e56de000, 262144)          = 0
mmap(NULL, 262144, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f32e56de000
munmap(0x7f32e56de000, 262144)          = 0
mmap(NULL, 262144, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f32e56de000
munmap(0x7f32e56de000, 262144)          = 0

は mmap の呼び出しは、この関数から来るようです。 _PyObject_ArenaMmap から Objects/obmalloc.c は obmalloc.c にはマクロ ARENA_SIZE であり、これは #define になるように (256 << 10) (つまり 262144 ); 同様に munmap は _PyObject_ArenaMunmap から obmalloc.c .

obmalloc.c はこう言っています。

Python 2.5 より前のバージョンでは、アリーナは決して free() 'されませんでした。 Python 2.5 からは を試みるようになりました。 free() アリーナが最終的に解放される可能性を高めるために、いくつかの穏やかなヒューリスティックな戦略を使用します。 アリーナが最終的に解放される可能性を高めるために、いくつかの穏やかな発見的戦略を使用します。

したがって、これらのヒューリスティックと、Pythonオブジェクトアロケータが、空きアリーナが空になるとすぐに解放するという事実が、次のように導きます。 python3 -mtimeit 'tuple(range(2000)) == tuple(range(2000))' は、1つの 256 kiB のメモリ領域が繰り返し再割り当て、解放されるような病的な振る舞いを引き起こし、この割り当てには mmap / munmap というように、システムコールであるため比較的コストがかかる - さらに。 mmap と MAP_ANONYMOUS は、新しくマップされたページがゼロでなければならないことを要求します - Pythonは気にしないでしょうが。

この挙動は、中間変数を使うコードには存在しません。なぜなら、中間変数を使うコードではわずかに より メモリを使用しており、いくつかのオブジェクトがまだそこに割り当てられているため、メモリアリーナを解放することはできません。それは timeit とは異なり、ループになるからです。

for n in range(10000)
    a = tuple(range(2000))
    b = tuple(range(2000))
    a == b

今の動作は、両方の a と b は再割り当てされるまで束縛されたままなので、2回目の反復では tuple(range(2000)) は3番目のタプルを確保し、割り当てられた a = tuple(...) は古いタプルの参照カウントを減らしてそれを解放し、新しいタプルの参照カウントを増やします。 b . したがって、最初の反復の後、これらのタプルは3つとは言わないまでも、少なくとも2つは常に存在するので、スラッシングは起こりません。

最も重要なことは、中間変数を使用するコードが常に高速であることを保証できないことです。実際、いくつかのセットアップでは、中間変数を使用することで余分な mmap の呼び出しがありますが、戻り値を直接比較するコードは問題ないかもしれません。

ある人が、この現象は timeit がガベージコレクションを無効にしている場合に発生します。確かに timeit はそれを行う :

ノート

デフォルトでは timeit() はタイミング中に一時的にガベージコレクションをオフにします。この方法の利点は、独立したタイミングをより比較可能にすることです。この欠点は、GCが測定される関数の性能の重要なコンポーネントであるかもしれないことです。もしそうなら、GCはセットアップ文字列の最初のステートメントとして再有効化することができます。たとえば、次のようになります。

しかし、Pythonのガベージコレクタはあくまで再利用するためにあるのであって 循環的なゴミ すなわち、参照がサイクルを形成するオブジェクトのコレクションです。その代わりに、これらのオブジェクトは参照カウントがゼロになったときに直ちに解放されます。