Mengapa memmove lebih cepat daripada memcpy?

89

Saya menyelidiki hotspot kinerja dalam sebuah aplikasi yang menghabiskan 50% waktunya di memmove (3). Aplikasi ini memasukkan jutaan integer 4-byte ke dalam array yang diurutkan, dan menggunakan memmove untuk menggeser data "ke kanan" untuk memberi ruang bagi nilai yang disisipkan.

Harapan saya adalah menyalin memori sangat cepat, dan saya terkejut bahwa begitu banyak waktu dihabiskan untuk memmove. Tapi kemudian saya mendapat ide bahwa memmove lambat karena memindahkan daerah yang tumpang tindih, yang harus diimplementasikan dalam loop yang ketat, daripada menyalin halaman memori yang besar. Saya menulis sebuah microbenchmark kecil untuk mengetahui apakah ada perbedaan kinerja antara memcpy dan memmove, mengharapkan memcpy menang telak.

Saya menjalankan benchmark saya pada dua mesin (core i5, core i7) dan melihat bahwa memmove sebenarnya lebih cepat daripada memcpy, pada core i7 yang lebih lama bahkan hampir dua kali lebih cepat! Sekarang saya mencari penjelasan.

Ini patokan saya. Ini menyalin 100 mb dengan memcpy, dan kemudian memindahkan sekitar 100 mb dengan memmove; sumber dan tujuan tumpang tindih. Berbagai "jarak" untuk sumber dan tujuan dicoba. Setiap tes dijalankan 10 kali, waktu rata-rata dicetak.

https://gist.github.com/cruppstahl/78a57cdf937bca3d062c

