Legalidad de la implementación de COW std:: string en C++ 11

c++11 stdstring

Question

Comprendí que copiar-en-escribir no es una forma viable de implementar una std::string conformes en C ++ 11, pero cuando se discutió recientemente me encontré incapaz de apoyar directamente esa declaración.

¿Tengo razón en que C ++ 11 no admite implementaciones basadas en std::string de std::string ?

Si es así, ¿esta restricción se establece explícitamente en algún lugar del nuevo estándar (dónde)?

O esta restricción está implícita, en el sentido de que es el efecto combinado de los nuevos requisitos en std::string que impide una implementación basada en COW de std::string . En este caso, me interesaría una derivación de estilo de capítulo y verso de ''C ++ 11 prohíbe efectivamente std::string implementaciones de std::string basadas en COW''.

Answer 1

¿Está COW basic_string prohibido en C ++ 11 y posterior?

Respecto a

" ¿Tengo razón en que C ++ 11 no admite implementaciones basadas en COW de std::string ?

Sí.

Respecto a

" De ser así, ¿esta restricción se establece explícitamente en algún lugar del nuevo estándar (dónde)?

Casi directamente, por requisitos de complejidad constante para una serie de operaciones que requerirían O ( n ) copia física de los datos de cadena en una implementación COW.

Por ejemplo, para las funciones miembro

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

... que en una implementación COW ¹puede desencadenar la copia de datos de cadena para des-compartir el valor de cadena, el estándar C ++ 11 requiere

C ++ 11 §21.4.5 / 4 :

" Complejidad: tiempo constante.

... que descarta dicha copia de datos, y por lo tanto, COW.

C ++ 03 admitía implementaciones COW al no tener estos requisitos de complejidad constante y, bajo ciertas condiciones restrictivas, permitir llamadas al operator[]() , at() , begin() , rbegin() , end() o rend() para invalidar referencias, punteros e iteradores que se refieren a los elementos de cadena, es decir, posiblemente incurrir en una copia de datos COW. Este soporte se eliminó en C ++ 11.

¿La VACA también está prohibida a través de las reglas de invalidación de C ++ 11?

En otra respuesta que en el momento de redactarse se selecciona como solución, y que está fuertemente votada y, por lo tanto, aparentemente se cree, se afirma que

" Para una cadena COW, llamar al operator[] const operator[] requeriría hacer una copia (e invalidar referencias), lo cual no está permitido por el párrafo [citado] arriba [C ++ 11 §21.4.1 / 6]. Por lo tanto, ya no es legal tener una cadena COW en C ++ 11.

Esa afirmación es incorrecta y engañosa de dos maneras principales:

• Indica incorrectamente que solo los const elementos no const deben desencadenar una copia COW de datos.
  Pero también los elementos de acceso de objetos necesitan activar la copia de datos, ya que permiten que el código del cliente forme referencias o punteros que (en C ++ 11) no pueden invalidar posteriormente mediante las operaciones que pueden activar la copia de datos COW.
• Asume incorrectamente que la copia de datos COW puede causar la invalidación de la referencia.
  Pero en una implementación correcta, la copia de datos COW, sin compartir el valor de la cadena, se realiza en un punto antes de que haya referencias que puedan invalidarse.

Para ver cómo funcionaría una implementación correcta de C ++ 11 COW de basic_string , cuando se ignoran los requisitos O (1) que hacen que esto no sea válido, piense en una implementación donde una cadena puede cambiar entre las políticas de propiedad. Una instancia de cadena comienza con la política Sharable. Con esta política activa, no puede haber referencias de elementos externos. La instancia puede realizar la transición a la política Única, y debe hacerlo cuando se crea potencialmente una referencia de elemento, como con una llamada a .c_str() (al menos si eso produce un puntero al búfer interno). En el caso general de que varias instancias compartan la propiedad del valor, esto implica copiar los datos de cadena. Después de esa transición a la política única, la instancia solo puede volver a la transición a Sharable mediante una operación que invalida todas las referencias, como la asignación.

Por lo tanto, aunque la conclusión de la respuesta, que las cadenas COW están descartadas, es correcta, el razonamiento ofrecido es incorrecto y muy engañoso.

Sospecho que la causa de este malentendido es una nota no normativa en el anexo C de C ++ 11:

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

