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

16

(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?
c++  performance  memory-efficiency 
Miałem wrażenie, że dequezawsze był implementowany w STL z wektorem.
— Tetrad
@Tetrad: Jeszcze kilka tygodni temu też byłem, ale potem przeczytałem, że często był implementowany przez konstrukcję przypominającą linę - i wydaje się, że tak jest w STLport.
STL ma otwarty szkic roboczy , który można wykorzystać do wyszukiwania informacji dotyczących różnych struktur danych (zarówno sekwencyjnych, jak i asocjacyjnych), algorytmów i klas pomocniczych. Wydaje się jednak, że narzut pamięci zależy od implementacji, a nie od specyfikacji.
— Thomas Russell
3
@Duck: Tworzenie gier to jedyne miejsce, w którym jestem świadomy tego, że regularnie korzysta z wysokiego poziomu funkcji C ++, ale musi dokładnie śledzić przydziały pamięci, ponieważ działa na systemach bez pamięci wirtualnej o niskiej pamięci. Każda odpowiedź na SO byłaby „nie przedwcześnie optymalizuj, STL jest w porządku, użyj go!” - Jak dotąd 50% odpowiedzi tutaj jest - a jednak test Maika wyraźnie pokazuje poważne zaniepokojenie grami, które chcą używać std :: map, oraz zamieszanie Tetrad i moje w związku z powszechnymi implementacjami std :: deque.
2
@Joe Wreschnig Nie chcę głosować za zamknięciem, ponieważ interesuje mnie wynik tego. : p
— Kaczka komunistyczna

Odpowiedzi:

6

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
— Maik Semder
źródło
Jest to przydatne, aby uzyskać szczegółowe informacje na temat przydziałów bazowych, ale niestety nie mówi nam nic o narzutu i oczekiwanej wydajności pamięci podręcznej.
@ Joe, prawda, trudno jest odpowiedzieć na wszystkie pytania w jednej odpowiedzi. Nie jestem pewien, co dokładnie masz na myśli przez „narzut”, a ponadto, w porównaniu do czego? Myślałem, że przez obciążenie rozumiesz zużycie pamięci.
— Maik Semder
Przez „koszty ogólne” rozumiałem bardziej rozmiar pustych instancji struktur i wszystkich powiązanych z nimi iteratorów oraz sposób, w jaki bardziej skomplikowane obsługują alokację - np. Czy std :: list wewnętrznie alokuje więcej niż jeden węzeł naraz, czy też zapłacić podstawowy koszt alokacji dla każdego węzła itp.?
1
Pytanie to nie tyle „Proszę zrobić to porównanie”, ile „gdzie jest zasób tego porównania” - nie sądzę, żeby SO było dobrym miejscem do „utrzymania” go. Być może powinieneś zacząć wyrzucać go na stronę Google, wiki lub coś takiego.
1
@Joe dobrze, teraz jest tutaj: p Nie jestem bardzo zainteresowany przeniesieniem go na inną stronę, po prostu interesowały mnie wyniki.
— Maik Semder
8

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.

— DeadMG
źródło
„Szkoda, że ​​standard C ++ 0x aktywnie banuje go jako strategię implementacyjną”. I zakazują tego, ponieważ poprzednie implementacje używały go lub próbowały go używać. Najwyraźniej żyjesz w świecie, w którym wszyscy cały czas korzystają z najnowszego optymalnie wdrożonego STL. Ta odpowiedź wcale nie jest pomocna.
Zastanawiam się również, jakie właściwości std :: deque uważasz, że zapobiegają ciągłemu przechowywaniu - iteratory są ważne tylko po usunięciu na początku / końcu, a nie w środku ani po wstawieniu, co można łatwo zrobić za pomocą wektora. A użycie okrągłego bufora wydaje się spełniać wszystkie gwarancje algorytmiczne - amortyzowane wstawianie i usuwanie O (1) na końcach, usuwanie O (n) na środku.
3
@Joe: Wydaje mi się, że od końca lat 90. CoW jest uważane za coś złego. Istnieją implementacje łańcuchowe, które tego używały - zwłaszcza CString - ale to nie znaczy, że std::stringtak było. Nie musisz do tego używać najnowszych i najlepszych implementacji STL. msdn.microsoft.com/en-us/library/22a9t119.aspx mówi „Jeśli element zostanie wstawiony z przodu, wszystkie odniesienia pozostaną ważne”. Nie wiesz, jak zamierzasz wdrożyć to z okrągłym buforem, ponieważ będziesz musiał zmienić rozmiar, gdy się zapełni.
— DeadMG,
— DeadMG,
Na pewno nie będę bronić COW jako techniki implementacji, ale nie jestem też naiwny, jak często oprogramowanie jest wdrażane przy użyciu złych technik długo po tym, jak zostaną zidentyfikowane jako słabe. Na przykład powyższy test Maika ujawnia nowoczesny stdlib, który przypisuje przy deklaracji. Dzięki za wskaźnik na temat ważności referencji deque. (Aby nitpick, wektor mógł spełnić wszystkie gwarancje dotyczące unieważnienia iteratora i złożoności algorytmu; wymaganie to nie jest takie.) Jeśli już, uważam to za dodatkową potrzebę dokumentu takiego jak moje pytanie.
2

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.

— Nicol Bolas
źródło
Odpowiedź spekulatywna. +1 za prawdopodobnie prawdę, -1 za brak możliwości udowodnienia.
— spowolniony,
W przeszłości widziałem wiele bardzo dobrych i szczegółowych porównań, ale wszystkie są nieaktualne. Wszystko przed wprowadzeniem ruchu jest obecnie praktycznie nieistotne.
— Peter
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.