Apakah ada dokumentasi yang membandingkan / membedakan implementasi perpustakaan standar C ++? [Tutup]

16

(Ini bukan pemrograman game sendiri, tapi saya yakin jika saya menanyakan ini pada SO, saya akan diberitahu untuk tidak mengoptimalkan secara prematur, meskipun sejarah memberitahu kita bahwa setiap game besar akhirnya mengkhawatirkan hal-hal ini.)

Apakah ada dokumen di mana saja yang merangkum perbedaan dalam kinerja, dan khususnya penggunaan memori, antara implementasi perpustakaan C ++ standar yang berbeda? Detail dari beberapa implementasi dilindungi oleh NDA, tetapi perbandingan antara bahkan STLport vs libstdc ++ vs libc ++ vs MSVC / Dinkumware (vs EASTL?) Sepertinya sangat bermanfaat.

Secara khusus saya mencari jawaban untuk pertanyaan seperti:

  • Berapa besar memori yang terkait dengan wadah standar?
  • Wadah apa, jika ada, yang dilakukan alokasi dinamis hanya dengan diumumkan?
  • Apakah std :: string melakukan copy-on-write? Optimasi string pendek? Tali?
  • Apakah std :: deque menggunakan buffer cincin atau itu omong kosong?

sumber
Saya mendapat kesan bahwa dequeselalu diimplementasikan dalam STL dengan vektor.
Tetrad
@Tetrad: Sampai beberapa minggu yang lalu saya juga, tetapi kemudian saya membacanya sering diimplementasikan oleh struktur seperti tali - dan sepertinya itulah yang ada di STLport.
STL memiliki draft kerja terbuka , yang dapat digunakan untuk menemukan informasi mengenai berbagai struktur data (baik sekuensial dan asosiatif), algoritma dan kelas pembantu yang diimplementasikan. Namun, tampaknya menjadi masalah bahwa overhead memori adalah implementasi spesifik, bukan spesifikasi yang ditentukan.
Thomas Russell
3
@Duck: Pengembangan game adalah satu-satunya tempat yang saya tahu yang secara teratur menggunakan fitur C ++ tingkat tinggi namun perlu melacak alokasi memori dengan cermat karena berjalan pada sistem memori-tanpa-memori-virtual rendah. Setiap jawaban tunggal pada SO adalah "jangan mengoptimalkan secara prematur, STL baik-baik saja, gunakan!" - 50% dari jawaban di sini sejauh ini adalah - namun tes Maik jelas menunjukkan kekhawatiran utama untuk game yang ingin menggunakan std :: map, dan kebingungan Tetrad dan menambang tentang implementasi std :: deque yang umum juga.
2
@ Jo Wreschnig Saya tidak ingin memilih untuk menutup karena saya tertarik dengan hasilnya. : p
Bebek Komunis

Jawaban:

6

Jika Anda tidak menemukan bagan perbandingan seperti itu, alternatifnya adalah menyuntikkan pengalokasi sendiri ke kelas STL yang dimaksud dan menambahkan beberapa pencatatan.

Implementasi yang saya uji (VC 8.0) tidak menggunakan alokasi memori hanya dengan mendeklarasikan string / vektor / deque, tetapi untuk itu daftar dan peta. String memiliki optimasi string pendek, karena menambahkan 3 karakter tidak memicu alokasi. Output ditambahkan di bawah kode.

// basic allocator implementation used from here
// http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c4079

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <map>

template <class T> class my_allocator;

// specialize for void:
template <> 
class my_allocator<void> 
{
public:
    typedef void*       pointer;
    typedef const void* const_pointer;
    // reference to void members are impossible.
    typedef void value_type;
    template <class U> 
    struct rebind 
    { 
        typedef my_allocator<U> other; 
    };
};

#define LOG_ALLOC_SIZE(call, size)      std::cout << "  " << call << "  " << std::setw(2) << size << " byte" << std::endl

template <class T> 
class my_allocator 
{
public:
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;
    typedef T*        pointer;
    typedef const T*  const_pointer;
    typedef T&        reference;
    typedef const T&  const_reference;
    typedef T         value_type;
    template <class U> 
    struct rebind 
    { 
        typedef my_allocator<U> other; 
    };

    my_allocator() throw() : alloc() {}
    my_allocator(const my_allocator&b) throw() : alloc(b.alloc) {}

    template <class U> my_allocator(const my_allocator<U>&b) throw() : alloc(b.alloc) {}
    ~my_allocator() throw() {}

    pointer       address(reference x) const                    { return alloc.address(x); }
    const_pointer address(const_reference x) const              { return alloc.address(x); }