Berikut adalah hasil pada Core i5 (Linux 3.5.0-54-generic # 81 ~ precision1-Ubuntu SMP x86_64 GNU / Linux, gcc adalah 4.6.3 (Ubuntu / Linaro 4.6.3-1ubuntu5). Angka dalam tanda kurung adalah jarak (ukuran celah) antara sumber dan tujuan:

memcpy        0.0140074
memmove (002) 0.0106168
memmove (004) 0.01065
memmove (008) 0.0107917
memmove (016) 0.0107319
memmove (032) 0.0106724
memmove (064) 0.0106821
memmove (128) 0.0110633

Memmove diimplementasikan sebagai kode assembler yang dioptimalkan SSE, menyalin dari belakang ke depan. Ia menggunakan perangkat keras prefetch untuk memuat data ke dalam cache, dan menyalin 128 byte ke register XMM, kemudian menyimpannya di tujuan.

( memcpy-ssse3-back.S , baris 1650 ff)

L(gobble_ll_loop):
    prefetchnta -0x1c0(%rsi)
    prefetchnta -0x280(%rsi)
    prefetchnta -0x1c0(%rdi)
    prefetchnta -0x280(%rdi)
    sub $0x80, %rdx
    movdqu  -0x10(%rsi), %xmm1
    movdqu  -0x20(%rsi), %xmm2
    movdqu  -0x30(%rsi), %xmm3
    movdqu  -0x40(%rsi), %xmm4
    movdqu  -0x50(%rsi), %xmm5
    movdqu  -0x60(%rsi), %xmm6
    movdqu  -0x70(%rsi), %xmm7
    movdqu  -0x80(%rsi), %xmm8
    movdqa  %xmm1, -0x10(%rdi)
    movdqa  %xmm2, -0x20(%rdi)
    movdqa  %xmm3, -0x30(%rdi)
    movdqa  %xmm4, -0x40(%rdi)
    movdqa  %xmm5, -0x50(%rdi)
    movdqa  %xmm6, -0x60(%rdi)
    movdqa  %xmm7, -0x70(%rdi)
    movdqa  %xmm8, -0x80(%rdi)
    lea -0x80(%rsi), %rsi
    lea -0x80(%rdi), %rdi
    jae L(gobble_ll_loop)

Mengapa memmove lebih cepat daripada memcpy? Saya berharap memcpy menyalin halaman memori, yang seharusnya jauh lebih cepat daripada perulangan. Dalam kasus terburuk, saya mengharapkan memcpy menjadi secepat memmove.

PS: Saya tahu bahwa saya tidak dapat mengganti memmove dengan memcpy di kode saya. Saya tahu bahwa sampel kode mencampurkan C dan C ++. Pertanyaan ini sebenarnya hanya untuk tujuan akademis.

UPDATE 1

Saya menjalankan beberapa variasi tes, berdasarkan berbagai jawaban.

  1. Saat menjalankan memcpy dua kali, maka proses kedua lebih cepat dari yang pertama.
  2. Ketika "menyentuh" ​​buffer tujuan dari memcpy ( memset(b2, 0, BUFFERSIZE...)) maka menjalankan memcpy yang pertama juga lebih cepat.
  3. memcpy masih sedikit lebih lambat dari memmove.

Berikut hasilnya:

memcpy        0.0118526
memcpy        0.0119105
memmove (002) 0.0108151
memmove (004) 0.0107122
memmove (008) 0.0107262
memmove (016) 0.0108555
memmove (032) 0.0107171
memmove (064) 0.0106437
memmove (128) 0.0106648

Kesimpulan saya: berdasarkan komentar dari @Oliver Charlesworth, sistem operasi harus melakukan memori fisik segera setelah buffer tujuan memcpy diakses untuk pertama kalinya (jika ada yang tahu cara "membuktikan" ini, tambahkan jawaban! ). Selain itu, seperti yang dikatakan @Mats Petersson, memmove lebih ramah cache daripada memcpy.

Terima kasih atas semua jawaban dan komentar yang bagus!

c++ c performance memory cruppstahl.dll
sumber
1
Anda melihat kode memmove, apakah Anda juga melihat kode memcpy?
Oliver Charlesworth
8
Harapan saya adalah menyalin memori sangat cepat - hanya jika memori dalam cache L1. Ketika data tidak sesuai dalam cache, kinerja penyalinan Anda berkurang.
Maxim Egorushkin
1
BTW, Anda hanya menyalin satu cabang memmove. Cabang ini tidak dapat menangani perpindahan ketika sumber tumpang tindih dengan tujuan dan tujuan berada di alamat yang lebih rendah.
Maxim Egorushkin
2
Saya belum punya waktu untuk mengakses mesin Linux, jadi saya belum bisa menguji teori ini. Tapi penjelasan lain yang mungkin terlalu berlebihan ; memcpyloop Anda adalah pertama kalinya konten b2diakses, sehingga OS harus menggunakan memori fisik untuk itu saat berjalan.
Oliver Charlesworth
2
PS: Jika ini menjadi hambatan saya akan mempertimbangkan kembali pendekatannya. Bagaimana dengan meletakkan nilai-nilai ke dalam daftar atau struktur pohon (misalnya pohon biner) dan kemudian membacanya menjadi sebuah larik di akhir. Node dalam pendekatan seperti itu akan menjadi kandidat yang sangat baik untuk alokasi kumpulan. Mereka hanya ditambahkan sampai akhir saat dirilis secara massal. Itu terutama benar jika Anda tahu berapa banyak yang Anda perlukan di awal. Pustaka peningkatan memiliki pengalokasi kumpulan.
Persixty

Jawaban:

57

memmovePanggilan Anda mengacak memori sebesar 2 hingga 128 byte, sementara memcpysumber dan tujuan Anda sama sekali berbeda. Entah bagaimana itu menjelaskan perbedaan kinerja: jika Anda menyalin ke tempat yang sama, Anda akan melihat memcpykemungkinan hasil yang sedikit lebih cepat, misalnya di ideone.com :

memmove (002) 0.0610362
memmove (004) 0.0554264
memmove (008) 0.0575859
memmove (016) 0.057326
memmove (032) 0.0583542
memmove (064) 0.0561934
memmove (128) 0.0549391
memcpy 0.0537919

Hampir tidak ada apa pun di dalamnya - tidak ada bukti bahwa menulis kembali ke halaman memori yang sudah salah memiliki banyak dampak, dan kami tentu saja tidak melihat separuh waktu ... tetapi itu menunjukkan bahwa tidak ada yang salah membuat memcpylebih lambat yang tidak perlu jika dibandingkan dengan apel -untuk-apel.

Tony Delroy
sumber
Saya berharap bahwa cache CPU tidak menyebabkan perbedaan karena buffer saya jauh lebih besar daripada cache.
cruppstahl
2
Tapi masing-masing membutuhkan jumlah akses memori utama yang sama, bukan? (Yaitu 100MB baca, dan 100MB tulis). Pola cache tidak bisa mengatasinya. Jadi satu-satunya cara yang satu bisa lebih lambat dari yang lain adalah jika beberapa hal harus dibaca / ditulis dari / ke memori lebih dari sekali.
Oliver Charlesworth
2
@Tony D - Kesimpulan saya adalah bertanya kepada orang yang lebih pintar dari saya;)
cruppstahl
1
Juga, apa yang terjadi jika Anda menyalin ke tempat yang sama, tetapi lakukan memcpydulu lagi?
Oliver Charlesworth
1
@OliverCharlesworth: pengujian pertama yang dijalankan selalu menghasilkan hasil yang signifikan, tetapi melakukan dua pengujian memcpy: memcpy 0.0688002 0.0583162 | memmove 0.0577443 0.05862 0.0601029 ... lihat ideone.com/8EEAcA
Tony Delroy
25

Saat Anda menggunakan memcpy, penulisan harus masuk ke cache. Saat Anda menggunakan memmovetempat saat Anda menyalin langkah kecil ke depan, memori yang Anda salin akan sudah berada di cache (karena terbaca 2, 4, 16 atau 128 byte "kembali"). Coba lakukan di memmovemana tujuannya adalah beberapa megabyte (> 4 * ukuran cache), dan saya curiga (tetapi tidak dapat diganggu untuk menguji) bahwa Anda akan mendapatkan hasil yang serupa.

Saya menjamin bahwa SEMUA adalah tentang pemeliharaan cache ketika Anda melakukan operasi memori besar.

