30
\$\begingroup\$

This is a follow-up of 'any' class implementation. After posting my answer, I kept working on the code towards parameterizing with respect to memory management as I had promised. I ended up in some pretty non-trivial piece of code that I decided to post here as a new question for review.

Basically, this is quite close to boost::any, with a number of differences. From my perspective it could be a complete replacement to boost::any, that I like to call some.

Minor differences:

  • Member-function, reference (not pointer)-based, type-checked/-unchecked data access (casting).

  • Simplified type-checked access via dynamic_cast instead of manual typeid checking. Using std::bad_cast instead of a custom exception type.

  • Type provided for casting should be already decayed; no references removed.

  • Conversion operators.

  • Free of const_cast hacks.

  • No type() functionality exposed; is<T>() check interface instead. Internally, custom type identification mechanism bypassing typeid and RTTI.

  • Move semantics fully supported. No constraints e.g. on reading from const rvalue references or providing non-const rvalue references to temporary objects.

  • Using empty base optimization, empty objects are stored with no space overhead on top of the required virtual function table.

Major differences:

  • Templated on a memory-management object that is roughly what an allocator is for STL containers, yet with a different, custom interface.

  • Default "allocator" type provides customizable storage space on stack. Similarly to small string optimization, and without run-time overhead, objects not larger than this space are placed on stack; larger ones on the free store.

So some is maybe somewhere between boost::any and boost::variant (in using the stack rather than restricting to pre-defined types). To get a rough idea about this "allocator", here is what it would look like if it used the free store only:

struct alloc
{
    template<typename D, typename V>
    D *copy(V &&v) { return new D{std::forward<V>(v)}; }

    template<typename D, typename V, typename B>
    B *move(V &&v, B *&p) { B *q = p; p = nullptr; return q; }

    template<typename D>
    void free(D *p) { delete p; }
};

This would really work, but it's not used in my examples. Here is the actual default one, including its own stack space:

template<size_t N = 16>
class store
{
    char space[N];

    template<typename T>
    static constexpr bool
    fits() { return sizeof(typename std::decay<T>::type) <= N; }

public:
    template<typename D, typename V>
    D *copy(V &&v)
    {
        return fits<D>() ? new(space) D{std::forward<V>(v)} :
                           new        D{std::forward<V>(v)};
    }

    template<typename D, typename V, typename B>
    B *move(V &&v, B *&p)
    {
        B *q = fits<D>() ? copy<D>(std::forward<V>(v)) : p;
        p = nullptr;
        return q;
    }

    template<typename D>
    void free(D *p) { fits<D>() ? p->~D() : delete p; }
};

Typically, on a 64-bit machine, 8 bytes go for the virtual function table, so the remaining 8 of the default size can store up to e.g. a long or a double without invoking any free store operation.

Expression fits<D>() is evaluated at compile time, so whenever it evaluates to false, store is equivalent to alloc, without any run time overhead. For N = 0, it is always equivalent (or I think so, right?).

Now, here is the complete definition of some:

template<typename A = store<>>
class some : A
{
    using id = size_t;

    template<typename T>
    struct type { static void id() { } };

    template<typename T>
    static id type_id() { return reinterpret_cast<id>(&type<T>::id); }

    template<typename T>
    using decay = typename std::decay<T>::type;

    template<typename T>
    using none = typename std::enable_if<!std::is_same<some, T>::value>::type;

//-----------------------------------------------------------------------------

    struct base
    {
        virtual ~base() { }
        virtual bool is(id) const = 0;
        virtual base *copy(A&) const = 0;
        virtual base *move(A&, base*&) = 0;
        virtual void free(A&) = 0;
    } *p = nullptr;

    template<typename T>
    struct data : base, std::tuple<T>
    {
        using std::tuple<T>::tuple;

        T       &get()      & { return std::get<0>(*this); }
        T const &get() const& { return std::get<0>(*this); }

        bool is(id i) const override { return i == type_id<T>(); }

        base *copy(A &a) const override
        {
            return a.template copy<data>(get());
        }

        base *move(A &a, base *&p) override
        {
            return a.template move<data>(std::move(get()), p);
        }

        void free(A &a) override { a.free(this); }
    };

//-----------------------------------------------------------------------------

    template<typename T>
    T &stat() { return static_cast<data<T>*>(p)->get(); }

