4
\$\begingroup\$

This is my attempt of implementing an efficient, cache-friendly, vector for polymorphic objects.

From now on I will refer to "virtual functions" as functions which are dependent on an object's underlying dynamic type, though they might not be strictly marked "virtual".

Memory model of polymorphic vector

Rather than storing a vector of std::unique_ptr (or other smart pointer) which points to an object on the heap, I store polymorphic objects of the same dynamic type together in the same vector (i.e. I have a vector of Bases and a vector of Derived). A tuple stores each vector of each dynamic type.

However, this has the downside that my polymorphic vector is unordered, so I store the vector index_map which stores the necessary information to represent the order.

Also, I store a vector of pointers to the base class (named ptrs) for efficient calls to non-virtual member functions.

Calling a virtual function at a given index

First, I lookup in index_map the type number and index number of the object. I then create some sort of static constexpr v-table of function pointers (in the functionapply_func_to_tuple). All in all, this requires two levels of indirection, resulting in the same performance as a virtual function.



/* Helper functions */
/* This set functions applies a function an element of a tuple given a runtime index */
template<typename R, int N, class T, class F>
R apply_one(T& p, F& func)
{
    static_assert(std::is_same<typename std::result_of<F(decltype(std::get<N>(p)))>::type, R>::value, "Wrong return type for polymorphic function");
    return func(std::get<N>(p) );
}

template<typename R, class T, class F, int... Is>
R apply_func_to_tuple(T& p, int index, F& func, seq<Is...>)
{
    using FT = R(T&, F&);
    /* This is the magic, a v-table is built on the spot here. */
    static constexpr FT* arr[] = { &apply_one<R, Is, T, F>... };
    return arr[index](p, func);
}

template<typename R, class T, class F>
R apply_func_to_tuple(T& p, int index, F&& func)
{

    return apply_func_to_tuple<R>(p, index, func, gen_seq<std::tuple_size<T>::value>{});
}

/* Helper class to find the index of a type from a tuple type list at compile - time */
template <class T, class Tuple>
struct Index;

template <class T, class... Types>
struct Index<T, std::tuple<T, Types...>> {
    static consteval int getValue() {
        return 0;
    }
};

template <class T, class U, class... Types>
struct Index<T, std::tuple<U, Types...>> {
    static consteval int getValue() {
        return 1 + Index<T, std::tuple<Types...>>::getValue();
    }
    //static const std::size_t value = 1 + Index<T, std::tuple<Types...>>::value;
};
/* Functions to calculate log at compile time, needed later */
constexpr unsigned floorlog2(unsigned x)
{
    return x == 1 ? 0 : 1+floorlog2(x >> 1);
}