Mats Petersson
sumber
+1 Saya pikir karena alasan yang Anda sebutkan, memmove perulangan mundur lebih ramah cache daripada memcpy. Namun, saya menemukan bahwa saat menjalankan pengujian memcpy dua kali, pengujian kedua secepat memmove. Mengapa? Buffer sangat besar sehingga menjalankan kedua memcpy harus menjadi tidak efisien (cache-bijaksana) seperti yang dijalankan pertama. Jadi sepertinya ada faktor tambahan di sini yang menyebabkan penalti kinerja.
cruppstahl
3
Dengan keadaan yang tepat, satu detik memcpyakan menjadi lebih cepat karena TLB sudah diisi sebelumnya. Selain itu, sedetik memcpypun tidak perlu mengosongkan cache dari hal-hal yang mungkin perlu Anda "singkirkan" (cache-lines yang kotor "buruk" untuk kinerja dalam banyak hal. Namun, untuk memastikannya, Anda harus menjalankan sesuatu seperti "perf" dan contoh hal-hal seperti cache-miss, TLB miss, dan sebagainya.
Mats Petersson
15

Secara historis, memmove dan memcopy adalah fungsi yang sama. Mereka bekerja dengan cara yang sama dan memiliki implementasi yang sama. Kemudian disadari bahwa memcopy tidak perlu (dan sering tidak) didefinisikan untuk menangani area yang tumpang tindih dengan cara tertentu.

Hasil akhirnya adalah memmove didefinisikan untuk menangani wilayah yang tumpang tindih dengan cara tertentu meskipun hal ini memengaruhi kinerja. Memcopy seharusnya menggunakan algoritme terbaik yang tersedia untuk wilayah yang tidak tumpang tindih. Penerapannya biasanya hampir identik.

Masalah yang Anda hadapi adalah ada begitu banyak variasi dari perangkat keras x86 sehingga tidak mungkin untuk mengetahui metode mana untuk memindahkan memori yang akan menjadi yang tercepat. Dan bahkan jika Anda merasa mendapatkan hasil dalam satu keadaan, sesuatu yang sederhana seperti memiliki 'langkah' yang berbeda dalam tata letak memori dapat menyebabkan kinerja cache yang sangat berbeda.

Anda dapat menentukan apa yang sebenarnya Anda lakukan atau mengabaikan masalah dan mengandalkan tolok ukur yang dilakukan untuk pustaka C.

Edit: Oh, dan satu hal terakhir; memindahkan banyak konten memori SANGAT lambat. Saya kira aplikasi Anda akan berjalan lebih cepat dengan sesuatu seperti implementasi B-Tree sederhana untuk menangani integer Anda. (Oh kamu, oke)

Sunting2: Untuk meringkas ekspansi saya di komentar: Microbenchmark adalah masalahnya di sini, ini tidak mengukur apa yang Anda pikirkan. Tugas yang diberikan untuk memcpy dan memmove sangat berbeda satu sama lain. Jika tugas yang diberikan ke memcpy diulangi beberapa kali dengan memmove atau memcpy hasil akhirnya tidak akan bergantung pada fungsi perpindahan memori yang Anda gunakan KECUALI jika regionnya tumpang tindih.

pengguna3710044
sumber
Tapi itu tentang - saya membandingkan apa yang sebenarnya saya lakukan. Pertanyaan ini tentang menafsirkan hasil tolok ukur, yang bertentangan dengan apa yang Anda klaim - bahwa memcpy lebih cepat untuk wilayah yang tidak tumpang tindih.
cruppstahl
Aplikasi saya adalah b-tree! Kapanpun integer disisipkan dalam leaf node, memmove dipanggil untuk memberi ruang. Saya sedang mengerjakan mesin database.
cruppstahl
1
Anda menggunakan tolok ukur mikro dan Anda bahkan tidak memiliki memcopy dan memmove menggeser data yang sama. Lokasi pasti dalam memori tempat data yang Anda atasi berada membuat perbedaan pada caching dan berapa banyak perjalanan bolak-balik ke memori yang harus dilakukan CPU.
pengguna3710044
Meskipun jawaban ini benar, namun sebenarnya tidak menjelaskan mengapa ini lebih lambat dalam kasus ini, pada dasarnya mengatakan "ini lebih lambat karena dalam beberapa kasus mungkin lebih lambat".
Oliver Charlesworth
Saya mengatakan bahwa untuk keadaan yang sama, termasuk tata letak memori yang sama untuk menyalin / memindahkan tolok ukur AKAN sama karena implementasinya sama. Masalahnya ada di microbenchmark.
pengguna3710044
2

"memcpy lebih efisien daripada memmove." Dalam kasus Anda, kemungkinan besar Anda tidak melakukan hal yang persis sama saat menjalankan kedua fungsi tersebut.

Secara umum, GUNAKAN memmove hanya jika perlu. GUNAKAN jika terdapat kemungkinan yang sangat wajar bahwa wilayah sumber dan tujuan bertumpuk.

Referensi: https://www.youtube.com/watch?v=Yr1YnOVG-4g Dr. Jerry Cain, (Kuliah Sistem Intro Stanford - 7) Waktu: 36:00

Ehsan
sumber