Boost logo

Boost :

Subject: Re: [boost] Proposal: Monotonic Containers - Comparison with boost::pool, boost::fast_pool and TBB
From: Christian Schladetsch (christian.schladetsch_at_[hidden])
Date: 2009-06-23 15:46:21

On Wed, Jun 24, 2009 at 3:49 AM, Stewart, Robert <Robert.Stewart_at_[hidden]>wrote:

> Simonson, Lucanus J wrote
> On Tuesday, June 23, 2009 11:38 AM
> >
> > For multiple threads to
> > use the allocator without interacting (we would prefer not to
> > pay for locks if we aren't actually sharing information
> > between threads) the allocator must differ by type. The only
> > way that can be accomplished is if every thread calls a
> > different function with a diferent instantiation of the
> > allocator. We don't want to instantiate dozens of copies of
> > the same functions at compile time to support many threads.
> Only the storage need be unique in each case. Factor out the code that
> doesn't depend upon the tag type -- the behavior -- from that which does.
> That said, it would be painful to create unique tags for each thread. Is
> it a problem for the allocator to look in TLS for that thread's storage?

I have thought on this and refactored the allocator signature to deal with
both of these issues:

template <
   class T
   , class Region = default_region_tag
    , class Access = default_access_tag>
struct allocator;

The basic usage is:

struct region0 {};
struct region1 {};
struct region2 {};

    // use default region and access
    std::list<int, monotonic::allocator<int> > list;

    // use specific region and access
    std::list<int, monotonic::allocator<int, region0,
monotonic::shared_access_tag> > list;
    std::list<int, monotonic::allocator<int, region0,
monotonic::thread_local_access_tag> > list;
    // equivalently:
    std::list<int, monotonic::shared_allocator<int, region0> > list;
    std::list<int, monotonic::thread_local_allocator<int, region0> > list;

    // equivalently, using wrapped container types defined in
    monotonic::list<int> list;
    monotonic::list<int, region0, monotonic::shared_access_tag> list;
    monotonic::list<int, region1, monotonic::thread_local_access_tag> list;

    // use different regions
    monotonic::map<int, monotonic::list<monotonic::string<region2>,
region1>, region0> map;


This deals with allocation from different regions based on a tag-type, and
also allows the user to specifiy what access type to use.

The remaining issue is that of local storage:

    monotonic::local<region0> storage0;
    monotonic::local<region1> storage1;
        std::list<int, monotonic::allocator<int, region0> > list0;
        std::list<int, monotonic::allocator<int, region1> > list1;
        fill_n(back_inserter(list0), 100, 42);
        fill_n(back_inserter(list1), 100, 42);

        std::basic_string<char, std::char_traits<char>,
monotonic::allocator<char, region0> > str("foo");
        str += "bar";
} // region0 and region1 will be reset automatically

Now, in this last case, it can be said that this is not re-entrant which is
correct. However, there is a simple idiom that can be used:

template <class Storage>
void Reenter(Storage &store, size_t count)
    if (count-- == 0) return;

    // use the Storage type to make new allocators
    typedef std::basic_string<char, std::char_traits<char>, typename
Storage::template allocator<char>::type> String;
    std::list<String, typename Storage::template allocator<String>::type>
    /// ... use list and string types... they will use the storage correctly

    // can also use storage directly:
    char *bytes = store.allocate_bytes<123>();
    string &str = store.create<string>("foo");
    array<int, 300> &nums = store.create<array<int, 300> >();


    Reenter(store, count);

struct my_local_region {};
void Start()
     monotonic::local<my_local_region/*, access_type_tag*/> storage;
     Reenter(storage, 500);
} // storage is reset on exit

Of course, Start() is still not reentrant. It can't be, because it uses a
static global. However, Reenter() is. It's the best that we can do.

I did a test that used this idiom over using a normal allocator and thrashed
a list of strings. The monotonic answer was twice the speed. Sure, it is
more work, but twice the speed is twice the speed.

I am interested to hear what people think of the new allocator model with
tags for Region and Access, and the local model that is based on tags as


Boost list run by bdawes at, gregod at, cpdaniel at, john at