Existe alguma documentação comparando / contrastando as implementações da biblioteca padrão do C ++? [fechadas]

16

(Isso não é programação de jogos em si, mas tenho certeza de que, se eu pedisse isso no SO, seria instruído a não otimizar prematuramente, embora a história nos diga que todo jogo grande acaba se preocupando com essas coisas.)

Existe um documento em qualquer lugar que resuma as diferenças de desempenho, e particularmente o uso de memória, entre diferentes implementações de bibliotecas padrão do C ++? Os detalhes de algumas implementações são protegidos pelo NDA, mas uma comparação entre mesmo STLport vs. libstdc ++ vs. libc ++ vs. MSVC / Dinkumware (vs. EASTL?) Parece ser imensamente útil.

Em particular, estou procurando respostas para perguntas como:

  • Quanta sobrecarga de memória está associada aos contêineres padrão?
  • Quais contêineres, se houver, fazem alocações dinâmicas apenas por serem declaradas?
  • O std :: string faz a cópia na gravação? Otimização de cadeia curta? Cordas?
  • O std :: deque usa um buffer de anel ou é uma porcaria?

fonte
Fiquei com a impressão de que dequesempre era implementado no STL com um vetor.
Tetrad
@Tetrad: Até algumas semanas atrás, eu também estava, mas depois li que muitas vezes era implementado por uma estrutura semelhante a uma corda - e isso parece ser o que está no STLport.
O STL possui um rascunho de trabalho aberto , que pode ser usado para encontrar informações sobre as várias estruturas de dados (seqüenciais e associativas), algoritmos e classes auxiliares implementadas. No entanto, parece ser que a sobrecarga de memória seja específica da implementação, em vez da especificação definida.
Thomas Russell
3
@ Duck: O desenvolvimento de jogos é o único lugar que sei que utiliza regularmente recursos de C ++ de alto nível, mas precisa rastrear meticulosamente as alocações de memória, porque roda em sistemas de memória virtual sem memória baixa. Cada resposta no SO seria "não otimize prematuramente, o STL está bem, use-o!" - 50% das respostas aqui até agora são essas - e, no entanto, o teste de Maik mostra claramente uma grande preocupação para jogos que desejam usar std :: map, e a confusão de Tetrad e a minha sobre implementações comuns de std :: deque da mesma forma.
2
@ Joe Wreschnig Eu realmente não quero votar para fechar porque estou interessado no resultado disso. : p
O pato comunista

Respostas:

6

Caso você não encontre um gráfico de comparação, a alternativa é injetar um próprio alocador nas classes STL em questão e adicionar algum log.

A implementação que testei (VC 8.0) não usa alocação de memória apenas declarando uma string / vetor / deque, mas lista e mapeia. A string possui uma otimização de string curta, pois a adição de 3 caracteres não acionou uma alocação. A saída é adicionada abaixo do código.

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

