5

When programming games, I used to store all game Objects in a std::vector with initialized and fixed size. Recently I felt the need for some inheritance among the game object classes.

So lets assume I have like 40 classes derived from my class Enemy. If I want to store objects/instances of those classes in a vector, I only have the option of storing them as vector Enemy* right? So the only thing thats contiguously allocated are the pointers, right? So I still will have a lot of cache misses when those need to be dereferenced, right?

Is there any "best practice" way, of storing derived classes in coniguous allocated memory, so that looping through them takes the minimum amount of time?

user3808217
  • 135
  • 3
  • 12
  • 1
    I think he's talking about class instances. That seemed clear to me. – TinkerTenorSoftwareGuy Jul 07 '17 at 21:09
  • I meant objects of those classes. Instances. The things which are created during runtime and are allocated. – user3808217 Jul 07 '17 at 21:09
  • use pointer to base class inside the vector, or if its fit better, some kind of smart pointers. – Klaus Jul 07 '17 at 21:09
  • I think storing them in a vector would be exactly what you're looking for. Vectors seem to be c++'s best practice tool for iteration and storage. And since they are pointers, it's the same as a vector so that's good too. – Chad K Jul 07 '17 at 21:12
  • pointer to base class is exactly the example I gave above, but asked, if I can avoid using pointers, because I want to loop through the objects as fast as possible, and would like to have something close to the efficiency of a contiguously allocated vector. – user3808217 Jul 07 '17 at 21:13
  • Pointers are probably the fastest way to do it anyways. It takes 1 assembly instruction to load a value from a pointer – Chad K Jul 07 '17 at 21:16
  • If you want to call virtual methods of derived objects you have to use pointers anyway... and iterating over different sized objects instead over pointers to objects is slower, because you need a list for this. Allocating the objects in a linear space can be done simply by "new at" operator. – Klaus Jul 07 '17 at 21:16
  • I personally would go with `std::vector>` by default - so you don't have to worry about the memory management yourself. – Daniel Schepler Jul 07 '17 at 21:33
  • 4
    There are several approaches but they are all technically quite complex. I strongly recommend that you start with `vector>` and benchmark. If you do need to go this route, this simplest/most feasible approach with such a large number of derived classes, is to use a custom allocator to ensure that all of the Enemies get constructed in a contiguous block of memory. You would still use a vector of unique_ptr's just with a custom deleter, and use some other function instead of `make_unique`. – Nir Friedman Jul 07 '17 at 22:07
  • Possible duplicate of [In which scenario do I use a particular STL container?](https://stackoverflow.com/questions/471432/in-which-scenario-do-i-use-a-particular-stl-container) – Retired Ninja Jul 07 '17 at 22:49

2 Answers2

3

Boost just accepted a library for exactly this purpose: poly_collection. In particular, you are looking for base_collection

Internally, it uses a number of vectors, one per (derived) type, while providing an interface close to standard containers.

This article by its author provides some design background and a comparison to other solutions, like a vector of unique_ptr. The advantage is two-fold: first, by not using pointers and dynamic memory allocation per element you have better memory locality, and second, grouping elements of the same type together, you help branch prediction and instruction cache for virtual member functions.

Ilya Popov
  • 3,765
  • 1
  • 17
  • 30
  • It's not clear at all that anything is more optimal if you group elements of the same type. In many scenarios, there is a strong relationship between objects allocated close together in time. In others, it's important only to have all objects of derived types stored together, with no need for grouping. Then objects may live forever, and all be deallocated together - then, an arena would perform better. As with most things, you have to profile when performance matters, and `poly_collection` may perform the best of the alternatives, or not quite. – Kuba hasn't forgotten Monica Sep 05 '19 at 13:08
0

What about this?

struct alignas(...) Base {};
struct Derived1 : Base {};
struct Derived2 : Base {};

int main()
{
    std::vector<Base> v(2);
    new (&v[0]) Derived1();
    new (&v[1]) Derived2();
    return 0;
}

Placement new does the trick. It works with polymorphism. The alignas is to ensure the vector contains objects of the same size. Replace the ... by a number (power of 2) such that instances of both Derived1 and Derived2 fit in the vector. If sizeof(Derived1) returns 16 and sizeof(Derived2) returns 24, you would need a alignas(32).

EDIT

As @KubaOber stated, alignas is not designed to manage allocation sizes, but only for positioning the object in memory. A better way to achieve your goal is using std::variant. Something like this:

int main()
{
    std::vector<std::variant<Derived1, Derived2>> v;
    v.emplace_back(Derived1());
    v.emplace_back(Derived2());

    for (const auto& e : v)
        std::visit(VisitPackage(), e);

    return 0;
}

where VisitPackage could be something like this:

struct VisitPackage
{
    void operator()(const Derived1&) { std::cout << "Derived 1.\n"; }
    void operator()(const Derived2&) { std::cout << "Derived 2.\n"; }
};
mfnx
  • 2,894
  • 1
  • 12
  • 28