Pool allocators, the Next Generation

[Phil Edwards]

Fragmenting memory where no memory has been fragmented bef- okay, that's
enough, I actually hate star trek.

I've been threatening to rework the pool allocator for years now.  After I
was snowed in last week, suffering from coder's block on my reflection
project, I decided it was past time to turn the diagrams on my whiteboard
into code.  And the first 90% is done.

One of the goals is to merge (if possible) the actively maintained
stl_alloc.h with the flaming mess of untouched code that is
pthread_allocimpl.h.  There is a good background thread here:

    http://gcc.gnu.org/ml/libstdc++/2001-11/msg00229.html

Three more messages on performance testing are here:

    http://gcc.gnu.org/ml/libstdc++/2003-02/subjects.html#00098

Stefan's recent post about making a patch for an MATDS[*] prompted me to
write this; I'll be writing up my notes once I get home.  All of the careful
work that he has done, plus the tuning in the original pthread_allocimpl.h,
needs to be preserved in my push for genericity.


For this email I'll call the new pool allocator "__foo".  Suggestions
solicited.

If you've read Alexandrescu's book, or have heard of the "policy classes"
that feature so prominently in it, then you have an idea of what I want
to accomplish.  A pool allocator is (in concept) extremely configurable;
we currently have hardcoded decisons in many places, but we should be able
to get a customized p.a. by "policy composition".  For example, my local
patch has a declaration like

  template<int __inst,
           typename _Locking,
           typename _FreeListParams,
           typename _FreeStore,
               [one more class param, more info later]
          >
    class __foo { ... };

Then we can compose some predefined allocators using predefined policies:

  // ignoring namespaces; __foo is in std, others are in __gnu_cxx
  typedef __foo<0,
                _GThreadsLocking,         // use gthr.h interface
                _NormalFreeListParams,    // alignment, max request size, etc
                _NewFreeStore,            // new/delete as underlying free store
                [shared]
               >  __alloc;

  typedef __foo<0,
                _NoLocking,
                _NormalFreeListParams,
                _NewFreeStore,
                [shared]
               >  __single_client_alloc;

  typedef __foo<0,
       ...

Loren's recent email raises the possibility of changing default allocators
based on platform configuration.  I think this would be easier given
policy composition.

Also, end-users would then be able to get custom pool allocators by writing
(squished for 80 columns)

  typedef
   std::__foo
    <42,                               // reserved for this project
     __gnu_cxx::_PThreadsLocking,      // forget gthr.h, use pthreads directly
     MyHugeListParams,                 // provided by user
     __gnu_cxx::_MallocFreeStore,      // malloc/free as underlying free store
     [per-thread]
    >  project_specific_alloc;

Then by using MyProject::SharedMemoryFreeStore in the fourth parameter,
the user suddenly gets a pool in shared mem, etc.


I plan on providing enough predefined policies ("policies" == "type arguments
to the p.a. template") to cover the functionality we currently have.
Then adding new policies should be much easier for both us and for end users.



Phil
[*] MT Allocator That Doesn't Suck

-- 
I would therefore like to posit that computing's central challenge, viz. "How
not to make a mess of it," has /not/ been met.
                                                 - Edsger Dijkstra, 1930-2002