koffman - Estructuras de datos persistentes en c++

estructuras en c++ pdf

Question

¿Hay implementaciones de estructuras de datos persistentes en c ++ similares a las de clojure?

Answer 1

Hice mi propio rollo pero está la biblioteca immer como un ejemplo bastante completo y está específicamente inspirado en clojure. Me emocioné mucho y me hice rodar hace algunos años después de escuchar un discurso de John Carmack, en el que estaba saltando por encima del carro de la programación funcional. Parecía poder imaginar un motor de juego en torno a estructuras de datos inmutables. Si bien no fue específico, y si bien parecía una idea confusa en su cabeza, el hecho de que lo estuviera considerando seriamente y que no parecía pensar que la sobrecarga en las tasas de fotogramas fuese suficiente para entusiasmarme. sobre la exploración de esa idea.

De hecho, lo uso como un detalle de optimización que puede parecer paradójico (hay una sobrecarga de inmutabilidad), pero me refiero a un contexto específico. Si absolutamente quiero hacer esto:

// We only need to change a small part of this huge data structure.
HugeDataStructure transform(HugeDataStructure input);

... y absolutamente no quiero que la función cause efectos secundarios para que pueda ser segura para subprocesos y nunca sea propensa al mal uso, entonces no tengo más remedio que copiar la enorme estructura de datos (que puede abarcar un gigabyte).

Y allí me parece que tener una pequeña biblioteca de estructuras de datos inmutables es inmensamente útil en ese contexto, ya que hace que el escenario anterior sea relativamente barato simplemente copiando y haciendo referencia a las partes no modificadas. Dicho esto, en su mayoría solo uso una estructura de datos inmutable que es básicamente una secuencia de acceso aleatorio, así:

Y como otros lo mencionaron, requirió un poco de cuidado, afinación, pruebas exhaustivas y muchas sesiones de VTune para que sea seguro y eficiente en los subprocesos, pero después de poner la grasa del codo, definitivamente hizo que todo fuera mucho más fácil.

Además de la seguridad de subprocesos automática, siempre que usamos estas estructuras para escribir funciones para estar libres de efectos secundarios, también obtiene elementos como la edición no destructiva, los sistemas triviales de deshacer, la seguridad trivial de excepciones (no es necesario retroceder los efectos secundarios a través de guardas de alcance). en una función que no causa ninguna en rutas excepcionales), y permite a los usuarios copiar y pegar datos y crear instancias sin tener mucha memoria hasta / a menos que modifiquen lo que pegan como bonificación. De hecho, encontré que estas bonificaciones son aún más útiles a diario que la seguridad de los hilos.

Uso ''transitorios'' (también conocidos como ''constructores'') como una forma de expresar cambios en la estructura de datos, de esta manera:

Immutable transform(Immutable input)
{
    Transient transient(input);

    // make changes to mutable transient.
    ...

    // Commit the changes to get a new immutable
    // (this does not touch the input).
    return transient.commit();
}

Incluso tengo una biblioteca de imágenes inmutables que utilizo para la edición de imágenes para trivializar la edición no destructiva. Utiliza una estrategia similar a la estructura anterior al tratar las imágenes como mosaicos de esta manera:

Cuando se modifica un transitorio y obtenemos un nuevo inmutable, solo las piezas modificadas se hacen únicas. El resto de los mosaicos se copian de forma superficial (solo índices de 32 bits):

Los uso en áreas bastante críticas para el rendimiento, como malla y procesamiento de video. Hubo un poco de ajuste en cuanto a la cantidad de datos que debe almacenar cada bloque (demasiado y desperdiciamos el procesamiento y la memoria copiando demasiados datos, muy poco y desperdiciamos el procesamiento y la memoria copiando demasiados punteros con bloqueos de subprocesos más frecuentes ).

No los uso para el trazado de rayos, ya que es una de las áreas críticas de rendimiento más extremas que se pueden imaginar y los usuarios pueden percibir una pequeña sobrecarga (en realidad comparan y notan diferencias de rendimiento en el rango del 2%), pero la mayoría de los tiempo, son lo suficientemente eficientes, y es un beneficio bastante impresionante cuando puede copiar estas enormes estructuras de datos a la izquierda y a la derecha para simplificar la seguridad de los subprocesos, deshacer los sistemas, la edición no destructiva, etc., sin preocuparse por el uso explosivo de la memoria. Y notables demoras las pasamos copiando todo profundamente.

Answer 2

Si entiendo la pregunta correctamente, lo que busca es la capacidad de duplicar un objeto sin pagar realmente la duplicación cuando se hace, solo cuando es necesario. Los cambios en cualquiera de los objetos se pueden hacer sin dañar el otro. Esto se conoce como "copia en escritura".

Si esto es lo que está buscando, esto puede implementarse bastante fácilmente en C ++ utilizando punteros compartidos (consulte shared_ptr de Boost, como una implementación). Inicialmente, la copia compartiría todo con la fuente, pero una vez que se realizan los cambios, las partes relevantes de los punteros compartidos del objeto se reemplazan por otros punteros compartidos que apuntan a objetos recién creados y copiados en profundidad. (Me doy cuenta de que esta explicación es vaga: si esto es lo que quiere decir, la respuesta puede ser elaborada).

Answer 3

La principal dificultad para obtener una estructura de datos persistente es, de hecho, la falta de recolección de basura.

Si no tiene un esquema de recolección de basura adecuado, puede obtener uno deficiente (es decir, conteo de referencias), pero esto significa que debe tener mucho cuidado de NO crear referencias cíclicas.

Cambia el núcleo mismo de la estructura. Por ejemplo, piense en árbol binario. Si crea una nueva versión de un nodo, entonces necesita una nueva versión de su padre para acceder a él (etc ...). Ahora, si la relación es bidireccional (padre <-> padre), de hecho duplicará toda la estructura. Esto significa que tendrá una relación padre - hijo, o lo contrario (menos común).

Puedo pensar en implementar un árbol binario o un B-Tree. Casi no veo cómo obtener una matriz adecuada, por ejemplo.

Por otro lado, estoy de acuerdo en que sería genial tener entornos eficientes en múltiples subprocesos.