Stack overflow error in C++ after vectorization

Question

I get a continuous stack overflow error when trying to test this little program to test the performance difference between a structure of arrays vs. an array of structures. I'm clearly doing something wrong, but I have a really hard time figuring it out. Is anyone able to help?

#include "stdafx.h"

#include <vector>

#define NUM_ITEMS 10000000

struct Vector3 {

    Vector3() : x(0.0f), y(0.0f), z(0.0f) {}

    float x, y, z;

    Vector3 operator+=(const Vector3& v) {
        Vector3 v_new;
        v_new.x = this->x + v.x;
        v_new.y = this->y + v.y;
        v_new.z = this->z + v.z;

        return v_new;
    }
};

struct SoA {
    SoA() : pos(NUM_ITEMS), vel(NUM_ITEMS) {}

    std::vector<Vector3> pos, vel;
};

struct AoS {
    Vector3 pos, vel;
};

int main()
{
    std::vector<AoS> entities[NUM_ITEMS];
    for (int i = 0; i < entities->size(); i++) {
        entities->at(i).pos += entities->at(i).vel;
    }

    SoA entityManager;
    for (int i = 0; i < NUM_ITEMS; i++) {
        entityManager.pos[i] += entityManager.vel[i];
    }

    return 0;
}

Edit: I see I accidentally put a 1 in the second for loop. This is supposed to be an i. But it doesn't affect the stack overflow so I just edited it out.

Does this compile considering that you have an array of vectors — Ed Heal
– Ed Heal, Commented Aug 30, 2017 at 21:16
Compiles just fine on my system. Seems to be occurring in second for loop. — pointerless
– pointerless, Commented Aug 30, 2017 at 21:16
The #include of a Windows-only header file ensures it doesn't most places ;) — marko
– marko, Commented Aug 30, 2017 at 21:18

Peter Mortensen · Accepted Answer · 2017-08-30 21:59:29Z

2

Change the second for loop from

for (int i = 0; 1 < NUM_ITEMS; i++) {

to

for (int i = 0; i < NUM_ITEMS; i++) {

Essentially you were infinitely appending to the vector.

edited Aug 30, 2017 at 21:59

Peter Mortensen

31.4k22 gold badges110 silver badges134 bronze badges

answered Aug 30, 2017 at 21:22

pointerless

7639 silver badges20 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Peter Mortensen · Accepted Answer · 2017-08-30 22:00:59Z

First,

Vector3 operator+=(const Vector3& v) {
    Vector3 v_new;
    v_new.x = this->x + v.x;
    v_new.y = this->y + v.y;
    v_new.z = this->z + v.z;

    return v_new;
}

should be

Vector3& operator+=(const Vector3& v) {
    this->x += v.x;
    this->y += v.y;
    this->z += v.z;

    return *this;
}
Vector3 operator+(const Vector3& v) const {
  auto v_new = *this;
  v_new += v;
  return v_new;
}

Second, your loop has an error (it does 1 < NUM_ITEMS which means "forever"). Fix this by ... not manually indexing.

Also you have a huge array of vectors of entities. Then you seem to think the empty vectors contain items.

std::vector<AoS> entities(NUM_ITEMS);
for (auto& e : entities) {
    e.pos += e.vel;
}

In the second loop it is tricker to eliminate manual bounds checking, but it can be done.

template<class Base>
struct index_iterator {
  Base b;
  Base operator*() const { return b; }
  index_iterator& operator++() { ++b; return *this; }
  index_iterator operator++(int) { auto r = *this; ++b; return r; }
  bool operator==(index_iterator const& o) const {
    return b == o.b;
  }
  bool operator!=(index_iterator const& o) const {
    return b != o.b;
  }
  index_iterator(index_iterator const&)=default;
  index_iterator(index_iterator &&)=default;
  index_iterator& operator=(index_iterator const&)=default;
  index_iterator& operator=(index_iterator &&)=default;
  index_iterator(Base bin):b(std::move(bin)) {}
};
template<class It>
struct range_t {
  It b, e;
  It begin() const{ return b; }
  It end() const{ return e; }
};
template<class It>
range_t<It> range( It b, It e ) { return {b,e}; }

using index = index_iterator<std::size_t>;
template<class T, std::size_t N>
range_t<index> indexes_into( T(&)[N] ) {
  return range<index>(0, N);
}
range_t<index> indexes_into( std::array<T,N> const& ) {
  return range<index>(0, N);
}
template<class C>
range_t<index> indexes_into( C const& c ) {
  return range<index>(0, c.size());
}

And now we can:

SoA entityManager;
for (auto i : indexes_into(entityManager.pos)) {
  entityManager.pos[i] += entityManager.vel[i];
}

And never screw up a for() loop with a fencepost error again.

But that is just me. I'd rather write a pile of metaprogramming code than deal with off-by-1 errors. Because metaprogramming is easy and testable, while off-by-1 errors are hard to avoid.

marko · Accepted Answer · 2017-08-30 22:11:09Z

0

The problem is quite literally as you describe: A stack overflow, and it occurs because of:

std::vector<AoS> entities[NUM_ITEMS];

This is an array with 100m std::vector of containing type AoS stored on the stack. Here (MacOSX 10.12.6; Apple LLVM version 7.0.0 (clang-700.0.72) - this results in 24 bytes of storage per element, for a total of ~240MB.

This is problematic as stack-space is finite on all modern operating systems - typically in the range a few MB per thread stack. The stack overflow occurs as the function prologue attempts to default construct the first element in the array (remember: items are stored from high-low memory on the stack, and it's well off the bottom).

When debugging it here, the crash occurs before main() has even started executing. Decreasing the value of NUM_ITEMS results in the program getting considerably further (it crashes at Vector3::operator+=() instead as other have found).

edited Aug 30, 2017 at 22:11

answered Aug 30, 2017 at 21:43

marko

9,1694 gold badges35 silver badges47 bronze badges

2 Comments

Lightningstorms Over a year ago

How can I still use large arrays if it doesn't fit on the stack? I hoped the vector would allocate the memory in a better place but I guess this is not the case.

marko Over a year ago

By allocating it on the heap, presumably.

Collectives™ on Stack Overflow

Stack overflow error in C++ after vectorization

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related