Apakah lebih baik menggunakan std :: memcpy () atau std :: copy () dalam hal kinerja?

Apakah lebih baik digunakan memcpyseperti yang ditunjukkan di bawah ini atau lebih baik digunakan std::copy()dalam hal kinerja? Mengapa?

char *bits = NULL;
...

bits = new (std::nothrow) char[((int *) copyMe->bits)[0]];
if (bits == NULL)
{
    cout << "ERROR Not enough memory.\n";
    exit(1);
}

memcpy (bits, copyMe->bits, ((int *) copyMe->bits)[0]);

Saya akan menentang kebijaksanaan umum di sini yang std::copyakan memiliki sedikit kehilangan kinerja, hampir tak terlihat. Saya hanya melakukan tes dan menemukan bahwa itu tidak benar: Saya memang melihat perbedaan kinerja. Namun, pemenangnya adalah std::copy.

Saya menulis implementasi C ++ SHA-2. Dalam pengujian saya, saya hash 5 string menggunakan keempat versi SHA-2 (224, 256, 384, 512), dan saya loop 300 kali. Saya mengukur waktu menggunakan Boost.timer. 300 loop counter itu cukup untuk sepenuhnya menstabilkan hasil saya. Saya menjalankan tes masing-masing 5 kali, bergantian antara memcpyversi dan std::copyversi. Kode saya mengambil keuntungan dari mengambil data dalam potongan sebanyak mungkin (banyak implementasi lain beroperasi dengan char/ char *, sedangkan saya beroperasi dengan T/ T *(di mana Tadalah tipe terbesar dalam implementasi pengguna yang memiliki perilaku overflow yang benar), sehingga akses memori cepat pada tipe terbesar yang saya dapat adalah pusat kinerja algoritma saya. Ini adalah hasil saya:

Waktu (dalam detik) untuk menyelesaikan uji SHA-2

std::copy   memcpy  % increase
6.11        6.29    2.86%
6.09        6.28    3.03%
6.10        6.29    3.02%
6.08        6.27    3.03%
6.08        6.27    3.03%

Total peningkatan rata-rata kecepatan std :: copy over memcpy: 2.99%

Kompiler saya adalah gcc 4.6.3 pada Fedora 16 x86_64. Bendera pengoptimalan saya adalah -Ofast -march=native -funsafe-loop-optimizations.

Kode untuk implementasi SHA-2 saya.

Saya memutuskan untuk menjalankan tes pada implementasi MD5 saya juga. Hasilnya jauh lebih tidak stabil, jadi saya memutuskan untuk melakukan 10 kali. Namun, setelah beberapa upaya pertama saya, saya mendapatkan hasil yang sangat bervariasi dari satu lari ke yang berikutnya, jadi saya menduga ada semacam aktivitas OS yang terjadi. Saya memutuskan untuk memulai dari awal.

Pengaturan dan bendera kompiler yang sama. Hanya ada satu versi MD5, dan ini lebih cepat dari SHA-2, jadi saya melakukan 3000 loop pada set yang sama dari 5 string tes.

Ini adalah 10 hasil akhir saya:

Waktu (dalam detik) untuk menyelesaikan tes MD5

std::copy   memcpy      % difference
5.52        5.56        +0.72%
5.56        5.55        -0.18%
5.57        5.53        -0.72%
5.57        5.52        -0.91%
5.56        5.57        +0.18%
5.56        5.57        +0.18%
5.56        5.53        -0.54%
5.53        5.57        +0.72%
5.59        5.57        -0.36%
5.57        5.56        -0.18%

Total penurunan rata-rata kecepatan std :: copy over memcpy: 0.11%

Kode untuk implementasi MD5 saya

Hasil ini menunjukkan bahwa ada beberapa optimasi yang std :: copy digunakan dalam tes SHA-2 saya yang std::copytidak dapat digunakan dalam tes MD5 saya. Dalam tes SHA-2, kedua array diciptakan dalam fungsi yang sama yang disebut std::copy/ memcpy. Dalam tes MD5 saya, salah satu array diteruskan ke fungsi sebagai parameter fungsi.

Saya melakukan sedikit pengujian lagi untuk melihat apa yang bisa saya lakukan untuk membuat std::copylebih cepat lagi. Jawabannya ternyata sederhana: aktifkan optimasi waktu tautan. Ini adalah hasil saya dengan LTO dihidupkan (opsi -flto di gcc):

Waktu (dalam detik) untuk menyelesaikan uji MD5 dengan -flto

std::copy   memcpy      % difference
5.54        5.57        +0.54%
5.50        5.53        +0.54%
5.54        5.58        +0.72%
5.50        5.57        +1.26%
5.54        5.58        +0.72%
5.54        5.57        +0.54%
5.54        5.56        +0.36%
5.54        5.58        +0.72%
5.51        5.58        +1.25%
5.54        5.57        +0.54%

Total peningkatan rata-rata kecepatan std :: copy over memcpy: 0.72%

Singkatnya, tampaknya tidak ada penalti kinerja untuk menggunakan std::copy. Bahkan, tampaknya ada peningkatan kinerja.

Penjelasan hasil

Jadi mengapa mungkin std::copymemberikan peningkatan kinerja?

Pertama, saya tidak berharap itu lebih lambat untuk implementasi apa pun, selama optimasi inlining dihidupkan. Semua penyusun inline secara agresif; itu mungkin optimasi yang paling penting karena memungkinkan banyak optimasi lainnya. std::copydapat (dan saya menduga semua implementasi dunia nyata lakukan) mendeteksi bahwa argumen sepele disalin dan bahwa memori diletakkan secara berurutan. Ini berarti bahwa dalam kasus terburuk, ketika memcpylegal, std::copyharus melakukan tidak lebih buruk. Implementasi sepele dari std::copyyang memcpyharus memenuhi kriteria kompiler Anda "selalu sebaris ini ketika mengoptimalkan untuk kecepatan atau ukuran".

Namun, std::copyjuga menyimpan lebih banyak informasinya. Saat Anda menelepon std::copy, fungsi tersebut menjaga jenisnya tetap utuh. memcpyberoperasi pada void *, yang membuang hampir semua informasi yang berguna. Sebagai contoh, jika saya memasukkan array std::uint64_t, kompiler atau pelaksana perpustakaan mungkin dapat memanfaatkan keselarasan 64-bit dengan std::copy, tetapi mungkin lebih sulit untuk melakukannya dengan memcpy. Banyak implementasi algoritma seperti ini bekerja dengan terlebih dahulu mengerjakan bagian yang tidak selaras di awal rentang, kemudian bagian yang disejajarkan, kemudian bagian yang tidak selaras di bagian akhir. Jika semuanya dijamin akan disejajarkan, maka kode menjadi lebih sederhana dan lebih cepat, dan lebih mudah bagi prediktor cabang dalam prosesor Anda untuk mendapatkan yang benar.

Optimalisasi prematur?

std::copyberada dalam posisi yang menarik. Saya berharap itu tidak pernah lebih lambat dari memcpydan kadang-kadang lebih cepat dengan kompiler optimisasi modern. Apalagi apa pun yang Anda bisa memcpy, Anda bisa std::copy. memcpytidak memungkinkan tumpang tindih dalam buffer, sedangkan std::copydukungan tumpang tindih dalam satu arah (dengan std::copy_backwarduntuk arah lain tumpang tindih). memcpyhanya bekerja pada pointer, std::copybekerja pada setiap iterator ( std::map, std::vector, std::deque, atau sendiri jenis kustom saya). Dengan kata lain, Anda hanya perlu menggunakan std::copysaat Anda perlu menyalin potongan data di sekitar.

Semua kompiler yang saya tahu akan mengganti yang sederhana std::copydengan yang memcpytepat, atau bahkan lebih baik, membuat salinan vektor sehingga akan lebih cepat dari a memcpy.

Dalam kasus apa pun: profil dan cari tahu sendiri. Kompiler yang berbeda akan melakukan hal yang berbeda, dan sangat mungkin itu tidak akan melakukan persis apa yang Anda minta.

Lihat presentasi ini tentang optimisasi kompiler (pdf).

Inilah yang dilakukan GCC untuk std::copytipe POD sederhana .

#include <algorithm>

struct foo
{
  int x, y;    
};

void bar(foo* a, foo* b, size_t n)
{
  std::copy(a, a + n, b);
}

Inilah pembongkaran (dengan hanya -Ooptimasi), menunjukkan panggilan ke memmove:

bar(foo*, foo*, unsigned long):
    salq    $3, %rdx
    sarq    $3, %rdx
    testq   %rdx, %rdx
    je  .L5
    subq    $8, %rsp
    movq    %rsi, %rax
    salq    $3, %rdx
    movq    %rdi, %rsi
    movq    %rax, %rdi
    call    memmove
    addq    $8, %rsp
.L5:
    rep
    ret

Jika Anda mengubah fungsi tanda tangan ke

void bar(foo* __restrict a, foo* __restrict b, size_t n)

kemudian memmovemenjadi memcpyuntuk sedikit peningkatan kinerja. Perhatikan bahwa memcpyitu sendiri akan sangat vektor.

Selalu gunakan std::copykarena memcpyterbatas hanya pada struktur POD gaya C, dan kompiler kemungkinan akan mengganti panggilan std::copydengan memcpyjika target sebenarnya adalah POD.

Plus, std::copydapat digunakan dengan banyak jenis iterator, bukan hanya pointer. std::copylebih fleksibel tanpa kehilangan kinerja dan merupakan pemenang yang jelas.

Secara teori, memcpymungkin memiliki keunggulan kinerja yang sedikit , tidak terlihat , sangat kecil , hanya karena tidak memiliki persyaratan yang sama std::copy. Dari halaman manual dari memcpy:

Untuk menghindari overflow, ukuran array yang ditunjuk oleh parameter tujuan dan sumber, harus setidaknya num byte, dan tidak boleh tumpang tindih (untuk tumpang tindih blok memori, memmove adalah pendekatan yang lebih aman).

Dengan kata lain, memcpybisa mengabaikan kemungkinan data yang tumpang tindih. (Melewati array yang tumpang tindih memcpyadalah perilaku yang tidak terdefinisi.) Jadi memcpytidak perlu memeriksa kondisi ini secara eksplisit, sedangkan std::copydapat digunakan selama OutputIteratorparameter tidak dalam kisaran sumber. Perhatikan ini tidak sama dengan mengatakan bahwa jangkauan sumber dan jangkauan tujuan tidak dapat tumpang tindih.

Jadi karena std::copymemiliki persyaratan yang agak berbeda, secara teori seharusnya sedikit (dengan penekanan ekstrem pada sedikit ) lebih lambat, karena mungkin akan memeriksa tumpang tindih array-C, atau mendelegasikan penyalinan array-C ke memmove, yang perlu melakukan memeriksa. Namun dalam praktiknya, Anda (dan sebagian besar profiler) mungkin bahkan tidak akan mendeteksi perbedaan apa pun.

Tentu saja, jika Anda tidak bekerja dengan POD , Anda tidak dapat menggunakannya memcpy.

Aturan saya sederhana. Jika Anda menggunakan C ++ lebih suka perpustakaan C ++ dan bukan C :)

