Mengapa menyalin daftar yang diacak jauh lebih lambat?

89

Menyalin range(10**6)daftar yang diacak sepuluh kali membutuhkan waktu sekitar 0,18 detik: (ini adalah lima proses)

0.175597017661
0.173731403198
0.178601711594
0.180330912952
0.180811964451

Menyalin daftar yang tidak diacak sepuluh kali membutuhkan waktu sekitar 0,05 detik:

0.058402235973
0.0505464636856
0.0509734306934
0.0526022752744
0.0513324916184

Inilah kode pengujian saya:

from timeit import timeit
import random

a = range(10**6)
random.shuffle(a)    # Remove this for the second test.
a = list(a)          # Just an attempt to "normalize" the list.
for _ in range(5):
    print timeit(lambda: list(a), number=10)

Saya juga mencoba menyalin dengan a[:], hasilnya serupa (yaitu, perbedaan kecepatan yang besar)

Mengapa perbedaan kecepatannya besar? Saya tahu dan memahami perbedaan kecepatan dalam array terkenal Mengapa lebih cepat untuk memproses array yang diurutkan daripada array yang tidak disortir? Misalnya, tetapi di sini pemrosesan saya tidak memiliki keputusan. Itu hanya menyalin referensi di dalam daftar secara membabi buta, bukan?

Saya menggunakan Python 2.7.12 di Windows 10.

Sunting: Mencoba Python 3.5.2 juga sekarang, hasilnya hampir sama (diacak secara konsisten sekitar 0,17 detik, diacak secara konsisten sekitar 0,05 detik). Berikut kode untuk itu:

a = list(range(10**6))
random.shuffle(a)
a = list(a)
for _ in range(5):
    print(timeit(lambda: list(a), number=10))
python python-internals Stefan Pochmann
sumber
22
Mengapa mengurutkan array membuat Python loop lebih cepat
vaultah
5
Tolong jangan berteriak pada saya, saya mencoba membantu Anda! Setelah mengubah urutan, saya mendapatkan kira-kira 0.25di setiap iterasi dari setiap tes. Jadi di platform saya, urutan itu penting.
barak manos
1
@vaultah Terima kasih, tapi saya sudah membacanya sekarang dan saya tidak setuju. Ketika saya melihat kodenya di sana, saya langsung teringat cache hits / miss ints, yang juga merupakan kesimpulan penulis. Tetapi kodenya menambahkan angka-angka, yang mengharuskan untuk melihatnya. Kode saya tidak. Punyaku hanya perlu menyalin referensi, bukan mengaksesnya.
Stefan Pochmann
2
Ada jawaban lengkap di tautan oleh @vaultah (Anda sedikit tidak setuju sekarang, saya mengerti). Tapi bagaimanapun saya masih berpikir bahwa kita tidak boleh menggunakan python untuk fitur tingkat rendah, dan karenanya perlu dikhawatirkan. Tapi topik itu menarik, terima kasih.
Nikolay Prokopyev
1
@NikolayProkopyev Ya, saya tidak khawatir tentang itu, hanya memperhatikan ini saat melakukan hal lain, tidak bisa menjelaskannya, dan menjadi penasaran. Dan saya senang saya bertanya dan punya jawaban sekarang :-)
Stefan Pochmann

Jawaban:

100

Hal yang menarik adalah bahwa itu tergantung pada urutan bilangan bulat pertama kali dibuat. Misalnya, alih-alih shufflemembuat urutan acak dengan random.randint:

from timeit import timeit
import random

a = [random.randint(0, 10**6) for _ in range(10**6)]
for _ in range(5):
    print(timeit(lambda: list(a), number=10))

Ini secepat menyalin list(range(10**6))(contoh pertama dan cepat) Anda.

Namun ketika Anda mengocok - maka bilangan bulat Anda tidak dalam urutan saat pertama kali dibuat lagi, itulah yang membuatnya lambat.

