CODEWITHSUNDEEP
c++c++11vectorstldata-oriented-design
csguth
csguth

Reputation: 576

How to use std::vector<std::tuple<A,B>> to manage memory (resize, reserve,...), but actually keeping the As before the Bs, contiguously

I'm working on an entity-component system (ECS), inspired on Bitsquid's blog series. My ECS is composed of two main classes: System (responsible for creating/destroying entities) and Property (responsible for storing a std::vector of a component, for a given System).

When an Entity is created/destroyed, the System triggers some signals to keep the Property instances aware of the state-change on Systems, in order to keep the data contiguous and well-mapped.

Follow below a simple example of a system of cars, and each car has two properties: point2d position, std::string name.

System<Car> cars;
Property<Car, point2d> positions(cars);
Property<Car, std::string> names(cars);
auto car0 = cars.add();
auto car1 = cars.add();
positions[car0] = {0.0, 0.0};
names[car0]     = "Car 0";
positions[car1] = {1.0, 2.0};
names[car1]     = "Car 1";

This way I can keep the data in separate "arrays".

Let's suppose I want to add 1000 Entities. I could do it calling std::vector::reserve(1000) on all of the properties, and then doing 1000 push_back on each one of them.

I've identified a problem on such approach: I would need 1+N reserves, if I have N properties. I was wondering if I could use a std::vector<tuple<point2d, std::string>> for handling the memory allocations, but manage the data pretending (reinterpret cast?) I have the all the point2d stored contiguously, followed by the strings.

This way I could take advantage of std::vector api for saving notifying/reserve/resizing operations. Although I'd have to adapt the accessing methods (like vector::at, operator[], begin, end).

Do you have any ideas on how to achieve that? Or any alternate suggestions if you think this is not a good idea?

Upvotes: 0

Views: 758

Answers (3)

csguth
csguth

Reputation: 576

I've (almost) finished my SoA implementation using std::vector as underlying data structure.

Suppose we want to create a SoA for types <int, double, char>. Instead of creating three vectors, one for each type, TupleVector<int, double, char> class creates a single std::vector. For data accessing/reserve/resize it plays with reinterpret cast, offset and tuple size calculations.

I just created a simple benchmark code that calls .resize(.size()+1) 10.000.000 times and my SoA implementation appears to be +-4x faster than using separate std::vectors.

Here you can see the benchmark code: https://github.com/csguth/Entity/blob/development/src/Test/TupleVectorBenchmark.cpp

Although this implementation still needs some iterator capabilities (trivial) and more benchmarking.

Hope this can be useful to someone!!

Upvotes: 1

Grisha
Grisha

Reputation: 536

Seems that there is no simple way to make std::vector<T> operate on some data other than it's own array of Ts. So, your options include searching for third party SoA (Stucture of Arrays) library, or making your own.

This might be a starting point for a SoA class, that mimics std::vector's interface:

// This snippet uses C++14 features
#include <functional>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

template <typename F, typename... Ts, std::size_t... Is>
void tuple_for_each(std::tuple<Ts...>& tuple, F f, std::index_sequence<Is...>) {
    using expander = int[];
    (void)expander{0, ((void)f(std::get<Is>(tuple)), 0)...};
}

template <typename F, typename... Ts>
void tuple_for_each(std::tuple<Ts...>& tuple, F f) {
    tuple_for_each(tuple, f, std::make_index_sequence<sizeof...(Ts)>());
}

// Missing in this example:
// - full support for std::vector's interface (iterators, exception safety guarantees, etc.);
// - access to individual homogeneous vectors;
// - lots of other things.

template <typename T, typename... Ts>
class soa_vector {
    std::tuple<std::vector<T>, std::vector<Ts>...> data_;

    template <std::size_t>
    void push_back_impl() const {}

    template <std::size_t position, typename Value, typename... Values>
    void push_back_impl(Value&& value, Values&&... values) {
        std::get<position>(data_).push_back(std::forward<Value>(value));
        push_back_impl<position + 1, Values...>(std::forward<Values>(values)...);
    }

    template<std::size_t... Is>
    std::tuple<std::add_lvalue_reference_t<T>, std::add_lvalue_reference_t<Ts>...>
    tuple_at(std::size_t position, std::index_sequence<Is...>) {
        return std::make_tuple(std::ref(std::get<Is>(data_)[position])...);
    }

public:    
    template <typename... Values>
    std::enable_if_t<sizeof...(Values) == sizeof...(Ts) + 1, void>
    push_back(Values&&... values) {
        push_back_impl<0, Values...>(std::forward<Values>(values)...);
    }

    void reserve(std::size_t new_capacity) {
        tuple_for_each(data_, [new_capacity](auto& vec) { vec.reserve(new_capacity); });
    }

    std::size_t size() const { return std::get<0>(data_).size(); }

    std::tuple<std::add_lvalue_reference_t<T>, std::add_lvalue_reference_t<Ts>...>
    operator[](std::size_t position) {
        return tuple_at(position, std::make_index_sequence<sizeof...(Ts) + 1>());
    }
};

On Coliru

Upvotes: 1

Andriy Tylychko
Andriy Tylychko

Reputation: 16256

It's not possible, at least not with std::tuple. You can consider tuple as a simple struct with members from tuples template args. This means they'll be aligned in memory each after another.

Instead all your managers can implement an interface that allows resizing (reserving) and you can register all your managers in er.. ManagerOfManagers that will resize all of them in a loop

Upvotes: 2

Related Questions