[boost] [pool] Tuning the growth characteristics of pool

From: Chris Newbold (Chris.Newbold_at_[hidden])
Date: 2008-03-26 19:25:04

Greetings.

We've started introducing boost::pool at various places in our software
in order to manage allocation of small, short-lived objects. We have run
into some difficulty, however, with the algorithm governing the growth
of the blocks allocated internally.

The currently implementation unconditionally doubles the number of
chunks in each subsequent block. This works well for small to medium
sized pools, but ends up becoming wasteful and, ultimately,
scalability-limiting for pools holding several million objects.

Right now we're using the get_next_size() and set_next_size() accessors
to meddle with the growth curve and to enforce an absolute limit on
next_size. This is somewhat clumsy, however, requiring us to wrap
boost::pool with additional logic to inspect next_size and take evasive
action when we don't like the new value.

I think there might be value in formally parameterizing the algorithm
used to expand the pool. My first thought on an interface for
controlling the growth algorithm was to add it to the UserAllocator
interface. Here's an example of how this might look with the default
algorithm hoisted to default_user_allocator_new_delete:

        // Default UserAllocator implementation for boost::pool;
        // the block size is doubled on each allocation
        struct default_user_allocator_new_delete
        {
                typedef std::size_t size_type;
                typedef std::ptrdiff_t difference_type;

                static char* malloc(const size_type bytes) { ... }
                static void free(char* const block) { ... }

                static size_type next_size(size_type size) {
                        return size << 1;
                }	
        };

        // An implementation of the UserAllocator interface for
        // use with boost::pool which allocates fixed-sized blocks
        // of 65536 chunks.
        struct fixed_block_size_allocator
                : public default_user_allocator_new_delete
        {
                static size_type next_size(size_type /* ignored */) {
                        return 2 << 15;
                }
        };

One problem I can see with this approach is that "more clever" growth
algorithms may want data assigned at runtime-- e.g. an absolute limit at
which to stop doubling the block size. This need could be accommodated
by making UserAllocators be copy-constructible and changing the
boost::pool constructor to take an instance to UserAllocator to be
copied and kept internally.

Another alternative would be to keep the growth algorithm parameter
separate from UserAllocator:

        // The default pool growth algorithm: it unconditionally doubles
        // the block size on each successive allocation
        struct default_growth_algorithm
        {
                static size_t operator()(size_t prev_size) {
                        return prev_size << 1;
                }
        };

        template <typename UserAllocator =
default_user_allocator_new_delete
                    typename GrowthAlgorithm = default_growth_algorithm>
        class pool;

The same comments about the potential need to pass a copy-constructible
instance of the algorithm to the boost::pool constructor apply to this
solution too.

I am more than willing to prototype some changes in the code if there is
interest in extending boost::pool in this manner.

--
Chris Newbold			cnewbold_at_[hidden]
The MathWorks, Inc.		+1.508.647.8077