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 23:30:45

>
> > Well, clearly [allocator::construct] 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 think that can be answered, but isn't that beside the point? If
construct can only do placement-new, then it is pointless.

For construct to do something more than just placement-new, then it has to
be called every time before a newly allocated object is used for the first
time.

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

I have struggled to understand what you mean by "local-but-non-local". Do
you mean that it is kinda local, but maybe not because other areas of the
program could still access the storage by using the same region-tag-type?

In this case, I don't think that is a design flaw. It may well be desirable
to have different regions for different uses that should be available
globally. For example, I can imagine using a distinct region for strings
that is shared across the program. A different region for, say, a physics
simulator, and a different region again for the deferred renderer and
another, possiblly shared region for the network layer. Of course I am using
a game system as an example here, but the same is true in general.

In any case, there are many ways to ensure that the tag type is safely
hidden; either in a namespace or as a private structure in a class type.

If this isn't what you meant by 'local but not local', sorry but I don't
follow.

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

Stateless allocators that use shared or thread-local storage won't have any
problem with threading. I do not know what you mean by "scoping allocator
lifetime" in the context of a stateless allocator.

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

As mentioned above, it is quite easy to ensure that region tags have the
correct visibility. Plus, monotonic allocators take a second tag-type that
specifies the access policy for the storage: either default (no locking),
shared (guarded by a mutex), or thread-local.

monotonic::allocator<int> global;
monotonic::allocator<int, my_region> distinct;
monotonic::allocator<int, my_region, shared_tag> distinct_guarded;
monotonic::allocator<int, my_region, local_tag> distinct_thread_local;

Each uses a distinct storage object. If you use a distinct_thread_local
allocator in one place, and use another distinct_thread_local allocator
somewhere else, then by definition you wish to use the same storage for
both. I guess you are saying that it is possible to use them together
inadvertently?

> This is just too much burden to reason about when all you want is
> scoped allocation.

If by this you mean scoped storage, then I am confused. You can't really
have scoped storage with a stateless allocator.

I currently have two ways of using monotonic allocators. The first, and
default, way, is stateless. These stateless allocators are delimited by
regions, and may be shared or use thread-local storage.

The second way is to make a storage object on the stack or the heap, and use
that to initialise a container that uses a monotonic allocator. This is the
statefull way of using it. This mode doesnt work with C++03 containers, but
as it turns out will indeed work with interprocess::containers, iff I wrap
them carefully.

[snip side-track about list::sort. as pointed out by Steven, the temporary
> lists made by interprocess::list::sort are benign]
>
> But you seem to be advocating for construct to be called on local
> value_types as well. Or am I wrong?

No, I just want a container system that always calls allocator::construct
before using an allocated object. I want this because I'd like to do
something in allocator::construct other than placement new.

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

I'll read it again.

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

I was just making the case that since construct is not used uniformly, it
cannot be used to propagate stateful allocators down into nested containers.
I fully understand that this is not something that you would always want to
do, but it could be done if construct was used uniformly.

> > Currently monotonic works stateless with std::containers and that is
> fine.
>
> I think it is too error prone.

I'd like to address any concerns you have. How could it be misused? By
inadvertently sharing region tags? I really don't think that is an issue.

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

I need construct to be called so that nested containers have a chance to
receive the correct stateful allocator.

> If you find a bug in interprocess w.r.t stateful allocators, then
> please report it.

I'm sticking with a thin wrapping of interprocess containers. I just got
spooked by the temporaries I saw, but they are not a problem because as
Steven pointed out those temporaries do not do allocation. It is a problem
in other STL implementations however.

Regards,
Christian.