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

117

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

acm
fuente
5
El error de GCC para su cadena COW es gcc.gnu.org/bugzilla/show_bug.cgi?id=21334#c45 . Uno de los errores que rastrea una nueva implementación compilante de C ++ 11 de std :: string en libstdc ++ es gcc.gnu.org/bugzilla/show_bug.cgi?id=53221
user7610

Respuestas:

120

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.

Dave S
fuente
4
Algunos motivos
MM
8
-1 La lógica no se sostiene. En el momento de una copia COW no hay referencias o iteradores que se puedan invalidar, el objetivo de hacer la copia es que dichas referencias o iteradores ahora se están obteniendo, por lo que es necesario copiar. Pero aún puede ser que C ++ 11 no permita implementaciones COW.
Saludos y hth. - Alf
11
@ Cheersandhth.-Alf: La lógica se puede ver en lo siguiente si se permitió COW: std::string a("something"); char& c1 = a[0]; std::string b(a); char& c2 = a[1]; c1 es una referencia a a. Luego "copia" a. Luego, cuando intenta tomar la referencia por segunda vez, tiene que hacer una copia para obtener una referencia no constante, ya que hay dos cadenas que apuntan al mismo búfer. Esto tendría que invalidar la primera referencia tomada, y está en contra de la sección citada anteriormente.
Dave S
9
@ Cheersandhth.-Alf, de acuerdo con esto , al menos la implementación COW de GCC hace exactamente lo que DaveS está diciendo. Entonces, al menos ese estilo de COW está prohibido por el estándar.
Tavian Barnes
4
@Alf: Esta respuesta argumenta que non-const operator[](1) debe hacer una copia y que (2) es ilegal que lo haga. ¿Con cuál de esos dos puntos no está de acuerdo? En cuanto a su primer comentario, parece que una implementación podría compartir la cadena, al menos bajo este requisito, hasta el momento en que se accede a ella, pero que tanto los accesos de lectura como los de escritura deberían dejar de compartirla. ¿Ese es tu razonamiento?
Ben Voigt
48

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.

Jonathan Wakely
fuente
3
Una implementación que deja de compartir en la llamada a .data()(y en cada devolución de puntero, referencia o iterador) no sufre ese problema. Es decir (invariante), un búfer no se comparte en ningún momento, o se comparte sin referencias externas. Pensé que habías pensado que el comentario sobre este ejemplo era un informe informal de error como comentario, ¡lo siento mucho por malinterpretarlo! Pero como puede ver al considerar la implementación que describo aquí, que funciona bien en C ++ 11 cuando noexceptse ignoran los requisitos, el ejemplo no dice nada sobre lo formal. Puedo proporcionar el código si lo desea.
Saludos y hth. - Alf
7
Si deja de compartir en casi todos los accesos a la cadena, perderá todos los beneficios de compartir. Una implementación COW tiene que ser práctica para que una biblioteca estándar se moleste en usarla std::string, y sinceramente dudo que pueda demostrar una cadena COW útil y eficaz que cumpla con los requisitos de invalidación de C ++ 11. Por lo tanto, mantengo que las noexceptespecificaciones que se agregaron en el último minuto son una consecuencia de la prohibición de las cadenas COW, no la razón subyacente. N2668 parece perfectamente claro, ¿por qué continúa negando la clara evidencia de la intención del comité descrita allí?
Jonathan Wakely
Además, recuerde que data()es una función de miembro const, por lo que debe ser seguro llamar al mismo tiempo con otros miembros const y, por ejemplo, llamar al data()mismo tiempo con otro hilo haciendo una copia de la cadena. Por lo tanto, necesitará toda la sobrecarga de un mutex para cada operación de cadena, incluso las constantes, o la complejidad de una estructura contada de referencias mutables sin bloqueo, y después de todo, solo podrá compartir si nunca modifica o accede sus cadenas, tantas, muchas cadenas tendrán un recuento de referencia de uno. Proporcione el código, no dude en ignorar las noexceptgarantías.
Jonathan Wakely
2
Simplemente armando un poco de código ahora descubrí que hay 129 basic_stringfunciones miembro, más funciones gratuitas. Costo de abstracción: este código de versión cero, no optimizado y listo para usar, es de 50 a 100% más lento con g ++ y MSVC. No hace la seguridad de los subprocesos ( shared_ptrcreo que es bastante fácil de aprovechar ) y es suficiente para admitir la clasificación de un diccionario con fines de sincronización, pero los errores de módulo demuestran que basic_stringse permite una referencia contada , excepto para los noexceptrequisitos de C ++ . github.com/alfps/In-principle-demo-of-ref-counted-basic_string
Saludos y hth. - Alf
1
Continuemos esta discusión en el chat .
Jonathan Wakely
20

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.