Hanya tambahan kecil: Perbedaan kecepatan antara memcpy()dan std::copy()dapat sedikit bervariasi tergantung pada apakah optimasi diaktifkan atau dinonaktifkan. Dengan g ++ 6.2.0 dan tanpa optimasi memcpy()jelas menang:

Benchmark             Time           CPU Iterations
---------------------------------------------------
bm_memcpy            17 ns         17 ns   40867738
bm_stdcopy           62 ns         62 ns   11176219
bm_stdcopy_n         72 ns         72 ns    9481749

Ketika optimisasi diaktifkan ( -O3), semuanya terlihat hampir sama lagi:

Benchmark             Time           CPU Iterations
---------------------------------------------------
bm_memcpy             3 ns          3 ns  274527617
bm_stdcopy            3 ns          3 ns  272663990
bm_stdcopy_n          3 ns          3 ns  274732792

Semakin besar array, semakin sedikit efek yang didapatnya, tetapi bahkan pada N=1000 memcpy() sekitar dua kali lebih cepat ketika optimasi tidak diaktifkan.

Kode sumber (memerlukan Google Benchmark):

#include <string.h>
#include <algorithm>
#include <vector>
#include <benchmark/benchmark.h>

constexpr int N = 10;

void bm_memcpy(benchmark::State& state)
{
  std::vector<int> a(N);
  std::vector<int> r(N);

  while (state.KeepRunning())
  {
    memcpy(r.data(), a.data(), N * sizeof(int));
  }
}