    template<typename T>
    T const &stat() const { return static_cast<data<T> const*>(p)->get(); }

    template<typename T>
    T &dyn() { return dynamic_cast<data<T>&>(*p).get(); }

    template<typename T>
    T const &dyn() const { return dynamic_cast<data<T> const&>(*p).get(); }

    base *move(some &s)       { return s.p->move(*this, s.p); }
    base *copy(some const &s) { return s.p->copy(*this); }

    base *read(some &&s)      { return s.p ? move(s) : s.p; }
    base *read(some const &s) { return s.p ? copy(s) : s.p; }

    template<typename V, typename U = decay<V>, typename = none<U>>
    base *read(V &&v) { return A::template copy<data<U>>(std::forward<V>(v)); }

    template<typename X>
    some &assign(X &&x)
    {
        if (!p) p = read(std::forward<X>(x));
        else
        {
            some t{std::move(*this)};
            try        { p = read(std::forward<X>(x)); }
            catch(...) { p = move(t); throw; }
        }
        return *this;
    }

    void swap(some &s)
    {
             if   (!p)   p = read(std::move(s));
        else if (!s.p) s.p = move(*this);
        else
        {
            some t{std::move(*this)};
            try        { p = move(s); }
            catch(...) { p = move(t); throw; }
            s.p = move(t);
        }
    }

//-----------------------------------------------------------------------------

public:
     some() { }
    ~some() { if (p) p->free(*this); }

    some(some &&s)      : p{read(std::move(s))} { }
    some(some const &s) : p{read(s)} { }

    template<typename V, typename = none<decay<V>>>
    some(V &&v) : p{read(std::forward<V>(v))} { }

    some &operator=(some &&s)      { return assign(std::move(s)); }
    some &operator=(some const &s) { return assign(s); }

    template<typename V, typename = none<decay<V>>>
    some &operator=(V &&v) { return assign(std::forward<V>(v)); }

    friend void swap(some &s, some &r) { s.swap(r); }

    void clear() { if(p) { p->free(*this); p = nullptr; } }

    bool empty() const { return p; }

    template<typename T>
    bool is() const { return p ? p->is(type_id<T>()) : false; }

    template<typename T> T      &&_()     && { return std::move(stat<T>()); }
    template<typename T> T       &_()      & { return stat<T>(); }
    template<typename T> T const &_() const& { return stat<T>(); }

    template<typename T> T      &&cast()     && { return std::move(dyn<T>()); }
    template<typename T> T       &cast()      & { return dyn<T>(); }
    template<typename T> T const &cast() const& { return dyn<T>(); }

    template<typename T> operator T     &&()     && { return std::move(_<T>()); }
    template<typename T> operator T      &()      & { return _<T>(); }
    template<typename T> operator T const&() const& { return _<T>(); }
};

Here is a live example with an extensive set of tests for most functionality.

