Mengapa memcpy () dan memmove () lebih cepat daripada peningkatan penunjuk?

Saya menyalin N byte dari pSrcke pDest. Ini dapat dilakukan dalam satu putaran:

for (int i = 0; i < N; i++)
    *pDest++ = *pSrc++

Mengapa ini lebih lambat dari memcpyatau memmove? Trik apa yang mereka gunakan untuk mempercepatnya?

Karena memcpy menggunakan penunjuk kata daripada pengarah byte, implementasi memcpy juga sering ditulis dengan instruksi SIMD yang memungkinkan untuk mengacak 128 bit pada satu waktu.

Instruksi SIMD adalah instruksi perakitan yang dapat melakukan operasi yang sama pada setiap elemen dalam vektor hingga panjang 16 byte. Itu termasuk memuat dan menyimpan instruksi.

Rutinitas penyalinan memori bisa jauh lebih rumit dan lebih cepat daripada penyalinan memori sederhana melalui petunjuk seperti:

void simple_memory_copy(void* dst, void* src, unsigned int bytes)
{
  unsigned char* b_dst = (unsigned char*)dst;
  unsigned char* b_src = (unsigned char*)src;
  for (int i = 0; i < bytes; ++i)
    *b_dst++ = *b_src++;
}

Perbaikan

Perbaikan pertama yang dapat dilakukan seseorang adalah menyelaraskan salah satu petunjuk pada batas kata (menurut kata yang saya maksud adalah ukuran integer asli, biasanya 32 bit / 4 byte, tetapi bisa 64 bit / 8 byte pada arsitektur yang lebih baru) dan menggunakan gerakan ukuran kata / salin instruksi. Ini membutuhkan penggunaan salinan byte ke byte sampai pointer sejajar.

void aligned_memory_copy(void* dst, void* src, unsigned int bytes)
{
  unsigned char* b_dst = (unsigned char*)dst;
  unsigned char* b_src = (unsigned char*)src;

  // Copy bytes to align source pointer
  while ((b_src & 0x3) != 0)
  {
    *b_dst++ = *b_src++;
    bytes--;
  }

  unsigned int* w_dst = (unsigned int*)b_dst;
  unsigned int* w_src = (unsigned int*)b_src;
  while (bytes >= 4)
  {
    *w_dst++ = *w_src++;
    bytes -= 4;
  }

  // Copy trailing bytes
  if (bytes > 0)
  {
    b_dst = (unsigned char*)w_dst;
    b_src = (unsigned char*)w_src;
    while (bytes > 0)
    {
      *b_dst++ = *b_src++;
      bytes--;
    }
  }
}

Arsitektur yang berbeda akan bekerja secara berbeda berdasarkan apakah sumber atau penunjuk tujuan disejajarkan dengan tepat. Misalnya pada prosesor XScale saya mendapatkan kinerja yang lebih baik dengan menyelaraskan penunjuk tujuan daripada penunjuk sumber.

Untuk lebih meningkatkan kinerja, beberapa loop unrolling dapat dilakukan, sehingga lebih banyak register prosesor yang dimuat dengan data dan itu berarti instruksi muat / penyimpanan dapat disisipkan dan latensinya disembunyikan oleh instruksi tambahan (seperti penghitungan loop, dll). Manfaat yang dibawa ini sedikit berbeda oleh prosesor, karena latensi instruksi muat / penyimpanan bisa sangat berbeda.

Pada tahap ini kode akhirnya ditulis dalam Assembly daripada C (atau C ++) karena Anda perlu menempatkan instruksi pemuatan dan penyimpanan secara manual untuk mendapatkan manfaat maksimal dari penyembunyian latensi dan throughput.

Umumnya, seluruh baris data cache harus disalin dalam satu iterasi dari loop yang tidak digulung.

Yang membawa saya ke peningkatan berikutnya, menambahkan pengambilan awal. Ini adalah instruksi khusus yang memberi tahu sistem cache prosesor untuk memuat bagian tertentu dari memori ke dalam cache-nya. Karena ada penundaan antara mengeluarkan instruksi dan mengisi baris cache, instruksi perlu ditempatkan sedemikian rupa sehingga data tersedia ketika akan disalin, dan tidak cepat / lambat.

