Re: [boost] Proposal: Monotonic Containers

Subject: Re: [boost] Proposal: Monotonic Containers
From: David Bergman (David.Bergman_at_[hidden])
Date: 2009-06-10 13:49:17

On Jun 10, 2009, at 4:32 AM, Christian Schladetsch wrote:

> I was wrong.
>
> boost::monotonic::inline_storage<N> storage;
> std::map<int, float, std::less<int>,  
> boost::monotonic::allocator<int> >
> v(storage);
>
> Won't even work. Storage is not the allocator. Rather, to not use the
> container overloads would require:
>
> boost::monotonic::inline_storage<N> storage;
> std::map<int, float, std::less<int>,  
> boost::monotonic::allocator<int> >
> v(boost::monotonic::allocator<int>(storage));
>
> Which is dramatically even worse again.

Yes, it is sad that C++ does not have parameterized typedef's, like  
haXe (http://www.haxe.org), but if you at least abstract away the  
specific containers, by:

template<template C, typename T>
class map : public C<T, std::less<T>, boost::monotonic::allocator<T> > {
        typedef C<T, std::less<T>, boost::monotonic::allocator<T> > base_cont;
        ....
};

and get rid of that polymorphic "storage_base", or at least use a good  
default; you should actually make it a policy instead of having to  
pass a "storage_base" (polymorphic) object to the constructor of your  
container.

Also, that the default constructor of your containers create a  
container that throws on any addition of elements is perhaps not  
ideal. Even the fact that the user has to make sure that this  
"storage_base" object reside in a safe place for the lifespan of your  
container is sad.

> On Wed, Jun 10, 2009 at 8:16 PM, Christian Schladetsch <
> christian.schladetsch_at_[hidden]> wrote:
>
>> 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!

Yes, I have noticed that you push that angle very hard.

Three comments:

1. In most high-performance applications I have written, the number of  
re-allocations of std::vector (or similar abstractions in other  
languages) has been quite low, and the cache hit ratio pretty good,  
with that quite firm contiguous block. You seem to think that there is  
something magical about stack space relative heap space here. Can you  
explain that in more detail: i.e., why is cache coherency for a fixed  
block, such as your "internal_storage" so much higher than for an  
equally fixed block on the heap (using std::vector)? This as you  
labelled the use of the former as silly and a no go in high- 
performance applications. To paraphrase, "nobody writing high-speed  
applications would ever consider using std::vector".

2. Why is cache coherency so much better when you use an inline array  
then when Thorsten does it? He also allocates inline (at first) and  
you only have a first, anyway. So, can you please explain why cache  
coherency is so much more King in your

        internal_storage<1000> storage;
        vector<Foo> chrisCont(storage); // and let us just pray that  
'storage' survives this ;-)
        
than in Thorsten's

        auto_buffer<store_n_bytes<1000> > thorCont;

?

NOTE: I know that your contiguous block could potentially scan various  
containers, which *could be* a good thing for cache coherence, but in  
real life, there is often *one* container involved in a certain high- 
performance task.

What is the use case you had in mind with more than one container,  
while having good cache coherence? It would have to involve a lot of  
activity in a specific region of that block (i.e., basically working  
on one container) or deal with a tiny block, which would make it less  
viable for most high-performance applications. And, there could not be  
many reallocations by the container class (such as growing.)

Corollary: did you even look at Thorsten's auto_buffer before  
exclaiming that "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.

What I mean is that if you look at the inheritance graph:

                                                storage_interface (abstract)
                                                                |
                                                storage_base (allocates on heap)
                                                                |
                                                internal_storage (allocates inline, or stack...)

It is weird that "storage_base" (i) is concrete and (ii) does a  
completely different thing than the leaf, "internal_storage"; and  
(iii) the name does not imply its behavior at all; it should be  
"heap_storage", and the graph should look like this:

                                                storage_interface (abstract)
                                                                |
                                                storage_base (whatever concrete stuff is common for all or most  
storages)
                                                   /                        \
                                heap_storage               internal_storage

I would actually merge the two abstract types, but that is just me.

>> 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 do not know what was advertised exactly, but (i) it does crash with  
a bus error when the container is default constructed, without  
explicitly setting a storage, and (ii) it does crash on certain  
platforms and uses cases, due to misaligned memory blocks. [I will  
comment more on this in another reply to you] Besides, it does not  
even compile on GCC with strict error checking. And, your 'map' does  
not work at all, since the allocator is expecting the key type instead  
of the proper 'pair<key, value>' which is expected by the standard  
container. Oh, well, by skipping the 'map' and changing the 'P' to 'p'  
in a few instances, I got it to compile.

What is the meaning of your "New" function in your allocator? It does  
some funky back-stepping, repeating a construction.

GCC NOTE: on 4.3 and 4.4, INT_MAX is not defined in your code, whereas  
on GCC 4.0 it is.

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

No, I did not miss that.

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

I do not follow you.

>> They are functionally equivalent,

So, you can replace 'std::vector' with 'boost::monotonic::vector',  
perhaps with a textual replace all?

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

Ah, yes, so they are not functionally equivalent per se.

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

The people you target, who would think that the, in my opinion, proper  
way of doing it is so much more hairy than your "wrapped" way would  
also assume that they can use the container default-constructed.

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

These issues are not important, in my opinion.

>> If I didn't think it was important, I wouldn't have proposed the  
>> library in
>> the first place.

Alas, it is intrinsically important, QED?

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

I think the usage that *requires* an explicit storage object is less  
than clean. You should at least default to a specific storage, worst  
case heap-allocating it, since you do not want to slice a concrete  
storage object.

I like some aspects of your idea, which is why I take the time to go  
through your code and run some samples. I think Thorsten's auto_buffer  
covers most cases in performance-critical applications, but like the  
idea of extending it to maps and lists. So, get rid of those wrappers  
and tidy up the allocators a bit, and see how you can integrate it  
with Thorsten's effort, and we might have ourselves a winner.

/David