Fastest Possible Struct-of-Arrays to Array-of-Structs Conversion

Question

I have a structure that looks like this:

struct SoA
{
    int arr1[COUNT];
    int arr2[COUNT];
};

And I want it to look like this:

struct AoS
{
    int arr1_data;
    int arr2_data;
};

std::vector<AoS> points;

as quickly as possible. Order must be preserved.

Is constructing each AoS object individually and pushing it back the fastest way to do this, or is there a faster option?

SoA before;
std::vector<AoS> after;

for (int i = 0; i < COUNT; i++)
    points.push_back(AoS(after.arr1[i], after.arr2[i]));

There are SoA/AoS related questions on StackOverflow, but I haven't found one related to fastest-possible conversion. Because of struct packing differences I can't see any way to avoid copying the data from one format to the next, but I'm hoping someone can tell me there's a way to simply reference the data differently and avoid a copy.

Off the wall solutions especially encouraged.

Answer 1

Binary layout of SoA and AoS[]/std::vector<AoS> is different, so there is really no way to transform one to another without copy operation.

Code you have is pretty close to optimal - one improvement maybe to pre-allocate vector with expected number of elements. Alternatively try raw array with both constructing whole element and per-property initialization. Changes need to be measured carefully (definitely measure using fully optimized build with array sizes you expect) and weighted against readabilty/correctness of the code.

If you don't need exact binary layout (seem to be that case as you are using vector) you may be able to achieve similarly looking syntax by creating couple custom classes that would expose existing data differently. This will avoid copying altogether.

You would need "array" type (provide indexing/iteration over instance of SoA) and "element" type (initialized with referece to instance of SoA and index, exposing accessors for separate fields at that index)

Rough sketch of code (add iterators,...):

class AoS_Element
{
   SoA& soa; 
   int index;
 public:
   AoS_Element(SoA& soa, int index) ...
   int arr1_data() { return soa.arr1[index];}
   int arr2_data() { return soa.arr2[index];}
}

class AoS
{
    SoA& soa;
public: 
    AoS(SoA& _soa):soa(_soa){}
    AoS_Element operator[](int index) { return AoS_Element(soa, index);}
}