void bm_stdcopy(benchmark::State& state)
{
  std::vector<int> a(N);
  std::vector<int> r(N);

  while (state.KeepRunning())
  {
    std::copy(a.begin(), a.end(), r.begin());
  }
}

void bm_stdcopy_n(benchmark::State& state)
{
  std::vector<int> a(N);
  std::vector<int> r(N);

  while (state.KeepRunning())
  {
    std::copy_n(a.begin(), N, r.begin());
  }
}

BENCHMARK(bm_memcpy);
BENCHMARK(bm_stdcopy);
BENCHMARK(bm_stdcopy_n);

BENCHMARK_MAIN()

/* EOF */

Jika Anda benar-benar membutuhkan kinerja penyalinan maksimum (yang mungkin tidak Anda), gunakan keduanya .

Ada banyak yang dapat dilakukan untuk mengoptimalkan penyalinan memori - bahkan lebih jika Anda bersedia menggunakan beberapa utas / inti untuk itu. Lihat, misalnya:

Apa yang hilang / kurang optimal dalam implementasi memcpy ini?

baik pertanyaan dan beberapa jawaban telah menyarankan implementasi atau tautan ke implementasi.

Profiling menunjukkan pernyataan itu: std::copy()selalu secepat memcpy()atau lebih cepat salah.

