Versi singkat: Mengembalikan objek besar — ​​seperti vektor / array — dalam banyak bahasa pemrograman merupakan hal yang umum. Apakah gaya ini sekarang dapat diterima di C ++ 0x jika kelas memiliki konstruktor bergerak, atau apakah pemrogram C ++ menganggapnya aneh / jelek / kekejian?

Versi panjang: Di C ++ 0x apakah ini masih dianggap bentuk yang buruk?

std::vector<std::string> BuildLargeVector();
...
std::vector<std::string> v = BuildLargeVector();

Versi tradisionalnya akan terlihat seperti ini:

void BuildLargeVector(std::vector<std::string>& result);
...
std::vector<std::string> v;
BuildLargeVector(v);

Dalam versi yang lebih baru, nilai yang dikembalikan dari BuildLargeVectoradalah nilai r, jadi v akan dibangun menggunakan konstruktor pemindahan std::vector, dengan asumsi (N) RVO tidak terjadi.

Bahkan sebelum C ++ 0x bentuk pertama sering kali "efisien" karena (N) RVO. Namun, (N) RVO adalah kebijaksanaan kompilator. Sekarang kita memiliki referensi rvalue, dijamin tidak ada deep copy yang akan dilakukan.

Sunting : Pertanyaan sebenarnya bukan tentang pengoptimalan. Kedua bentuk yang ditampilkan memiliki kinerja yang hampir identik dalam program dunia nyata. Padahal, di masa lalu, bentuk pertama bisa saja memiliki urutan yang lebih buruk kinerja. Sebagai hasilnya, formulir pertama adalah bau kode utama dalam pemrograman C ++ untuk waktu yang lama. Tidak lagi, kuharap?

Dave Abrahams memiliki analisis yang cukup komprehensif tentang kecepatan operan / pengembalian nilai .

Jawaban singkatnya, jika Anda perlu mengembalikan nilai maka kembalikan nilai. Jangan gunakan referensi keluaran karena kompilator tetap melakukannya. Tentu saja ada peringatan, jadi Anda harus membaca artikel itu.

Setidaknya IMO, biasanya ide yang buruk, tetapi bukan untuk alasan efisiensi. Itu ide yang buruk karena fungsi yang dimaksud biasanya harus ditulis sebagai algoritme umum yang menghasilkan keluarannya melalui iterator. Hampir semua kode yang menerima atau mengembalikan kontainer alih-alih beroperasi pada iterator harus dianggap mencurigakan.

Jangan salah paham: ada kalanya masuk akal untuk membagikan objek seperti koleksi (mis., String) tetapi untuk contoh yang dikutip, saya akan mempertimbangkan untuk meneruskan atau mengembalikan vektor sebagai ide yang buruk.

Intinya adalah:

Copy Elision dan RVO dapat menghindari "salinan menakutkan" (compiler tidak diperlukan untuk mengimplementasikan pengoptimalan ini, dan dalam beberapa situasi itu tidak dapat diterapkan)

Referensi C ++ 0x RValue memungkinkan implementasi string / vektor yang menjamin hal itu.

Jika Anda bisa meninggalkan compiler / implementasi STL yang lebih lama, kembalikan vektor dengan bebas (dan pastikan objek Anda juga mendukungnya). Jika basis kode Anda perlu mendukung kompiler "lebih rendah", tetap gunakan gaya lama.

Sayangnya, itu berpengaruh besar pada antarmuka Anda. Jika C ++ 0x bukan merupakan opsi, dan Anda memerlukan jaminan, Anda dapat menggunakan objek yang dihitung referensi atau salin-saat-tulis dalam beberapa skenario. Mereka memiliki kelemahan dengan multithreading.

(Saya berharap hanya satu jawaban dalam C ++ yang sederhana dan lugas dan tanpa syarat).

Memang, sejak C ++ 11, biaya menyalin yang std::vectorhilang dalam banyak kasus.

