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 19:39:37

On Tue, Jun 23, 2009 at 7:14 PM, Christian
Schladetsch<christian.schladetsch_at_[hidden]> wrote:
>>
>>  Christian> The other thing I'd like is for map<> etc to ensure that new
>>> containers
>>> added to them use a rebound allocator. I do this for monotonic containers
>>> via a trait is_monotonic<Container>;
>>>
>>
>> Felipe> I don't think you should do that. It is unintuitive IMHO. Elements
>> inside the map are different beasts. If the user wants to use the same
>> allocator. Then he shouldn't use operator[]. Which default-constructs the
>> object.
>
> Irrespective of that issue, surely there is a case to be made for
> normalising the use of allocator::construct?

I think so. But we should do so with C++0x in mind. I believe we want
these newer allocators to work with the new C++0x containers right?

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

Unfortunately I don't know what the original intended purpose was
there for allocator::construct.

> By ensuring that it is always called before an object is used, we can start
> to use it how it was first intended.

How is that?

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

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

> So, consider the following, which purports to use a statefull allocator with
> a container that norminally respects statefull allocators:
>
>   boost::containers::list<int, my_custom_allocator<int> >
> list(stateful_allocator);
>   generate_n(back_inserter(list), 100, rand);
>   list.sort();
>
> In this case, 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.
This sort operation should only swap integers. And even if it did allocate
something, it should do with my_custom_allocator. 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.

> This is useless and contradicts
> the entire purpose of supporting statefull allocators in the first place.

I don't see it.

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

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

> or if the parent container creates
> default-constructed value_types on the stack.

What is the problem with that?

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

> 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. 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. At least not for monotonic. It
is understandable for shared memory though. Where we want containers
inside other containers to work with shared memory.

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

> Regards,
> Christian

Regards,
-- 
Felipe Magno de Almeida