Selingan singkat:

  • Semua objek Python ada di heap, jadi setiap objek adalah pointer.
  • Menyalin daftar adalah operasi yang dangkal.
  • Namun Python menggunakan penghitungan referensi sehingga ketika sebuah objek dimasukkan ke dalam wadah baru, jumlah referensi itu harus bertambah ( Py_INCREFdalamlist_slice ), jadi Python benar-benar perlu pergi ke tempat objek itu berada. Itu tidak bisa hanya menyalin referensi.

Jadi, ketika Anda menyalin daftar Anda, Anda mendapatkan setiap item dari daftar itu dan meletakkannya "sebagaimana adanya" di daftar baru. Saat item Anda berikutnya dibuat tidak lama setelah item saat ini, ada kemungkinan besar (tidak ada jaminan!) Bahwa item tersebut disimpan di sebelahnya di heap.

Mari kita asumsikan bahwa setiap kali komputer Anda memuat item dalam cache, ia juga memuat xitem berikutnya di memori (lokalitas cache). Kemudian komputer Anda dapat melakukan penambahan jumlah referensi untuk x+1item pada cache yang sama!

Dengan urutan yang diacak, ini masih memuat item berikutnya dalam memori tetapi ini bukan yang berikutnya dalam daftar. Jadi ia tidak dapat melakukan kenaikan jumlah referensi tanpa "benar-benar" mencari item berikutnya.

TL; DR: Kecepatan sebenarnya bergantung pada apa yang terjadi sebelum penyalinan: dalam urutan apa item ini dibuat dan dalam urutan apa item ini ada dalam daftar.

Anda dapat memverifikasi ini dengan melihat id:

Detail implementasi CPython: Ini adalah alamat objek di memori.

a = list(range(10**6, 10**6+100))
for item in a:
    print(id(item))

Hanya untuk menampilkan kutipan singkat:

1496489995888
1496489995920  # +32
1496489995952  # +32
1496489995984  # +32
1496489996016  # +32
1496489996048  # +32
1496489996080  # +32
1496489996112
1496489996144
1496489996176
1496489996208
1496489996240
1496507297840
1496507297872
1496507297904
1496507297936
1496507297968
1496507298000
1496507298032
1496507298064
1496507298096
1496507298128
1496507298160
1496507298192

Jadi objek ini benar-benar "bersebelahan di heap". Dengan shufflemereka tidak:

import random
a = list(range(10**6, 100+10**6))
random.shuffle(a)
last = None
for item in a:
    if last is not None:
        print('diff', id(item) - id(last))
    last = item

Yang menunjukkan ini tidak benar-benar bersebelahan dalam memori:

diff 736
diff -64
diff -17291008
diff -128
diff 288
diff -224
diff 17292032
diff -1312
diff 1088
diff -17292384
diff 17291072
diff 608
diff -17290848
diff 17289856
diff 928
diff -672
diff 864
diff -17290816
diff -128
diff -96
diff 17291552
diff -192
diff 96
diff -17291904
diff 17291680
diff -1152
diff 896
diff -17290528
diff 17290816
diff -992
diff 448

Catatan penting:

Saya sendiri belum memikirkan ini. Sebagian besar informasi dapat ditemukan di postingan blog Ricky Stewart .

Jawaban ini didasarkan pada implementasi CPython "resmi" dari Python. Detail dalam implementasi lain (Jython, PyPy, IronPython, ...) mungkin berbeda. Terima kasih @ JörgWMittag telah menunjukkan hal ini .