Sistem saya:

HP-Compaq-dx7500-Microtower 3.13.0-24-generic # 47-Ubuntu SMP Jumat 2 Mei 23:30:00 UTC 2014 x86_64 x86_64 x86_64 GNU / Linux.

gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2

Kode (bahasa: c ++):

    const uint32_t arr_size = (1080 * 720 * 3); //HD image in rgb24
    const uint32_t iterations = 100000;
    uint8_t arr1[arr_size];
    uint8_t arr2[arr_size];
    std::vector<uint8_t> v;

    main(){
        {
            DPROFILE;
            memcpy(arr1, arr2, sizeof(arr1));
            printf("memcpy()\n");
        }

        v.reserve(sizeof(arr1));
        {
            DPROFILE;
            std::copy(arr1, arr1 + sizeof(arr1), v.begin());
            printf("std::copy()\n");
        }

        {
            time_t t = time(NULL);
            for(uint32_t i = 0; i < iterations; ++i)
                memcpy(arr1, arr2, sizeof(arr1));
            printf("memcpy()    elapsed %d s\n", time(NULL) - t);
        }

        {
            time_t t = time(NULL);
            for(uint32_t i = 0; i < iterations; ++i)
                std::copy(arr1, arr1 + sizeof(arr1), v.begin());
            printf("std::copy() elapsed %d s\n", time(NULL) - t);
        }
    }

g ++ -O0 -o test_stdcopy test_stdcopy.cpp

memcpy () profil: utama: 21: sekarang: 1422969084: 04859 terlewati: 2650 us
std :: salin () profil: utama: 27: sekarang: 1422969084: 04862 berlalu: 2745 us
memcpy () elapsed 44 s std :: copy ( ) berlalu 45 s

g ++ -O3 -o test_stdcopy test_stdcopy.cpp

memcpy () profil: utama: 21: sekarang: 1422969601: 04939 berlalu: 2385 us
std :: salin () profil: utama: 28: sekarang: 1422969601: 04941 berlalu: 2690 us
memcpy () elaped 27 s std :: copy ( ) berlalu 43 s

Red Alert menunjukkan bahwa kode tersebut menggunakan memcpy dari array ke array dan std :: copy dari array ke vektor. Itu bisa menjadi alasan untuk memcpy lebih cepat.

Karena ada

v.reserve (sizeof (arr1));

tidak akan ada perbedaan dalam salinan ke vektor atau array.

Kode diperbaiki untuk menggunakan array untuk kedua kasus. memcpy masih lebih cepat:

{
    time_t t = time(NULL);
    for(uint32_t i = 0; i < iterations; ++i)
        memcpy(arr1, arr2, sizeof(arr1));
    printf("memcpy()    elapsed %ld s\n", time(NULL) - t);
}

{
    time_t t = time(NULL);
    for(uint32_t i = 0; i < iterations; ++i)
        std::copy(arr1, arr1 + sizeof(arr1), arr2);
    printf("std::copy() elapsed %ld s\n", time(NULL) - t);
}

memcpy()    elapsed 44 s
std::copy() elapsed 48 s