Namun, perlu diingat bahwa biaya untuk membangun vektor baru (kemudian menghancurkannya ) masih ada, dan menggunakan parameter keluaran alih-alih mengembalikan nilai masih berguna saat Anda ingin menggunakan kembali kapasitas vektor. Ini didokumentasikan sebagai pengecualian dalam F.20 dari Pedoman Inti C ++.

Mari bandingkan:

std::vector<int> BuildLargeVector1(size_t vecSize) {
    return std::vector<int>(vecSize, 1);
}

dengan:

void BuildLargeVector2(/*out*/ std::vector<int>& v, size_t vecSize) {
    v.assign(vecSize, 1);
}

Sekarang, misalkan kita perlu memanggil metode ini numIterkali dalam loop yang ketat, dan melakukan beberapa tindakan. Misalnya, mari menghitung jumlah semua elemen.

Menggunakan BuildLargeVector1, Anda akan melakukan:

size_t sum1 = 0;
for (int i = 0; i < numIter; ++i) {
    std::vector<int> v = BuildLargeVector1(vecSize);
    sum1 = std::accumulate(v.begin(), v.end(), sum1);
}

Menggunakan BuildLargeVector2, Anda akan melakukan:

size_t sum2 = 0;
std::vector<int> v;
for (int i = 0; i < numIter; ++i) {
    BuildLargeVector2(/*out*/ v, vecSize);
    sum2 = std::accumulate(v.begin(), v.end(), sum2);
}

Dalam contoh pertama, ada banyak alokasi dinamis / deallocations yang tidak perlu terjadi, yang dicegah pada contoh kedua dengan menggunakan parameter keluaran dengan cara lama, menggunakan kembali memori yang telah dialokasikan. Layak atau tidaknya pengoptimalan ini bergantung pada biaya relatif alokasi / deallocation dibandingkan dengan biaya komputasi / mutasi nilai.

Tolok ukur

Mari bermain-main dengan nilai vecSizedan numIter. Kami akan menjaga vecSize * numIter konstan sehingga "dalam teori", itu akan memakan waktu yang sama (= ada jumlah tugas dan penambahan yang sama, dengan nilai yang sama persis), dan perbedaan waktu hanya dapat berasal dari biaya alokasi, deallocations, dan penggunaan cache yang lebih baik.

Lebih khusus lagi, mari gunakan vecSize * numIter = 2 ^ 31 = 2147483648, karena saya memiliki 16GB RAM dan nomor ini memastikan bahwa tidak lebih dari 8GB dialokasikan (sizeof (int) = 4), memastikan bahwa saya tidak menukar ke disk ( semua program lain ditutup, saya memiliki ~ 15GB tersedia saat menjalankan tes).

Ini kodenya:

#include <chrono>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

class Timer {
    using clock = std::chrono::steady_clock;
    using seconds = std::chrono::duration<double>;
    clock::time_point t_;

public:
    void tic() { t_ = clock::now(); }
    double toc() const { return seconds(clock::now() - t_).count(); }
};

std::vector<int> BuildLargeVector1(size_t vecSize) {
    return std::vector<int>(vecSize, 1);
}

void BuildLargeVector2(/*out*/ std::vector<int>& v, size_t vecSize) {
    v.assign(vecSize, 1);
}

