Pertanyaan Kinerja mengubah ukuran std :: vector >


Konsepsi umum tampaknya seperti itu std::unique_ptr punya tidak ada waktu di atas kepala dibandingkan dengan benar menggunakan pointer mentah, diberikan optimasi yang cukup.

Tapi bagaimana dengan menggunakan std::unique_ptr dalam struktur data majemuk, khususnya std::vector<std::unique_ptr<T>>? Misalnya, mengubah ukuran data yang mendasari vektor, yang dapat terjadi selama push_back. Untuk mengisolasi kinerja, saya berputar-putar pop_back, shrink_to_fit, emplace_back:

#include <chrono>
#include <vector>
#include <memory>
#include <iostream>

constexpr size_t size = 1000000;
constexpr size_t repeat = 1000;
using my_clock = std::chrono::high_resolution_clock;

template<class T>
auto test(std::vector<T>& v) {
    v.reserve(size);
    for (size_t i = 0; i < size; i++) {
        v.emplace_back(new int());
    }
    auto t0 = my_clock::now();
    for (int i = 0; i < repeat; i++) {
        auto back = std::move(v.back());
        v.pop_back();
        v.shrink_to_fit();
        if (back == nullptr) throw "don't optimize me away";
        v.emplace_back(std::move(back));
    }
    return my_clock::now() - t0;
}

int main() {
    std::vector<std::unique_ptr<int>> v_u;
    std::vector<int*> v_p;

    auto millis_p = std::chrono::duration_cast<std::chrono::milliseconds>(test(v_p));
    auto millis_u = std::chrono::duration_cast<std::chrono::milliseconds>(test(v_u));
    std::cout << "raw pointer: " << millis_p.count() << " ms, unique_ptr: " << millis_u.count() << " ms\n";
    for (auto p : v_p) delete p; // I don't like memory leaks ;-)
}

Menyusun kode dengan -O3 -o -march=native -std=c++14 -g dengan gcc 7.1.0, clang 3.8.0, dan 17.0.4 di Linux pada Intel Xeon E5-2690 v3 @ 2.6 GHz (tidak ada turbo):

raw pointer: 2746 ms, unique_ptr: 5140 ms  (gcc)
raw pointer: 2667 ms, unique_ptr: 5529 ms  (clang)
raw pointer: 1448 ms, unique_ptr: 5374 ms  (intel)

Versi pointer mentah menghabiskan semua waktunya di dioptimalkan memmove (Intel tampaknya memiliki yang jauh lebih baik daripada dentang dan gcc). Itu unique_ptr kode tampaknya pertama menyalin data vektor dari satu blok memori ke yang lain dan menetapkan yang asli dengan nol - semua dalam loop yang tidak dioptimalkan. Dan kemudian melompati blok asli data lagi untuk melihat apakah ada yang hanya nol akan nol dan perlu dihapus. Detail berdarah penuh bisa dilihat godbolt. Pertanyaannya bukan bagaimana kode yang dikompilasi berbeda, itu cukup jelas. Pertanyaannya adalah Mengapa compiler gagal untuk mengoptimalkan apa yang umumnya dianggap sebagai abstraksi no-extra-overhead.

Mencoba memahami bagaimana alasan kompiler tentang penanganan std::unique_ptr, Saya melihat sedikit lebih pada kode yang terisolasi. Contohnya:

void foo(std::unique_ptr<int>& a, std::unique_ptr<int>& b) {
  a.release();
  a = std::move(b);
}

atau yang serupa

a.release();
a.reset(b.release());

tidak ada kompiler x86 tampaknya dapat mengoptimalkan diri tidak masuk akal if (ptr) delete ptr;. Compiler Intel bahkan memberikan kesempatan menghapus 28%. Anehnya, pemeriksaan penghapusan secara konsisten dihilangkan untuk:

auto tmp = b.release();
a.release();
a.reset(tmp);

Bit-bit ini bukan aspek utama dari pertanyaan ini, tetapi semua ini membuat saya merasa bahwa saya kehilangan sesuatu.

Mengapa berbagai kompiler gagal mengoptimalkan realokasi dalam std::vector<std::unique_ptr<int>>? Apakah ada sesuatu dalam standar yang mencegah menghasilkan kode seefisien dengan pointer mentah? Apakah ini masalah dengan implementasi perpustakaan standar? Atau apakah kompiler tidak cukup pintar (belum)?

