AoS vs SoA

26, Apr, 2019

Math and performance can be complicated. Most interesting transformations acts on 3-vector (a position, normal, …), but SIMD instructions acts on powers-of-two - eg. on 4 or 8 components. One may use homogeneous coordinates with 4-vectors (wher w component is distinction between vector and pseudovector) and use 4×4 matrix for general transformations (translation/rotation/dilation/shears…). However, most useful are only translation, rotation and uniform scaling. And most efficient (by means of number of operations) implementation of those transformations is to use 3×3 matrix (rotation/dilation) paired with translation vector. This reduces computation from 16 multiplies and 12 additions to only 9 multiplies (matrix) and 9 additions (6 for matrix multiply 3 for translation).

But, the common way of storing 3 vectors as array is to store components in the interleaved form (x0, y0, z0, x1, y1, z1, x2, …). Or more straight way:

struct {
    type x;
    type y;
    type z;
} vectors[];

It also named AoS, the Array of Structures. So the trivial approach would require to load unaligned that, mask of last vector, and omit 1/4 of vector operations to do the job. More, advanced approach would load 4 consecutive vectors and shuffle them, so each operation will act on x, y or z component of consecutive four vectors. But, maybe we can eliminate shuffling?

This can be done by arranging vector components in separate arrays (x0, x1, x2,…) (y0, y1,…) (z0,…) in C:

struct {
    type *x;
    type *y;
    type *z;
} vectors;

It is so called SoA - the Struct of Arrays. Now, vectors can be loaded an transformed without any additional operations. However, this also may have some drawbacks. We need to use 3x more address registers (one for each array) - as these are spare on x86/amd64 - possibly loading and storing them (ah why PowerPC hasn’t won?!). This maybe solved also by storing these arrays one by one so from one address next may be reached - but this mostly will require additional instructions (or use of some more fat instructions). Also the cache management may be more challenging - we may need also to hint processor about what shall be in cache.

So, is there any golden bullet. Yes, it is. The AoSoA - array of structs of arrays. Simply write it down:

struct {
    type x[4];    /* 4 or whatever fits in your SIMD register */
    type y[4];
    type z[4];
} vectors[];

In this arrangement we only need one address register for input (possibly another for output), there is only one stream which goes through the cache to the CPU and all SoA optimizations are in place.

So, long live the AoSoA!

p.s. Have you seen that, I did not specify the type? Isn’t it a float? But, that is another story…