    pointer allocate(size_type s, 
               my_allocator<void>::const_pointer hint = 0)      { LOG_ALLOC_SIZE("my_allocator::allocate  ", s * sizeof(T)); return alloc.allocate(s, hint); }
    void deallocate(pointer p, size_type n)                     { LOG_ALLOC_SIZE("my_allocator::deallocate", n * sizeof(T)); alloc.deallocate(p, n); }

    size_type max_size() const throw()                          { return alloc.max_size(); }

    void construct(pointer p, const T& val)                     { alloc.construct(p, val); }
    void destroy(pointer p)                                     { alloc.destroy(p); }

    std::allocator<T> alloc;
};

int main(int argc, char *argv[])
{

    {
        typedef std::basic_string<char, std::char_traits<char>, my_allocator<char> > my_string;

        std::cout << "===============================================" << std::endl;
        std::cout << "my_string ctor start" << std::endl;
        my_string test;
        std::cout << "my_string ctor end" << std::endl;
        std::cout << "my_string add 3 chars" << std::endl;
        test = "abc";
        std::cout << "my_string add a huge number of chars chars" << std::endl;
        test += "d df uodfug ondusgp idugnösndögs ifdögsdoiug ösodifugnösdiuödofu odsugöodiu niu od unoudö n nodsu nosfdi un abc";
        std::cout << "my_string copy" << std::endl;
        my_string copy = test;
        std::cout << "my_string copy on write test" << std::endl;
        copy[3] = 'X';
        std::cout << "my_string dtors start" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "vector ctor start" << std::endl;
        std::vector<int, my_allocator<int> > v;
        std::cout << "vector ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            v.push_back(i);
        }
        std::cout << "vector dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "deque ctor start" << std::endl;
        std::deque<int, my_allocator<int> > d;
        std::cout << "deque ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "deque insert start" << std::endl;
            d.push_back(i);
            std::cout << "deque insert end" << std::endl;
        }
        std::cout << "deque dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "list ctor start" << std::endl;
        std::list<int, my_allocator<int> > l;
        std::cout << "list ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "list insert start" << std::endl;
            l.push_back(i);
            std::cout << "list insert end" << std::endl;
        }
        std::cout << "list dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "map ctor start" << std::endl;
        std::map<int, float, std::less<int>, my_allocator<std::pair<const int, float> > > m;
        std::cout << "map ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "map insert start" << std::endl;
            std::pair<int, float> a(i, (float)i);
            m.insert(a);
            std::cout << "map insert end" << std::endl;
        }
        std::cout << "map dtor starts" << std::endl;
    }

    return 0;
}

Sejauh ini VC8 dan STLPort 5.2 diuji, berikut ini perbandingannya (termasuk dalam tes: string, vektor, deque, daftar, peta)

                    Allocation on declare   Overhead List Node      Overhead Map Node

VC8                 map, list               8 Byte                  16 Byte
STLPort 5.2 (VC8)   deque                   8 Byte                  16 Byte
Paulhodge's EASTL   (none)                  8 Byte                  16 Byte

String keluaran VC8 / vektor / deque / daftar / peta:

===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
my_string add a huge number of chars chars
  my_allocator::allocate    128 byte
my_string copy
  my_allocator::allocate    128 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  128 byte
  my_allocator::deallocate  128 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    12 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate  12 byte
  my_allocator::allocate    24 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  24 byte

===============================================
deque ctor start
deque ctor end
deque insert start
  my_allocator::allocate    32 byte
  my_allocator::allocate    16 byte
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
  my_allocator::allocate    16 byte
deque insert end
deque dtor starts
  my_allocator::deallocate  16 byte
  my_allocator::deallocate  16 byte
  my_allocator::deallocate  32 byte

===============================================
list ctor start
  my_allocator::allocate    12 byte
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
  my_allocator::allocate    24 byte
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte

STLPort 5.2. output dikompilasi dengan VC8

===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
my_string add a huge number of chars chars
  my_allocator::allocate    115 byte
my_string copy
  my_allocator::allocate    115 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  115 byte
  my_allocator::deallocate  115 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::deallocate   0 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    32 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  32 byte

===============================================
deque ctor start
  my_allocator::allocate    32 byte
  my_allocator::allocate    128 byte
deque ctor end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque dtor starts
  my_allocator::deallocate  128 byte
  my_allocator::deallocate  32 byte

===============================================
list ctor start
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte

Hasil EASTL , tidak ada deque yang tersedia

===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
  my_allocator::allocate     9 byte
my_string add a huge number of chars chars
  my_allocator::allocate    115 byte
  my_allocator::deallocate   9 byte
my_string copy
  my_allocator::allocate    115 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  115 byte
  my_allocator::deallocate  115 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    32 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  32 byte

