title: Rust - Why such a big difference in memory usage between malloc/alloc and more 'idiomatic' approaches
body: <p>I've been using and modifying this library <a href="https://github.com/sile/patricia_tree" rel="nofollow noreferrer">https://github.com/sile/patricia_tree</a></p>
  <p>One thing that bothered a bit was how much unsafe was used in node.rs, particularly, it's defined as just a pointer to some heap location. When doing the first benchmark listed on the readme page (wikipedia inputs), the PatriciaSet uses ~700mb (PatriciaSet is just holding a Node at it's root)</p>
  <pre><code>pub struct Node&lt;V&gt; {
      // layout:
      // all these fields accessed with ptr.offset
      //   - flags: u8
      //   - label_len: u8
      //   - label: [u8; label_len]
      //   - value: Option&lt;V&gt;
      //   - child: Option&lt;Node&lt;V&gt;&gt;
      //   - sibling: Option&lt;Node&lt;V&gt;&gt;
      ptr: *mut u8,
      _value: PhantomData&lt;V&gt;,
  }
  </code></pre>
  <p>and uses <code>malloc</code> for allocation:</p>
  <pre><code>        let ptr = unsafe { libc::malloc(block_size) } as *mut u8;
  </code></pre>
  <p>I was told this memory is not aligned properly, so I tried to add the new alloc api and use Layout/alloc, this is also still not aligning properly just seems to 'work'. <a href="https://github.com/sile/patricia_tree/pull/6" rel="nofollow noreferrer">full pr</a></p>
  <pre><code>       let layout = Layout::array::&lt;u8&gt;(block_size).expect(&quot;Failed to get layout&quot;);
         let ptr = unsafe { alloc::alloc(layout) as *mut u8 };
  </code></pre>
  <p>This single change, which also holds the <code>layout</code> in the block of memory pointed to by <code>ptr</code>, caused memory consumption to go up 40% under the performance tests for very large trees. The layout type is just 2 words wide, so this was unexpected. For the same tests this uses closer to ~1000mb (compared to previous 700)</p>
  <p>In another attempt, I tried to remove most of the unsafe and go with something a bit more rust-y <a href="https://github.com/sile/patricia_tree/pull/7/files#diff-12d610bc541176e32ea0df8d15d0a369L43" rel="nofollow noreferrer">full pr here</a></p>
  <pre><code>pub struct Node&lt;V&gt; {
      value: Option&lt;V&gt;,
      child: Option&lt;*mut Node&lt;V&gt;&gt;,
      sibling: Option&lt;*mut Node&lt;V&gt;&gt;,
      label: SmallVec&lt;[u8; 10]&gt;,
      _value: PhantomData&lt;V&gt;,
  }
  </code></pre>
  <p>creating the node in a manner you may expect in rust</p>
  <pre><code>        let child = child.map(|c| Box::into_raw(Box::new(c)));
          let sibling = sibling.map(|c| Box::into_raw(Box::new(c)));
          Node {
              value,
              child,
              sibling,
              label: SmallVec::from_slice(label),
              _value: PhantomData,
          }
  </code></pre>
  <p>Performance wise, it's about equivalent to the original unmodified library, <em>but</em> it's memory consumption appears to be not much better than just inserting every single item in a HashSet, using around ~1700mb for the first benchmark.</p>
  <p>The final data structure which uses node is a compressed trie or a 'patricia tree'. No other code was changed other than the structure of the <code>Node</code> and the implementations of some of its methods that idiomatically fall out of those changes.</p>
  <p>I was hoping someone could tip me off of a what exactly is causing such a drastic difference in memory consumption between these implementations. In my mind, they should be about equivalent. They all allocate around the same number of fields with about the same widths. The unsafe first one is able to store a dynamic label length in-line, so that could be one reason. But smallvec should be able to do something similar with smaller label sizes (using just Vec was even worse).</p>
  <p>Looking for any suggestions or help on why the ending results are so different. If curious, the code to run these is <a href="https://github.com/sile/patricia_tree#benchmarks" rel="nofollow noreferrer">here</a> though it is spread across the original authors and my own repo</p>
  <p>Tools for how to investigate the differences between these would be open to hearing that as well!</p>