digitalmars.D.learn - data-oriented struct abstraction ?
- short2cave (35/35) May 30 2015 Consider this struct:
- Rikki Cattermole (2/36) May 30 2015 What exactly are you doing that such a micro optimization is necessary?
- short2cave (23/76) May 30 2015 It's just that i try to concrectly apply some things read in a
- Rikki Cattermole (13/85) May 30 2015 There is one other cost to mention, the human cost. The cost to which
- short2cave (4/109) May 30 2015 template, man, think template. Once it's done it can be
- "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> (4/7) May 30 2015 Right. But I also think to get a good API, you need to know how
- Anonymous (4/121) May 30 2015 This may be somewhat related.
- short2cave (2/126) May 30 2015 Damn, that's it (soa)! Thx a lot for the link.
- "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> (22/22) May 30 2015 Something like this?
- short2cave (27/49) May 30 2015 Yes, kind of. The template should be able to generate the
- Michael Coulombe (62/88) May 31 2015 Proof of concept:
- Vlad Levenfeld (2/2) May 31 2015 Justin Whear pretty much nailed it, I think. What I would really
Consider this struct:
---
Foo
{
uint a,b,c;
float d,e,f;
}
---
in a collection:
---
Foo[] foos;
---
Looping a particular member is not cache friendly
---
foreach(foo;foos){/*foo.a = ...*/}
---
but to write clear, understable, structured code, the struct is
necessary.
So, is it possible to imagine an abstraction such as
---
FooData
{
uint[] a,b,c;
float[] d,e,f;
Foo[] items(){}
}
---
that would allow to loop over the data in a cache-friendly way ?
You think that an item as the member but they are actually stored
using another memory layout ?
A template for this would be particularly usefull:
template DataFriendlyStruct(T) if (is(T==struct) && isPOD!T)
{
alias DataFriendlyStruct = ...
}
May 30 2015
On 30/05/2015 11:46 p.m., short2cave wrote:
Consider this struct:
---
Foo
{
uint a,b,c;
float d,e,f;
}
---
in a collection:
---
Foo[] foos;
---
Looping a particular member is not cache friendly
---
foreach(foo;foos){/*foo.a = ...*/}
---
but to write clear, understable, structured code, the struct is necessary.
So, is it possible to imagine an abstraction such as
---
FooData
{
uint[] a,b,c;
float[] d,e,f;
Foo[] items(){}
}
---
that would allow to loop over the data in a cache-friendly way ?
You think that an item as the member but they are actually stored using
another memory layout ?
A template for this would be particularly usefull:
template DataFriendlyStruct(T) if (is(T==struct) && isPOD!T)
{
alias DataFriendlyStruct = ...
}
What exactly are you doing that such a micro optimization is necessary?
May 30 2015
On Saturday, 30 May 2015 at 12:34:21 UTC, Rikki Cattermole wrote:On 30/05/2015 11:46 p.m., short2cave wrote:It's just that i try to concrectly apply some things read in a paper a few monthes ago. I won't be able to find the link again but the idea is simple, here is a short summary:Consider this struct: --- Foo { uint a,b,c; float d,e,f; } --- in a collection: --- Foo[] foos; --- Looping a particular member is not cache friendly --- foreach(foo;foos){/*foo.a = ...*/} --- but to write clear, understable, structured code, the struct is necessary. So, is it possible to imagine an abstraction such as --- FooData { uint[] a,b,c; float[] d,e,f; Foo[] items(){} } --- that would allow to loop over the data in a cache-friendly way ? You think that an item as the member but they are actually stored using another memory layout ? A template for this would be particularly usefull: template DataFriendlyStruct(T) if (is(T==struct) && isPOD!T) { alias DataFriendlyStruct = ... }What exactly are you doing that such a micro optimization is necessary?structured types are dead, people gotta stup using classes and structs. >They're not efficient.That's not a scoop. Programs are slow because of that but struct and class allow a complexity in the design that you can't reach with globals. The problem if you have global declarations of data everywhere things become quickly super heavy, for example: --- float[] effect1_filter_1_omega; float[] effect1_filter_2_omega; float[] effect2_filter_1_omega; float[] effect2_filter_2_omega; float[] voice1_osc1_phasemod_source1 float[] voice1_osc2_phasemod_source2 float[] voice2_osc1_phasemod_source1 float[] voice2_osc2_phasemod_source2 --- efficient to loop but imagine that we talking about 8 oscillators, 32 voices per oscillator, 2 effects per voice, etc... so an abstraction is required to give a "pseudo-structured-interface".
May 30 2015
On 31/05/2015 1:49 a.m., short2cave wrote:On Saturday, 30 May 2015 at 12:34:21 UTC, Rikki Cattermole wrote:There is one other cost to mention, the human cost. The cost to which the developer takes to understand it. That's why I called it a micro optimisation. But in this case, it will still depend upon what you are doing. Food for thought. CPU caches are pretty weird now days. You can't really predicate what will go into them and when. So while yes you would put everything into arrays to group the data. You probably will be relying on an item from one and an item for another. So a struct should be a unit of work. Also allocated the array in one go. Large as possible. It'll make things a little bit happier. I can't really talk about much else.On 30/05/2015 11:46 p.m., short2cave wrote:It's just that i try to concrectly apply some things read in a paper a few monthes ago. I won't be able to find the link again but the idea is simple, here is a short summary:Consider this struct: --- Foo { uint a,b,c; float d,e,f; } --- in a collection: --- Foo[] foos; --- Looping a particular member is not cache friendly --- foreach(foo;foos){/*foo.a = ...*/} --- but to write clear, understable, structured code, the struct is necessary. So, is it possible to imagine an abstraction such as --- FooData { uint[] a,b,c; float[] d,e,f; Foo[] items(){} } --- that would allow to loop over the data in a cache-friendly way ? You think that an item as the member but they are actually stored using another memory layout ? A template for this would be particularly usefull: template DataFriendlyStruct(T) if (is(T==struct) && isPOD!T) { alias DataFriendlyStruct = ... }What exactly are you doing that such a micro optimization is necessary?structured types are dead, people gotta stup using classes and structs. >They're not efficient.That's not a scoop. Programs are slow because of that but struct and class allow a complexity in the design that you can't reach with globals. The problem if you have global declarations of data everywhere things become quickly super heavy, for example: --- float[] effect1_filter_1_omega; float[] effect1_filter_2_omega; float[] effect2_filter_1_omega; float[] effect2_filter_2_omega; float[] voice1_osc1_phasemod_source1 float[] voice1_osc2_phasemod_source2 float[] voice2_osc1_phasemod_source1 float[] voice2_osc2_phasemod_source2 --- efficient to loop but imagine that we talking about 8 oscillators, 32 voices per oscillator, 2 effects per voice, etc... so an abstraction is required to give a "pseudo-structured-interface".
May 30 2015
On Saturday, 30 May 2015 at 13:57:28 UTC, Rikki Cattermole wrote:On 31/05/2015 1:49 a.m., short2cave wrote:template, man, think template. Once it's done it can be instantiated at the ∞ with any struct used as model. A library template, a type cons. Once the template done, it has 0 cost.On Saturday, 30 May 2015 at 12:34:21 UTC, Rikki Cattermole wrote:There is one other cost to mention, the human cost. The cost to which the developer takes to understand it. That's why I called it a micro optimisation. But in this case, it will still depend upon what you are doing. Food for thought. CPU caches are pretty weird now days. You can't really predicate what will go into them and when. So while yes you would put everything into arrays to group the data. You probably will be relying on an item from one and an item for another. So a struct should be a unit of work. Also allocated the array in one go. Large as possible. It'll make things a little bit happier. I can't really talk about much else.On 30/05/2015 11:46 p.m., short2cave wrote:It's just that i try to concrectly apply some things read in a paper a few monthes ago. I won't be able to find the link again but the idea is simple, here is a short summary:Consider this struct: --- Foo { uint a,b,c; float d,e,f; } --- in a collection: --- Foo[] foos; --- Looping a particular member is not cache friendly --- foreach(foo;foos){/*foo.a = ...*/} --- but to write clear, understable, structured code, the struct is necessary. So, is it possible to imagine an abstraction such as --- FooData { uint[] a,b,c; float[] d,e,f; Foo[] items(){} } --- that would allow to loop over the data in a cache-friendly way ? You think that an item as the member but they are actually stored using another memory layout ? A template for this would be particularly usefull: template DataFriendlyStruct(T) if (is(T==struct) && isPOD!T) { alias DataFriendlyStruct = ... }What exactly are you doing that such a micro optimization is necessary?structured types are dead, people gotta stup using classes and structs. >They're not efficient.That's not a scoop. Programs are slow because of that but struct and class allow a complexity in the design that you can't reach with globals. The problem if you have global declarations of data everywhere things become quickly super heavy, for example: --- float[] effect1_filter_1_omega; float[] effect1_filter_2_omega; float[] effect2_filter_1_omega; float[] effect2_filter_2_omega; float[] voice1_osc1_phasemod_source1 float[] voice1_osc2_phasemod_source2 float[] voice2_osc1_phasemod_source1 float[] voice2_osc2_phasemod_source2 --- efficient to loop but imagine that we talking about 8 oscillators, 32 voices per oscillator, 2 effects per voice, etc... so an abstraction is required to give a "pseudo-structured-interface".
May 30 2015
"Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> On Saturday, 30 May 2015 at 14:17:51 UTC, short2cave wrote:template, man, think template. Once it's done it can be instantiated at the ∞ with any struct used as model. A library template, a type cons. Once the template done, it has 0 cost.Right. But I also think to get a good API, you need to know how it will be used in practice. So there's probably not a solution that "fits all sizes".
May 30 2015
This may be somewhat related. http://forum.dlang.org/thread/ckeqxhkqjyvmqodrfhhj forum.dlang.org#post-m9rj0d:242m9e:243:40digitalmars.com https://github.com/economicmodeling/soa On Saturday, 30 May 2015 at 14:17:51 UTC, short2cave wrote:On Saturday, 30 May 2015 at 13:57:28 UTC, Rikki Cattermole wrote:On 31/05/2015 1:49 a.m., short2cave wrote:template, man, think template. Once it's done it can be instantiated at the ∞ with any struct used as model. A library template, a type cons. Once the template done, it has 0 cost.On Saturday, 30 May 2015 at 12:34:21 UTC, Rikki Cattermole wrote:There is one other cost to mention, the human cost. The cost to which the developer takes to understand it. That's why I called it a micro optimisation. But in this case, it will still depend upon what you are doing. Food for thought. CPU caches are pretty weird now days. You can't really predicate what will go into them and when. So while yes you would put everything into arrays to group the data. You probably will be relying on an item from one and an item for another. So a struct should be a unit of work. Also allocated the array in one go. Large as possible. It'll make things a little bit happier. I can't really talk about much else.On 30/05/2015 11:46 p.m., short2cave wrote:It's just that i try to concrectly apply some things read in a paper a few monthes ago. I won't be able to find the link again but the idea is simple, here is a short summary:Consider this struct: --- Foo { uint a,b,c; float d,e,f; } --- in a collection: --- Foo[] foos; --- Looping a particular member is not cache friendly --- foreach(foo;foos){/*foo.a = ...*/} --- but to write clear, understable, structured code, the struct is necessary. So, is it possible to imagine an abstraction such as --- FooData { uint[] a,b,c; float[] d,e,f; Foo[] items(){} } --- that would allow to loop over the data in a cache-friendly way ? You think that an item as the member but they are actually stored using another memory layout ? A template for this would be particularly usefull: template DataFriendlyStruct(T) if (is(T==struct) && isPOD!T) { alias DataFriendlyStruct = ... }What exactly are you doing that such a micro optimization is necessary?structured types are dead, people gotta stup using classes and structs. >They're not efficient.That's not a scoop. Programs are slow because of that but struct and class allow a complexity in the design that you can't reach with globals. The problem if you have global declarations of data everywhere things become quickly super heavy, for example: --- float[] effect1_filter_1_omega; float[] effect1_filter_2_omega; float[] effect2_filter_1_omega; float[] effect2_filter_2_omega; float[] voice1_osc1_phasemod_source1 float[] voice1_osc2_phasemod_source2 float[] voice2_osc1_phasemod_source1 float[] voice2_osc2_phasemod_source2 --- efficient to loop but imagine that we talking about 8 oscillators, 32 voices per oscillator, 2 effects per voice, etc... so an abstraction is required to give a "pseudo-structured-interface".
May 30 2015
On Saturday, 30 May 2015 at 14:32:01 UTC, Anonymous wrote:This may be somewhat related. http://forum.dlang.org/thread/ckeqxhkqjyvmqodrfhhj forum.dlang.org#post-m9rj0d:242m9e:243:40digitalmars.com https://github.com/economicmodeling/soa On Saturday, 30 May 2015 at 14:17:51 UTC, short2cave wrote:Damn, that's it (soa)! Thx a lot for the link.On Saturday, 30 May 2015 at 13:57:28 UTC, Rikki Cattermole wrote:On 31/05/2015 1:49 a.m., short2cave wrote:template, man, think template. Once it's done it can be instantiated at the ∞ with any struct used as model. A library template, a type cons. Once the template done, it has 0 cost.On Saturday, 30 May 2015 at 12:34:21 UTC, Rikki Cattermole wrote:There is one other cost to mention, the human cost. The cost to which the developer takes to understand it. That's why I called it a micro optimisation. But in this case, it will still depend upon what you are doing. Food for thought. CPU caches are pretty weird now days. You can't really predicate what will go into them and when. So while yes you would put everything into arrays to group the data. You probably will be relying on an item from one and an item for another. So a struct should be a unit of work. Also allocated the array in one go. Large as possible. It'll make things a little bit happier. I can't really talk about much else.On 30/05/2015 11:46 p.m., short2cave wrote:It's just that i try to concrectly apply some things read in a paper a few monthes ago. I won't be able to find the link again but the idea is simple, here is a short summary:Consider this struct: --- Foo { uint a,b,c; float d,e,f; } --- in a collection: --- Foo[] foos; --- Looping a particular member is not cache friendly --- foreach(foo;foos){/*foo.a = ...*/} --- but to write clear, understable, structured code, the struct is necessary. So, is it possible to imagine an abstraction such as --- FooData { uint[] a,b,c; float[] d,e,f; Foo[] items(){} } --- that would allow to loop over the data in a cache-friendly way ? You think that an item as the member but they are actually stored using another memory layout ? A template for this would be particularly usefull: template DataFriendlyStruct(T) if (is(T==struct) && isPOD!T) { alias DataFriendlyStruct = ... }What exactly are you doing that such a micro optimization is necessary?structured types are dead, people gotta stup using classes and structs. >They're not efficient.That's not a scoop. Programs are slow because of that but struct and class allow a complexity in the design that you can't reach with globals. The problem if you have global declarations of data everywhere things become quickly super heavy, for example: --- float[] effect1_filter_1_omega; float[] effect1_filter_2_omega; float[] effect2_filter_1_omega; float[] effect2_filter_2_omega; float[] voice1_osc1_phasemod_source1 float[] voice1_osc2_phasemod_source2 float[] voice2_osc1_phasemod_source1 float[] voice2_osc2_phasemod_source2 --- efficient to loop but imagine that we talking about 8 oscillators, 32 voices per oscillator, 2 effects per voice, etc... so an abstraction is required to give a "pseudo-structured-interface".
May 30 2015
Something like this?
struct S {
static int[] a_;
static float[] b_;
const size_t idx;
property ref int a() { return a_[idx]; }
property ref float b() { return b_[idx]; }
void opAssign(const S other) {
a_[idx] = a_[other.idx];
b_[idx] = b_[other.idx];
}
// opSliceAssign() ...
}
// ... initialize S.a_ and S.b_ here ...
auto s = S(200); // 200th entry
writefln("a = %s, b = %s", s.a, s.b);
You can then simply iterate over S.a_ directly. With some UDA and
mixin template magic, the accessors can be generated
automatically.
Of course, depending on what you're actually trying to do with
it, other abstractions may be more useful to support your typical
access patterns.
May 30 2015
On Saturday, 30 May 2015 at 14:23:37 UTC, Marc Schütz wrote:
Something like this?
struct S {
static int[] a_;
static float[] b_;
const size_t idx;
property ref int a() { return a_[idx]; }
property ref float b() { return b_[idx]; }
void opAssign(const S other) {
a_[idx] = a_[other.idx];
b_[idx] = b_[other.idx];
}
// opSliceAssign() ...
}
// ... initialize S.a_ and S.b_ here ...
auto s = S(200); // 200th entry
writefln("a = %s, b = %s", s.a, s.b);
You can then simply iterate over S.a_ directly. With some UDA
and mixin template magic, the accessors can be generated
automatically.
Of course, depending on what you're actually trying to do with
it, other abstractions may be more useful to support your
typical access patterns.
Yes, kind of. The template should be able to generate the
accessors using the fields of the struct passed as template
argument. But also a special accessor wich returns all the items
accessors, in a structured way:
---
struct Model
{
uint a, b;
}
template Structured(T)
{
alias Structured = ...;
}
---
allowing things like:
---
Structured!Model sm;
sm[0].a = 0;
sm[0].b = 0;
auto item = sm[0];
sm.a = 0;
sm.pushBack;
auto item = sm.back;
sm.length += 1,
---
etc.
May 30 2015
On Saturday, 30 May 2015 at 15:06:16 UTC, short2cave wrote:
Yes, kind of. The template should be able to generate the
accessors using the fields of the struct passed as template
argument. But also a special accessor wich returns all the
items accessors, in a structured way:
---
struct Model
{
uint a, b;
}
template Structured(T)
{
alias Structured = ...;
}
---
allowing things like:
---
Structured!Model sm;
sm[0].a = 0;
sm[0].b = 0;
auto item = sm[0];
sm.a = 0;
sm.pushBack;
auto item = sm.back;
sm.length += 1,
---
etc.
Proof of concept:
import std.stdio, std.string, std.typetuple, std.traits,
std.container;
private auto genIndexerCode(string[] memberNames) {
enum f = ` property auto ref %s() { return
__parent.members[%s][__index]; }`;
string s = "";
foreach(i, member ; memberNames) {
s ~= format(f, member, i);
}
return s;
}
class ArrayOf(S) if (is(S == struct) && !isNested!S) {
private:
alias memberNames = FieldNameTuple!S;
alias memberTypes = FieldTypeTuple!S;
staticMap!(Array, memberTypes) members;
static struct Indexer {
private:
ArrayOf!S __parent;
size_t __index;
public:
S __get() {
S copy;
foreach(member ; memberNames) {
mixin(`copy.%s = this.%s;`.format(member,member));
}
return copy;
}
alias __get this;
void opAssign(S src) {
foreach(member ; memberNames) {
mixin(`this.%s = src.%s;`.format(member,member));
}
}
mixin(genIndexerCode([memberNames]));
}
public:
this() {}
auto opIndex(size_t i) {
return Indexer(this, i);
}
void insertBack(S s) {
foreach(i, mem ; memberNames) {
mixin(`members[%s].insertBack(s.%s);`.format(i, mem));
}
}
}
struct Test {
int x;
string y;
}
unittest {
auto aos = new ArrayOf!Test();
aos.insertBack(Test(5, "hi"));
aos[0].x = -7;
aos.insertBack(Test.init);
aos[1] = Test(11,"boo");
assert(aos[0] == Test(-7,"hi"));
assert(aos[1] == Test(11,"boo"));
}
May 31 2015
Justin Whear pretty much nailed it, I think. What I would really like to see is some benchmarks.
May 31 2015