===============================================
list ctor start
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
Maik Semder
sumber
Ini berguna untuk mendapatkan detail alokasi yang mendasarinya, tetapi sayangnya tidak memberi tahu kami apa pun tentang kinerja cache yang diharapkan.
@Joe benar, sulit untuk menjawab semua pertanyaan Anda dalam satu jawaban. Saya tidak yakin apa yang Anda maksud dengan "overhead" dan lebih dari itu, dibandingkan dengan apa? Saya pikir dengan overhead yang Anda maksud adalah konsumsi memori.
Maik Semder
Yang saya maksud dengan "overhead" adalah ukuran yang lebih besar dari contoh kosong dari struktur dan semua iterator yang terkait, dan bagaimana yang lebih rumit menangani alokasi - mis. Apakah std :: list secara internal mengalokasikan lebih dari satu node pada suatu waktu, atau apakah saya membayar biaya alokasi dasar untuk setiap node, dll?
1
Pertanyaannya tidak terlalu banyak "Tolong lakukan perbandingan ini" sebagai "di mana ada sumber daya untuk perbandingan ini" - Saya tidak berpikir SO adalah tempat yang baik untuk "mempertahankan" itu. Mungkin Anda harus mulai membuangnya di situs Google atau wiki atau sesuatu.
1
@Joe baik sekarang di sini: p Saya tidak begitu tertarik untuk memindahkannya ke situs lain, saya hanya tertarik dengan hasilnya.
Maik Semder
8

std::stringtidak melakukan copy on write. CoW dulu merupakan pengoptimalan, tetapi begitu beberapa utas masuk ke dalam gambar, ini melampaui pesimis - ia dapat memperlambat kode dengan faktor besar. Sangat buruk bahwa Standar C ++ 0x secara aktif melarangnya sebagai strategi implementasi. Bukan hanya itu, tetapi permisif std::stringdengan mengeluarkan iterator yang bisa berubah dan referensi karakter berarti bahwa "menulis" untuk std::stringmemerlukan hampir setiap operasi.

Optimasi string pendek adalah sekitar 6 karakter, saya percaya, atau sesuatu di wilayah itu. Tali tidak diizinkan - std::stringharus menyimpan memori yang berdekatan untuk c_str()fungsi tersebut. Secara teknis, Anda bisa mempertahankan string yang berdekatan dan tali di kelas yang sama, tetapi tidak ada yang pernah melakukannya. Selain itu, dari apa yang saya ketahui tentang tali, membuat mereka aman untuk dimanipulasi akan sangat lambat - mungkin sama buruk atau lebih buruk dari Kontrak Karya.

Tidak ada wadah yang melakukan alokasi memori dengan dinyatakan dalam STL modern. Wadah berbasis node seperti daftar dan peta yang digunakan untuk melakukannya tetapi sekarang mereka memiliki optimasi akhir tertanam dan tidak membutuhkannya. Adalah umum untuk melakukan optimasi yang disebut "swaptimization" di mana Anda bertukar dengan wadah kosong. Mempertimbangkan:

std::vector<std::string> MahFunction();
int main() {
    std::vector<std::string> MahVariable;
    MahFunction().swap(MahVariable);
}

Tentu saja, dalam C ++ 0x ini berlebihan, tetapi dalam C ++ 03 maka ketika ini biasa digunakan, jika MahVariable mengalokasikan memori pada deklarasi maka itu mengurangi efektivitasnya. Saya tahu fakta bahwa ini digunakan untuk realokasi kontainer yang lebih cepat seperti vectorpada MSVC9 STL yang menghilangkan kebutuhan untuk menyalin elemen.

dequemenggunakan sesuatu yang disebut sebagai daftar tertaut yang belum dibuka. Ini pada dasarnya daftar array, biasanya ukuran-in-node tetap. Dengan demikian, untuk sebagian besar penggunaan, ia mempertahankan manfaat dari kedua struktur data - akses yang berdampingan dan penghapusan O (1) yang diamortisasi dan mampu menambahkan ke depan dan belakang dan pembatalan iterator yang lebih baik daripada vector. dequetidak pernah dapat diimplementasikan oleh vektor karena kompleksitas algoritmiknya dan jaminan pembatalan iterator.

Berapa banyak overhead memori yang terkait? Sejujurnya, itu adalah pertanyaan yang tidak perlu ditanyakan. Wadah STL dirancang agar efisien, dan jika Anda mereplikasi fungsinya, Anda akan berakhir dengan sesuatu yang berkinerja lebih buruk atau berada di tempat yang sama lagi. Dengan mengetahui struktur data yang mendasarinya, Anda dapat mengetahui overhead memori yang mereka gunakan, berikan atau terima, dan itu hanya akan lebih dari itu untuk alasan yang bagus, seperti optimasi string kecil.

