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 = ...
}

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?

On Saturday, 30 May 2015 at 12:34:21 UTC, Rikki Cattermole wrote:
> 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?

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:

>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".

On 31/05/2015 1:49 a.m., short2cave wrote:
> On Saturday, 30 May 2015 at 12:34:21 UTC, Rikki Cattermole wrote:
>> 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?
>
> 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:
>
>> 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".

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 Saturday, 30 May 2015 at 13:57:28 UTC, Rikki Cattermole wrote:
> On 31/05/2015 1:49 a.m., short2cave wrote:
>> On Saturday, 30 May 2015 at 12:34:21 UTC, Rikki Cattermole wrote:
>>> 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?
>>
>> 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:
>>
>>> 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".
>
> 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.

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.

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.

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".

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:
>>> On Saturday, 30 May 2015 at 12:34:21 UTC, Rikki Cattermole wrote:
>>>> 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?
>>>
>>> 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:
>>>
>>>> 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".
>>
>> 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.
>
> 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 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:
>> On Saturday, 30 May 2015 at 13:57:28 UTC, Rikki Cattermole wrote:
>>> On 31/05/2015 1:49 a.m., short2cave wrote:
>>>> On Saturday, 30 May 2015 at 12:34:21 UTC, Rikki Cattermole wrote:
>>>>> 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?
>>>>
>>>> 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:
>>>>
>>>>> 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".
>>>
>>> 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.
>>
>> 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.

Damn, that's it (soa)! Thx a lot for the link.

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.