Ini berarti meletakkan instruksi prefetch di awal fungsi serta di dalam loop salinan utama. Dengan instruksi prefetch di tengah-tengah loop salinan mengambil data yang akan disalin dalam beberapa waktu iterasi.

Saya tidak dapat mengingatnya, tetapi mungkin juga bermanfaat untuk mengambil lebih dulu alamat tujuan serta alamat sumber.

Faktor

Faktor utama yang mempengaruhi seberapa cepat memori dapat disalin adalah:

• Latensi antara prosesor, cache, dan memori utama.
• Ukuran dan struktur baris cache prosesor.
• Instruksi pemindahan / salin memori prosesor (latensi, throughput, ukuran register, dll).

Jadi, jika Anda ingin menulis rutinitas mengatasi memori yang efisien dan cepat, Anda harus mengetahui cukup banyak tentang prosesor dan arsitektur yang Anda tulis. Cukuplah untuk mengatakan, kecuali Anda menulis pada beberapa platform tertanam, akan jauh lebih mudah untuk hanya menggunakan rutinitas penyalinan memori bawaan.

memcpydapat menyalin lebih dari satu byte sekaligus tergantung pada arsitektur komputer. Kebanyakan komputer modern dapat bekerja dengan 32 bit atau lebih dalam satu instruksi prosesor.

Dari satu contoh implementasi :

    00026 * Untuk penyalinan cepat, optimalkan kasus umum di mana kedua penunjuk
    00027 * dan panjangnya disejajarkan dengan kata, dan salin kata-pada-waktu sebagai gantinya
    00028 * byte-at-a-time. Jika tidak, salin per byte.

Anda dapat mengimplementasikan memcpy()menggunakan salah satu teknik berikut, beberapa bergantung pada arsitektur Anda untuk peningkatan performa, dan semuanya akan jauh lebih cepat daripada kode Anda:

1. Gunakan unit yang lebih besar, seperti kata 32-bit, bukan byte. Anda juga dapat (atau mungkin harus) berurusan dengan penyelarasan di sini juga. Anda tidak dapat membaca / menulis kata 32-bit ke lokasi memori yang aneh misalnya di beberapa platform, dan di platform lain Anda membayar penalti performa yang sangat besar. Untuk mengatasinya, alamatnya harus berupa unit yang dapat dibagi 4. Anda dapat menggunakan hingga 64-bit untuk 64-bit CPU, atau bahkan lebih tinggi menggunakan instruksi SIMD (Instruksi tunggal, banyak data) ( MMX , SSE , dll.)

2. Anda dapat menggunakan instruksi CPU khusus yang kompilator Anda mungkin tidak dapat mengoptimalkan dari C. Misalnya, pada 80386, Anda dapat menggunakan instruksi awalan "rep" + instruksi "movsb" untuk memindahkan N byte yang ditentukan dengan menempatkan N dalam hitungan daftar. Kompiler yang baik hanya akan melakukan ini untuk Anda, tetapi Anda mungkin berada pada platform yang tidak memiliki kompiler yang baik. Perhatikan, contoh itu cenderung menjadi demonstrasi kecepatan yang buruk, tetapi dikombinasikan dengan penyelarasan + instruksi unit yang lebih besar, ini bisa lebih cepat daripada kebanyakan hal lain pada CPU tertentu.

3. Loop unrolling - branch bisa sangat mahal pada beberapa CPU, jadi membuka loop dapat menurunkan jumlah cabang. Ini juga merupakan teknik yang baik untuk menggabungkan instruksi SIMD dan unit berukuran sangat besar.

Misalnya, http://www.agner.org/optimize/#asmlib memiliki memcpypenerapan yang paling berhasil (dengan jumlah yang sangat kecil). Jika Anda membaca kode sumbernya, kode tersebut akan penuh dengan banyak kode perakitan sebaris yang menarik ketiga teknik di atas, memilih teknik mana dari teknik tersebut berdasarkan CPU yang Anda gunakan.

Perhatikan, ada juga pengoptimalan serupa yang dapat dilakukan untuk menemukan byte dalam buffer juga. strchr()dan teman-teman akan sering lebih cepat dari yang setara dengan lemparan tangan Anda. Ini terutama berlaku untuk .NET dan Java . Misalnya, dalam .NET, built-in String.IndexOf()jauh lebih cepat daripada pencarian string Boyer-Moore , karena menggunakan teknik pengoptimalan di atas.

