(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?
deque
sempre era implementado no STL com um vetor.Respostas:
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.
Até agora testado o VC8 e o STLPort 5.2, aqui está a comparação (incluída no teste: string, vetor, deque, lista, mapa)
Cadeia de saída VC8 / vetor / deque / list / map:
STLPort 5.2. saída compilada com VC8
Resultados EASTL , sem deque disponível
fonte
std::string
nã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" parastd::string
envolve 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 ac_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:
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 como
vector
no MSVC9 STL, o que eliminou a necessidade de copiar os elementos.deque
usa 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
.deque
nunca 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.
fonte
std::string
na é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.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.
fonte