Now, what I would like:

  • Not much interested in style like function/variable names, indentation etc. I know the code is not really for sharing; it's very compact with one-line function definitions where possible, with one-letter parameters in most cases, and no comments. Please ignore that.

  • Can you see or find any bugs that may have by-passed my tests? Any possibility for leaks? I know this is necessarily low-level code.

  • Can you see any unnecessary performance loss or anything else that could be easily further optimized?

  • I have done my best to provide a strong exception guarantee to all operations. assign and swap are the most non-trivial ones, where due the (potential) use of the stack, operation sequencing is not enough and I had to write try/catch blocks around the most critical operations.

    • Do you think everything is correct? For instance, I have made the assumption that if A is moved to B without throwing, then B can be safely moved back to A.

    • If yes, could it be done in a more efficient way? In assign, for instance, I am making an additional move (in fact, copy) operation to handle the possibility that some constructor throws.

  • I have found out that all tests work fine without self-test on assignment. Is there any case where this might fail?

  • I have preferred to explicitly use constructors (placement-new) and destructors for stack operations. I know direct use of std::copy would be equivalent for trivially copyable types and more efficient, but I think is too low-level and would make the code even more complex. Should I reconsider?

  • Is it well-defined to delete an object or explicitly call its destructor via a call to a virtual function (even if it's sure this is the last operation on it)? I couldn't find any other way to choose the right operation (delete vs. destructor call).

  • Not sure if needed, but, any idea how to simplify the allocator interface so that it could be used in a more general setting? I know it's clearly different from std::allocator in any case.

\$\endgroup\$
  • \$\begingroup\$ After some t{std::move(*this)};, isn't it UB to access anything in the class? \$\endgroup\$ – BЈовић Apr 28 '14 at 11:10
  • \$\begingroup\$ @BЈовић After that, I know that p==nullptr and anything previously stored in space has been moved, so space is free to reuse (its content is undefined, but I am not attempting to read it). This is exactly the state after default-initialization, i.e. *this is empty. The very next operation is of the form p = ..., i.e. something new is read into *this. I think this is well-defined, no? \$\endgroup\$ – iavr Apr 28 '14 at 22:30
  • \$\begingroup\$ No idea. You are doing return *this; after that. \$\endgroup\$ – BЈовић Apr 29 '14 at 4:22
  • \$\begingroup\$ How about using id = void (*)(); You never know what size a function pointer is going to have. Also put your any in some repository please. \$\endgroup\$ – user1095108 May 29 '14 at 10:49
  • \$\begingroup\$ @user1095108 You are right this is a weak point. That's why I later wrote a cleaner solution for a type ID, which does not need any reinterpret_cast at all. The improved any, called some, is now here. This is already part of a repository, but is no longer independent. Among several other things, it uses the improved type ID, part of the same repository. \$\endgroup\$ – iavr May 29 '14 at 11:25
7
\$\begingroup\$

The very idea of the storage inside some made me think about the problems it brings in swap() and assign(). I was first thinking about adding the swap() as another virtual method, possibly even the assignment. That could help you solve the problem in a bit different way - you will know if you are moving the pointer or need to copy/move the object from one embedded storage to another.

But on second thought, the optimization behind the scene could as well be solved with good allocator for small objects utilizing some free-list and spinlocks or some other lockfree technique - e.g. boost::pool or my own same-size allocator (very old school project). That will help you a lot with the problem of exceptions in swap/assign, without the need for temporary, try..catch and repair.

If you still think about using the storage, I would not inherit it in some, but in inner class containing the pointer first (one base class having the pointer) and the store next (second base class or composition, which would be better regarding next paragraph). This could speed it a bit more by making it more sequential on reading (pointer first, vmtptr next, data last). You could as well move the vmtptr next to data pointer (no matter the storage), with few more tricks with placement new (separating virtual methods from the data and a bit terrible hack to access the data pointer next to this as you know the layout). I wouldn't write this not seeing you trying to optimize it with the embedded storage, which itself is overkill - std::allocator should handle this - I still think that solving this (fast allocation of tiny objects) will render your embedded storage as not needed (and possibly helping other containers on the way).

The allocator seems more like a feature of some, than allocator or usable extension/option for it. I would personally not expose it and make some a simple class (not a template). Or pass a real (but universal) allocator, something like std::allocator<char>, with allocate and deallocate optimized for tiny blocks. You could as well use rebind for all the types.


The Alloc/Store Interface

  • copy accepts universal (rvalue) reference and therfore looks like to be something else, but from the code I can see you use it on one and only place - data::copy which uses it with simple (lvalue) reference. I think that it would be a good idea to change the signature to match it (otherwise it may became a sort of move instead of copy). Actually, it mimics construct(allocate(1), v).
  • move seems to be there to move data from one storage to another (either embeded or heap). It looks to be doing what it was designed for, but I would change the inner copy<D> to new(space) ..., to make it more clear (and understandable).
  • free is good, it means destroy + possibly dispose.
  • swap is something I would definitelly add (using std::swap) to help you solve the problems you have in some::swap() - I would just copy the noexcept from it and remove try..catch. It simply should not throw and you can take advantage of std::swap and possible specializations (using std::swap; swap(x,y) - you may look there for copy-and-swap to get some more related info).

Author: Expression fits<D>() is evaluated at compile time, so whenever it evaluates to false, store is equivalent to alloc, without any run time overhead. For N = 0, it is always equivalent (or I think so, right?).

For me it looks to be related to this:

template<size_t N = 16>
class store
{
    char space[N];

    template<typename T>
    static constexpr bool
    fits() { return sizeof(typename std::decay<T>::type) <= N; }

sizeof will never return negative value, and zero-size array at the end of structure is allowed from what I know (at least good working extension I have used few times). If you run into problems, you can simply specialize the template (for N = 0).


Now it seems I have nothing to add, unless I see some feedback ;)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.