Jawaban singkat:

• isi cache
• wordsize mentransfer alih-alih yang byte jika memungkinkan
• Keajaiban SIMD

Saya tidak tahu apakah itu benar-benar digunakan dalam implementasi dunia nyata memcpy, tapi saya pikir Perangkat Duff layak disebutkan di sini.

Dari Wikipedia :

send(to, from, count)
register short *to, *from;
register count;
{
        register n = (count + 7) / 8;
        switch(count % 8) {
        case 0:      do {     *to = *from++;
        case 7:              *to = *from++;
        case 6:              *to = *from++;
        case 5:              *to = *from++;
        case 4:              *to = *from++;
        case 3:              *to = *from++;
        case 2:              *to = *from++;
        case 1:              *to = *from++;
                } while(--n > 0);
        }
}

Perhatikan bahwa hal di atas bukan memcpykarena sengaja tidak menaikkan topenunjuk. Ini mengimplementasikan operasi yang sedikit berbeda: penulisan ke dalam register yang dipetakan memori. Lihat artikel Wikipedia untuk detailnya.

Seperti orang lain mengatakan salinan memcpy lebih besar dari potongan 1-byte. Menyalin dalam potongan berukuran kata jauh lebih cepat. Namun, sebagian besar implementasi mengambil langkah lebih jauh dan menjalankan beberapa instruksi MOV (kata) sebelum melakukan perulangan. Keuntungan dari menyalin, katakanlah, 8 blok kata per loop adalah bahwa loop itu sendiri mahal. Teknik ini mengurangi jumlah cabang bersyarat dengan faktor 8, mengoptimalkan salinan untuk balok raksasa.

Jawaban yang besar, tetapi jika Anda masih ingin menerapkan cepat suatu memcpydiri Anda, ada sebuah posting blog menarik tentang memcpy cepat, memcpy Cepat di C .

void *memcpy(void* dest, const void* src, size_t count)
{
    char* dst8 = (char*)dest;
    char* src8 = (char*)src;

    if (count & 1) {
        dst8[0] = src8[0];
        dst8 += 1;
        src8 += 1;
    }

    count /= 2;
    while (count--) {
        dst8[0] = src8[0];
        dst8[1] = src8[1];

        dst8 += 2;
        src8 += 2;
    }
    return dest;
}

Bahkan, bisa lebih baik lagi dengan mengoptimalkan akses memori.

Karena seperti banyak rutinitas perpustakaan, ini telah dioptimalkan untuk arsitektur yang Anda jalankan. Yang lain telah memposting berbagai teknik yang dapat digunakan.

Diberikan pilihan, gunakan rutinitas perpustakaan daripada roll Anda sendiri. Ini adalah variasi KERING yang saya sebut DRO (Don't Repeat Others). Selain itu, rutinitas perpustakaan cenderung tidak salah dibandingkan penerapan Anda sendiri.

Saya telah melihat pemeriksa akses memori mengeluh tentang pembacaan di luar batas pada memori atau buffer string yang bukan merupakan kelipatan dari ukuran kata. Ini adalah hasil dari pengoptimalan yang digunakan.

Anda dapat melihat implementasi MacOS dari memset, memcpy dan memmove.

Saat boot, OS menentukan prosesor mana yang menjalankannya. Ini telah membangun kode yang dioptimalkan secara khusus untuk setiap prosesor yang didukung, dan pada saat boot menyimpan instruksi jmp ke kode yang tepat di lokasi hanya baca / tetap.

Implementasi C memset, memcpy dan memmove hanyalah lompatan ke lokasi tetap itu.

Implementasi menggunakan kode yang berbeda tergantung pada penyelarasan sumber dan tujuan untuk memcpy dan memmove. Mereka jelas menggunakan semua kemampuan vektor yang tersedia. Mereka juga menggunakan varian non-caching saat Anda menyalin data dalam jumlah besar, dan memiliki instruksi untuk meminimalkan menunggu tabel halaman. Ini bukan hanya kode assembler, ini adalah kode assembler yang ditulis oleh seseorang dengan pengetahuan yang sangat baik tentang setiap arsitektur prosesor.

Intel juga menambahkan instruksi assembler yang dapat membuat operasi string lebih cepat. Misalnya dengan instruksi untuk mendukung strstr yang melakukan perbandingan 256 byte dalam satu siklus.