¿Cómo implementar Copy-on-Write?

Question

Quiero implementar un copy-on-write en mi clase personalizada C++ String, y me pregunto cómo ...

Intenté implementar algunas opciones, pero todas resultaron muy ineficaces.

Gracias chicos :-)

Answer 1

En un environemnt multi-hilo (que es la mayoría de ellos hoy en día) vaca es con frecuencia un gran impacto en el rendimiento en lugar de una ganancia. Y con un uso cuidadoso de las referencias de const, no es mucho una ganancia de rendimiento incluso en un entorno de subproceso único.

Este viejo artículo de DDJ explica just how bad CoW can be in a multithreaded environment, even if there's only one thread.

Además, como han señalado otras personas, las cadenas de CoW son realmente difíciles de implementar y es fácil cometer errores. Eso, junto con su pobre desempeño en situaciones de enhebrado, me hace realmente cuestionar su utilidad en general. Esto se vuelve aún más cierto una vez que comience a usar la construcción de movimientos de C++ 11 y la asignación de movimiento.

Pero, para responder a su pregunta ....

Aquí hay un par de técnicas de implementación que pueden ayudar con el rendimiento.

Primero, almacene la longitud en la cadena misma. Se accede a la longitud con bastante frecuencia y la eliminación de la referencia del puntero probablemente sea útil. Lo haría, solo por coherencia pongo la longitud asignada allí también. Esto le costará en términos de que sus objetos de cadena sean un poco más grandes, pero la sobrecarga en espacio y tiempo de copia es muy pequeña, especialmente dado que estos valores serán más fáciles para el compilador para jugar trucos de optimización interesantes.

Esto le deja con una clase de cadena que se ve así:

class MyString { 
    ... 
private: 
    class Buf { 
     ... 
    private: 
     ::std::size_t refct_; 
     char *data_; 
    }; 

    ::std::size_t len_; 
    ::std::size_t alloclen_; 
    Buf *data_; 
}; 

Ahora, hay otras optimizaciones que se pueden realizar. La clase Buf parece que realmente no contiene o no hace mucho, y esto es cierto. Además, requiere asignar tanto una instancia de Buf como un buffer para contener los caracteres. Esto parece un desperdicio Por lo tanto, vamos a convertir a una técnica común aplicación C, tampones elásticos:

class MyString { 
    ... 
private: 
    struct Buf { 
     ::std::size_t refct_; 
     char data_[1]; 
    }; 

    void resizeBufTo(::std::size_t newsize); 
    void dereferenceBuf(); 

    ::std::size_t len_; 
    ::std::size_t alloclen_; 
    Buf *data_; 
}; 

void MyString::resizeBufTo(::std::size_t newsize) 
{ 
    assert((data_ == 0) || (data_->refct_ == 1)); 
    if (newsize != 0) { 
     // Yes, I'm using C's allocation functions on purpose. 
     // C++'s new is a poor match for stretchy buffers. 
     Buf *newbuf = ::std::realloc(data_, sizeof(*newbuf) + (newsize - 1)); 
     if (newbuf == 0) { 
     throw ::std::bad_alloc(); 
     } else { 
     data_ = newbuf_; 
     } 
    } else { // newsize is 0 
     if (data_ != 0) { 
     ::std::free(data_); 
     data_ = 0; 
     } 
    } 
    alloclen_ = newsize; 
} 

Al hacer las cosas de esta manera, a continuación, puede tratar data_->data_ como si contuviera alloclen_ bytes en lugar de sólo 1.

Tenga en cuenta que, en todos estos casos, deberá asegurarse de que nunca lo utilice en un entorno de subprocesos múltiples o de que se asegure de que refct_ sea un tipo que tenga tanto un incremento atómico como un valor atómico. instrucción de disminución y prueba para.

Hay una técnica de optimización aún más avanzada que implica el uso de una unión para almacenar cadenas cortas dentro de los bits de datos que usaría para describir una cadena más larga. Pero eso es aún más complejo, y no creo que me sienta inclinado a editar esto para poner un ejemplo simplificado aquí más adelante, pero nunca se sabe.

Answer 2

No hay mucho que COW. Básicamente, usted copia cuando quiere cambiarlo, y deja que la persona que no quiera cambiarlo mantenga la referencia a la instancia anterior. Necesitará un recuento de referencias para realizar un seguimiento de quién sigue haciendo referencia al objeto y, como está creando una copia nueva, debe disminuir el recuento de la instancia "anterior".Un atajo sería no hacer una copia cuando ese conteo es uno (usted es la única referencia).

Aparte de eso, no hay mucho que decir, a menos que haya un problema específico al que se enfrente.

Answer 3

Hay una serie de artículos sobre esto exactamente en el libro More Exceptional C++ de Herb Sutter. Si no tiene acceso, puede intentar seguir a través de los artículos de Internet: part 1, part 2 y part 3.

Answer 4

