Se permitiría esta optimización en la aplicación de std :: string?

Question

Yo estaba pensando en la implementación de std::string::substr. Devuelve un nuevo objeto std::string, que parece un desperdicio poco a mí. ¿Por qué no devolver un objeto que se refiere al contenido de la cadena original y se pueden asignar de forma implícita a un std::string? Un tipo de evaluación perezosa de la copia real. Clase A de este tipo podría ser algo como esto:

template <class Ch, class Tr, class A>
class string_ref {
public:
    // not important yet, but *looks* like basic_string's for the most part

private:
    const basic_string<Ch, Tr, A> &s_;
    const size_type pos_;
    const size_type len_;    
};

La interfaz pública de esta clase sería imitar todas las operaciones de sólo lectura de un std::string reales, por lo que el empleo sea transparente. std::string podría entonces tener un nuevo constructor que toma un string_ref por lo que el usuario nunca se daría cuenta. En el momento que intenta "almacenar" el resultado, se termina la creación de una copia, por lo que no problemas reales con la referencia que apunta a los datos y luego tener que modificarse por detrás de su espalda.

La idea es que un código como éste:

std::string s1 = "hello world";
std::string s2 = "world";
if(s1.substr(6) == s2) {
    std::cout << "match!" << std::endl;
}

tendría no más de 2 std::string objetos construidos en total. Esto parece una optimización útil para código que que realiza una gran cantidad de manipulaciones de cadenas. Por supuesto, esto no sólo se aplica a std::string, sino a cualquier tipo que puede devolver un subconjunto de su contenido.

Por lo que yo sé, no hay implementaciones de hacer esto.

supongo que el núcleo de la cuestión es:

En vista de una clase que se puede convertir implícitamente a un std::string según sea necesario, tendría que ser compatibles con el estándar para un escritor biblioteca para cambiar el prototipo del tipo de regresar de un miembro? O más en general, hacer los escritores de la biblioteca tienen el margen de maniobra para volver "objetos proxy" en lugar de objetos habituales en este tipo de casos como una optimización?

Mi instinto es que esto no está permitido y que los prototipos debe coincidir exactamente. Teniendo en cuenta que no se puede sobrecargar el tipo de retorno solos, que no dejarían espacio para los escritores de la biblioteca para tomar ventaja de este tipo de situaciones. Como he dicho, creo que la respuesta es no, pero pensé que había que pregunto: -).

Answer 1

Esta idea es copy-on-write , pero en lugar de COW'ing toda la memoria intermedia, realizar un seguimiento de qué subconjunto de la memoria intermedia es la cadena "real". (COW, en su forma normal, era (es?) Utilizado en algunas implementaciones de la biblioteca.)

Así que no es necesario un objeto proxy o el cambio de interfaz en absoluto, porque estos detalles se pueden hacer completamente interno. Conceptualmente, es necesario hacer un seguimiento de cuatro cosas: un búfer de origen, un contador de referencia para el búfer, y el inicio y el final de la cadena dentro de este buffer

.

Anytime un modifica la operación del búfer en absoluto, crea su propia copia ( desde el inicio y final delimitadores ), disminuye el contador de referencia de la antigua memoria intermedia por uno, y los conjuntos de referencia del nuevo buffer contar hasta uno. El resto de las reglas de recuento de referencia son los mismos: la copia y el aumento de recuento por uno, destruct una cadena y la reducción del recuento de a uno, lleguen a cero y borrar, etc.

.

substr sólo hace una nueva instancia de serie, excepto con los delimitadores de inicio y final especificados explícitamente.

Answer 2

Esta es una optimización bastante bien conocido que es relativamente ampliamente utilizado, llamado copia en escritura o una vaca. Lo fundamental no es ni siquiera que ver con subseries, pero con algo tan simple como

s1 = s2;

Ahora, el problema con esta optimización es que para bibliotecas de C ++ que se supone que se usa en objetivos que apoyan múltiples hilos, el recuento de referencia para la cadena tiene que ser visitada mediante operaciones atómicas (o peor, protegido con un mutex en el caso la plataforma de destino no suministra operaciones atómicas). Esto es bastante caro que en la mayoría de los casos, la implementación simple no es la cadena vaca es más rápido.

