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 reply 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
parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Monday, 15 May 2017 at 17:10:49 UTC, Per Nordlöw wrote:
 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
I'm trying to implement reference access via for instance T.init[0].i given that struct S { int i, float f; } alias T = SOA!S; by adding /// Reference to element in `soaPtr` at index `elementIndex`. private struct ElementRef { SOA* soaPtr; size_t elementIndex; auto ref opDispatch(string name)() trusted return scope { return (*soaPtr).name[elementIndex]; } } but when I also define ref inout(ElementRef) opIndex(size_t elementIndex) inout return scope { return ElementRef(this, elementIndex); } the compilation errors as soa.d-mixin-143(143,7): Error: variable soa.SOA!(S).SOA.container0LU cannot be further field because it will change the determined SOA size soa.d-mixin-143(143,28): Error: variable soa.SOA!(S).SOA.container1LU cannot be further field because it will change the determined SOA size soa.d(193,14): Error: template instance soa.SOA!(S) error instantiating soa.d(195,5): Error: static assert (is(typeof((__error)()) == int[])) is false What's wrong?
May 15
parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Monday, 15 May 2017 at 19:52:03 UTC, Nordlöw wrote:
 soa.d-mixin-143(143,7): Error: variable 
 soa.SOA!(S).SOA.container0LU cannot be further field because it 
 will change the determined SOA size
 soa.d-mixin-143(143,28): Error: variable 
 soa.SOA!(S).SOA.container1LU cannot be further field because it 
 will change the determined SOA size
 soa.d(193,14): Error: template instance soa.SOA!(S) error 
 instantiating
 soa.d(195,5): Error: static assert  (is(typeof((__error)()) == 
 int[])) is false

 What's wrong?
When I removed the scope qualifier I went forward with `opDispatch` to make it work here http://forum.dlang.org/post/wvulryummkqtskiwrusb forum.dlang.org What about adding this little D-magic to std.typecons?
May 23
parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Tuesday, 23 May 2017 at 16:46:18 UTC, Nordlöw wrote:
 http://forum.dlang.org/post/wvulryummkqtskiwrusb forum.dlang.org
Correction; should be: https://github.com/nordlow/phobos-next/blob/a324f16515bd1c3c1185ba0482dae2886d811bb1/src/soa.d
May 23
parent Stanislav Blinov <stanislav.blinov gmail.com> writes:
On Tuesday, 23 May 2017 at 16:48:31 UTC, Nordlöw wrote:
 On Tuesday, 23 May 2017 at 16:46:18 UTC, Nordlöw wrote:
 http://forum.dlang.org/post/wvulryummkqtskiwrusb forum.dlang.org
Correction; should be: https://github.com/nordlow/phobos-next/blob/a324f16515bd1c3c1185ba0482dae2886d811bb1/src/soa.d
What if you instantiate it with a nested struct? What about structs that themselves aggregate other structs? What about custom operators on such structs?.. As I said earlier, generic solution is not easy. The implementation you have is very niche, certainly not "std.".
May 23
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