which is faster, a single array of object, or multiple array of data attributes?

Question

Here is a simplified example. Note that I chose simple types, but in an application I might have many more attribute

struct object
{
    float a, b;
    int c;
};
vector<object> objects;

or

vector<float> a, b;
vector<int> c;

In a game application where you access each attribute at least once, performance might vary. The game loop will run through the whole index, no matter what.

I know the first example is much more convenient (much easier to organize code with one single struct) and that it might depend on what the application is really doing, but isn't the second example more cache friendly ?

I know it's not the proper way to make an application at first with the Knuth premature optimization thing, but I'd just like to know... I've read this in a gamedev slide once and I'm wonder if it's true or not, and why.

I think the only way to know for sure for your specific case is to test it for your specific case. — BoBTFish, Mar 04 '14 at 10:30
The second is more cache friendly in a loop that only accesses one member (or so) of each object. If "you access each attribute at least once", then the first is probably more efficient, as well as more convenient. — Mike Seymour, Mar 04 '14 at 10:33

score 2 · Accepted Answer · answered Mar 04 '14 at 11:24

"It depends!"

Really, there is not only one best data distribution for all the problems, otherwise the compilers and the programming languages would be built around it.

It depends on the algorithm where most of the time is spend in computations.

So, array-of-structs is more cache-friendly/page-miss-friendly; struct-of-arrays is better suited for SSE/AVX SIMD optimization, have better memory channel utilization (that's evident with CUDA for example).

My preferred approach is to start using array-of-objects, and using interfaces only (getter/setters). Than trying to optimize making the objects be an interface to the underlying arrays, in case I have the evidence that I am missing some important optimization by profiling.

and remember... "early optimization is evil of all programming" ;)

+1 for "early optimization is evil..." – hildensia Mar 04 '14 at 11:31 — hildensia, Mar 04 '14 at 11:31

score 2 · Answer 2 · edited May 23 '17 at 12:03

If a, b, c are related and will likely be read together then the struct is more cache friendly.

But packing that puts all the same datatypes together sequentially in memory has the advantage of possibly been (auto) vectorizable.

Anyway some related questions to delve deeper into the matter are:

score 1 · Answer 3 · answered Mar 04 '14 at 10:32

1

In my opinion it is better to have only one vector of class objects than three vectors of its data members. In the last case all operations are duplicated three times including memory allocation/deallocation.

Mpreover in the last case there is a logical inconsistence because these three vectors are not connected with objects. You will be unable to find an object that contains these attributes.

answered Mar 04 '14 at 10:32

Vlad from Moscow

301,070
26
186
335

problem is my access pattern can be very complex, it includes physics, other objects from libraries, so I might not access those thing just once, I might access them to calculate an average, or to access near physical object. For example, in box2d it seems fixtures and bodies are allocated in separates ways, while a fixture actually do belong to a body – jokoon Mar 04 '14 at 11:18

score 1 · Answer 4 · answered Mar 04 '14 at 10:34

1

One vector of objects will probably perform better due to data locality and being more cache friendly, but it's always better to be sure by actually profiling your use scenario, which especially depends on your access pattern.

answered Mar 04 '14 at 10:34

concept3d

2,248
12
21

which is faster, a single array of object, or multiple array of data attributes?

4 Answers4