constexpr unsigned ceillog2(unsigned x)
{
    return x == 1 ? 0 : floorlog2(x - 1) + 1;
}
/* The element class of my "order vector" , I use a bitfield to pack as much data as I can in 8 bytes */
template <typename Base, typename ...Ts>
struct IndexElement {
    unsigned long type : ceillog2(sizeof...(Ts) + 1);
    unsigned long index: 64 - ceillog2(sizeof...(Ts) + 1);
};
/* Start the class */
template <typename Base, typename ...Ts>
struct PolymorphicVector {
public:
    /* Vector which represents the order of the objects */
    std::vector<IndexElement<Base, Ts...>> index_map;
    /* This contains the actual objects, as you can see they are stored without order, which is why index_map is needed to represent the order */
    std::tuple<std::vector<Base>, std::vector<Ts>...> vec;
    /* This vector seems a little bit redundant, but is used to apply efficiently a non-virtual method at a given index */
    std::vector<Base*> ptrs;
public:
    /* Apply a "virtual" functor at a given index */
    template <typename Functor>
    decltype(auto) apply(int index, Functor&& fn) {

        auto true_index = index_map[index].index;

        return apply_func_to_tuple<typename std::result_of<Functor(Base&)>::type>
        (vec , index_map[index].type , [true_index, &fn] (auto& vec) {return fn(vec[true_index]);});

    }
    /* Apply a virtual functor to all the elements of my vector in order */
    template <typename Functor>
    void ordered_apply(Functor&& fn) {
        for (int i = 0; i < index_map.size(); i++) {
            apply(i, std::move(fn));
        }
    }
    /* Apply a non-virtual method at an index */
    template <typename Functor>
    inline decltype(auto) apply_method(unsigned long index, Functor&& fn) {
        return fn(ptrs[index]);
        
    }
private:
    /* Helper methods */
    template <typename Functor, typename Head, typename... Tail>
    void unordered_apply(Functor& fn) {
        for (int i = 0; i < std::get<std::vector<Head>>(vec).size(); i ++) {
            fn(std::get<std::vector<Head>>(vec)[i]);
        }
        unordered_apply<Functor, Tail...>(fn);
    }
    template <typename Functor>
    void unordered_apply(Functor& fn) {
    }
public:
    /* Apply a functor to all the elements in my vector without committing to a specific order. */
    template <typename Functor>
    void unordered_apply(Functor&& fn) {
        unordered_apply<Functor, Base, Ts...>(fn);
    }
    /* Add an element to the vector */
    template <typename Derived>
    PolymorphicVector& append(const Derived& derived) {
        // Check if reallocation is necessary
        if (std::get<std::vector<Derived>>(vec).capacity() == std::get<std::vector<Derived>>(vec).size()) {
            Derived* start = &std::get<std::vector<Derived>>(vec)[0];
            std::get<std::vector<Derived>>(vec).push_back(derived);
            auto offset = &std::get<std::vector<Derived>>(vec)[0] - start;
            // Reinitialise invalidated pointers.
            for (int i = 0; i < index_map.size(); i ++) {
                 ptrs[i] += (index_map[i].type == Index<Derived, std::tuple<Base, Ts...>>::getValue()) * offset;
              
            }
            index_map.push_back(IndexElement<Base, Ts...>{Index<Derived, std::tuple<Base, Ts...>>::getValue(), std::get<std::vector<Derived>>(vec).size() - 1});

            ptrs.push_back(static_cast<Base*>(&std::get<std::vector<Derived>>(vec).back()));

            return *this; 


        } 
        std::get<std::vector<Derived>>(vec).push_back(derived);
        ptrs.push_back(static_cast<Base*>(&std::get<std::vector<Derived>>(vec).back()));
        
        index_map.push_back(IndexElement<Base, Ts...>{Index<Derived, std::tuple<Base, Ts...>>::getValue(), std::get<std::vector<Derived>>(vec).size() - 1});
        return *this;
    }
    template <typename Derived>
    std::vector<Derived>& getVectorOf() {
      return std::get<Derived>(vec);
    }
    template <typename Derived>
    inline bool checkIndexIs(unsigned int index) {
      return index == Index<Derived, std::tuple<Base, Ts...>>::getValue();
    }

private:
    template <typename Head, typename First, typename... Tail>
    void reserve(unsigned long num) {
      std::get<std::vector<Head>>(vec).reserve(num);
      reserve<First, Tail...>(num);
      
    }
    template <typename Last>
    void reserve(unsigned long num) {
      std::get<std::vector<Last>>(vec).reserve(num);
      
    }
public:
    // Reserve
    void reserve(unsigned long num) {
      reserve<Base, Ts...>(num);
    }
};

Example use case:

struct Base {
    virtual int a_method(int x) {
       z += x;
       std::cout << z;
     }
     int z;
};

struct Derived: public Base {
     virtual int a_method(int x) {
         z*=x;
         std::cout << z;
     }
};
int main() {
  PolymorphicVector<Base, Derived> x;
  x.append(Derived{5});
  x.append(Base{10});
  x.apply(0, [] (auto& base) { return base.a_method(5);}); // 25

  return 0;
}

Advantages of this implementation over a vector pointer-to-base

  • Huge performance increase when applying a functor to all the elements of my vector without committing to a specific order (4 times faster for a non-virtual method, 20 times faster for a virtual method). This is due to cache-friendliness and not actually having any dynamic dispatch in the virtual case.

  • Retains all the type information (i.e. we can retrieve all elements of a certain type, check if an object at a certain index has a certain dynamic type)

  • Small performance increase when adding objects to the vector (heap memory does not need to be found for each object, thereby decreasing heap fragmentation)

  • Does not require virtual methods to achieve polymorphic behaviour (my implementation allows the use of virtual free function/ functors)

  • Same performance for applying methods/ virtual methods at a given index.

Drawbacks

  • Must specify all the polymorphic types you want to store (as opposed to a vector of std::unique_ptr<Base> where you can store all the types derived from a single type)

  • My implementation uses a less user-friendly "visitor" pattern to modify its elements.

  • Small overhead when the vector undergoes reallocation

  • Each element is not polymorphic in itself, the vector is polymorphic.

Questions for code review:

  1. Is the code well defined and portable (no UB) ?
  2. Is my implementation as performant as it could be?
  3. Is my implementation as memory-efficient as it could be?
  4. Can my implementation be made a bit more user-friendly?
