guidelines - c++ best practices

¿Cómo implementar Copy-on-Write?

Question

Quiero implementar una copia en escritura en mi clase de cadena de C ++ personalizada, y me pregunto cómo ...

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

Gracias chicos :-)

Answer 1

En un entorno de subprocesos múltiples (que es la mayoría de ellos en la actualidad), CoW es con frecuencia un gran éxito de rendimiento en lugar de una ganancia. Y con el uso cuidadoso de las referencias const, no es una ganancia de rendimiento incluso en un entorno de un solo hilo.

Este antiguo artículo de DDJ explica qué tan malo puede ser el CoW en un entorno multiproceso, incluso si solo hay un hilo .

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

Pero, para responder a tu pregunta ....

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

En primer lugar, almacene la longitud en la propia cadena. Se accede a la longitud con bastante frecuencia y probablemente ayudaría eliminar la desreferencia de puntero. Lo haría, solo por coherencia, poner la longitud asignada allí también. Esto le costará en términos de que los objetos de cadena sean un poco más grandes, pero la sobrecarga en el espacio y el tiempo de copia es muy pequeña, especialmente porque estos valores serán más fáciles para que el compilador juegue con interesantes trucos de optimización.

Esto te 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 puedes realizar. La clase de Buf allí parece que realmente no contiene o hace mucho, y esto es cierto. Además, requiere la asignación de una instancia de Buf y un búfer para contener los caracteres. Esto parece un desperdicio. Por lo tanto, recurriremos a una técnica de implementación en C común, los amortiguadores 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;
}

Cuando hace las cosas de esta manera, puede tratar los data_->data_ como si contuviera alloclen_ bytes en lugar de solo 1.

Tenga en cuenta que, en todos estos casos, tendrá que asegurarse de que nunca use esto en un entorno de subprocesos múltiples o de que refct_ es un tipo que tiene un incremento atómico y un atómico Decremento e instrucción de prueba para.

Existe 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 puede decir.

Answer 2

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

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

Answer 3

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

Answer 4

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

Aparte de eso, no se puede decir mucho, a menos que esté enfrentando un problema específico.

Answer 5

Yo sugeriría que si uno quiere implementar la copia en escritura de manera eficiente (para cadenas o lo que sea), debería definir un tipo de envoltura que se comportará como una cadena mutable y que contendrá tanto una referencia anulable a una cadena mutable (no siempre existirá otra referencia a ese elemento) y una referencia anulable a una cadena "inmutable" (referencias a las cuales nunca existirán fuera de cosas que no intentarán mutarlas). Los envoltorios siempre se crearán con al menos una de esas referencias no nula; una vez que la referencia del elemento mutable se establezca 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 o no contener una referencia). a un valor de pre-mutación).

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

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

Para clonar un objeto, si se espera que el clon se clone nuevamente antes de ser mutado, recupere el valor de la referencia del "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. Luego cree un nuevo contenedor cuya referencia de "elemento mutable" sea nula, y cuya referencia de "elemento inmutable" sea el valor recuperado (si no fuera nulo) o el nuevo elemento (si lo fue).

Para clonar un objeto, si se espera que el clon se mute antes de clonarlo, recupere el valor de la referencia del "elemento inmutable". Si es nulo, recupere la referencia "elemento mutable". Copie el destino de la referencia que se recuperó y cree un nuevo contenedor cuyo punto de referencia de "elemento mutable" apunte a la nueva copia, y cuya referencia de "elemento inmutable" sea nulo.

Los dos métodos de clonación serán semánticamente idénticos, pero elegir uno incorrecto para una situación dada resultará en una operación de copia adicional. Si uno elige sistemáticamente la operación de copia correcta, obtendrá la mayor parte del beneficio de un enfoque de copia en escritura "agresivo", pero con mucho menos sobrecarga de subprocesos. Cada objeto de retención de datos (por ejemplo, una cadena) será mutable no compartido o inmutable compartido, y ningún objeto cambiará entre esos estados. Por consiguiente, si se desea, se podría eliminar toda "sobrecarga de subprocesos / sincronización" (reemplazando las operaciones de CompareExchange con almacenes directos) siempre que no se utilice ningún objeto de envoltura en más de un subproceso simultáneamente. Dos objetos envoltorios podrían contener referencias al mismo titular de datos inmutables, pero podrían ser ajenos a la existencia de cada uno.

Tenga en cuenta que es posible que se requieran algunas operaciones de copia más cuando se utiliza este método que cuando se utiliza un método "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 contendrá referencias al titular de la cadena original y una inmutable que contiene una copia de los datos. Los seis envoltorios copiados solo tendrían una referencia a la cadena inmutable (dos cadenas en total, aunque si la cadena original nunca se mutara después de que se hiciera la copia, una implementación agresiva podría sobrevivir con una). Si se mutara la envoltura original, junto con cinco de las seis copias, todas las referencias a la cadena inmutable, excepto una, se invalidarán. En ese momento, si se mutara la sexta copia de envoltorio, una implementación agresiva de copia en escritura podría darse cuenta de que era la única referencia a su cadena y, por lo tanto, decidir que una copia no era necesaria. La implementación que describo, sin embargo, crearía una nueva copia mutable y abandonaría la inmutable. A pesar del hecho de que hay algunas operaciones de copia adicionales, sin embargo, la reducción en la sobrecarga de subprocesos debería en la mayoría de los casos compensar el costo. Si la mayoría de las copias lógicas que se producen nunca se mutan, este enfoque puede ser más eficiente que hacer siempre copias de cadenas.

Answer 6

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);
}
}