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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017