Cambio : los requisitos de basic_string ya no permiten cadenas contadas por referencia
Justificación: la invalidación es sutilmente diferente con cadenas contadas por referencia. Este cambio regulariza behavor (sic) para este estándar internacional.
Efecto en la característica original: el código válido de C ++ 2003 puede ejecutarse de manera diferente en esta norma internacional

Aquí, la explicación explica la principal razón por la cual se decidió eliminar el soporte especial de CW 03 de CW. Este razonamiento, el por qué , no es cómo el estándar efectivamente desautoriza la implementación de COW. El estándar no permite VACA a través de los requisitos O (1).

En resumen, las reglas de invalidación de C ++ 11 no excluyen una implementación COW de std::basic_string . Pero descartan una implementación COW sin restricciones de C ++ 03 de estilo razonablemente eficiente, como la que se realiza al menos en una de las implementaciones de bibliotecas estándar de g ++. El soporte especial de C ++ 03 COW permitió la eficacia práctica, en particular al usar accesorios de elemento const , a costa de reglas sutiles y complejas para la invalidación:

C ++ 03 §21.3 / 5 que incluye soporte de VAC de "primera llamada":

"Las referencias, punteros e iteradores que hacen referencia a los elementos de una secuencia basic_string pueden ser invalidados por los siguientes usos de ese objeto basic_string :
- Como argumento para las funciones no miembro swap() (21.3.7.8), operator>>() (21.3.7.9) y getline() (21.3.7.9).
- Como argumento para basic_string::swap() .
- Funciones de miembro de calling data() y c_str() .
- Llamar a las funciones miembro const , excepto operator[]() , at() , begin() , rbegin() , end() y rend() .
- Después de cualquiera de los usos anteriores excepto las formas de insert() y erase() que devuelven iteradores, la primera llamada a las funciones miembro no const operator[]() , at() , begin() , rbegin() , end() o rend() .

Estas reglas son tan complejas y sutiles que dudo que muchos programadores, si alguno, pudieran dar un resumen preciso. No podría.

¿Qué pasa si los requisitos de O (1) no se tienen en cuenta?

Si no se tienen en cuenta los requisitos de tiempo constante C ++ 11 en, por ejemplo, operator[] , entonces COW para basic_string podría ser técnicamente factible, pero difícil de implementar.

Las operaciones que podrían acceder al contenido de una cadena sin incurrir en copia de datos COW incluyen:

• Concatenación a través de + .
• Salida a través de << .
• Usar un basic_string como argumento para las funciones de biblioteca estándar.

Esto último porque se permite que la biblioteca estándar dependa de construcciones y conocimientos específicos de la implementación.

Además, una implementación podría ofrecer diversas funciones no estándar para acceder al contenido de cadena sin activar la copia de datos COW.

Un factor de complicación principal es que en C ++ 11 el elemento basic_string de basic_string acceso debe desencadenar la copia de datos (sin compartir los datos de cadena) pero no arrojar , por ejemplo, C ++ 11 §21.4.5 / 3 " Tira: nada". . Por lo tanto, no puede usar la asignación dinámica ordinaria para crear un nuevo búfer para la copia de datos COW. Una forma de evitar esto es usar un montón especial donde la memoria se pueda reservar sin estar realmente asignada, y luego reservar la cantidad requerida para cada referencia lógica a un valor de cadena. Reservar y no reservar en un montón de este tipo puede ser un tiempo constante, O (1) y asignar la cantidad que ya se ha reservado, puede ser sin noexcept . Con el fin de cumplir con los requisitos de la norma, con este enfoque parece que debería haber un tal montón especial basado en reservas por asignador distinto.

^{Notas:
¹ El elemento de acceso const desencadena una copia COW de datos porque permite que el código del cliente obtenga una referencia o puntero a los datos, que no se puede invalidar mediante una copia posterior de datos desencadenada, por ejemplo, por el elemento no objeto de acceso.}

Answer 2

Como ahora se garantiza que las cadenas se almacenan contiguamente y ahora se le permite tomar un puntero al almacenamiento interno de una cadena, (es decir, & str [0] funciona como lo haría para una matriz), no es posible crear una VACA útil. implementación. Tendría que hacer una copia para demasiadas cosas. Incluso el solo uso de operator[] o begin() en una cadena no const requeriría una copia.

