Qual è il modo più veloce per deserializzare un albero in C++

Question

Sto lavorando con una struttura ad albero non troppo piccola (è un albero Burkhard-Keller,> 100 MB di memoria) implementato in C++. I puntatori ai figli di ciascun nodo sono memorizzati in un QHash.

Ogni nodo x ha n figli y [1] ... y [n], i bordi dei bambini sono etichettati con la distanza di modifica d (x, y [i]), quindi utilizzando un hash per memorizzare il i nodi sono una soluzione ovvia.

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

voglio anche serializzare e deserializzare in un file (Attualmente uso un QDataStream). L'albero è appena costruito una volta e non cambia poi.

Costruire l'albero e deserializzare è piuttosto lento. Sto caricando l'albero in modo ovvio: costruendo ricorsivamente ciascun nodo. Penso che questo non sia ottimale a causa dei molti nodi creati separatamente con l'operatore new. Ho letto da qualche parte che lo new è piuttosto lento. La build iniziale non è un grosso problema perché l'albero è piuttosto stabile e non deve essere ricostruito molto spesso. Ma caricare l'albero da un file dovrebbe essere il più veloce possibile.

Qual è il modo migliore per farlo?

Deve essere molto meglio salvare l'intero albero in un singolo blocco di memoria con nodi adiacenti. La serializzazione e la deserializzazione sarebbero quindi ridotte per salvare e caricare l'intero blocco, che devo allocare solo una volta.

Ma per implementarlo dovrei reimplementare QHash, AFAIK.

Cosa faresti per accelerare la deserializzazione?

Addendum

Grazie per il suggerimento di fare un po 'di profilazione. Ecco i risultati:

Mentre ricostruire l'albero da un file

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 

Quindi non è sicuramente mie nuove chiamate che causano il ritardo, ma la ricostruzione del QHash oggetti in ogni nodo. Questo è fondamentalmente fatto con:

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

Devo scavare QHash e guardate cosa sta succedendo sotto il cofano c'è? Penso che la soluzione migliore sarebbe un oggetto hash che può essere serializzato con una singola operazione di lettura e scrittura senza la necessità di ricostruire la struttura interna dei dati.

Answer 1

Un altro approccio sarebbe quello di serializzare i puntatori e ripristinarli durante il caricamento.Voglio dire:

Serializzare:

nodeList = collectAllNodes(); 

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

deserializzazione:

//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] 

In questo modo se non si insert-rimuovere nuovi nodi è possibile assegnare un vettore, una volta e l'uso che memoria, riducendo la tua allocazione alle mappe (come ha detto rpg, potrebbe essere più veloce con liste o persino vettori).

Answer 2

Consiglio vivamente il boost serialization library. Dovrebbe funzionare con le soluzioni che stai utilizzando.

Answer 3

Il modo più veloce di serializzare/deserializzare è scrivere un blocco di memoria contigua sul disco come dici tu. Se hai modificato la struttura ad albero per crearlo (probabilmente usando una routine di allocazione personalizzata) sarebbe molto semplice.

Sfortunatamente non sono così familiare con QHash, ma dal guardarlo sembra un Hashtable piuttosto che un albero. Ti ho frainteso? Stai usando questo per mappare i nodi duplicati?

Vorrei usare un profiler (ho usato Quantify, ora chiamato Rational PurifyPlus, ma ci sono un sacco listed here) per trovare dove stai usando il tempo, ma suppongo che sia più allocazioni di memoria piuttosto che una singola allocazione o più letture piuttosto che una singola lettura. Per risolvere entrambi questi problemi si conosce in anticipo (perché lo si memorizza) quanti nodi sono necessari, quindi si scrive/legge un array di nodi della lunghezza corretta, in cui ogni puntatore è un indice nell'array, piuttosto che un puntatore in memoria .

Answer 4

Un'altra soluzione sarebbe utilizzare il proprio allocatore di memoria, che utilizzerà uno spazio di memoria continuo. Quindi sarai in grado di scaricare la memoria così com'è e ricaricarla. È sensibile alla piattaforma (cioè big endian/little endian, 32 bit/64 bit).

Answer 5

Come hai detto, l'allocazione di oggetti con nuovi potrebbe essere lenta. Ciò può essere migliorato allocando un pool di oggetti e quindi utilizzando oggetti preassegnati finché il pool non è esaurito. Potresti anche essere in grado di implementarlo per lavorare in background sovraccaricando gli operatori new/delete della classe in questione.

Answer 6

Prima di tutto - profila la tua applicazione in modo che tu sappia cosa richiede tempo: basare il sospetto su nuovo perché hai letto da qualche parte che può essere lento o sull'iterazione attraverso l'albero non è sufficiente.

È possibile che siano le operazioni di I/O - forse il formato del file non è corretto/inefficiente.

Forse hai un difetto da qualche parte?

O forse c'è un ciclo quadratico da qualche parte che non ricordi di aver causato i problemi? :)

Misurare ciò che richiede davvero tempo nel tuo caso e quindi affrontare il problema - ti farà risparmiare un sacco di tempo e eviterai di rompere il tuo design/codice per risolvere problemi di prestazioni che non esistono prima di trovare la vera causa.

Answer 7

L'allocazione di memoria propria con un operatore sovraccarico new() ed delete() è un'opzione a basso costo (tempo di sviluppo). Tuttavia, ciò influisce solo sul tempo di allocazione della memoria e non sui tempi del Ctor. Il tuo chilometraggio può variare, ma potrebbe valere la pena provare.

Answer 8

mi espando il mio commento un po ':

Dal momento che il profiling suggerisce che la serializzazione QHash prende la maggior parte del tempo, credo che la sostituzione con un QHash QList produrrebbe un miglioramento significativo quando si tratta di velocità di deserializzazione.

La serializzazione QHash restituisce solo le coppie chiave/valore, ma la deserializzazione costruisce una struttura dati hash!

Anche se hai affermato che è necessaria la ricerca rapida figlio, ti consiglio di provare a sostituire QHash con QList> come test. Se non ci sono molti bambini per ogni nodo (per esempio, meno di 30), la ricerca dovrebbe essere abbastanza veloce anche con una QList. Se scopri che QList non è abbastanza veloce, puoi ancora usarlo solo per (de) serializaton e successivamente convertirlo in un hash una volta che l'albero è stato caricato.