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 20:47:51

> > Christian> The fact that it is only sometimes used by the STL containers
> renders it
> > practically useless. You currently can't do anything useful in
> > allocator::construct, which seems to me to be counter to its original
> > intended purpose.
>
> Felipe> Unfortunately I don't know what the original intended purpose was
> there for allocator::construct.

Well, clearly it was intended as a hook for a custom allocator to do some
work. Because it is not used consistently, this work (whatever that is),
cannot be done.

> I don't really care for fast local-but-non-local allocators. They are too
> hard to prove correctness.

Hmm, but I can prove that this works at least:

    monotonic::storage<> storage;
    {
        monotonic::vector<monotonic::map<int, monotonic::string<> > >
vec(storage);
        vec.resize(1);
        vec[0][42] = "foo";
        BOOST_ASSERT(vec.get_allocator().get_storage() == &storage);
        BOOST_ASSERT(vec[0].get_allocator().get_storage() == &storage);
        BOOST_ASSERT(vec[0][42].get_allocator().get_storage() == &storage);
    }

> > [...] without at least ensuring that allocator::construct is called
> > in list::sort when it creates temporary lists, the sort method will
> create
> > lists that do not use a correct allocator.
>
> I'm not sure I follow you. Where are the lists being created? [...] All I
> see is integers being inserted in the list and a sort operation.

For instance, MSVC creates temporary lists in std::list::sort:

            const size_t _MAXBINS = 25;
            _Myt _Templist(this->_Alval), _Binlist[_MAXBINS + 1];

Note that the first temporary is made by at least passing the allocator -
but the other lists are made on the stack using default construction, so
there is no way to pass a statefull allocator as a parameter.

> This sort operation should only swap integers. And even if it did allocate
> something, it should do with my_custom_allocator.

But it doesn't - that is my entire point.

> I don't get it why you need to get construct for list nodes with
> my_custom_allocator.
> Or am I missing something? I probably am.

I am talking about entire lists here, not list nodes. One would like to
assume that list nodes are *always* dealt with correctly.

> > This is useless and contradicts
> > the entire purpose of supporting statefull allocators in the first place.
>
> I don't see it.

I am sorry if I am unable to make myself clear. I am saying that if a
container constructs instances of itself without using a rebound allocator,
it breaks any notion of safe use of stateful allocators.

> > There are other specific areas where this is a problem as well, but it
> truly
> > is a general problem.
> >
> > monotonic::containers attempt to solve this by dealing with it at the
> > allocation level, which uses traits to determine when what is being
> > constucted is in turn a monotonic container that uses the same allocator
> > type and if so, passes itself as a construction parameter in
> > allocator::construct. This means that default-constructed temporaries
> > created by the parent container will indeed use a correct statefull
> > allocator.
>
> I'm completely lost.

Perhaps my phrase "default-constructed temporaries" was misleading. What I
meant was, a container that respects stateful allocators must not do this:

    typedef container<...> This;
    This temp;

but rather do:

    This temp(get_allocator());

or:

    typename my_allocator::template rebind<This>::other
this_alloc(get_allocator());
    This *temp = this_alloc.allocate(1);
    this_alloc.construct(temp);

but not this either:

    typename my_allocator::template rebind<This>::other
this_alloc(get_allocator());
    This *temp = this_alloc.allocate(1);
    new (temp) This();

> But this can't work if the parent container simply calls
> allocator::allocate
> > then uses placement new,
>
> Why not? This should only not work when passing the same allocator
> down the inner containers. Which I advocate that it shouldn't do it
> automatically.

I agree that allocators should not be propagated into nested containers by
default.

> Ironically, if the container
> > used its allocator correctly, it would use both ::allocate and
> ::construct,
> > and the value_type may well be on the stack...
>
> I'm not sure construct should be used with value_types constructed
> outside the allocated area from the allocator. It seems wrong to me.
> But the allocator expert here is Ion. I hope he can shed some light.

I am not suggesting that construct should be called before or instead of
allocate. I am suggesting that construct should always be called after
allocate and before the object is used. You can still allocate N objects and
use M where M < N, but I suggest that construct should be called on each of
the M objects before they are used and after they are allocated for.

Failing to do so means that allocator::construct is practically useless.

> > In summary, sometimes STL containers use allocator::construct, sometimes
> > they don't, which renders allocator::construct effectively and
> practically
> > pointless.
>
> If it is done randomly, I agree it makes construct pointless.

And it is, in general, because there is no requirement in the standard which
states otherwise.

> But I'm not sure construct should be always called, and even if it is
> called.
> I'm pretty sure they shouldn't be used to pass automagically the allocator
> down with other containers.

That is a seperate issue. What I do in construct is my own business ;) I'm
just saying that with the current state of affairs, even
boost::interprocess::containers do not work with stateful allocators. For
example, interprocess::list is implemented using intrusive::list, which does
the following in its sort method:

         list_impl counter[64];

This invalidates the use of stateful allocators, because it is making
multiple temporary lists that do not use the allocator that the parent
container was supplied with.

> At least not for monotonic. It is understandable for shared memory though.
> Where we want containers
> inside other containers to work with shared memory.

   // use shared storage in a custom region
   struct my_region {};
   monotonic::map<int, monotonic::list<int, my_region, shared_access>,
my_region, shared_access> map;

This allows for multiple containers to use different regions of shared
storage, and doesnt need stateful allocators. However:

   // use local storage
   monotonic::storage<> storage;
   monotonic::map<int, monotonic::list<int> > map(storage);
   map[42].push_back(123);

In this case, I really do want the inner list to use the same (stateful)
allocator that the map uses. I tried doing that first with std::containers,
then with boost::interprocess::containers, but neither of them allow for
safe use of statefull allocators, so I had to roll my own. This wasn't so
bad however, because I wanted to change the type signatures anyway to make
it easy to change the Region and Access types.

> > By not at least ensuring that allocator::construct is called before a
> > contained object is used, the nominal support for statefull allocators in
> > the proposed boost::containers is rendered useless, and I'm back to
> making
> > my own.
>
> I don't know why.

Because I need to ensure that if a container is using a stateful allocator,
that container will respect it.

Currently monotonic works stateless with std::containers and that is fine.

It also works with stateful allocators (allowing for truly local storage on
the stack), but only with monotonic::containers. It seems that there is no
short-cut I can make by leveraging boost::interprocess containers.

Regards,
Christian.