Re: [boost] Proposal: Monotonic Containers - Comparison with boost::pool, boost::fast_pool and TBB

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 {};

BOOST_AUTO_TEST_CASE(test_shared_allocation)
{
    // 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/container/*.hpp:
    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;
}

See https://svn.boost.org/svn/boost/sandbox/monotonic/boost/monotonic/

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:

BOOST_AUTO_TEST_CASE(test_local)
{
    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>
list;
    /// ... 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> >();

    store.destroy(str);

    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
well.

Regards,
Christian.