\$\endgroup\$
6
  • \$\begingroup\$ Looks interesting! Besides your core questions: This part void unordered_apply(Functor&& fn) --> I think, you've forgotten to apply std::forward to your forwarding/universal reference within the function body!? \$\endgroup\$
    – Secundi
    Feb 19, 2021 at 13:03
  • \$\begingroup\$ And this might be a mistake: template <typename Functor> void ordered_apply(Functor&& fn) { --> there you are always moving the functor for each array element but you can only do that for the last element. The robust clean solution might require some kind of a case separating forwarding proxy helper I think: always forward the const ref for const ref case, move for the rvalue case but only for the last element/index of the array. \$\endgroup\$
    – Secundi
    Feb 19, 2021 at 13:12
  • \$\begingroup\$ @Secundi Yes, I should be more careful with my r-value references / universal references ... I'm a bit sloppy with it. For your second comment, I think the solution would be to have a second overload of "Polymorphic::apply(int index, Functor& func)" taking a reference so that my the functor r-value reference in ordered_apply could be taken by reference. \$\endgroup\$ Feb 19, 2021 at 13:55
  • \$\begingroup\$ @Secundi What do you think of my implementation/ memory model of my vector? Could it be improved. Feel free to ask questions if further clarifications are needed. \$\endgroup\$ Feb 19, 2021 at 13:56
  • \$\begingroup\$ I'm going to write an answer here soon. \$\endgroup\$
    – Secundi
    Feb 20, 2021 at 17:17

1 Answer 1

2
+50
\$\begingroup\$

A short analysis of some things that are quite clear to me:

Rvalues and Forwarding references

At first as already mentioned within the comments, you should refer to a clean move-semantic/forwarding scheme. For universal/forwarding references, only refer to std::forward. If no move semantic is effectively involved for all cases, do not refer to it: neither explicit rvalue usage nor forwarding reference usage. Otherwise, it's quite hard to follow data ownership flows for instance, at latest when your code expands later on.

Moving data for the last iteration step of a loop:

   template <typename Functor>
    void ordered_apply(Functor&& fn) {
        for (int i = 0; i < index_map.size(); i++) {
            apply(i, std::move(fn));
        }
    }

As already mentioned, this is wrong as soon as the functors from calling side are rvalues effectively. You can simply correct it "inline" via

apply(i, i == index_map.size() - 1 ? std::forward<Functor>(fn) : fn);

The correct behavior here is ensured by the standard, but requires a further temporary in between. Therefore I prefer it more explicitly:

for (int i = 0; i < index_map.size(); i++) {
    if (i == index_map.size() - 1)
        apply(i, std::forward<Functor>(fn));
    else
        apply(i, fn);
}

But since this all is a no-op for the const reference argument case, the better overall design approach is to force a clean rvalue vs. lvalue separation via an internal helper struct and write the operations there in a very explicit way:

template <typename Functor>
struct CategorizedApplyForwarder
{
    // implement doApply(Functor&& fnc);
    // implement doApply(const Functor& fnc);
};

The first overload would then allow the move for the last element, the second would simply call the final apply() function with your arguments by const reference semantics.

But since apply() doesn't really take ownership,

template <typename Functor>
    decltype(auto) apply(int index, Functor&& fn) {

        auto true_index = index_map[index].index;

        return apply_func_to_tuple<typename std::result_of<Functor(Base&)>::type>
        (vec , index_map[index].type , [true_index, &fn] (auto& vec) {return fn(vec[true_index]);});
    }

the move/forwarding-semantics are no-ops. Being confident about the semantics can prevent you from a lot of trouble in doubt.

The concrete questions

Is the code well defined and portable (no UB) ?

Except the rvalue issues from above, I'd say yes so far. In detail, you should ensure that your subscript operator usage (index-based) is range-safe always. I didn't analyze that deep in detail here. What you should reconsider is the general question about exception safety. As far as I know, this is almost one of the most important questions why the standard avoids excessively optimized containers in general.

Is my implementation as performant as it could be?

That question is not specific enough :) If you mean performance in terms of what the actual code is trying to achieve (line-wise granular), I'd say there are not obvious issues here. Maybe this line could be further improved via emplace_back usage:

index_map.push_back(IndexElement<Base, Ts...>{Index<Derived, std::tuple<Base, Ts...>>::getValue(), std::get<std::vector<Derived>>(vec).size() - 1});

In terms of general performance behavior, you should distinguish at first, what the main purposes of your vector are in detail and how the general proportionality between the advantages and drawbacks should be. A deeper analysis here can become quite intensive in doubt. Accidental vs. theoretical complexity analysis is an important keyword here, as cache-line behavior is in doubt.

Is my implementation as memory-efficient as it could be?

Similar to the performance question, the devil is in the details. But from your internals only seen in general, I'd say you're quite fine since you refer to contiguous storage of "direct objects" only.

Can my implementation be made a bit more user-friendly?

I'd hide the internals of PolymorphicVector as far as possible. Make them private? I also miss a public clear() function.

Compared to the common visitor approach, I really have to say that I prefer the common visitor on a std::vector of variants in terms of design principles and explicit usage. But I know that the common visitor approach is not as efficient as one might hope it is.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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