int main() {
    Timer t;

    size_t vecSize = size_t(1) << 31;
    size_t numIter = 1;

    std::cout << std::setw(10) << "vecSize" << ", "
              << std::setw(10) << "numIter" << ", "
              << std::setw(10) << "time1" << ", "
              << std::setw(10) << "time2" << ", "
              << std::setw(10) << "sum1" << ", "
              << std::setw(10) << "sum2" << "\n";

    while (vecSize > 0) {

        t.tic();
        size_t sum1 = 0;
        {
            for (int i = 0; i < numIter; ++i) {
                std::vector<int> v = BuildLargeVector1(vecSize);
                sum1 = std::accumulate(v.begin(), v.end(), sum1);
            }
        }
        double time1 = t.toc();

        t.tic();
        size_t sum2 = 0;
        {
            std::vector<int> v;
            for (int i = 0; i < numIter; ++i) {
                BuildLargeVector2(/*out*/ v, vecSize);
                sum2 = std::accumulate(v.begin(), v.end(), sum2);
            }
        } // deallocate v
        double time2 = t.toc();

        std::cout << std::setw(10) << vecSize << ", "
                  << std::setw(10) << numIter << ", "
                  << std::setw(10) << std::fixed << time1 << ", "
                  << std::setw(10) << std::fixed << time2 << ", "
                  << std::setw(10) << sum1 << ", "
                  << std::setw(10) << sum2 << "\n";

        vecSize /= 2;
        numIter *= 2;
    }

    return 0;
}

Dan inilah hasilnya:

$ g++ -std=c++11 -O3 main.cpp && ./a.out
   vecSize,    numIter,      time1,      time2,       sum1,       sum2
2147483648,          1,   2.360384,   2.356355, 2147483648, 2147483648
1073741824,          2,   2.365807,   1.732609, 2147483648, 2147483648
 536870912,          4,   2.373231,   1.420104, 2147483648, 2147483648
 268435456,          8,   2.383480,   1.261789, 2147483648, 2147483648
 134217728,         16,   2.395904,   1.179340, 2147483648, 2147483648
  67108864,         32,   2.408513,   1.131662, 2147483648, 2147483648
  33554432,         64,   2.416114,   1.097719, 2147483648, 2147483648
  16777216,        128,   2.431061,   1.060238, 2147483648, 2147483648
   8388608,        256,   2.448200,   0.998743, 2147483648, 2147483648
   4194304,        512,   0.884540,   0.875196, 2147483648, 2147483648
   2097152,       1024,   0.712911,   0.716124, 2147483648, 2147483648
   1048576,       2048,   0.552157,   0.603028, 2147483648, 2147483648
    524288,       4096,   0.549749,   0.602881, 2147483648, 2147483648
    262144,       8192,   0.547767,   0.604248, 2147483648, 2147483648
    131072,      16384,   0.537548,   0.603802, 2147483648, 2147483648
     65536,      32768,   0.524037,   0.600768, 2147483648, 2147483648
     32768,      65536,   0.526727,   0.598521, 2147483648, 2147483648
     16384,     131072,   0.515227,   0.599254, 2147483648, 2147483648
      8192,     262144,   0.540541,   0.600642, 2147483648, 2147483648
      4096,     524288,   0.495638,   0.603396, 2147483648, 2147483648
      2048,    1048576,   0.512905,   0.609594, 2147483648, 2147483648
      1024,    2097152,   0.548257,   0.622393, 2147483648, 2147483648
       512,    4194304,   0.616906,   0.647442, 2147483648, 2147483648
       256,    8388608,   0.571628,   0.629563, 2147483648, 2147483648
       128,   16777216,   0.846666,   0.657051, 2147483648, 2147483648
        64,   33554432,   0.853286,   0.724897, 2147483648, 2147483648
        32,   67108864,   1.232520,   0.851337, 2147483648, 2147483648
        16,  134217728,   1.982755,   1.079628, 2147483648, 2147483648
         8,  268435456,   3.483588,   1.673199, 2147483648, 2147483648
         4,  536870912,   5.724022,   2.150334, 2147483648, 2147483648
         2, 1073741824,  10.285453,   3.583777, 2147483648, 2147483648
         1, 2147483648,  20.552860,   6.214054, 2147483648, 2147483648

(Intel i7-7700K @ 4.20GHz; 16GB DDR4 2400Mhz; Kubuntu 18.04)

Notasi: mem (v) = v.size () * sizeof (int) = v.size () * 4 di platform saya.

