Re: [boost] Interest in a "Heterogenous Container" system?

Subject: Re: [boost] Interest in a "Heterogenous Container" system?
From: Christian Schladetsch (christian.schladetsch_at_[hidden])
Date: 2009-08-02 20:31:35

On Sun, Aug 2, 2009 at 1:31 PM, Mathias Gaunard <
mathias.gaunard_at_[hidden]> wrote:

> Christian Schladetsch wrote:
>
>> [snip]
>> I wanted a way to make the cloning operation for ptr_container to use the
>> same allocator that the container uses (and indeed, have the container use
>> the correct allocator at all!).
>>
>
> Standard allocators are inherently incompatible with the very idea of
> cloneable objects, since the type information is supposed to be lost.
>
> The only sensible thing you can do (IMHO) is use a standard allocator of
> char or use an allocator interface similar to that of malloc or operator
> new.
>
> I personally never understood why they tied the type into the allocator.
> Having just the size and alignment would be so much better.

This is largely what I did. The allocation model used by Cloneable is based
on covariant virtual methods that are passed an 'abstract allocator' which
takes the alignment as an argument.

        struct abstract_allocator
        {
            typedef char *pointer;
            virtual pointer allocate_bytes(size_t num_bytes, size_t
alignment) = 0;
            virtual void deallocate_bytes(pointer, size_t alignment) = 0;
            static size_t calc_padding(pointer ptr, size_t alignment);
        };

An abstract allocator is then adapted from a type that models std::allocator
and is passed to methods used to create objects used by the system. Yes, it
means that 'type info' is lost, as the allocations are really just sequences
of correctly-aligned bytes - but I can't see this as a problem (and anyway,
it is exactly what is happening). As you say, there doesn't seem to be
anything to gain from having the type information in the signature of an
allocator type - and much to lose. So I just inverted it, removed the type
from the allocator signature, and now pass the alignment down as needed from
where the type information is.

> You simply have to use emplace semantics for these containers;
> > otherwise you aren't respecting the allocator
>
> For when you copy the container later, do you maybe add a pointer overhead
> per object on your heterogeneous list to reference a rightly rebound
> function for cloning with the given container allocator?
> Not something very nice, since it could be avoided.

No, there is no per-object overhead. Each object in the container is
`cloneable`, via the mixin that is added in the declaration:

struct MyDerived : cloneable::base<MyDerived, SomeBase> { ... };

This of couse adds a vtbl to all your types used by the library, but that is
unavoidable. The main costs are the dynamic_cast's used by the system, both
internally and to answer queries for the associative containers (which
answer based on type and value). Dynamic_cast<> can be very slow, but the
effect is mitigated because in general the casts succeed (dynamic_cast is
slowest for classes with many derived types when the cast eventually fails).
The need for dynamic_cast<> over static_cast<> was introduced when I had to
make the base virtual to allow rudimentary multiple inheritance support.

That said, there is a structure in the libary called 'cloneable::instance<>'
which stores an object pointer and a reference to the allocator that made
it. This is used by the system when adding new objects to containers but is
not stored anywhere. However, I found the idea of pairing objects with their
allocators so appealing that I exposed it in the public interface for the
library. It is one thing to be able to clone an object using clone(Q) or
Q.clone(); but that is only half the story. To be complete, IMO, these
methods should also be able to make a clone using the same allocator as the
original. Hence the idea of a 'cloneable::instance<>'.

How important this is in general may be questionable. But for
high-performance system software, where lifetime management is often
optimised for different timeframes (scope-local, per-frame, across
milliseconds, across seconds, across hours etc), then knowledge about an
instance including its allocator can be very handy. It is a way of adding
semantics to an instance, not all of which are created equally.

Anyway, I'm currently blocked on how to deal with multiple inheritance and
will have to make the call soon about whether to drop explicit support for
it, or to basically re-write it to pass the derived types to the cloneable
system and have it synthesise everything itself. That approach may or may
not even work.

Regards,
Christian.