Pertanyaan Mengapa kode menggunakan variabel perantara lebih cepat daripada kode tanpa?


Saya telah mengalami perilaku aneh ini dan gagal menjelaskannya. Ini adalah tolok ukur:

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

Bagaimana perbandingan dengan tugas variabel lebih cepat daripada menggunakan satu liner dengan variabel sementara lebih dari 27%?

Dengan dokumen Python, pengumpulan sampah dinonaktifkan selama waktu sehingga tidak bisa begitu. Apakah ini semacam optimasi?

Hasilnya juga dapat direproduksi dengan Python 2.x meskipun lebih sedikit.

Menjalankan Windows 7, CPython 3.5.1, Intel i7 3,40 GHz, 64 bit baik OS dan Python. Sepertinya mesin yang berbeda saya sudah mencoba berjalan di Intel i7 3,60 GHz dengan Python 3.5.0 tidak mereproduksi hasil.


Menjalankan menggunakan proses Python yang sama dengan timeit.timeit() @ 10.000 loop menghasilkan 0,703 dan 0,804 masing-masing. Masih menunjukkan meskipun pada tingkat yang lebih rendah. (~ 12,5%)


75
2018-04-11 12:19


asal


Jawaban:


Hasil saya mirip dengan Anda: kode menggunakan variabel perantara cukup konsisten setidaknya 10-20% lebih cepat dalam Python 3.4 yang saya capai. Namun ketika saya menggunakan IPython pada interpreter Python 3.4 yang sama, saya mendapat hasil ini:

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

Khususnya, saya tidak pernah berhasil mendekati angka 74,2 µs untuk yang pertama ketika saya menggunakannya -mtimeit dari baris perintah.

Jadi Heisenbug ini ternyata menjadi sesuatu yang cukup menarik. Saya memutuskan untuk menjalankan perintah dengan strace dan memang ada sesuatu yang mencurigakan terjadi:

% 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

Sekarang itu alasan yang bagus untuk perbedaannya. Kode yang tidak menggunakan variabel menyebabkan mmap system call disebut hampir 1000x lebih dari yang menggunakan variabel perantara.

Itu withoutvars penuh mmap/munmap untuk wilayah 256k; garis-garis yang sama ini diulang berkali-kali:

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

Itu mmap panggilan tampaknya berasal dari fungsi _PyObject_ArenaMmap dari Objects/obmalloc.c; itu obmalloc.c juga mengandung makro ARENA_SIZE, yang mana #defined untuk menjadi (256 << 10) (itu adalah 262144); sama dengan itu munmap cocok dengan _PyObject_ArenaMunmap dari obmalloc.c.

obmalloc.c mengatakan itu

Sebelum Python 2.5, arena tidak pernah free()'ed. Dimulai dengan Python 2.5,   kami mencoba untuk free() arena, dan menggunakan beberapa strategi heuristik ringan untuk meningkat   kemungkinan bahwa arena akhirnya dapat dibebaskan.

Dengan demikian heuristik ini dan fakta bahwa pengalokasi objek Python melepaskan arena bebas ini segera setelah mereka dikosongkan mengarah ke python3 -mtimeit 'tuple(range(2000)) == tuple(range(2000))' memicu perilaku patologis di mana satu area memori 256 kiB dialokasikan kembali dan dilepaskan berulang kali; dan alokasi ini terjadi dengan mmap/munmap, yang relatif mahal karena mereka panggilan sistem - lebih jauh lagi, mmap dengan MAP_ANONYMOUS mensyaratkan bahwa halaman yang baru dipetakan harus memusatkan perhatian - meskipun Python tidak akan peduli.

Perilaku ini tidak ada dalam kode yang menggunakan variabel perantara, karena menggunakan sedikit lebih memori dan tidak ada arena memori yang dapat dibebaskan karena beberapa objek masih dialokasikan di dalamnya. Itu karena timeit akan membuatnya menjadi lingkaran yang tidak berbeda

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

Sekarang perilakunya adalah keduanya adan b akan tetap terikat sampai mereka * dipindahkan, jadi di iterasi kedua, tuple(range(2000)) akan mengalokasikan tupel ke-3, dan tugas a = tuple(...) akan mengurangi jumlah referensi tupel lama, menyebabkannya dilepaskan, dan meningkatkan jumlah referensi tupel baru; maka hal yang sama terjadi pada b. Oleh karena itu setelah iterasi pertama selalu ada setidaknya 2 dari tupel ini, jika tidak 3, jadi labrakan tidak terjadi.

