Legalidade da implementação COW std :: string em C ++ 11

Foi meu entendimento que copy-on-write não é uma maneira viável de implementar uma conformidade std::stringem C ++ 11, mas quando surgiu em discussão recentemente, descobri que não era possível apoiar diretamente essa declaração.

Estou correto que C ++ 11 não admite implementações baseadas em COW std::string?

Em caso afirmativo, essa restrição está explicitamente declarada em algum lugar do novo padrão (onde)?

Ou essa restrição está implícita, no sentido de que é o efeito combinado dos novos requisitos sobre o std::stringque impede uma implementação baseada em COW std::string. Neste caso, eu estaria interessado em uma derivação de estilo de capítulo e verso de 'C ++ 11 efetivamente proíbe std::stringimplementações baseadas em COW '.

Não é permitido, porque de acordo com o padrão 21.4.1 p6, a invalidação de iteradores / referências só é permitida para

- como um argumento para qualquer função de biblioteca padrão tendo uma referência a não const basic_string como um argumento.

- Chamar funções-membro não const, exceto operator [], at, front, back, begin, rbegin, end e rend.

Para uma string COW, chamar non-const operator[]exigiria fazer uma cópia (e invalidar as referências), o que não é permitido pelo parágrafo acima. Portanto, não é mais legal ter uma string COW em C ++ 11.

As respostas de Dave S e gbjbaanb estão corretas . (E a de Luc Danton também está correta, embora seja mais um efeito colateral da proibição das strings COW do que a regra original que proíbe isso.)

Mas, para esclarecer alguma confusão, vou adicionar mais algumas exposições. Vários comentários vinculam a um comentário meu no bugzilla GCC que dá o seguinte exemplo:

std::string s("str");
const char* p = s.data();
{
    std::string s2(s);
    (void) s[0];
}
std::cout << *p << '\n';  // p is dangling

O objetivo desse exemplo é demonstrar por que a string de contagem de referência (COW) do GCC não é válida em C ++ 11. O padrão C ++ 11 requer que esse código funcione corretamente. Nada no código permite que o pseja invalidado em C ++ 11.

Usando a std::stringimplementação de contagem de referência antiga do GCC , esse código tem comportamento indefinido, porque p é invalidado, tornando-se um ponteiro pendente. (O que acontece é que, quando s2é construído, ele compartilha os dados s, mas obter uma referência não const via s[0]requer que os dados sejam descompartilhados, o mesmo sacontece com uma "cópia na gravação" porque a referência s[0]poderia potencialmente ser usada para gravar s, então s2vai fora do escopo, destruindo a matriz apontada por p).

O padrão C ++ 03 permite explicitamente esse comportamento em 21.3 [lib.basic.string] p5, onde diz que após uma chamada para data()a primeira chamada para operator[]()pode invalidar ponteiros, referências e iteradores. Portanto, a string COW do GCC era uma implementação válida do C ++ 03.

O padrão C ++ 11 não permite mais esse comportamento, porque nenhuma chamada para operator[]()pode invalidar ponteiros, referências ou iteradores, independentemente de seguirem uma chamada para data().

Portanto, o exemplo acima deve funcionar em C ++ 11, mas não funciona com o tipo de string COW de libstdc ++, portanto, esse tipo de string COW não é permitido em C ++ 11.

É, CoW é um mecanismo aceitável para fazer cordas mais rápidas ... mas ...

torna o código multithreading mais lento (todo aquele bloqueio para verificar se você é o único a escrever mata o desempenho ao usar muitas strings). Esta foi a principal razão pela qual CoW foi morto anos atrás.

Os outros motivos são que o []operador irá retornar os dados da string, sem qualquer proteção para você sobrescrever uma string que outra pessoa espera que não seja alterada. O mesmo se aplica a c_str()e data().

O Google rápido diz que o multithreading é basicamente a razão pela qual foi efetivamente desabilitado (não explicitamente).

A proposta diz:

Proposta

Nossa proposta é tornar todas as operações de acesso a iteradores e elementos executáveis ​​simultaneamente com segurança.

Estamos aumentando a estabilidade das operações mesmo em código sequencial.

Essa alteração desabilita efetivamente as implementações de cópia na gravação.

Seguido por

A maior perda potencial de desempenho devido à mudança das implementações de cópia na gravação é o aumento do consumo de memória para aplicativos com strings de leitura muito grandes. No entanto, acreditamos que para essas aplicações os cabos são uma solução técnica melhor e recomendamos que uma proposta de cabos seja considerada para inclusão na Biblioteca TR2.

