Thread overview | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
|
May 15, 2017 Structure of Arrays vs Array of Structures | ||||
---|---|---|---|---|
| ||||
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 15, 2017 Re: Structure of Arrays vs Array of Structures | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | 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 15, 2017 Re: Structure of Arrays vs Array of Structures | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nicholas Wilson | 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 Re: Structure of Arrays vs Array of Structures | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nicholas Wilson | 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 Re: Structure of Arrays vs Array of Structures | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | 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 Re: Structure of Arrays vs Array of Structures | ||||
---|---|---|---|---|
| ||||
Posted in reply to Per Nordlöw | 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 23, 2017 Re: Structure of Arrays vs Array of Structures | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | 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 Re: Structure of Arrays vs Array of Structures | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | 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 Re: Structure of Arrays vs Array of Structures | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | 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.".
|
Copyright © 1999-2021 by the D Language Foundation