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

Tenía entendido que la copia en escritura no es una forma viable de implementar una conformidad std::stringen C ++ 11, pero cuando surgió en la discusión recientemente, me encontré incapaz de respaldar directamente esa declaración.

¿Estoy en lo cierto de que C ++ 11 no admite implementaciones basadas en COW std::string?

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

¿O está implícita esta restricción, en el sentido de que es el efecto combinado de los nuevos requisitos sobre lo std::stringque excluye una implementación basada en COW de std::string. En este caso, estaría interesado en una derivación de estilo de capítulo y verso de 'C ++ 11 prohíbe efectivamente las std::stringimplementaciones basadas en COW '.

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

- como argumento para cualquier función de biblioteca estándar tomando como argumento una referencia a cadena_básica no constante.

- Llamar a funciones miembro que no son constantes, excepto operador [], at, front, back, begin, rbegin, end y rend.

Para una cadena COW, llamar a non-const operator[]requeriría hacer una copia (e invalidar 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.

Las respuestas de Dave S y gbjbaanb son correctas . (Y Luc Danton también tiene razón, aunque es más un efecto secundario de prohibir las cuerdas COW que la regla original que lo prohíbe).

Pero para aclarar algo de confusión, agregaré una exposición adicional. Varios comentarios enlazan a un comentario mío sobre el bugzilla de GCC 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 ese 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 pque se invalide en C ++ 11.

Usando la antigua std::stringimplementación contada de referencias 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 s2se construye comparte los datos con s, pero obtener una referencia no constante a través de s[0]requiere que los datos no se compartan, también lo shace una "copia al escribir" porque la referencia s[0]podría potencialmente usarse para escribir s, luego s2va fuera de alcance, destruyendo la matriz apuntada 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 a 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 a 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 que ese tipo de cadena COW no está permitido en C ++ 11.

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

hace que el código de subprocesos múltiples sea más lento (todo ese bloqueo para verificar si eres el único que escribe mata el rendimiento cuando se usan muchas cadenas). Esta fue la razón principal por la que CoW fue asesinado hace años.

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

Quick google dice que el multiproceso es básicamente la razón por la que se rechazó efectivamente (no explícitamente).

La propuesta dice:

Propuesta

Proponemos hacer que todas las operaciones de acceso a elementos e iteradores sean ejecutables simultáneamente de forma segura.

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

Este cambio no permite efectivamente las implementaciones de copia en escritura.

seguido por

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

Las cuerdas son parte de STLPort y SGIs STL.

De 21.4.2 constructores y operadores de asignación basic_string [string.cons]

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

[...]

2 Efectos : Construye un objeto de clase basic_stringcomo se indica en la Tabla 64. [...]

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

apunta al primer elemento de una copia asignada de la matriz cuyo primer elemento es apuntado por str.data ()

Existen requisitos similares para otros constructores similares.

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

¿Está COW basic_stringprohibido en C ++ 11 y posteriores?

Respecto a

” ¿Estoy en lo cierto en que C ++ 11 no admite implementaciones basadas en COW std::string?

Si.

Respecto a

” Si es 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 ¹ambos activarían la copia de datos de cadena para no compartir el valor de cadena, el estándar C ++ 11 requiere

” Complejidad: tiempo constante.

… Lo que excluye la copia de tales datos y, por lo tanto, COW.

C ++ 03 apoya implementaciones vaca por no tener estos requisitos de complejidad constante, y por, bajo ciertas condiciones restrictivas, lo que permite llamadas a operator[](), at(), begin(), rbegin(), end(), o rend()la Bibliografía de anular, punteros e iteradores que se refieren a los elementos de la secuencia, es decir, a la posibilidad de incurrir en una Copia de datos de VACA. Este soporte se eliminó en C ++ 11.

¿COW también está prohibido a través de las reglas de invalidación de C ++ 11?

En otra respuesta que en el momento de escribir este artículo se selecciona como solución, y que tiene una gran votación a favor y, por lo tanto, aparentemente se cree, se afirma que

” Para una cadena COW, llamar a non- const operator[]requeriría hacer una copia (e invalidar referencias), lo cual no está permitido por el párrafo [citado] anterior [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 formas principales:

• Indica incorrectamente que solo los accesadores constque no son elementos necesitan activar una copia de datos COW.
  Pero también los constaccesadores de elementos deben activar la copia de datos, porque permiten que el código del cliente forme referencias o punteros que (en C ++ 11) no se pueden invalidar más adelante a través de las operaciones que pueden activar la copia de datos COW.
• Supone incorrectamente que la copia de datos COW puede provocar la invalidación de la referencia.
  Pero en una implementación correcta, la copia de datos COW, que no comparte 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 COW de C ++ 11 correcta basic_string, cuando se ignoran los requisitos O (1) que hacen que esto no sea válido, piense en una implementación en la que una cadena pueda cambiar entre políticas de propiedad. Una instancia de cadena comienza con la política Compartible. Con esta política activa no puede haber referencias de artículos externos. La instancia puede realizar la transición a la política Unique 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 la cadena. Después de esa transición a la política Unique, la instancia solo puede volver a Sharable mediante una operación que invalide todas las referencias, como la asignación.

Entonces, si bien la conclusión de esa 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:

Cambio : los basic_stringrequisitos ya no permiten cadenas contadas por referencias
Justificación: la invalidación es sutilmente diferente con cadenas contadas por referencias. Este cambio regulariza el comportamiento (sic) de esta Norma Internacional.
Efecto sobre la característica original: el código C ++ 2003 válido puede ejecutarse de manera diferente en esta Norma Internacional

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

En resumen, las reglas de invalidación de C ++ 11 no descartan una implementación COW de std::basic_string. Pero descartan una implementación COW de estilo C ++ 03 sin restricciones razonablemente eficiente como la de al menos una de las implementaciones de biblioteca estándar de g ++. El soporte especial COW de C ++ 03 permitió la eficiencia práctica, en particular el uso de constaccesores de elementos, a costa de reglas sutiles y complejas para la invalidación:

”Las referencias, punteros e iteradores que se refieren a los elementos de una basic_stringsecuencia pueden ser invalidados por los siguientes usos de ese basic_stringobjeto:
- Como argumento para 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 llamada data()y c_str()miembro.
- Llamar a no constfunciones miembro, excepto operator[](), at(), begin(), rbegin(), end(), y rend().
- Con posterioridad a cualquiera de los usos anteriores, excepto las formas de insert()y erase()los que regresan iteradores, la primera llamada a no constfunciones miembro operator[](), at(), begin(), rbegin(),end(), o rend().

Estas reglas son tan complejas y sutiles que dudo que muchos programadores, si es que hay alguno, puedan dar un resumen preciso. No pude.

¿Qué sucede si se ignoran los requisitos de O (1)?

Si se ignoran los requisitos de tiempo constante de C ++ 11 en, por ejemplo operator[], COW for basic_stringpodría ser técnicamente factible, pero difícil de implementar.

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

• Concatenación vía +.
• Salida vía <<.
• Uso de un basic_stringargumento como para las funciones de biblioteca estándar.

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

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

Un factor de complicación principal es que en C ++ 11 basic_stringel acceso al elemento debe desencadenar la copia de datos (no compartir los datos de la cadena) pero se requiere que no arroje , por ejemplo, C ++ 11 §21.4.5 / 3 “ Lanza: Nada”. Por tanto, no puede utilizar 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 ser asignada realmente, y luego reservar la cantidad requerida para cada referencia lógica a un valor de cadena. Reservar y anular la reserva en tal montón puede ser un tiempo constante, O (1), y asignar la cantidad que uno ya ha reservado, puede sernoexcept. Para cumplir con los requisitos de la norma, con este enfoque, parece que sería necesario un montón especial basado en reservas por asignador distinto.

^{Notas:
¹ El constdescriptor de acceso al elemento activa una copia de datos COW porque permite que el código del cliente obtenga una referencia o puntero a los datos, que no está permitido invalidar mediante una copia de datos posterior activada, por ejemplo, por el constacceso que no es del elemento.}

Siempre me preguntaba acerca de las vacas inmutables: una vez que se crea la vaca, solo puedo cambiar a través de la asignación de otra vaca, por lo tanto, cumplirá con el estándar.

Tuve tiempo de probarlo hoy para una prueba de comparación simple: un mapa de tamaño N codificado por cadena / vaca con cada nodo que contiene un conjunto de todas las cadenas en el mapa (tenemos un número NxN de objetos).

Con cadenas con un tamaño de ~ 300 bytes y N = 2000, las vacas son un poco más rápidas y usan casi un orden de magnitud menos de memoria. Vea a continuación, los tamaños están en kbs, la ejecución b es con 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