title: Efficient heap-manager for heavy churn, tiny allocs?
body: <p>I'm looking for ideas for a heap-manager to handle a very specific situation: Lots and lots of very small allocations, ranging from 12 to 64 bytes each. Anything bigger, I will pass on to the regular heap-manager, so only tiny blocks need be catered for. Only 4-byte alignment is needed.</p>
  
  <p>My main concerns are</p>
  
  <ol>
  <li>Overhead. The regular libc heap will typically round up an allocation to a multiple of 16 bytes, then add another 16 byte header - this means over 50% overhead on a 20-byte allocation, which sucks.</li>
  <li>Performance</li>
  </ol>
  
  <p>One helpful aspect is that Lua (which is the user of this heap) will tell you the size of the block it's freeing when it calls free() - this may enable certain optimisations.</p>
  
  <p>I'll post my current approach, which works ok, but I'd like to improve on it if at all possible. Any ideas?</p>