DeadMG
sumber
"Sangat buruk bahwa Standar C ++ 0x secara aktif melarangnya sebagai strategi implementasi." Dan mereka melarangnya karena implementasi sebelumnya menggunakannya, atau mencoba menggunakannya. Anda tampaknya hidup di dunia di mana setiap orang menggunakan STL terbaru yang diimplementasikan secara optimal setiap saat. Jawaban ini sama sekali tidak membantu.
Saya juga ingin tahu apa sifat std :: deque yang menurut Anda mencegah penyimpanan mendasar yang bersebelahan - iterator hanya valid setelah pemindahan pada awal / akhir, bukan di tengah atau setelah sisipan, yang dapat dengan mudah dilakukan dengan vektor. Dan menggunakan buffer bundar tampaknya memenuhi semua jaminan algoritmik - O diamortisasi (1) menyisipkan dan menghapus di ujungnya, O (n) hapus di tengah.
3
@ Jo: Saya pikir bahwa Kontrak Karya telah dicatat sebagai hal yang buruk sejak akhir tahun 90an. Ada implementasi string yang menggunakannya - terutama CString - tetapi itu tidak berarti bahwa sudah std::stringsaatnya. Anda tidak harus menggunakan implementasi STL terbaru dan terhebat untuk itu. msdn.microsoft.com/en-us/library/22a9t119.aspx mengatakan "Jika sebuah elemen dimasukkan di depan, semua referensi tetap valid". Tidak yakin bagaimana Anda bermaksud menerapkannya dengan buffer bundar, karena Anda perlu mengubah ukuran ketika sudah penuh.
DeadMG
Saya tentu saja tidak akan membela SAP sebagai teknik implementasi, tetapi saya juga tidak naif tentang seberapa sering perangkat lunak terus diimplementasikan menggunakan teknik yang buruk lama setelah mereka diidentifikasi sebagai miskin. Sebagai contoh, tes Maik di atas mengungkapkan stdlib modern yang tidak mengalokasikan pada deklarasi. Terima kasih atas petunjuk tentang validitas referensi deque. (Untuk nitpick, vektor dapat memenuhi semua jaminan tentang pembatalan iterator dan kompleksitas algoritmik; persyaratan itu juga tidak.) Jika ada, saya melihat ini sebagai kebutuhan lebih lanjut untuk dokumen seperti yang ditanyakan oleh pertanyaan saya.
2

Pertanyaannya bukanlah "Tolong lakukan perbandingan ini" seperti "di mana ada sumber daya untuk perbandingan ini"

Jika itu benar-benar pertanyaan Anda (yang pastinya bukan apa yang Anda katakan dalam teks pertanyaan aktual Anda, yang berakhir dalam 4 pertanyaan, tidak ada yang menanyakan di mana Anda mungkin menemukan sumber daya), maka jawabannya hanyalah:

Tidak ada.

Mayoritas pemrogram C ++ tidak perlu terlalu peduli dengan overhead dari struktur pustaka standar, kinerja cache dari mereka (yang sangat tergantung pada kompiler), atau hal semacam itu. Belum lagi, Anda biasanya tidak bisa memilih implementasi perpustakaan standar Anda; Anda menggunakan apa yang datang dengan kompiler Anda. Jadi, bahkan jika itu melakukan beberapa hal yang tidak menyenangkan, pilihan untuk alternatif terbatas.

Tentu saja ada programmer yang peduli tentang hal semacam ini. Tapi mereka semua bersumpah menggunakan perpustakaan standar sejak lama.

Jadi, Anda memiliki satu kelompok programmer yang tidak peduli. Dan sekelompok programmer lain yang akan peduli jika mereka menggunakannya, tetapi karena mereka tidak menggunakannya, mereka tidak peduli. Karena tidak ada yang peduli tentang hal itu, tidak ada informasi nyata tentang hal semacam ini. Ada tambalan informal informasi di sana-sini (C ++ Efektif memiliki bagian tentang std :: string implementasi dan perbedaan besar di antara mereka), tetapi tidak ada yang komprehensif. Dan tentu saja tidak ada yang diperbarui.

Nicol Bolas
sumber
Jawaban spekulatif. +1 untuk mungkin benar, -1 tanpa cara untuk membuktikannya.
deceleratedcaviar
Saya telah melihat banyak perbandingan yang sangat bagus dan terperinci di masa lalu, tetapi semuanya sudah usang. Apa pun sebelum pengenalan langkah ini cukup tidak relevan saat ini.
Peter - Unban Robert Harvey