Até agora testado o VC8 e o STLPort 5.2, aqui está a comparação (incluída no teste: string, vetor, 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

Cadeia de saída VC8 / vetor / 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. saída compilada com 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

Resultados EASTL , sem deque disponível

===============================================
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
fonte
Isso é útil para obter os detalhes das alocações subjacentes, mas infelizmente não nos diz nada sobre a sobrecarga e o desempenho esperado do cache.
@ Joe bem, é difícil responder a todas as suas perguntas em uma resposta. Não sei o que exatamente você quer dizer com "sobrecarga" e, além disso, em comparação com o que? Eu pensei que por sobrecarga você quer dizer o consumo de memória.
Maik Semder
Por "overhead", eu quis dizer mais o tamanho de instâncias vazias das estruturas e todos os seus iteradores associados e como as mais complicadas lidam com a alocação - por exemplo, std :: list aloca internamente internamente mais de um nó por vez, ou eu pagar o custo de alocação base para cada nó, etc?
1
A questão não é tanto "Por favor, faça esta comparação" como "onde está um recurso para essa comparação" - não acho que o SO seja um bom lugar para "mantê-lo". Talvez você deva começar a vomitar em um site ou wiki do Google ou algo assim.
1
@ Joe bem, agora está aqui: p Não estou muito interessado em movê-lo para outro site, estava apenas interessado nos resultados.
Maik Semder
8

std::stringnão copia na gravação. O CoW costumava ser uma otimização, mas assim que vários threads entram em cena, está além de uma pessimização - ele pode retardar o código por fatores maciços. É tão ruim que o C ++ 0x Standard proíbe-o ativamente como uma estratégia de implementação. Não apenas isso, mas a permissividade destd::string distribuir iteradores mutáveis ​​e referências de caracteres significa que "escrever" para std::stringenvolve quase todas as operações.

A otimização de cadeia curta tem cerca de 6 caracteres, acredito, ou algo nessa região. Cordas não são permitidas-std::string devem armazenar memória contígua para a c_str()função. Tecnicamente, você pode manter uma corda contígua e uma corda na mesma classe, mas ninguém nunca fez isso. Além disso, pelo que sei das cordas, torná-las seguras para manipular os fios seria incrivelmente lento - talvez tão ruim ou pior que o CoW.

Nenhum contêiner faz alocação de memória sendo declarado em STLs modernas. Os contêineres baseados em nós, como lista e mapa, costumavam fazer isso, mas agora eles têm uma otimização final incorporada e não precisam disso. É comum executar uma otimização chamada "swaptimization" em que você troca com um contêiner vazio. Considerar:

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

Obviamente, no C ++ 0x isso é redundante, mas no C ++ 03, quando isso era comumente usado, se o MahVariable alocasse memória na declaração, isso reduziria a eficácia. Sei que isso foi usado para realocações mais rápidas de contêineres comovector no MSVC9 STL, o que eliminou a necessidade de copiar os elementos.

dequeusa algo conhecido como uma lista vinculada desenrolada. É basicamente uma lista de matrizes, geralmente em nó de tamanho fixo. Como tal, para a maioria dos usos, ele mantém os benefícios das estruturas de dados - acesso contínuo e remoção O (1) amortizada, além de poder adicionar à frente e à trás e uma melhor invalidação do iterador do quevector . dequenunca pode ser implementado por vetor devido à sua complexidade algorítmica e garantias de invalidação do iterador.

Quanta sobrecarga de memória está associada? Bem, honestamente, essa é uma pergunta inútil. Os contêineres da STL são projetados para serem eficientes e, se você replicar a funcionalidade deles, você terminará com algo com desempenho pior ou no mesmo local novamente. Ao conhecer suas estruturas de dados subjacentes, você pode conhecer a sobrecarga de memória que eles usam, fornecem ou recebem, e será apenas mais do que isso por um bom motivo, como otimização de pequenas cadeias de caracteres.

DeadMG
fonte
"É tão ruim que o C ++ 0x Standard proíba-o ativamente como uma estratégia de implementação". E eles o banem porque implementações anteriores o usaram ou tentaram usá-lo. Aparentemente, você vive em um mundo em que todos usam o mais recente STL idealmente implementado o tempo todo. Esta resposta não é de todo útil.
Também estou curioso para saber quais propriedades do std :: deque você acha que impedem um armazenamento subjacente contíguo - os iteradores são válidos somente após remoções no início / fim, não no meio nem após inserções, o que pode ser feito facilmente com um vetor. E o uso de um buffer circular parece atender a todas as garantias algorítmicas - O (1) amortizado insere e exclui no final, O (n) exclui no meio.
3
@ Joe: Eu acho que o CoW é uma coisa ruim desde o final dos anos 90. Existem implementações de strings que o usaram - notavelmente CString -, mas isso não significa que isso aconteceu std::stringna época. Você não precisa usar as melhores e mais recentes implementações de STL para isso. msdn.microsoft.com/en-us/library/22a9t119.aspx diz "Se um elemento for inserido na frente, todas as referências permanecerão válidas". Não sabe ao certo como pretende implementá-lo com um buffer circular, pois você precisará redimensionar quando ficar cheio.
31711 DeadMG
gotw.ca/publications/optimizations.htm . Julho 1999.
DeadMG 31/07
Certamente não vou defender o COW como uma técnica de implementação, mas também não sou ingênuo quanto à frequência com que o software continua sendo implementado usando técnicas ruins muito tempo depois de serem identificados como ruins. Por exemplo, o teste de Maik acima revela um stdlib moderno que é alocado na declaração. Obrigado pelo ponteiro sobre a validade de referência de deque. (Para nitpick, um vetor pode atender a todas as garantias sobre a invalidação do iterador e a complexidade algorítmica; esse requisito também não é necessário.)
2

A questão não é tanto "faça esta comparação" como "onde está um recurso para essa comparação"

Se essa é realmente a sua pergunta (que certamente não é o que você disse no texto da pergunta real, que terminou em quatro perguntas, nenhuma das quais perguntava onde você poderia encontrar um recurso), a resposta é simplesmente:

Não existe um.

A maioria dos programadores de C ++ não precisa se preocupar tanto com a sobrecarga das estruturas de bibliotecas padrão, com o desempenho em cache delas (que é altamente dependente do compilador) ou com esse tipo de coisa. Sem mencionar, você geralmente não escolhe sua implementação de biblioteca padrão; você usa o que vem com seu compilador. Portanto, mesmo que faça coisas desagradáveis, as opções para alternativas são limitadas.

É claro que há programadores que se preocupam com esse tipo de coisa. Mas todos juraram usar a biblioteca padrão há muito tempo.

Então você tem um grupo de programadores que simplesmente não se importam. E outro grupo de programadores que se importariam se estivessem usando, mas como não estão usando, não se importam. Como ninguém se importa com isso, não há informações reais sobre esse tipo de coisa. Há patches informais de informações aqui e ali (o C ++ eficaz possui uma seção sobre implementações std :: string e as vastas diferenças entre elas), mas nada abrangente. E certamente nada se manteve atualizado.

Nicol Bolas
fonte
Resposta especulativa. +1 para provavelmente verdadeiro, -1 para não provar.
Deceleratedcaviar
Eu já vi muitas comparações muito boas e detalhadas no passado, mas estão todas desatualizadas. Qualquer coisa antes da introdução da mudança é praticamente irrelevante hoje em dia.
Peter - Unban Robert Harvey