www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Structure of Arrays vs Array of Structures

reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
After having watched Jonathan Blow's talk on Jai

https://www.youtube.com/watch?v=TH9VCN6UkyQ&t=2880s

I realized that we should add his Array-of-Structures (AoS) 
concept to Phobos, preferrably in std.typecons.StructArrays, as 
something like

template StructArrays(Members...)
{
     struct StructArrays
     {
         // template mixin magic that creates

         // a pointers elements plus accessors for each Member in 
Members

         // element type for members functions that
         // mimic array of structures
         struct Struct
         {
             Members members;
         }

         // and used here
         Struct byStruct() // perhaps also opSlice
         {
              // returns call to map
         }

         size_t length;
     }
}

Have anybody done this already?
May 14
parent reply Nicholas Wilson <iamthewilsonator hotmail.com> writes:
On Monday, 15 May 2017 at 06:44:53 UTC, Nordlöw wrote:
 After having watched Jonathan Blow's talk on Jai

 https://www.youtube.com/watch?v=TH9VCN6UkyQ&t=2880s

 I realized that we should add his Array-of-Structures (AoS) 
 concept to Phobos, preferrably in std.typecons.StructArrays, as 
 something like

 template StructArrays(Members...)
 {
     struct StructArrays
     {
         // template mixin magic that creates

         // a pointers elements plus accessors for each Member 
 in Members

         // element type for members functions that
         // mimic array of structures
         struct Struct
         {
             Members members;
         }

         // and used here
         Struct byStruct() // perhaps also opSlice
         {
              // returns call to map
         }

         size_t length;
     }
 }

 Have anybody done this already?
Yes, https://maikklein.github.io/post/soa-d/
May 14
next sibling parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Monday, 15 May 2017 at 06:50:04 UTC, Nicholas Wilson wrote:
 Yes, https://maikklein.github.io/post/soa-d/
Ok, great. Thanks. I can't seem to find any Github code repo, tough. Does it exist?
May 15
parent Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Monday, 15 May 2017 at 07:31:25 UTC, Nordlöw wrote:
 On Monday, 15 May 2017 at 06:50:04 UTC, Nicholas Wilson wrote:
 Yes, https://maikklein.github.io/post/soa-d/
Ok, great. Thanks. I can't seem to find any Github code repo, tough. Does it exist?
Here's my fixed version of soa-d that doesn't use Tuple and therefore compiles and links 3 times as fast. https://github.com/nordlow/phobos-next/blob/master/src/soa.d
May 15
prev sibling parent Stanislav Blinov <stanislav.blinov gmail.com> writes:
On Monday, 15 May 2017 at 06:50:04 UTC, Nicholas Wilson wrote:
 On Monday, 15 May 2017 at 06:44:53 UTC, Nordlöw wrote:
 Have anybody done this already?
Yes, https://maikklein.github.io/post/soa-d/
The code in that article is overly simplified. Concrete use cases would require more than just storing one POD type. Looking back at Jonathan Blow's example, what if you wanted to store this type in a SoA?
struct Entity {
    Vector3 position;
    Quaternion orientation;
}
This, obviously, gets more involved, as now the SoA code needs to flatten that whole type recursively, otherwise it'd just store vectors packed together and then quaternions packed together, i.e: [vx0, vy0, vz0, vx1, vy1, vz1...][qx0, qy0, qz0, qw0, qx1, qy1, qz1, qw1...] whereas it should store [vx0, vx1...][vy0, vy1...][vz0, vz1...][qx0, qx1...][qy0, qy1...][qz0, qz1...][qw0, qw1...] Then, if you need to occasionally reassemble PODs from SoA, you need to deal with member alignment. And then there's a matter of providing actual functions dealing with types that are sparsely stored. Also, there is a... debatable assessment of viability there:
But sometimes you still want to access all components of your 
data. An example would be a >vector. [...]
Most operations will use all components anyways like add, 
subtract, dot, length and many >more. And even if you sometimes 
end up with

struct Vec3{
    float x;
    float y;
    float z;
}

Array!Vec3 positions;

positions[].filter!(v => v.x < 10.0f);

and you want to filter all vectors where the x component is less 
than 10.0f, you will >still only load two additional floats.
"You will still *only* load two additional floats": that is incorrect. The CPU (at least, x86/64) won't load "only" two floats. It first needs to fetch the whole cache line only to touch every third float in it. That's ~66% of access time wasted. (Imagine how severe that is if it actually has to fetch from RAM. Scratch that, don't imagine, time it.). And if you not only read, but write data, it gets that much more wasteful. That is precisely the problem SoA is intended to solve: it would always visit 100% of data it needs to fetch. But of course, if you do need to reconstruct tightly packed PODs from SoA, you'll get a pretty severe penalty. So, once you commit to storing data this way, you have to organize the code accordingly, otherwise you're more likely to degrade performance rather than gain it. I do have an ongoing code experiment to see how far D could take us with it, but at this point it's rather immature. Perhaps in a couple of weeks I'd get it to a state that I could publish, if you guys would like to pitch in.
May 15