gbjbaanb
fuente
2
El problema del operador [] no es realmente un problema. La variante const ofrece protección, y la variante no constante siempre tiene la opción de hacer el CoW en ese momento (o estar realmente loco y configurar una falla de página para activarlo).
Christopher Smith
+1 Va a los problemas.
Saludos y hth. - Alf
5
es una tontería que no se haya incluido una clase std :: cow_string, con lock_buffer (), etc., hay muchas veces que sé que el enhebrado no es un problema. la mayoría de las veces, en realidad.
Erik Aronesty
Me gusta la sugerencia de una alternativa, cuerdas ig. Me pregunto si hay otros tipos de alternativas e implementaciones disponibles.
Voltaire
5

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.

Luc Danton
fuente
+1 Explica cómo C ++ 11 (al menos parcialmente) prohíbe COW.
Saludos y hth. - Alf
Lo siento, estaba cansado. No explica nada más que una llamada a .data () debe activar la copia COW si el búfer está actualmente compartido. Aún así, es información útil, así que dejo el voto a favor.
Saludos y hth. - Alf
1

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.

Dirk Holsopple
fuente
1
Creo que se garantiza que las cadenas en C ++ 11 se almacenarán de forma contigua.
mfontanini
4
En el pasado tenías que hacer las copias en todas esas situaciones y no era un problema ...
David Rodríguez - dribeas 30/08/12
@mfontanini sí, pero no lo eran anteriormente
Dirk Holsopple
3
Aunque C ++ 11 garantiza que las cadenas sean contiguas, eso es ortogonal a prohibir las cadenas COW. La cadena COW de GCC es contigua, por lo que claramente su afirmación de que "no es posible realizar una implementación COW útil" es falsa.
Jonathan Wakely
1
@supercat, solicitando el almacén de respaldo (por ejemplo, llamando c_str()) debe ser O (1) y no puede lanzar, y no debe introducir carreras de datos, por lo que es muy difícil cumplir con esos requisitos si concatenas perezosamente. En la práctica, la única opción razonable es almacenar siempre datos contiguos.
Jonathan Wakely
1

¿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

C ++ 11 §21.4.5 / 4 :

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:

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

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:

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

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

Saludos y hth. - Alf
fuente
3
" Su ejemplo es un buen ejemplo de una implementación incorrecta para C ++ 11. Posiblemente fue correcto para C ++ 03". Sí, ese es el punto del ejemplo . Muestra una cadena COW que era legal en C ++ 03 porque no rompe las reglas de invalidación del iterador antiguo y no es legal en C ++ 11 porque rompe las reglas de invalidación del nuevo iterador. Y también contradice la declaración que cité en el comentario anterior.
Jonathan Wakely
2
Si hubiera dicho que se puede compartir, no se compartió inicialmente , no habría discutido. Decir que algo se comparte inicialmente es confuso. ¿Compartido consigo mismo? Eso no es lo que significa la palabra. Pero repito: su intento de argumentar que las reglas de invalidación del iterador C ++ 11 no prohíben alguna cadena COW hipotética que nunca se usó en la práctica (y tendría un rendimiento inaceptable), cuando lo más seguro es que prohíban el tipo de cadena COW que se utilizó en la práctica, es algo académico y sin sentido.
Jonathan Wakely
5
Su cadena COW propuesta es interesante, pero no estoy seguro de cuán útil sería. El objetivo de una cadena COW es copiar solo los datos de la cadena en el caso de que se escriban las dos cadenas. Su implementación sugerida requiere copia cuando ocurre cualquier operación de lectura definida por el usuario. Incluso si el compilador sabe que es solo una lectura, aún debe copiar. Además, copiar una cadena única dará como resultado una copia de sus datos de cadena (presumiblemente a un estado Compartible), lo que nuevamente hace que COW sea bastante inútil. Entonces, sin las garantías de complejidad, podrías escribir ... una cadena COW realmente horrible .
Nicol Bolas
2
Entonces, si bien está técnicamente en lo cierto en que las garantías de complejidad son lo que le impide escribir cualquier forma de COW, realmente es [basic.string] / 5 lo que le impide escribir cualquier forma realmente útil de cadena COW.
Nicol Bolas
4
@JonathanWakely: (1) Tu cotización no es la cuestión. Aquí está la pregunta: “¿Estoy en lo cierto de que C ++ 11 no admite implementaciones de std :: string basadas en COW? Si es así, ¿esta restricción se establece explícitamente en algún lugar del nuevo estándar (dónde)? " (2) Su opinión de que un COW std::string, al ignorar los requisitos O (1), sería ineficiente, es su opinión. No sé cuál podría ser la actuación, pero creo que esa afirmación se presenta más por la sensación, por las vibraciones que transmite, que por la relevancia de esta respuesta.
Saludos y hth. - Alf
0

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