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

117

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 '.

acm
fonte
5
O bug GCC para a string COW é gcc.gnu.org/bugzilla/show_bug.cgi?id=21334#c45 . Um dos bugs que rastreiam uma nova implementação compilante C ++ 11 de std :: string em libstdc ++ é gcc.gnu.org/bugzilla/show_bug.cgi?id=53221
user7610

Respostas:

120

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.

Dave S
fonte
4
Algumas razões: N2534
MM
8
-1 A lógica não se sustenta. No momento de uma cópia de COW, não há referências ou iteradores que possam ser invalidados, o objetivo principal de fazer a cópia é que tais referências ou iteradores agora estão sendo obtidos, então a cópia é necessária. Mas ainda pode ser que o C ++ 11 não permita implementações COW.
Saúde e hth. - Alf
11
@ Cheersandhth.-Alf: A lógica pode ser vista a seguir se COW fosse permitido: std::string a("something"); char& c1 = a[0]; std::string b(a); char& c2 = a[1]; c1 é uma referência a a. Você então "copia" a. Em seguida, quando você tenta obter a referência pela segunda vez, é necessário fazer uma cópia para obter uma referência não const, pois há duas strings que apontam para o mesmo buffer. Isso teria que invalidar a primeira referência feita e vai contra a seção citada acima.
Dave S
9
@ Cheersandhth.-Alf, de acordo com isso , pelo menos a implementação COW do GCC faz exatamente o que DaveS está dizendo. Portanto, pelo menos esse estilo de COW é proibido pela norma.
Tavian Barnes
4
@Alf: Esta resposta argumenta que non-const operator[](1) deve fazer uma cópia e que (2) é ilegal fazê-lo. De qual desses dois pontos você discorda? Olhando para seu primeiro comentário, parece que uma implementação poderia compartilhar a string, pelo menos sob esse requisito, até o momento em que ela seja acessada, mas os acessos de leitura e gravação precisariam cancelar o compartilhamento. É esse o seu raciocínio?
Ben Voigt
48

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.

Jonathan Wakely
fonte
3
Uma implementação que cancela o compartilhamento na chamada para .data()(e em cada retorno de ponteiro, referência ou iterador) não sofre desse problema. Ie (invariante) um buffer é a qualquer momento não compartilhado, ou então compartilhado sem refs externos. Achei que você pretendia fazer o comentário sobre este exemplo como um relatório informal de bug como um comentário, sinto muito por entendê-lo mal! Mas, como você pode ver, considerando a implementação que descrevo aqui, que funciona bem em C ++ 11 quando os noexceptrequisitos são ignorados, o exemplo não diz nada sobre o formal. Posso fornecer o código se você quiser.
Saúde e hth. - Alf
7
Se você cancelar o compartilhamento em quase todos os acessos à string, perderá todos os benefícios do compartilhamento. Uma implementação COW deve ser prática para uma biblioteca padrão se preocupar em usá-la std::string, e eu sinceramente duvido que você possa demonstrar uma string COW útil e de desempenho que atenda aos requisitos de invalidação do C ++ 11. Portanto, mantenho que as noexceptespecificações que foram adicionadas no último minuto são uma consequência da proibição das strings COW, não o motivo subjacente. N2668 parece perfeitamente claro, por que você continua a negar a evidência clara da intenção do comitê delineada lá?
Jonathan Wakely,
Além disso, lembre-se de que data()é uma função de membro const, portanto, deve ser seguro chamar simultaneamente com outros membros const e, por exemplo, chamar data()simultaneamente com outro thread fazendo uma cópia da string. Então você vai precisar de toda a sobrecarga de um mutex para cada operação de string, mesmo const uns, ou a complexidade de uma estrutura de contagem de referência mutável sem bloqueio e, afinal de contas, você só terá compartilhamento se nunca modificar ou acessar suas strings, tantas, muitas strings terão uma contagem de referência de um. Forneça o código, fique à vontade para ignorar as noexceptgarantias.
Jonathan Wakely,
2
Apenas remendando alguns códigos agora descobri que existem 129 basic_stringfunções-membro, além de funções livres. Custo de abstração: este código de versão zeroth fresco não otimizado é 50 a 100% mais lento com g ++ e MSVC. Ele não oferece segurança de thread (aproveitamento fácil shared_ptr, eu acho) e é apenas o suficiente para dar suporte à classificação de um dicionário para fins de tempo, mas o módulo bugs prova que uma referência contada basic_stringé permitida, exceto para noexceptrequisitos de C ++ . github.com/alfps/In-principle-demo-of-ref-counted-basic_string
Saudações e hth. - Alf
1
Vamos continuar essa discussão no chat .
Jonathan Wakely
20

É, 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.