Apa yang dapat dilakukan untuk menghindari dampak kinerja dibandingkan menggunakan pointer mentah?

Catatan: Asumsikan itu T adalah polimorfik dan mahal untuk bergerak, jadi std::vector<T> bukan pilihan.


32
2017-07-13 19:01


asal


Jawaban:


Klaim itu unique_ptr melakukan serta penunjuk mentah setelah pengoptimalan sebagian besar hanya berlaku untuk operasi dasar pada penunjuk tunggal, seperti pembuatan, dereferencing, penunjukan satu penunjuk dan penghapusan. Operasi-operasi tersebut didefinisikan cukup sederhana sehingga kompilator yang mengoptimasi biasanya dapat membuat transformasi yang diperlukan sehingga kode yang dihasilkan setara (atau hampir sama) dalam kinerja ke versi raw0.

Satu tempat ini berantakan terutama optimisasi berbasis bahasa tingkat tinggi pada wadah berbasis larik seperti std::vector, seperti yang Anda catat dengan tes Anda. Wadah ini biasanya digunakan tingkat sumber optimisasi yang bergantung pada jenis sifat untuk menentukan pada waktu kompilasi jika suatu tipe dapat dengan aman disalin menggunakan salinan byte-bijaksana seperti memcpy, dan delegasi ke metode seperti itu jika demikian, atau sebaliknya jatuh kembali ke loop copy elemen-bijaksana.

Agar aman bisa diterima memcpy sebuah objek harus sepele yang bisa ditagih. Sekarang std::unique_ptr tidak sepele copyable karena memang gagal beberapa Persyaratan seperti hanya memiliki salinan atau pindah konstruktor yang tidak penting atau dihapus. Mekanisme yang tepat tergantung pada perpustakaan standar yang terlibat, tetapi secara umum suatu kualitas std::vector implementasi akan berakhir dengan memanggil bentuk khusus dari sesuatu seperti std::uninitialized_copy untuk jenis-jenis yang dapat ditiru yang hanya didelegasikan memmove.

Detail penerapan yang khas cukup disiksa, tetapi untuk libstc++ (digunakan oleh gcc) Anda dapat melihat perbedaan tingkat tinggi di std::uninitialized_copy:

 template<typename _InputIterator, typename _ForwardIterator>
 inline _ForwardIterator
 uninitialized_copy(_InputIterator __first, _InputIterator __last,
                    _ForwardIterator __result)
 {
        ...
   return std::__uninitialized_copy<__is_trivial(_ValueType1)
                                    && __is_trivial(_ValueType2)
                                    && __assignable>::
     __uninit_copy(__first, __last, __result);
 }

Dari sana Anda dapat mengambil kata saya yang banyak std::vector Metode "gerakan" berakhir di sini, dan itu __uninitialized_copy<true>::__uinit_copy(...) akhirnya panggilan memmove selagi <false> versi tidak - atau Anda dapat melacak sendiri kode (tetapi Anda sudah melihat hasilnya dalam tolok ukur Anda).

Pada akhirnya kemudian, Anda berakhir dengan beberapa loop yang melakukan langkah-langkah menyalin yang diperlukan untuk benda-benda non-sepele, seperti memanggil konstruktor bergerak dari objek tujuan, dan kemudian memanggil destructor dari semua objek sumber. Ini adalah loop terpisah dan bahkan kompilator modern akan cukup banyak tidak dapat beralasan tentang sesuatu seperti "OK, di loop pertama saya memindahkan semua objek tujuan sehingga mereka ptr anggota akan nol, sehingga loop kedua adalah no-op ". Akhirnya, untuk menyamakan kecepatan pointer mentah, tidak hanya kompiler perlu dioptimalkan di dua loop ini, mereka akan perlu memiliki transformasi yang mengakui bahwa keseluruhan Hal bisa diganti dengan memcpy atau memmove2.

Jadi satu jawaban untuk pertanyaan Anda adalah bahwa kompiler tidak cukup cerdas untuk melakukan optimasi ini, tetapi itu sebagian besar karena versi "raw" memiliki banyak waktu kompilasi yang membantu untuk melewatkan kebutuhan untuk optimasi ini sepenuhnya.

Loop Fusion