Es posible que desee emular la cadena 'inmutable' que tienen otros lenguajes (Python, C# hasta donde yo sé).

La idea es que cada cuerda es inmutable, por lo tanto, cualquier trabajo en una cuerda crea una nueva inmutable ... o esa es la idea básica, para evitar una explosión, no necesitarías crear otra si hay una similar .

Answer 5

template <class T> struct cow { 
    typedef boost::shared_ptr<T> ptr_t; 
    ptr_t _data; 

    ptr_t get() 
    { 
    return boost::atomic_load(&_data); 
    } 

    void set(ptr_t const& data) 
    { 
    boost::atomic_store(&_data, data); 
    } 
} 

Answer 6

Yo sugeriría que si uno quiere implementar copia en escritura eficiente (por cuerdas o lo que sea), se debe definir un tipo de envoltura que se comportará como una cadena mutable, y que llevará a cabo tanto una anulable referencia a una cadena mutable (no existirá ninguna otra referencia a ese elemento) y una referencia anulable a una cadena "inmutable" (referencias a las cuales nunca existirán fuera de las cosas que no intenten mutarlas). Los empaquetadores siempre se crearán con al menos una de esas referencias no nulas; una vez que la referencia del elemento mutable alguna vez se establece en un valor no nulo (durante o después de la construcción) siempre se referirá al mismo objetivo. Siempre que ambas referencias no sean nulas, la referencia del elemento inmutable apuntará a una copia del elemento que se realizó algún tiempo después de la mutación completa más reciente (durante una mutación, la referencia del elemento inmutable puede contener o no una referencia a un valor previo a la mutación).

Para leer un objeto, verifique si la referencia "elemento variable" no es nula. Si es así, úsalo. De lo contrario, verifique si la referencia de "elemento inmutable" no es nula. Si es así, úsalo. De lo contrario, utilice la referencia "elemento variable" (que a partir de ahora no será nula).

Para cambiar un objeto, verifique si la referencia "elemento variable" no es nula. De lo contrario, copie el objetivo de la referencia de "elemento inmutable" y CompareExchange una referencia al nuevo objeto en la referencia de "elemento mutable". Luego mute el objetivo de la referencia de "elemento mutable" e invalide la referencia de "elemento inmutable".

Para clonar un objeto, si se espera que el clon se clone nuevamente antes de que se mute, recupere el valor de la referencia "elemento inmutable". Si es nulo, haga una copia del objetivo del "elemento mutable" y CompareExchange una referencia a ese nuevo objeto en la referencia del elemento inmutable. A continuación, cree una nueva envoltura cuya referencia de "elemento mutable" sea nula y cuya referencia de "elemento inmutable" sea el valor recuperado (si no fue nulo) o el nuevo (si lo fue).

Para clonar un objeto, si se espera que el clon se mute antes de clonarse, recupere el valor de la referencia "elemento inmutable". Si es nulo, recupera la referencia de "elemento mutable". Copie el destino de cualquier referencia que se haya recuperado y cree un nuevo contenedor cuya referencia de "elemento mutable" apunte a la nueva copia, y cuya referencia de "elemento inmutable" sea nula.

Los dos métodos de clonación serán semánticamente idénticos, pero elegir el incorrecto para una situación determinada dará como resultado una operación de copia adicional. Si uno elige consistentemente la operación de copia correcta, obtendrá la mayor parte del beneficio de un enfoque de copiado por escritura "agresivo", pero con mucho menos sobrecarga. Cada objeto de retención de datos (por ejemplo, cadena) será mudable o compartirá inmutable, y ningún objeto cambiará entre esos estados.En consecuencia, se podría, si se desea, eliminar toda la "sobrecarga de subprocesamiento/sincronización" (reemplazando las operaciones de CompareExchange con tiendas directas) siempre que no se utilice ningún objeto de envoltura en más de un subproceso simultáneamente. Dos objetos envoltorios pueden contener referencias al mismo titular de datos inmutables, pero pueden ser ajenos a la existencia de los demás.

Tenga en cuenta que pueden requerirse algunas operaciones de copia más cuando se utiliza este enfoque que cuando se utiliza un enfoque "agresivo". Por ejemplo, si se crea una nueva envoltura con una nueva cadena, y esa envoltura se muta y se copia seis veces, la envoltura original mantendría referencias al titular de la cadena original y una inmutable que contiene una copia de los datos. Las seis envolturas copiadas solo mantendrían una referencia a la cadena inmutable (dos cadenas en total, aunque si la cadena original nunca fuera mutada después de que se hizo la copia, una implementación agresiva podría funcionar con una). Si la envoltura original fuera mutada, junto con cinco de las seis copias, todas menos una de las referencias a la cadena inmutable serían invalidadas. En ese momento, si la sexta copia contenedora se mudaba, una implementación agresiva de escritura por escritura podría darse cuenta de que contenía la única referencia a su cadena y, por lo tanto, decidir que no era necesaria una copia. La implementación que describo, sin embargo, crearía una nueva copia mutable y abandonaría la inmutable. Sin embargo, a pesar del hecho de que hay algunas operaciones de copia adicionales, la reducción en la sobrecarga de enhebrado debería en la mayoría de los casos compensar con creces el costo. Si la mayoría de las copias lógicas que se producen nunca son mutadas, este enfoque puede ser más eficiente que siempre hacer copias de cadenas.