MSeifert
sumber
6
@augurar Menyalin referensi menyiratkan menaikkan penghitung referensi yang ada di objek (sehingga akses objek tidak dapat dihindari)
Leon
1
@StefanPochmann Fungsi yang melakukan penyalinan adalah list_slicedan pada baris 453 Anda dapat melihat Py_INCREF(v);panggilan yang perlu mengakses objek yang dialokasikan heap.
MSeifert
1
@MSeifert Eksperimen bagus lainnya adalah menggunakan a = [0] * 10**7(naik dari 10 ** 6 karena itu terlalu tidak stabil), yang bahkan lebih cepat daripada menggunakan a = range(10**7)(dengan faktor sekitar 1,25). Jelas karena itu lebih baik untuk caching.
Stefan Pochmann
1
Saya hanya bertanya-tanya mengapa saya mendapatkan integer 32bit pada komputer 64bit dengan python 64bit. Tapi sebenarnya itu bagus untuk caching juga :-) Bahkan [0,1,2,3]*((10**6) // 4)secepat a = [0] * 10**6. Namun dengan bilangan bulat dari 0-255 ada fakta lain yang masuk: Ini disimpan sehingga dengan ini urutan pembuatan (di dalam skrip Anda) tidak penting lagi - karena mereka dibuat ketika Anda memulai python.
MSeifert
2
Perhatikan bahwa dari empat implementasi Python siap produksi yang ada, hanya satu yang menggunakan penghitungan referensi. Jadi, analisis ini benar-benar hanya berlaku untuk satu implementasi.
Jörg W Mittag
24

Saat Anda mengacak item daftar, item tersebut memiliki lokalitas referensi yang lebih buruk, yang menyebabkan kinerja cache lebih buruk.

Anda mungkin berpikir bahwa menyalin daftar hanya menyalin referensi, bukan objek, jadi lokasinya di heap seharusnya tidak menjadi masalah. Namun, menyalin masih melibatkan mengakses setiap objek untuk memodifikasi refcount.

augurar
sumber
Ini mungkin jawaban yang lebih baik untuk saya (setidaknya jika itu memiliki tautan ke "bukti" seperti MSeifert's) karena hanya ini yang saya lewatkan dan itu sangat ringkas, tapi saya pikir saya akan tetap menggunakan MSeifert seperti yang saya rasakan mungkin lebih baik untuk orang lain. Terima kasih juga, terima kasih.
Stefan Pochmann
Juga akan menambahkan bahwa pentioid, athlum dll memiliki logika mistik di dalamnya untuk mendeteksi pola alamat, dan akan mulai mengambil data saat mereka melihat pola. Yang dalam hal ini, bisa menendang untuk mengambil data lebih dulu (mengurangi kehilangan cache) ketika angka-angka itu berurutan. Tentu saja, efek ini merupakan tambahan pada peningkatan% klik dari lokalitas.
Greggo
5

Seperti yang dijelaskan oleh orang lain, itu tidak hanya menyalin referensi tetapi juga meningkatkan jumlah referensi di dalam benda-benda dan dengan demikian benda yang diakses dan cache berperan.

Di sini saya hanya ingin menambahkan lebih banyak eksperimen. Tidak begitu banyak tentang shuffled vs unshuffled (di mana mengakses satu elemen mungkin melewatkan cache tetapi memasukkan elemen-elemen berikut ke dalam cache sehingga mereka terkena). Tetapi tentang elemen berulang, di mana akses nanti dari elemen yang sama mungkin mengenai cache karena elemen tersebut masih dalam cache.

Menguji rentang normal:

>>> from timeit import timeit
>>> a = range(10**7)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[5.1915339142808925, 5.1436351868889645, 5.18055115701749]

Daftar dengan ukuran yang sama tetapi dengan hanya satu elemen yang diulang terus-menerus lebih cepat karena selalu menyentuh cache:

>>> a = [0] * 10**7
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[4.125743135926939, 4.128927210087596, 4.0941229388550795]

Dan sepertinya tidak masalah berapa jumlahnya:

>>> a = [1234567] * 10**7
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[4.124106479141709, 4.156590225249886, 4.219242600790949]

Menariknya, itu menjadi lebih cepat ketika saya malah mengulangi dua atau empat elemen yang sama:

>>> a = [0, 1] * (10**7 / 2)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[3.130586101607932, 3.1001001764957294, 3.1318465707127814]

>>> a = [0, 1, 2, 3] * (10**7 / 4)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[3.096105435911994, 3.127148431279352, 3.132872673690855]

Saya kira ada sesuatu yang tidak suka penghitung tunggal yang sama meningkat sepanjang waktu. Mungkin beberapa jalur pipa terhenti karena setiap kenaikan harus menunggu hasil dari peningkatan sebelumnya, tetapi ini adalah tebakan liar.

Bagaimanapun, coba ini untuk jumlah elemen berulang yang lebih besar:

from timeit import timeit
for e in range(26):
    n = 2**e
    a = range(n) * (2**25 / n)
    times = [timeit(lambda: list(a), number=20) for _ in range(3)]
    print '%8d ' % n, '  '.join('%.3f' % t for t in times), ' => ', sum(times) / 3

Outputnya (kolom pertama adalah jumlah elemen yang berbeda, untuk setiap saya menguji tiga kali dan kemudian mengambil rata-rata):

       1  2.871  2.828  2.835  =>  2.84446732686
       2  2.144  2.097  2.157  =>  2.13275338734
       4  2.129  2.297  2.247  =>  2.22436720645
       8  2.151  2.174  2.170  =>  2.16477771575
      16  2.164  2.159  2.167  =>  2.16328197911
      32  2.102  2.117  2.154  =>  2.12437970598
      64  2.145  2.133  2.126  =>  2.13462250728
     128  2.135  2.122  2.137  =>  2.13145065221
     256  2.136  2.124  2.140  =>  2.13336283943
     512  2.140  2.188  2.179  =>  2.1688431668
    1024  2.162  2.158  2.167  =>  2.16208440826
    2048  2.207  2.176  2.213  =>  2.19829998424
    4096  2.180  2.196  2.202  =>  2.19291917834
    8192  2.173  2.215  2.188  =>  2.19207065277
   16384  2.258  2.232  2.249  =>  2.24609975704
   32768  2.262  2.251  2.274  =>  2.26239771771
   65536  2.298  2.264  2.246  =>  2.26917420394
  131072  2.285  2.266  2.313  =>  2.28767871168
  262144  2.351  2.333  2.366  =>  2.35030805124
  524288  2.932  2.816  2.834  =>  2.86047313113
 1048576  3.312  3.343  3.326  =>  3.32721167007
 2097152  3.461  3.451  3.547  =>  3.48622758473
 4194304  3.479  3.503  3.547  =>  3.50964316455
 8388608  3.733  3.496  3.532  =>  3.58716466865
16777216  3.583  3.522  3.569  =>  3.55790996695
33554432  3.550  3.556  3.512  =>  3.53952594744

Jadi dari sekitar 2,8 detik untuk satu elemen (berulang) turun menjadi sekitar 2,2 detik untuk 2, 4, 8, 16, ... elemen yang berbeda dan tetap di sekitar 2,2 detik hingga ratusan ribu. Saya pikir ini menggunakan cache L2 saya (4 × 256 KB, saya memiliki i7-6700 ).

Kemudian selama beberapa langkah, waktunya naik menjadi 3,5 detik. Saya rasa ini menggunakan campuran cache L2 saya dan cache L3 saya (8 MB) hingga "habis" juga.

Pada akhirnya itu tetap sekitar 3,5 detik, saya kira karena cache saya tidak lagi membantu dengan elemen yang berulang.

Stefan Pochmann
sumber
0

Sebelum pengacakan, saat dialokasikan di heap, objek indeks yang berdekatan berdekatan dalam memori, dan tingkat ketepatan memori tinggi saat diakses; setelah pengocokan, objek dari indeks yang berdekatan dari daftar baru tidak ada dalam memori. Berdekatan, hit rate sangat buruk.

xws
sumber