As cordas fazem parte do STLPort e SGIs STL.

De 21.4.2 construtores de basic_string e operadores de atribuição [string.cons]

basic_string(const basic_string<charT,traits,Allocator>& str);

[...]

2 Efeitos : Constrói um objeto de classe basic_stringconforme indicado na Tabela 64. [...]

A Tabela 64 documenta de forma útil que, após a construção de um objeto por meio deste (cópia) construtor, this->data()tem como valor:

aponta para o primeiro elemento de uma cópia alocada do array cujo primeiro elemento é apontado por str.data ()

Existem requisitos semelhantes para outros construtores semelhantes.

Uma vez que agora é garantido que as strings são armazenadas de forma contígua e agora você tem permissão para levar um ponteiro para o armazenamento interno de uma string (ou seja, & str [0] funciona como faria para uma matriz), não é possível fazer um COW útil implementação. Você teria que fazer uma cópia para muitas coisas. Mesmo usando apenas operator[]ou begin()em uma string não const, seria necessária uma cópia.

O COW é basic_stringproibido em C ++ 11 e posterior?

A respeito de

” Estou correto que C ++ 11 não admite implementações baseadas em COW std::string?

Sim.

A respeito de

”Em caso afirmativo, esta restrição está explicitamente declarada em algum lugar do novo padrão (onde)?

Quase diretamente, por requisitos de complexidade constante para uma série de operações que exigiriam O ( n ) cópia física dos dados da string em uma implementação COW.

Por exemplo, para as funções de membro

auto operator[](size_type pos) const -> const_reference;
auto operator[](size_type pos) -> reference;

... que em uma implementação de COW, ambos acionariam a cópia dos dados da string para não compartilhar o valor da string, o padrão C ++ 11 requer

” Complexidade: tempo constante.

… Que exclui a cópia de dados e, portanto, COW.

C ++ 03 suportado implementações da vaca por não ter esses requisitos constantes complexidade, e, sob certas condições restritivas, permitindo chamadas para operator[](), at(), begin(), rbegin(), end(), ou rend()para referências invalidar os ponteiros e iterators referentes aos itens corda, ou seja, possivelmente incorrer em uma Cópia de dados COW. Este suporte foi removido no C ++ 11.

O COW também é proibido por meio das regras de invalidação do C ++ 11?

Em outra resposta que no momento da redação foi selecionada como solução, e que foi fortemente votada e, portanto, aparentemente acreditada, afirma-se que

” Para uma string COW, chamar não- const operator[]exigiria fazer uma cópia (e invalidar as referências), o que não é permitido pelo parágrafo [citado] acima [C ++ 11 §21.4.1 / 6]. Portanto, não é mais legal ter uma string COW em C ++ 11.

Essa afirmação é incorreta e enganosa de duas maneiras principais:

• Indica incorretamente que apenas os constacessadores de não itens precisam acionar uma cópia de dados COW.
  Mas também os constacessadores de item precisam acionar a cópia de dados, porque eles permitem que o código do cliente forme referências ou ponteiros que (em C ++ 11) não é permitido invalidar posteriormente por meio das operações que podem acionar a cópia de dados COW.
• Ele assume incorretamente que a cópia de dados COW pode causar invalidação de referência.
  Mas, em uma implementação correta, a cópia de dados COW, não compartilhando o valor da string, é feita em um ponto antes que haja qualquer referência que possa ser invalidada.

Para ver como uma implementação COW correta do C ++ 11 basic_stringfuncionaria, quando os requisitos O (1) que tornam isso inválido são ignorados, pense em uma implementação em que uma string pode alternar entre as políticas de propriedade. Uma instância de string começa com política compartilhável. Com esta política ativa, não pode haver referências de itens externos. A instância pode fazer a transição para a política Exclusiva e deve fazer isso quando uma referência de item é potencialmente criada, como com uma chamada para .c_str()(pelo menos se isso produzir um ponteiro para o buffer interno). No caso geral de várias instâncias compartilhando a propriedade do valor, isso envolve a cópia dos dados da string. Após essa transição para a política Exclusiva, a instância só pode fazer a transição de volta para Compartilhável por uma operação que invalida todas as referências, como atribuição.

Portanto, embora a conclusão dessa resposta, de que as sequências de COW estão descartadas, seja correta, o raciocínio oferecido é incorreto e fortemente enganoso.

Suspeito que a causa desse mal-entendido seja uma nota não normativa no anexo C do C ++ 11:

