title: What's the fastest way to deserialize a tree in C++
body: <p>I'm working with a not so small tree structure (it's a Burkhard-Keller-Tree, > 100 MB in memory) implemented in C++. The pointers to the children of each node are stored in a QHash. </p>
  
  <p>Each node x has n children y[1] ... y[n], the edges to the children are labeled with the edit distance d(x, y[i]), so using a hash to store the nodes is an obvious solution.</p>
  
  <pre><code>class Node {
      int value;
      QHash&lt;int, Node*&gt; children;
      /* ... */
  };
  </code></pre>
  
  <p>I also want to serialize and deserialize it into a file (I currently use a QDataStream). The tree is just built once and doesn't change then.</p>
  
  <p>Building the tree and deserializing it is rather slow. I'm loading the tree in the obvious way: Recursively building each node. I think this is suboptimal due to the many nodes that are created seperately with the <code>new</code> operator. I read somewhere that <code>new</code> is pretty slow. The initial build is not a big problem because the tree's rather stable and doesn't have to be rebuilt very often. But loading the tree from a file should be as fast as possible.</p>
  
  <p>What's the best way to accomplish this?</p>
  
  <p>It must be much better to save the whole tree in a single memory block with adjacent nodes. Serializing and deserializing would then be reduced to save and load the whole block, which I have to allocate just once.</p>
  
  <p>But to implement this I would have to re-implement the QHash, AFAIK. </p>
  
  <p>What would you do to speed up the deserialization?</p>
  
  <p><strong>Addendum</strong></p>
  
  <p>Thank you for your suggestion to do some profiling. Here are the results:</p>
  
  <p>While rebuilding the tree from a file</p>
  
  <pre><code> 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
  </code></pre>
  
  <p>So it's definitly not my new calls which cause the delay but the rebuild of the QHash objects at every node. This is basically done with:</p>
  
  <pre><code> QDataStream in(&amp;infile);
   in &gt;&gt; node.hash;
  </code></pre>
  
  <p>Do I have to dig into QHash and look what's going on under the hood there? I think the best solution would be a hash object that can be serialized with a single read and write operation without the need to rebuild the internal data structure.</p>