Tidak mengherankan, jika numIter = 1(yaitu, mem (v) = 8GB), waktunya sangat identik. Memang, dalam kedua kasus kami hanya mengalokasikan satu kali vektor besar 8GB dalam memori. Ini juga membuktikan bahwa tidak ada salinan yang terjadi saat menggunakan BuildLargeVector1 (): Saya tidak memiliki cukup RAM untuk menyalin!

Ketika numIter = 2, menggunakan kembali kapasitas vektor daripada mengalokasikan kembali vektor kedua adalah 1,37x lebih cepat.

Ketika numIter = 256, menggunakan kembali kapasitas vektor (alih-alih mengalokasikan / membatalkan alokasi vektor berulang kali 256 kali ...) adalah 2,45x lebih cepat :)

Kita dapat melihat bahwa time1 cukup banyak konstan dari numIter = 1ke numIter = 256, yang berarti bahwa mengalokasikan satu vektor besar 8GB sama mahal dengan mengalokasikan 256 vektor 32MB. Namun, mengalokasikan satu vektor besar 8GB jelas lebih mahal daripada mengalokasikan satu vektor 32MB, jadi menggunakan kembali kapasitas vektor memberikan peningkatan kinerja.

From numIter = 512(mem (v) = 16MB) to numIter = 8M(mem (v) = 1kB) adalah sweet spot: kedua metode sama cepatnya, dan lebih cepat dari semua kombinasi numIter dan vecSize lainnya. Ini mungkin ada hubungannya dengan fakta bahwa ukuran cache L3 dari prosesor saya adalah 8MB, sehingga vektor cukup cocok sepenuhnya dalam cache. Saya tidak benar-benar menjelaskan mengapa lompatan tiba-tiba time1adalah untuk mem (v) = 16MB, tampaknya lebih logis terjadi setelahnya, ketika mem (v) = 8MB. Perhatikan bahwa yang mengejutkan, di sweet spot ini, tidak menggunakan kembali kapasitas ternyata sedikit lebih cepat! Saya tidak benar-benar menjelaskan ini.

Ketika numIter > 8Msegala sesuatunya mulai menjadi buruk. Kedua metode menjadi lebih lambat tetapi mengembalikan vektor berdasarkan nilai menjadi lebih lambat. Dalam kasus terburuk, dengan vektor yang hanya berisi satu tunggal int, menggunakan kembali kapasitas alih-alih menampilkan nilai adalah 3,3x lebih cepat. Diduga, hal ini dikarenakan biaya tetap malloc () yang mulai mendominasi.

Perhatikan bagaimana kurva untuk time2 lebih halus daripada kurva untuk time1: tidak hanya menggunakan kembali kapasitas vektor umumnya lebih cepat, tetapi mungkin yang lebih penting, ini lebih dapat diprediksi .

Perhatikan juga bahwa di sweet spot, kami dapat melakukan 2 miliar penambahan bilangan bulat 64bit dalam ~ 0,5 detik, yang cukup optimal pada prosesor 64bit 4.2Ghz. Kami dapat melakukan lebih baik dengan memparalelkan komputasi untuk menggunakan semua 8 inti (pengujian di atas hanya menggunakan satu inti dalam satu waktu, yang telah saya verifikasi dengan menjalankan ulang pengujian sambil memantau penggunaan CPU). Kinerja terbaik dicapai ketika mem (v) = 16kB, yang merupakan urutan besarnya cache L1 (cache data L1 untuk i7-7700K adalah 4x32kB).

Tentu saja, perbedaan menjadi semakin tidak relevan jika semakin banyak perhitungan yang harus Anda lakukan pada data. Berikut hasil jika kita ganti sum = std::accumulate(v.begin(), v.end(), sum);dengan for (int k : v) sum += std::sqrt(2.0*k);:

Kesimpulan

