Cuál es la manera más rápida de deserializar un árbol en C++

Question

Estoy trabajando con una estructura de árbol no tan pequeña (es un Burkhard-Keller-Tree,> 100 MB en memoria) implementada en C++. Los punteros a los hijos de cada nodo se almacenan en un QHash.

Cada nodo x tiene n hijos y [1] ... y [n], los bordes de los niños están etiquetados con la distancia de edición d (x, y [i]), usando un hash para almacenar el nodos es una solución obvia.

class Node { 
    int value; 
    QHash<int, Node*> children; 
    /* ... */ 
}; 

También quiero serializar y deserializar en un archivo (en la actualidad utilizo un QDataStream). El árbol se acaba de construir una vez y no cambia entonces.

Construir el árbol y deserializarlo es bastante lento. Estoy cargando el árbol de la manera obvia: construyendo recursivamente cada nodo. Creo que esto no es óptimo debido a los muchos nodos que se crean por separado con el operador new. Leí en algún lado que new es bastante lento. La construcción inicial no es un gran problema porque el árbol es bastante estable y no tiene que ser reconstruido muy a menudo. Pero cargar el árbol desde un archivo debe ser lo más rápido posible.

¿Cuál es la mejor manera de lograr esto?

Debe ser mucho mejor guardar todo el árbol en un solo bloque de memoria con nodos adyacentes. Serializar y deserializar se reduciría para guardar y cargar todo el bloque, que tengo que asignar solo una vez.

Pero para implementar esto tendría que volver a implementar QHash, AFAIK.

¿Qué harías para acelerar la deserialización?

Adición

Gracias por su sugerencia para hacer un poco de perfiles. Aquí están los resultados:

Mientras que la reconstrucción del árbol desde un archivo

1 % of the time is consumed by my own new calls 
65 % is consumed by loading the QHash objects (this is implemented by the 
    Qt Library) of each node 
12 % is consumed by inserting the nodes into the existing tree 
20 % is everything else 

Así que no es definitivamente mis nuevas llamadas que causan el retraso pero la reconstrucción de la QHash objetos en cada nodo. Esto se realiza básicamente con:

QDataStream in(&infile); 
in >> node.hash; 

¿Tengo que cavar en QHash y mirar lo que está pasando bajo el capó hay? Creo que la mejor solución sería un objeto hash que se pueda serializar con una sola operación de lectura y escritura sin la necesidad de reconstruir la estructura interna de datos.

Answer 1

Otro enfoque sería serializar los punteros y restaurarlos al cargar.Es decir:

Serializar:

nodeList = collectAllNodes(); 

for n in nodelist: 
write (&n) 
writeNode(n) //with pointers as-they-are. 

deserializar:

//read all nodes into a list. 
while (! eof(f)) 
    read(prevNodeAddress) 
    readNode(node) 
    fixMap[prevNodeAddress] = &node; 
    nodeList.append(node); 

//fix pointers to new values. 
for n in nodeList: 
    for child in n.children: 
     child->node = fixMap[child->node] 

De esta manera si usted no Insert-quita nuevos nodos puede asignar un vector de una vez que el uso memoria, reduciendo su asignación a los mapas (como dijo RPG, podría ser más rápido con listas o incluso vectores).

Answer 2

Recomiendo encarecidamente el boost serialization library. Debería funcionar con las soluciones que estás usando.

Answer 3

La manera más rápida y más rápida de serialización/deserialización es escribir un bloque de memoria contigua en el disco como usted dice. Si cambió su estructura de árbol para crear esto (probablemente usando una rutina de asignación personalizada) esto sería muy fácil.

Lamentablemente no estoy tan familiarizado con QHash, pero al mirarlo parece una Hashtable en lugar de un árbol. ¿Te he entendido mal? ¿Estás usando esto para mapear nodos duplicados?

Usaría un generador de perfiles (solía usar Quantify, ahora se llama Rational PurifyPlus, pero hay muchos listed here) para encontrar dónde está usando el tiempo, pero supongo que es varias asignaciones de memoria en lugar de una sola asignación, o múltiples lecturas en lugar de una sola lectura. Para resolver ambos problemas, sabe de antemano (porque lo almacena) cuántos nodos necesita, luego escribe/lee una matriz de nodos de la longitud correcta, donde cada puntero es un índice en la matriz, en lugar de un puntero en la memoria .

Answer 4

Otra solución sería usar su propio asignador de memoria, que utilizará un espacio de memoria continuo. Luego podrá volcar la memoria tal como está y cargarla nuevamente. Es sensible a la plataforma (es decir, big endian/little endian, 32 bits/64 bits).

Answer 5

Como dijo, la asignación de objetos con nuevos puede ser lenta. Eso se puede mejorar asignando un grupo de objetos y luego usando objetos preasignados hasta que se agote el grupo. Incluso podría implementar esto para trabajar en segundo plano al sobrecargar los operadores nuevos/eliminar de la clase en cuestión.

Answer 6

En primer lugar, perfile su aplicación para que sepa lo que toma tiempo: basar la sospecha en nueva porque ha leído en algún lugar puede ser lenta o en la iteración a través del árbol no es suficiente.

Es posible que se trate de operaciones IO, tal vez su formato de archivo no sea correcto/ineficiente.

¿Tal vez tiene un defecto en alguna parte?

¿O tal vez hay un bucle cuadrático en algún lugar del que no recuerdas haber causado los problemas? :)

Mida lo que realmente toma tiempo en su caso y luego aborde el problema - le ahorrará mucho tiempo y evitará romper su diseño/código para corregir problemas de rendimiento que no existen antes de encontrar la verdadera causa

Answer 7

Su propia asignación de memoria con un operador sobrecargado new() y delete() es una opción de bajo costo (tiempo de desarrollo). Sin embargo, esto solo afecta el tiempo de asignación de memoria, y no los tiempos de Ctor. Su millaje puede variar, pero puede intentarlo.

Answer 8

Voy a ampliar mi comentario un poco:

Desde su perfilado sugiere que la serialización QHash toma mucho tiempo, creo que la sustitución de QHash con un QList produciría una mejora significativa cuando se trata de velocidad deserialización.

La serialización QHash simplemente emite los pares clave/valor, ¡pero la deserialización construye una estructura de datos hash!

Incluso si dijiste que necesitas la búsqueda rápida de hijos, te recomendaría que reemplaces QHash con una QList> como prueba. Si no hay muchos hijos para cada nodo (digamos, menos de 30), la búsqueda debe ser lo suficientemente rápida incluso con una QList. Si encuentra que QList no es lo suficientemente rápido, puede usarlo solo para la (de) serialización y luego convertirlo a un hash una vez que se haya cargado el árbol.