title: strategy to allocate/free lots of small objects
body: <p>I am toying with certain caching algorithm, which is challenging somewhat.
  Basically, it needs to allocate lots of small objects (double arrays, 1 to 256 elements), with objects accessible through mapped value, <code>map[key] = array</code>.  time to initialized array may be quite large, generally more than 10 thousand cpu cycles.</p>
  
  <p>By lots I mean around gigabyte in total.  objects may need to be popped/pushed as needed,  generally in random places, one object at a time.  lifetime of an object is generally long, minutes or more, however, object may be subject to allocation/deallocation several times during duration of program.</p>
  
  <p>What would be good strategy to avoid memory fragmentation, while still maintaining reasonable allocate deallocate speed?</p>
  
  <p>I am using C++, so I can use new and malloc.
  Thanks.</p>
  
  <p>I know there a similar questions on website, <a href="https://stackoverflow.com/questions/2156745/efficiently-allocating-many-short-lived-small-objects">Efficiently allocating many short-lived small objects</a>, are somewhat different, thread safety is not immediate issue for me.</p>
  
  <p>my development platform is Intel Xeon, linux operating system.
  Ideally I would like to work on PPC linux as well, but it is not the most important for me.</p>