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: Felipe Magno de Almeida (felipe.m.almeida_at_[hidden])
Date: 2009-06-23 21:27:27

On Tue, Jun 23, 2009 at 9:47 PM, Christian
Schladetsch<christian.schladetsch_at_[hidden]> wrote:
>> > 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.

OK. But what work was that envisioned?

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

Can you really? I've said local-but-non-local. This example uses a
stateful-allocator-aware-container.
You've snipped what I was answering to:

> > > Back to the idea of nested containers using the same allocator. I agree that
> > > there is a case to be made against automatically spreading an allocator down
> > > into contained types. monotonic currently solves this by using regions:
> > >
> > >    struct my_region{};
> > >    std::map<int, std::list<int, monotonic::allocator<int, my_region>>,
> > > std::less<int>, monotonic::allocator<int, my_region> > map;
> > >
> > > and that works - both the map and the inner list will use the same storage
> > > and both can be defalt constructed. But it doesn't allow for truly local
> > > storage and doesnt use a stateful allocator.

Here you're using C++03 containers and tags to create stateless
allocators. Which have their own problems w.r.t. threading and scoping
allocator lifetime.
You must ensure you don't use inadvertedly the same tag somewhere
else. And if you do, that the other is correct w.r.t threading and
lifetime etc.
This is just too much burden to reason about when all you want is
scoped allocation.

>> > [...] 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.

But MSVC list is not stateful-allocator-aware. I don't see how that
can be used as an example.
It doesn't have anything to do with construct. It has to do with
different allocators instance always comparing equal.
Which I'm arguing to not have any support at all.

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

It doesn't in C++03 containers. That's not relevant.

[snip]

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

Of course it shouldn't. But what it have to do with construct?

> but rather do:
>
>    This temp(get_allocator());

Correct.
[snip]

>> 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 didn't assume that.

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

But you seem to be advocating for construct to be called on local
value_types as well. Or am I wrong?

[snip]

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

Of course. But have you checked the allocators proposals on this issue
for C++0x?
That's what I think you should concentrate on before adding
requirements to containers.

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

I don't see how. You posted an example from MSVC STL to prove that
interprocess containers don't work?

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

I've grepped my boost copy and couldn't find this line. Could you
point it to me?
And which boost version are you using?

>> 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:

Well, as I've explained before, I don't really care for stateless
allocators for local storage
since they are too error prone. I'm not sure how others feel about it.

[snip]

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

Sure. I just don't know what it has to do with allocator::construct.

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

I think it is too error prone.

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

Because you need construct? It doesn't seem to make sense to me.
If you find a bug in interprocess w.r.t stateful allocators, then
please report it.

> Regards,
> Christian.

-- 
Felipe Magno de Almeida