1. Menggunakan parameter keluaran alih-alih mengembalikan berdasarkan nilai dapat memberikan peningkatan kinerja dengan menggunakan kembali kapasitas.
2. Pada komputer desktop modern, tampaknya ini hanya berlaku untuk vektor besar (> 16MB) dan vektor kecil (<1kB).
3. Hindari mengalokasikan jutaan / miliar vektor kecil (<1kB). Jika memungkinkan, gunakan kembali kapasitas, atau lebih baik lagi, rancang arsitektur Anda secara berbeda.

Hasil mungkin berbeda di platform lain. Seperti biasa, jika kinerja itu penting, tulislah tolok ukur untuk kasus penggunaan spesifik Anda.

Saya masih berpikir ini adalah praktik yang buruk tetapi perlu dicatat bahwa tim saya menggunakan MSVC 2008 dan GCC 4.1, jadi kami tidak menggunakan kompiler terbaru.

Sebelumnya banyak hotspot yang ditampilkan di vtune dengan MSVC 2008 turun ke penyalinan string. Kami memiliki kode seperti ini:

String Something::id() const
{
    return valid() ? m_id: "";
}

... perhatikan bahwa kami menggunakan tipe String kami sendiri (ini diperlukan karena kami menyediakan kit pengembangan perangkat lunak di mana penulis plugin dapat menggunakan kompiler yang berbeda dan karenanya berbeda, implementasi yang tidak kompatibel dari std :: string / std :: wstring).

Saya membuat perubahan sederhana dalam menanggapi sesi pembuatan profil pengambilan sampel grafik panggilan yang menunjukkan String :: String (const String &) akan menghabiskan banyak waktu. Metode seperti pada contoh di atas adalah kontributor terbesar (sebenarnya sesi pembuatan profil menunjukkan alokasi memori dan deallocation menjadi salah satu hotspot terbesar, dengan konstruktor salinan String menjadi kontributor utama untuk alokasi).

Perubahan yang saya buat sederhana:

static String null_string;
const String& Something::id() const
{
    return valid() ? m_id: null_string;
}

Namun ini membuat dunia berbeda! Hotspot menghilang dalam sesi profiler berikutnya, dan selain itu kami melakukan banyak pengujian unit secara menyeluruh untuk melacak kinerja aplikasi kami. Semua jenis waktu uji kinerja turun secara signifikan setelah perubahan sederhana ini.

Kesimpulan: kami tidak menggunakan compiler terbaru absolut, tetapi kami tampaknya masih tidak dapat bergantung pada compiler yang mengoptimalkan penyalinan untuk dikembalikan dengan nilai secara andal (setidaknya tidak dalam semua kasus). Itu mungkin tidak terjadi bagi mereka yang menggunakan kompiler yang lebih baru seperti MSVC 2010. Saya menantikan kapan kita dapat menggunakan C ++ 0x dan cukup menggunakan referensi rvalue dan tidak perlu khawatir bahwa kita pesimis dengan kode kita dengan mengembalikan kompleks kelas berdasarkan nilai.

[Sunting] Seperti yang ditunjukkan Nate, RVO berlaku untuk mengembalikan temporer yang dibuat di dalam suatu fungsi. Dalam kasus saya, tidak ada sementara seperti itu (kecuali untuk cabang yang tidak valid di mana kami membuat string kosong) dan dengan demikian RVO tidak akan berlaku.

Hanya untuk sedikit nitpick: tidak umum dalam banyak bahasa pemrograman untuk mengembalikan array dari fungsi. Dalam kebanyakan dari mereka, referensi ke array dikembalikan. Dalam C ++, analogi terdekat akan kembaliboost::shared_array

Jika kinerja adalah masalah nyata, Anda harus menyadari bahwa semantik pemindahan tidak selalu lebih cepat daripada menyalin. Misalnya jika Anda memiliki string yang menggunakan pengoptimalan string kecil maka untuk string kecil, konstruktor pemindahan harus melakukan jumlah pekerjaan yang sama persis sebagai konstruktor salinan biasa.