I have a class like this:
//Array of Structures
class Unit
{
public:
float v;
float u;
//And similarly many other variables of float type, upto 10-12 of them.
void update()
{
v+=u;
v=v*i*t;
//And many other equations
}
};
I create an array of objects of Unit type. And call update on them.
int NUM_UNITS = 10000;
void ProcessUpdate()
{
Unit *units = new Unit[NUM_UNITS];
for(int i = 0; i < NUM_UNITS; i++)
{
units[i].update();
}
}
In order to speed up things, and possibly autovectorize the loop, I converted AoS to structure of arrays.
//Structure of Arrays:
class Unit
{
public:
Unit(int NUM_UNITS)
{
v = new float[NUM_UNITS];
}
float *v;
float *u;
//Mnay other variables
void update()
{
for(int i = 0; i < NUM_UNITS; i++)
{
v[i]+=u[i];
//Many other equations
}
}
};
When the loop fails to autovectorize, i am getting a very bad performance for structure of arrays. For 50 units, SoA's update is slightly faster than AoS.But then from 100 units onwards, SoA is slower than AoS. At 300 units, SoA is almost twice as worse. At 100K units, SoA is 4x slower than AoS. While cache might be an issue for SoA, i didnt expect the performance difference to be this high. Profiling on cachegrind shows similar number of misses for both approach. Size of a Unit object is 48 bytes. L1 cache is 256K, L2 is 1MB and L3 is 8MB. What am i missing here? Is this really a cache issue?
Edit: I am using gcc 4.5.2. Compiler options are -o3 -msse4 -ftree-vectorize.
I did another experiment in SoA. Instead of dynamically allocating the arrays, i allocated "v" and "u" in compile time. When there are 100K units, this gives a performance which is 10x faster than the SoA with dynamically allocated arrays. Whats happening here? Why is there such a performance difference between static and dynamically allocated memory?
A structure creates a data type that can be used to group items of possibly different types into a single type. Array refers to a collection consisting of elements of homogeneous data type. Structure refers to a collection consisting of elements of heterogeneous data type.
Structure due to use defined data type become slow in performance as access and searching of element is slower in Structure as compare to Array. On other hand in case of Array access and searching of element is faster and hence better in performance.
Advantages of Structure over Array:The structure can store different types of data whereas an array can only store similar data types. Structure does not have limited size like an array. Structure elements may or may not be stored in contiguous locations but array elements are stored in contiguous locations.
An array of structure in C programming is a collection of different datatype variables, grouped together under a single name. General form of structure declaration. The structural declaration is as follows − struct tagname{ datatype member1; datatype member2; datatype member n; }; Here, struct is the keyword.
Two things you should be aware that can made a huge difference, depending on your CPU:
Since you are using SSE4, using a specialized memory allocation function that returns an address that aligned at a 16 byte boundary instead of new
may give you a boost, since you or the compiler will be able to use aligned load and stores. I have not noticed much difference in newer CPUs, but using unaligned load and stores on older CPUs may be a little bit slower.
As for cache line aliasing, Intel explicit mentions it on its reference manuals (search for "Intel® 64 and IA-32 Architectures Optimization Reference Manual"). Intel says it is something you should be aware, specially when using SoA. So, one thing you can try is to pad your arrays so the lower 6 bits of their addresses are different. The idea is to avoid having them fighting for the same cache line.
Structure of arrays is not cache friendly in this case.
You use both u
and v
together, but in case of 2 different arrays for them they will not be loaded simultaneously into one cache line and cache misses will cost huge performance penalty.
_mm_prefetch
can be used to make AoS
representation even faster.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With