Ver GOTW # 43-45:

http://www.gotw.ca/gotw/043.htm

http://www.gotw.ca/gotw/044.htm

http://www.gotw.ca/gotw/045.htm

Para empeorar las cosas, las bibliotecas que tienen VACA utilizados, como la biblioteca GNU C ++, no puede simplemente reversión a la simple aplicación ya que ello romper el ABI. (Aunque, C ++ 0x al rescate, ya que esto requeriría un ABI bump de todos modos! :))

Answer 3

Desde vuelve substr std::string, no hay manera de devolver un objeto proxy, y no pueden simplemente cambiar el tipo de retorno o sobrecarga en él (por las razones que usted ha mencionado).

Se puede hacer esto haciendo string que es capaz de ser un sub de otra cadena. Esto significaría una penalización de memoria para todos los usos (para mantener una cadena adicional y dos size_types). Además, todas las operaciones tendrían que comprobar para ver si tiene los caracteres o es un proxy. Tal vez esto se podría hacer con un puntero de aplicación -. El problema es que ahora estamos haciendo una clase de propósito general más lento para un posible caso extremo

Si usted necesita esto, la mejor manera es crear otra clase, substring, que las construcciones de una cadena, pos, la longitud, la coberteras de cadena. No se puede utilizar como s1.substr(6), pero se puede hacer

 substring sub(s1, 6);

También necesitaría para crear operaciones comunes que tienen una subcadena y la cadena para evitar la conversión (ya que es el punto entero).

Answer 4

En cuanto a su ejemplo específico, esto funcionó para mí:

if (&s1[6] == s2) {
    std::cout << "match!" << std::endl;
}

Eso no puede responder a su pregunta de una solución de propósito general. Para ello, se necesitaría CdT sub-cadena, como sugiere @GMan.

Answer 5

Lo que está hablando es (o era) una de las funciones principales de la clase java.lang.String de Java ( http://fishbowl.pastiche.org/2005/04/27/the_string_memory_gotcha/ ). En muchos sentidos, los diseños de clase y String de Java C ++ 's basic_string plantilla son similares, por lo que me imagino que la escritura de una implementación de la plantilla basic_string la utilización de esta 'optimización subcadena' es posible.

Una cosa que usted tendrá que considerar es la forma de escribir la puesta en práctica del miembro c_str() const. Dependiendo de la ubicación de una cadena como una subcadena de otra, puede tener que crear una nueva copia. Definitivamente tendría que crear una nueva copia de la matriz interna si la cadena para la que se solicitó a la c_str no es una subcadena de arrastre. Creo que esto hace necesario el uso de la palabra clave mutable en la mayoría, si no todos, de los miembros de datos de la aplicación basic_string, lo que complica en gran medida la aplicación de otros métodos const porque el compilador ya no es capaz de ayudar al programador corrección const.

EDIT: En realidad, para dar cabida a c_str() const y data() const, se puede utilizar un solo campo mutable del tipo const charT*. Inicialmente se establece en NULL, podría ser por instancia, inicializado a un puntero a una nueva matriz charT siempre c_str() const o data() const son llamados y borrado en el destructor basic_string si no NULL.

Answer 6

Si y sólo si realmente necesita más rendimiento que std :: string proporciona a continuación, seguir adelante y escribir algo que funciona de la manera que lo necesite a. He trabajado con variantes de cadenas antes.

Mi preferencia es utilizar cadenas no mutables en lugar de copia en escritura, y para impulsar el uso :: shared_ptr o equivalente, pero sólo cuando la cadena es en realidad más allá del 16 de longitud, por lo que la clase string también tiene un privado tampón para cadenas cortas.

Esto significa que la clase string podría llevar un poco de peso.

También tengo en mi lista de colecciones una clase de "corte" que puede mirar a un "subconjunto" de una clase que vive en otro lugar, siempre que el tiempo de vida del objeto original está intacta. Así, en su caso pude cortar la cuerda para ver una subcadena. Por supuesto que no sería terminada en nulo, ni hay ninguna manera de hacer que tales sin copiarlo. Y no es una clase de cadena.