Alteração : os basic_stringrequisitos não permitem mais sequências de contagem de referência
Justificativa: A invalidação é sutilmente diferente com sequências de contagem de referência. Esta mudança regulariza o comportamento (sic) para esta Norma.
Efeito na característica original: o código C ++ 2003 válido pode ser executado de forma diferente nesta Norma

Aqui, a justificativa explica o principal motivo pelo qual alguém decidiu remover o suporte COW especial do C ++ 03. Este raciocínio, o porquê , não é como o padrão efetivamente desautoriza a implementação de COW. O padrão não permite COW através dos requisitos O (1).

Resumindo, as regras de invalidação do C ++ 11 não excluem uma implementação COW de std::basic_string. Mas eles descartam uma implementação COW irrestrita no estilo C ++ 03, razoavelmente eficiente, como aquela em pelo menos uma das implementações de biblioteca padrão do g ++. O suporte COW especial C ++ 03 permitiu eficiência prática, em particular usando constacessores de item, ao custo de regras sutis e complexas para invalidação:

” Referências, ponteiros e iteradores referentes aos elementos de uma basic_stringsequência podem ser invalidados pelos seguintes usos desse basic_stringobjeto:
- Como um argumento para funções não-membro swap()(21.3.7.8), operator>>()(21.3.7.9) e getline()(21.3. 7,9).
- Como um argumento para basic_string::swap().
- Funções de chamada data()e c_str()membro.
- Chamando não constfunções de membro, exceto operator[](), at(), begin(), rbegin(), end(), e rend().
- subsequente com qualquer uma das utilizações acima, excepto as formas de insert()e erase()que iterators regresso, a primeira chamada para não constfunções membro operator[](), at(), begin(), rbegin(),end(), ou rend().

Essas regras são tão complexas e sutis que duvido que muitos programadores, se houver, possam fornecer um resumo preciso. Eu não pude.

E se os requisitos O (1) forem desconsiderados?

Se os requisitos de tempo constante do C ++ 11 em, por exemplo, operator[]forem desconsiderados, o COW para basic_stringpoderia ser tecnicamente viável, mas difícil de implementar.

As operações que podem acessar o conteúdo de uma string sem incorrer na cópia de dados COW incluem:

• Concatenação via +.
• Saída via <<.
• Usando um basic_stringcomo argumento para funções de biblioteca padrão.

Este último porque a biblioteca padrão pode contar com conhecimentos e construções específicas de implementação.

Além disso, uma implementação pode oferecer várias funções não padronizadas para acessar o conteúdo da string sem acionar a cópia de dados COW.

Um fator complicador principal é que no C ++ 11 o basic_stringacesso ao item deve acionar a cópia dos dados (cancelar o compartilhamento dos dados da string), mas é necessário não lançar , por exemplo, C ++ 11 §21.4.5 / 3 “ Lança: Nada.”. E, portanto, ele não pode usar a alocação dinâmica comum para criar um novo buffer para cópia de dados COW. Uma maneira de contornar isso é usar um heap especial onde a memória pode ser reservada sem ser realmente alocada e, em seguida, reservar a quantidade necessária para cada referência lógica a um valor de string. Reservar e cancelar a reserva em tal heap pode ser tempo constante, O (1), e alocar a quantidade que já foi reservada, pode sernoexcept . A fim de cumprir os requisitos do padrão, com essa abordagem, parece que seria necessário um tal heap especial baseado em reserva por alocador distinto.

^{Notas:
¹ O constacessador de item aciona uma cópia de dados COW porque permite que o código do cliente obtenha uma referência ou ponteiro para os dados, que não é permitido invalidar por uma cópia posterior de dados acionada, por exemplo, pelo constacessador de não item.}

Eu sempre me perguntei sobre vacas imutáveis: uma vez que a vaca é criada, eu só poderia ser mudado através da designação de outra vaca, portanto, ela estará em conformidade com o padrão.

Tive tempo para experimentá-lo hoje para um teste de comparação simples: um mapa de tamanho N digitado por string / vaca com cada nó segurando um conjunto de todas as strings no mapa (temos o número NxN de objetos).

Com strings de aproximadamente 300 bytes e N = 2000, as vacas são um pouco mais rápidas e usam quase menos memória da ordem de magnitude. Veja abaixo, os tamanhos estão em kbs, a corrida b é com vacas.

~/icow$ ./tst 2000
preparation a
run
done a: time-delta=6 mem-delta=1563276
preparation b
run
done a: time-delta=3 mem-delta=186384