Seperti disebutkan yang ada vector implementasi mengimplementasikan operasi pengubahan ukuran dalam dua loop terpisah (selain pekerjaan non-loop seperti mengalokasikan penyimpanan baru dan membebaskan penyimpanan lama):

  • Menyalin objek sumber ke dalam array tujuan yang baru saja dialokasikan (secara konseptual menggunakan sesuatu seperti penempatan baru memanggil konstruktor bergerak).
  • Menghancurkan objek sumber di wilayah lama.

Secara konseptual Anda bisa membayangkan cara alternatif: melakukan ini semua dalam satu lingkaran, menyalin setiap elemen dan mereka segera menghancurkannya. Ada kemungkinan bahwa kompiler bahkan dapat melihat bahwa dua loop iterate atas set nilai yang sama dan sekering dua loop menjadi satu. [Rupanya], howevever, (https://gcc.gnu.org/ml/gcc/2015-04/msg00291.html) gcc tidak melakukan apapun lingkaran fusi hari ini, dan juga tidak clang atau icc jika kamu percaya tes ini.

Jadi kemudian kita dibiarkan mencoba menempatkan loop bersama secara eksplisit di tingkat sumber.

Sekarang implementasi dua-loop membantu mempertahankan kontrak keamanan pengecualian operasi dengan tidak menghancurkan objek sumber apa pun sampai kita tahu bagian konstruksi dari salinan telah selesai, tetapi juga membantu untuk mengoptimalkan salinan dan penghancuran ketika kita memiliki sepele-copyable dan benda-benda yang dapat dirusak secara trivial. Secara khusus, dengan seleksi berdasarkan sifat sederhana kita dapat mengganti salinan dengan memmove dan lingkaran kehancuran dapat ditelusuri seluruhnya3.

Jadi pendekatan dua-loop membantu ketika optimisasi itu berlaku, tetapi sebenarnya menyakitkan dalam kasus umum objek yang tidak sepele copyable atau destructible. Ini berarti Anda perlu dua melewati objek dan Anda kehilangan kesempatan untuk mengoptimalkan dan menghilangkan kode antara salinan objek dan kehancuran berikutnya. Dalam unique_ptr Jika Anda kehilangan kemampuan untuk kompiler untuk menyebarkan pengetahuan yang sumbernya unique_ptr akan memiliki NULL intern ptr anggota dan karenanya lewati if (ptr) delete ptr periksa seluruhnya4.

Trivially Bergerak

Sekarang orang mungkin bertanya apakah kita bisa menerapkan jenis-kompilasi waktu-kompilasi yang sama ke unique_ptr kasus. Misalnya, orang mungkin melihat sepele yang bisa ditagih persyaratan dan melihat bahwa mereka mungkin terlalu ketat untuk umum pindah operasi di std::vector. Tentu, a unique_ptr jelas tidak sepele copyable karena salinan bit-bijaksana akan meninggalkan kedua sumber dan objek tujuan karena penunjuk yang sama (dan mengakibatkan penghapusan ganda), tetapi tampaknya itu harus sedikit-bijaksana bergerak: jika Anda memindahkan file unique_ptr dari satu area memori ke yang lain, sedemikian rupa sehingga Anda tidak lagi menganggap sumber sebagai objek hidup (dan karenanya tidak akan memanggil destruktornya) itu seharusnya "hanya bekerja", untuk khas  unique_ptr pelaksanaan.

Sayangnya, tidak ada konsep "langkah sepele" yang ada, meskipun Anda dapat mencoba untuk menggulirkannya sendiri. Sepertinya ada sebuah debat terbuka tentang apakah ini UB atau bukan untuk objek yang dapat disalin berdasarkan byte dan tidak bergantung pada konstruktor atau perilaku destruktor mereka dalam skenario perpindahan.

Anda selalu bisa mengimplementasikan konsep Anda sendiri yang mudah dipindahkan, yang akan menjadi seperti itu (A) objek memiliki konstruktor langkah sepele dan (b) ketika digunakan sebagai argumen sumber dari konstruktor bergerak objek yang tersisa dalam keadaan di mana itu destruktor tidak berpengaruh. Perhatikan bahwa definisi seperti itu saat ini sebagian besar tidak berguna, karena "konstruktor langkah sepele" (pada dasarnya menyalin unsur-bijak dan tidak ada yang lain) tidak konsisten dengan modifikasi dari objek sumber. Jadi misalnya, konstruktor langkah sepele tidak dapat mengatur ptr anggota sumber unique_ptr ke nol. Jadi, Anda harus melompat meskipun beberapa lingkaran seperti memperkenalkan konsep a gerakan destruktif operasi yang membuat objek sumber dihancurkan, bukan dalam keadaan yang valid tetapi tidak ditentukan.

Anda dapat menemukan beberapa diskusi yang lebih rinci tentang "sepele ini" utas ini pada grup diskusi usenet ISO C ++. Secara khusus, dalam balasan terkait, masalah vektor yang tepat unique_ptr ditujukan:

Ternyata banyak pointer pintar (unique_ptr dan shared_ptr termasuk)   masuk dalam ketiga kategori tersebut dan dengan menerapkannya Anda bisa   memiliki vektor pointer pintar dengan biaya overhead nol di atas mentah   pointer bahkan dalam membangun debug yang tidak dioptimalkan.

Lihat juga relokasi usul.


0 Meskipun contoh non-vektor di akhir pertanyaan Anda menunjukkan bahwa ini tidak selalu terjadi. Di sini adalah karena mungkin aliasing sebagai zneak menjelaskan jawabannya. Pointer mentah akan menghindari banyak masalah aliasing karena mereka tidak memiliki tipuan itu unique_ptr memiliki (misalnya, Anda meneruskan pointer mentah berdasarkan nilai, daripada struktur dengan penunjuk berdasarkan referensi) dan sering kali dapat menghilangkan if (ptr) delete ptr periksa seluruhnya.

2 Ini sebenarnya lebih sulit dari yang Anda kira, karena memmove, misalnya, memiliki semantik yang agak berbeda dari lingkaran salin objek, ketika sumber dan tujuan tumpang tindih. Tentu saja kode jenis karakter tingkat tinggi yang berfungsi untuk poin mentah tahu (berdasarkan kontrak) bahwa tidak ada tumpang tindih, atau perilaku memmove konsisten bahkan jika ada tumpang tindih, tetapi membuktikan hal yang sama pada beberapa lintasan pengoptimalan acak berikutnya mungkin jauh lebih sulit.

3 Penting untuk dicatat bahwa optimisasi ini lebih atau kurang independen. Sebagai contoh, banyak objek dirusak secara sepele yang pada umumnya tidak dapat ditiru.

4 Meskipun dalam tes saya tidak juga gcc maupun clang mampu menekan cek, bahkan dengan __restrict__ diterapkan, tampaknya karena analisis aliasing tidak cukup kuat, atau mungkin karena std::move strip "membatasi" kualifikasi entah bagaimana.


36
2017-07-13 20:02



Saya tidak memiliki jawaban yang tepat untuk apa yang menggigit Anda di belakang dengan vektor; Sepertinya BeeOnRope mungkin sudah memilikinya untuk Anda.

Untungnya, saya dapat memberi tahu Anda apa yang menggigit Anda di belakang untuk mikro-contoh Anda yang melibatkan cara berbeda untuk me-reset pointer: analisis alias. Secara khusus, kompiler tidak dapat membuktikan (atau tidak mau menyimpulkan) bahwa keduanya unique_ptr referensi tidak tumpang tindih. Mereka memaksa diri untuk memuat ulang unique_ptr nilai jika penulisan ke yang pertama telah memodifikasi yang kedua. baz tidak menderita karena kompiler dapat membuktikan bahwa tidak ada parameter, dalam program yang terbentuk dengan baik, mungkin bisa dengan alias tmp, yang memiliki penyimpanan otomatis fungsi-lokal.

Anda dapat memverifikasi ini dengan menambahkan __restrict__ kata kunci (yang, seperti digarisbawahi ganda menyiratkan, tidak standar C ++) untuk baik unique_ptr parameter referensi. Kata kunci itu memberi tahu kompiler bahwa referensi adalah satu-satunya referensi yang memungkinkan memori itu dapat diakses, dan oleh karena itu tidak ada risiko yang dapat dilakukan oleh hal lain. Ketika Anda melakukannya, semua tiga versi dari fungsi Anda dikompilasi ke kode mesin yang sama dan tidak perlu memeriksa apakah unique_ptrperlu dihapus.


8
2017-07-13 20:55