gbjbaanb
fonte
2
O problema do operador [] não é realmente um problema. A variante const oferece proteção, e a variante não const sempre tem a opção de fazer o CoW naquele momento (ou ser realmente maluco e configurar uma falha de página para acioná-la).
Christopher Smith
+1 vai para os problemas.
Saúde e hth. - Alf
5
é simplesmente bobo que uma classe std :: cow_string não foi incluída, com lock_buffer (), etc. muitas vezes eu sei que threading não é um problema. na maioria das vezes, na verdade.
Erik Aronesty
Gosto da sugestão de uma alternativa, cordas de ig. Gostaria de saber se existem outros tipos de alternativas e implementações disponíveis.
Voltaire
5

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.

Luc Danton
fonte
+1 Explica como C ++ 11 (pelo menos parcialmente) proíbe COW.
Saúde e hth. - Alf
Desculpe, estava cansado. Isso não explica nada mais do que uma chamada de .data () deve acionar a cópia COW se o buffer estiver compartilhado atualmente. Ainda assim, é uma informação útil, então deixo o voto positivo de pé.
Saúde e hth. - Alf
1

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.

Dirk Holsopple
fonte
1
Acho que as strings em C ++ 11 têm garantia de armazenamento contíguo.
mfontanini
4
Antigamente você tinha que fazer as cópias em todas aquelas situações e não era problema ...
David Rodríguez - dribeas 30/08/12
@mfontanini sim, mas não eram anteriormente
Dirk Holsopple
3
Embora o C ++ 11 garanta que as strings sejam contíguas, isso é ortogonal ao banimento das strings COW. A string COW do GCC é contígua, então claramente sua afirmação de que "não é possível fazer uma implementação COW útil" é falsa.
Jonathan Wakely,
1
@supercat, pedir pelo armazenamento de apoio (por exemplo, chamando c_str()) deve ser O (1) e não pode lançar, e não deve introduzir corridas de dados, então é muito difícil atender a esses requisitos se você concatenar preguiçosamente. Na prática, a única opção razoável é sempre armazenar dados contíguos.
Jonathan Wakely
1

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

C ++ 11 §21.4.5 / 4 :

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:

C ++ 11 §C.2.11 [diff.cpp03.strings], sobre §21.3:

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:

C ++ 03 §21.3 / 5, que inclui suporte COW de "primeira chamada":

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.

Saúde e hth. - Alf
fonte
3
" Seu exemplo é um bom exemplo de uma implementação incorreta para C ++ 11. Possivelmente estava correto para C ++ 03." Sim, esse é o ponto do exemplo . Ele mostra uma string COW que era válida em C ++ 03 porque não quebra as regras de invalidação de iterador antigas e não é válida em C ++ 11 porque quebra as novas regras de invalidação de iterador. E também contradiz a afirmação que citei no comentário acima.
Jonathan Wakely
2
Se você tivesse dito compartilhável não compartilhado inicialmente, eu não teria discutido. Dizer que algo é inicialmente compartilhado é apenas confuso. Compartilhado consigo mesmo? Não é isso que a palavra significa. Mas eu repito: sua tentativa de argumentar que as regras de invalidação do iterador C ++ 11 não proíbem alguma string COW hipotética que nunca foi usada na prática (e teria um desempenho inaceitável), quando eles certamente proíbem o tipo de string COW que foi usado na prática, é um tanto acadêmico e sem sentido.
Jonathan Wakely
5
Sua string COW proposta é interessante, mas não tenho certeza de quão útil seria. O objetivo de uma string COW é apenas copiar os dados da string caso as duas strings sejam gravadas. Sua implementação sugerida requer cópia quando ocorre qualquer operação de leitura definida pelo usuário. Mesmo que o compilador saiba que é apenas uma leitura, ele ainda deve copiar. Além disso, copiar uma string Unique resultará em uma cópia de seus dados de string (presumivelmente para um estado compartilhável), o que novamente torna o COW bastante inútil. Portanto, sem as garantias de complexidade, você poderia escrever ... uma string COW realmente ruim .
Nicol Bolas
2
Então, embora você esteja tecnicamente correto que as garantias de complexidade são o que o impede de escrever qualquer formulário de COW, realmente é [basic.string] / 5 que o impede de escrever qualquer forma genuinamente útil de sequência de COW.
Nicol Bolas
4
@JonathanWakely: (1) Sua citação não é a questão. Aqui está a pergunta: “Estou correto que C ++ 11 não admite implementações baseadas em COW de std :: string? Em caso afirmativo, esta restrição está explicitamente declarada em algum lugar do novo padrão (onde)? ” (2) A sua opinião de que um COW std::string, ao desconsiderar os requisitos O (1), seria ineficiente, é a sua opinião. Não sei o que poderia ser a performance, mas acho que essa afirmação é feita mais pela sensação, pelas vibrações que transmite, do que por qualquer relevância para esta resposta.
Saúde e hth. - Alf
0

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
zzz777
fonte