Terutama tidak dapat dijamin bahwa kode menggunakan variabel perantara selalu lebih cepat - memang di beberapa pengaturan mungkin menggunakan variabel perantara akan menghasilkan tambahan mmap panggilan, sedangkan kode yang membandingkan nilai kembali secara langsung mungkin baik-baik saja.


Seseorang bertanya mengapa ini terjadi, kapan timeit menonaktifkan pengumpulan sampah. Memang benar demikian timeit melakukannya:

Catatan

Secara default, timeit() untuk sementara mematikan pengumpulan sampah selama waktunya. Keuntungan dari pendekatan ini adalah bahwa hal itu membuat timing independen lebih dapat dibandingkan. Kerugian ini adalah bahwa GC dapat menjadi komponen penting dari kinerja fungsi yang sedang diukur. Jika demikian, GC dapat diaktifkan kembali sebagai pernyataan pertama dalam string penyiapan. Sebagai contoh:

Namun, pengumpul sampah Python hanya ada di sana untuk merebut kembali sampah siklik, yaitu koleksi objek yang rujukannya membentuk siklus. Itu tidak terjadi di sini; alih-alih objek ini dibebaskan segera ketika jumlah referensi turun menjadi nol.


101
2018-04-11 13:08



Pertanyaan pertama di sini adalah, apakah bisa direproduksi? Bagi sebagian dari kita, setidaknya itu pasti meskipun orang lain mengatakan mereka tidak melihat efeknya. Ini di Fedora, dengan tes kesetaraan berubah menjadi is sebagai benar-benar melakukan perbandingan tampaknya tidak relevan dengan hasilnya, dan rentangnya didorong hingga 200.000 karena tampaknya memaksimalkan efeknya:

$ python3 -m timeit "a = tuple(range(200000));  b = tuple(range(200000)); a is b"
100 loops, best of 3: 7.03 msec per loop
$ python3 -m timeit "a = tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 10.2 msec per loop
$ python3 -m timeit "tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 10.2 msec per loop
$ python3 -m timeit "a = b = tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 9.99 msec per loop
$ python3 -m timeit "a = b = tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 10.2 msec per loop
$ python3 -m timeit "tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 10.1 msec per loop
$ python3 -m timeit "a = tuple(range(200000));  b = tuple(range(200000)); a is b"
100 loops, best of 3: 7 msec per loop
$ python3 -m timeit "a = tuple(range(200000));  b = tuple(range(200000)); a is b"
100 loops, best of 3: 7.02 msec per loop

Saya perhatikan bahwa variasi antara proses, dan urutan di mana ekspresi dijalankan membuat sedikit perbedaan pada hasil.

Menambahkan tugas ke adan b ke versi lambat tidak mempercepatnya. Kenyataannya seperti yang kita harapkan menugaskan untuk variabel lokal memiliki efek yang dapat diabaikan. Satu-satunya hal yang mempercepatnya adalah memecah ekspresi sepenuhnya menjadi dua. Satu-satunya perbedaan yang harus dibuat adalah mengurangi kedalaman tumpukan maksimum yang digunakan oleh Python ketika mengevaluasi ekspresi (dari 4 hingga 3).

Itu memberi kita petunjuk bahwa efeknya terkait dengan kedalaman tumpukan, mungkin tingkat ekstra mendorong tumpukan ke halaman memori lain. Jika demikian, kita harus melihat bahwa membuat perubahan lain yang memengaruhi tumpukan akan berubah (kemungkinan besar membunuh efeknya), dan sebenarnya itulah yang kita lihat:

$ python3 -m timeit -s "def foo():
   tuple(range(200000)) is tuple(range(200000))" "foo()"
100 loops, best of 3: 10 msec per loop
$ python3 -m timeit -s "def foo():
   tuple(range(200000)) is tuple(range(200000))" "foo()"
100 loops, best of 3: 10 msec per loop
$ python3 -m timeit -s "def foo():
   a = tuple(range(200000));  b = tuple(range(200000)); a is b" "foo()"
100 loops, best of 3: 9.97 msec per loop
$ python3 -m timeit -s "def foo():
   a = tuple(range(200000));  b = tuple(range(200000)); a is b" "foo()"
100 loops, best of 3: 10 msec per loop

Jadi, saya pikir efeknya sepenuhnya karena seberapa banyak tumpukan Python dikonsumsi selama proses waktu. Itu masih aneh.


7
2018-04-11 13:04