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:
- Is the code well defined and portable (no UB) ?
- Is my implementation as performant as it could be?
- Is my implementation as memory-efficient as it could be?
- Can my implementation be made a bit more user-friendly?