Answer 3

Desde 21.4.2 constructores de cadena básica y operadores de asignación [string.cons]

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

[...]

2 Efectos : construye un objeto de clase basic_string como se indica en la Tabla 64. [...]

La Tabla 64 útilmente documenta que después de la construcción de un objeto a través de este (copia) constructor, this->data() tiene como valor:

señala el primer elemento de una copia asignada de la matriz cuyo primer elemento apunta a str.data ()

Existen requisitos similares para otros constructores similares.

Answer 4

Es decir, CoW es un mecanismo aceptable para hacer cadenas más rápidas ... pero ...

hace que el código multiproceso sea más lento (todo ese bloqueo para comprobar si eres el único que mata el rendimiento cuando utilizas muchas cadenas). Esta fue la razón principal por la cual se mató a CoW hace años.

Las otras razones son que el operador [] le devolverá los datos de la cadena, sin ninguna protección para que usted sobrescriba una cadena que otra persona espera que no cambie. Lo mismo aplica para c_str() y data() .

Google rápido dice que el multihilo es básicamente la razón por la que fue desautorizado de manera efectiva (no explícitamente).

La propuesta dice:

Propuesta

Proponemos hacer que todas las operaciones de acceso a iterador y elemento sean ejecutables de forma segura simultáneamente.

Estamos aumentando la estabilidad de las operaciones incluso en código secuencial.

Este cambio no permite implementaciones de copia en escritura.

seguido por

La mayor pérdida potencial en el rendimiento debido a un cambio de las implementaciones de copia sobre escritura es el mayor consumo de memoria para aplicaciones con cadenas de lectura muy grandes. Sin embargo, creemos que para esas aplicaciones, las cuerdas son una mejor solución técnica, y recomendamos que una propuesta de cuerda sea considerada para su inclusión en la Biblioteca TR2.

Ropes son parte de STLPort y SGI STL.

Answer 5

Las respuestas de Dave S y gbjbaanb son correctas . (Y el de Luc Danton también es correcto, aunque es más un efecto secundario de prohibir cadenas COW en lugar de la regla original que lo prohíbe).

Pero para aclarar algo de confusión, voy a agregar algo más de exposición. Varios comentarios enlazan a this que da el siguiente ejemplo:

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

El objetivo de este ejemplo es demostrar por qué la cadena de referencia contada (COW) de GCC no es válida en C ++ 11. El estándar C ++ 11 requiere que este código funcione correctamente. Nada en el código permite que la p se invalide en C ++ 11.

Usando la implementación de std::string contada por referencia de GCC, ese código tiene un comportamiento indefinido, porque p se invalida y se convierte en un puntero colgante. (Lo que sucede es que cuando se construye s2 , comparte los datos con s , pero obtener una referencia no const a través de s[0] requiere que los datos se compartan, entonces s hace una "copia al escribir" porque la referencia s[0] podría usarse potencialmente para escribir en s , luego s2 sale del alcance, destruyendo la matriz señalada por p ).

El estándar C ++ 03 permite explícitamente ese comportamiento en 21.3 [lib.basic.string] p5 donde dice que después de una llamada a data() la primera llamada al operator[]() puede invalidar punteros, referencias e iteradores. Entonces, la cadena COW de GCC era una implementación válida de C ++ 03.

El estándar C ++ 11 ya no permite ese comportamiento, porque ninguna llamada al operator[]() puede invalidar punteros, referencias o iteradores, independientemente de si siguen una llamada a data() .

Por lo tanto, el ejemplo anterior debe funcionar en C ++ 11, pero no funciona con el tipo de cadena COW de libstdc ++, por lo tanto, ese tipo de cadena COW no está permitida en C ++ 11.

Answer 6

No está permitido, porque según el estándar 21.4.1 p6, la invalidación de iteradores / referencias solo está permitida

- como argumento para cualquier función de biblioteca estándar tomando como referencia una cadena básica no const como argumento.

- Llamar a funciones miembro no-const, excepto operator [], en, front, back, begin, rbegin, end, y rend.

Para una cadena COW, llamar al operator[] non-const operator[] requeriría hacer una copia (e invalidar las referencias), lo cual no está permitido por el párrafo anterior. Por lo tanto, ya no es legal tener una cadena COW en C ++ 11.