Czy jest jakaś dokumentacja porównująca / kontrastująca implementacje biblioteki standardowej C ++? [Zamknięte]

(Nie jest to samo w sobie programowanie gier, ale jestem pewien, że jeśli zapytam o to SO, powiedzą mi, żebym nie przedwcześnie optymalizował, chociaż historia mówi nam, że każda duża gra kończy się martwiąc o te rzeczy.)

Czy jest gdzieś dokument, który podsumowuje różnice w wydajności, a zwłaszcza w użyciu pamięci, między różnymi implementacjami biblioteki standardowej C ++? Szczegóły niektórych implementacji są chronione przez NDA, ale porównanie nawet STLport vs. libstdc ++ vs. libc ++ vs. MSVC / Dinkumware (vs. EASTL?) Wydaje się niezwykle przydatne.

W szczególności szukam odpowiedzi na pytania takie jak:

• Ile narzutu pamięci wiąże się ze standardowymi kontenerami?
• Jakie kontenery, jeśli istnieją, dokonują alokacji dynamicznych jedynie poprzez deklarację?
• Czy std :: string wykonuje kopiowanie przy zapisie? Optymalizacja krótkiego ciągu? Liny
• Czy std :: deque używa bufora pierścieniowego, czy to bzdura?

W przypadku, gdy nie znajdziesz takiej tabeli porównawczej, alternatywą jest wstrzyknięcie własnego alokatora do danych klas STL i dodanie logowania.

Testowana przeze mnie implementacja (VC 8.0) nie korzysta z alokacji pamięci, tylko deklarując ciąg / wektor / deque, ale robi to na liście i mapowaniu. Ciąg ma optymalizację krótkiego ciągu, ponieważ dodanie 3 znaków nie uruchomiło przydziału. Dane wyjściowe są dodawane poniżej kodu.

// 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;
}

Do tej pory testowane VC8 i STLPort 5.2, oto porównanie (zawarte w teście: ciąg, wektor, deque, lista, mapa)

                    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

Łańcuch wyjściowy VC8 / wektor / deque / list / map:

===============================================
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. wyjście skompilowane z 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

Wyniki EASTL , brak dostępnych danych

===============================================
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

std::stringnie kopiuje przy zapisie. CoW była kiedyś optymalizacją, ale jak tylko wiele wątków wejdzie na obraz, jest to poza pesymizacją - może spowolnić kod z powodu ogromnych czynników. Szkoda, że ​​C ++ 0x Standard aktywnie zakazuje go jako strategii implementacji. Nie tylko to, ale permisywność std::stringeliminowania zmiennych iteratorów i odwołań do znaków oznacza, że ​​„pisz” std::stringoznacza prawie każdą operację.

Wydaje mi się, że optymalizacja krótkich ciągów znaków to około 6 znaków lub coś w tym regionie. Liny nie są dozwolone - std::stringmusi przechowywać ciągłą pamięć dla c_str()funkcji. Technicznie rzecz biorąc, możesz utrzymywać zarówno ciągły sznurek, jak i linę w tej samej klasie, ale nikt tego nigdy nie zrobił. Co więcej, z tego, co wiem o linach, uczynienie ich bezpiecznymi do manipulowania nicią byłoby niezwykle powolne - może tak złe lub gorsze niż CoW.

Żaden kontener nie dokonuje alokacji pamięci, ponieważ został zadeklarowany w nowoczesnych STL. Kontenery oparte na węzłach, takie jak lista i mapa, służyły do ​​tego, ale teraz mają wbudowaną optymalizację końca i nie potrzebują jej. Często wykonuje się optymalizację zwaną „swaptimization”, w której zamieniasz pusty pojemnik. Rozważać:

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

Oczywiście w C ++ 0x jest to nadmiarowe, ale w C ++ 03 wtedy, gdy było to powszechnie używane, jeśli MahVariable przydziela pamięć na deklarację, zmniejsza to efektywność. Wiem na pewno, że zostało to wykorzystane do szybszych realokacji kontenerów, jak vectorw MSVC9 STL, co wyeliminowało potrzebę kopiowania elementów.

dequekorzysta z czegoś, co określa się jako rozwiniętą listę połączoną Zasadniczo jest to lista tablic, zwykle w węźle o stałej wielkości. Jako taki, do większości zastosowań, zachowuje zalety obu struktur danych - ciągły dostęp i amortyzowane usuwanie O (1) oraz możliwość dodawania zarówno z przodu, jak iz tyłu oraz lepsze unieważnienie iteratora niż vector. dequenigdy nie może zostać zaimplementowany przez wektor ze względu na złożoność algorytmu i gwarancje unieważnienia iteratora.

Ile narzutu pamięci jest związane? Cóż, szczerze mówiąc, to trochę bezwartościowe pytanie. Kontenery STL zostały zaprojektowane tak, aby były wydajne, a jeśli powielasz ich funkcjonalność, albo uzyskasz coś gorszego, albo w tym samym miejscu. Znając ich podstawowe struktury danych, możesz poznać narzut pamięci, którego używają, dają lub zabierają, i będzie to więcej niż tylko z dobrego powodu, takiego jak optymalizacja małych ciągów.

Pytanie to nie tyle „Proszę zrobić to porównanie”, ile „gdzie jest zasób dla tego porównania”

Jeśli to naprawdę twoje pytanie (które jest z całą pewnością nie jest tym, co powiedziałeś w tekście pytania, które zakończyło się 4 pytaniami, z których żadne nie zadawało pytania, gdzie możesz znaleźć zasób), odpowiedź brzmi po prostu:

Nie ma jednego

Większość programistów C ++ nie musi przejmować się zbytnio standardowymi strukturami bibliotek, ich wydajnością w pamięci podręcznej (co jest wysoce zależna od kompilatora), czy czymś podobnym. Nie wspominając o tym, że zazwyczaj nie można wybrać standardowej implementacji biblioteki; korzystasz z kompilatora. Więc nawet jeśli robi to nieprzyjemne rzeczy, opcje alternatyw są ograniczone.

Są oczywiście programiści, którzy dbają o tego rodzaju rzeczy. Ale wszyscy dawno przysięgali, że korzystają ze standardowej biblioteki.

Więc masz jedną grupę programistów, których po prostu nie obchodzi. I kolejna grupa programistów, którzy by się przejmowali, gdyby go używali, ale ponieważ go nie używają, nie obchodzi ich to. Ponieważ nikt się tym nie przejmuje, nie ma prawdziwych informacji na ten temat. Istnieją nieformalne łaty informacji tu i tam (Efektywne C ++ ma sekcję na temat implementacji std :: string i ogromnych różnic między nimi), ale nic kompleksowego. I na pewno nic nie było na bieżąco.