Re: [boost] Proposal: Monotonic Containers

Subject: Re: [boost] Proposal: Monotonic Containers
From: Christian Schladetsch (christian.schladetsch_at_[hidden])
Date: 2009-06-10 04:16:08

Hi David,

auto_buffer is, in fact, related, inasmuch as it also attempts to use the
>> stack for storage.
>>
>
> Ok, so you could use Thorsten's auto_buffer as your storage, which actually
> would give you, potentially, the best of two worlds (allocation speed and -
> you seem to push this angle - cache) and dynamic heap beyond that initial
> segment.

Cache coherency is King!

auto_buffer<T> is not analogous to monotonic::inline_storage<N>

 However, boost::monotonic provides an allocator that means that *all* STL
> containers - and other ones - can use the stack for storage. Or the heap.
>

NOTE: your "storage_base" is not a base abstraction at all, but a
> "heap_storage"; having a non-leaf having a concrete but totally different
> behavior from its leaf child is less than beautiful.

I agree that the current implementation is not ideal, but I don't follow
what you mean here. storage_base may be ugly, but it is also required so
that different containers can use the same storage.

I agree that it could be improved. I had a lot of problems with the more
fundamental problems of std::allocator

> Why is the behavior of whether to pick the heap storage ("storage_base"...
> ugh) or stack (if not embedded in a heap-allocated object...) decided at
> runtime, via that polymorphic "storage_interface"? It is set at the creation
> of the allocator, so why not make it a type parameter of the allocator, with
> a default to, say, "inline_storage"? Do you think it is important to have
> two containers sharing the exact same type even when one uses "storage_base"
> and the other "inline_storage"?

I agree that there are some ugly aspects to the current proposal. However,
it also works as advertised which is very important.

I hate the current implementation's basis of using a virtual base class. It
is anathema to me. I only presented it as it stands because I was more
concerned about adoption of the general idea, rather than the smaller and
less-relevant details of the implementation. I think most of us could write
this from scratch with no problem, and without virtuals.

Point being, if the idea is adopted, then yes there are optimisations and
beautifying to do.

That said, you may have also missed the point that multiple containers can
use the same storage - which may be on the heap or the stack.

> In that respect, auto_buffer<T> is a subset of the proposed
> boost::monotonic::vector<T>.
>

I still fail to see why you wrap all those containers, instead of providing
> just that allocator. Is the only reason what I just mentioned, to keep the
> storage mechanism variable ("storage_base" or "internal_storage") while the
> container types equal? That is the only somewhat logical rationale for me.
> Regarding injecting stuff, such as your allocator, in a template class
> higher up the hierarchy (such as in std::vector), you should have a look at
> my proposal at a "type injector":
> http://blog.davber.com/2006/07/24/hierarchy-generation-in-c/

I will consider dropping the idea of including the containers on top of the
allocator.

The 'wrapping of the containers' is very small, very straight-forward, only
requires the passing-forward of construction parameters, and is completely
safe as none of them have any state outside of their base classes.

Inheriting from the std::containers also means that existing code that
pattern-matches against the std::containers will also match against
monotonic::containers. They are functionally equivalent, and in-memory
equivalent. They are the same thing, except that monotonic::containers must
be given either an allocator or storage from which to make one.

The fact that STL containers do not have virtual dtors is not relevant.
There is no state in the proposed monotonic containers that is not in
std::containers.

There is a case for:

boost::monotonic::inline_storage<N> storage;
std::vector<int, boost::monotonic::allocator<int> > v(storage); // (A)

versus:
boost::monotonic::inline_storage<N> storage;
boost::monotonic::vector<int> v(storage); // (B)

but what about:
boost::monotonic::inline_storage<N> storage;
boost::monotonic::map<int, float> v(storage);

versus:
boost::monotonic::inline_storage<N> storage;
std::map<int, float, std::less<int>, boost::monotonic::allocator<int> >
v(storage);

My main concern would be that people just aren't comfortable with the idea
of using custom allocator types, but they will accept the idea of needing to
pass the storage in once they realised that they needed a monotonic
container.

There are other important issues, like having to give the predicate type for
the associative containers first.

If I didn't think it was important, I wouldn't have proposed the library in
the first place. Given that I think that it's important, it is also
important to me that the usage is clean. (A) above may be `better`,  but (B)
is cleaner.

Take care.
>
> /David

Cheers,
Christian