www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - Interesting work on packing tuple layout

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
https://github.com/ZigaSajovic/optimizing-the-memory-layout-of-std-tuple

Would be interesting to adapt it for std.tuple.
Jun 13 2020
next sibling parent user1234 <user1234 12.de> writes:
On Saturday, 13 June 2020 at 19:11:33 UTC, Andrei Alexandrescu 
wrote:

 https://github.com/ZigaSajovic/optimizing-the-memory-layout-of-std-tuple

 Would be interesting to adapt it for std.tuple.


Look possible. At first glance, staticSort on the template 
variadic argument based on a predicate template that looks at 
alignment of element maybe.

   struct Tuple(A...)
   {
       staticsort!(pred, A) members;
   }

although with the possibility to name each member this will be in 
practice more complicated
Jun 13 2020
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 13.06.20 21:11, Andrei Alexandrescu wrote:

 https://github.com/ZigaSajovic/optimizing-the-memory-layout-of-std-tuple
 
 Would be interesting to adapt it for std.tuple.
 


That's likely to run into the following arbitrary language limitation:

---
alias Seq(T...)=T;
struct T{
     int a,b;
     alias expand=Seq!(b,a);
}
void main(){
     import std.stdio;
     writeln(T(1,2).expand);
}
---
Error: need `this` for `b` of type `int`
Error: need `this` for `a` of type `int`
---

Another question is if automatic packing is worth making the layout 
harder to predict.
Jun 13 2020
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/13/20 7:30 PM, Timon Gehr wrote:

 Another question is if automatic packing is worth making the layout 
 harder to predict.


I think so. Size does matter.
Jun 13 2020
parent reply Avrina <avrina12309412342 gmail.com> writes:
On Sunday, 14 June 2020 at 03:08:48 UTC, Andrei Alexandrescu 
wrote:

 On 6/13/20 7:30 PM, Timon Gehr wrote:

 Another question is if automatic packing is worth making the 
 layout harder to predict.


 I think so. Size does matter.


If you are talking about implementing a tuple type into the 
language, and that the *default* behavior should be that it 
stores the elements in a tuple in memory to be as efficiently as 
it can be. That would be more limiting. If implemented correctly 
then a tuple that store it in memory the way it is specified in 
order. Then you could implement the storing one on top of it with 
a library implementation. This will allow the user to customize 
how it is stored. What is efficient or not could differ from 
person to person and what they are doing. If it was implemented 
in the language with it changing the storage to be organized for 
size. Then you couldn't implement anything any other way, you are 
stuck with what is forced on you.
Jun 13 2020
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/13/20 11:55 PM, Avrina wrote:

 On Sunday, 14 June 2020 at 03:08:48 UTC, Andrei Alexandrescu wrote:

 On 6/13/20 7:30 PM, Timon Gehr wrote:

 Another question is if automatic packing is worth making the layout 
 harder to predict.


 I think so. Size does matter.


 
 If you are talking about implementing a tuple type into the language, 


negative
Jun 13 2020
parent reply Avrina <avrina12309412342 gmail.com> writes:
On Sunday, 14 June 2020 at 03:57:40 UTC, Andrei Alexandrescu 
wrote:

 On 6/13/20 11:55 PM, Avrina wrote:

 On Sunday, 14 June 2020 at 03:08:48 UTC, Andrei Alexandrescu 
 wrote:

 On 6/13/20 7:30 PM, Timon Gehr wrote:

 Another question is if automatic packing is worth making the 
 layout harder to predict.


 I think so. Size does matter.


 
 If you are talking about implementing a tuple type into the 
 language,


 negative


The situation also applies to the only tuple implementation in D. 
If you are proposing a new type with emphasis on reducing the 
footprint of the tuple then I don't see a problem with that. 
Changing the existing tuple implementation would be problematic.
Jun 14 2020
next sibling parent reply Paul Backus <snarwin gmail.com> writes:
On Sunday, 14 June 2020 at 16:26:17 UTC, Avrina wrote:

 The situation also applies to the only tuple implementation in 
 D. If you are proposing a new type with emphasis on reducing 
 the footprint of the tuple then I don't see a problem with 
 that. Changing the existing tuple implementation would be 
 problematic.


Presumably any such change would be made backwards-compatible. So 
Tuple.opIndex and Tuple.expand would still return elements in the 
order specified by the user, even if that order is different from 
the internal storage order.
Jun 14 2020
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 14.06.20 20:25, Paul Backus wrote:

 On Sunday, 14 June 2020 at 16:26:17 UTC, Avrina wrote:

 The situation also applies to the only tuple implementation in D. If 
 you are proposing a new type with emphasis on reducing the footprint 
 of the tuple then I don't see a problem with that. Changing the 
 existing tuple implementation would be problematic.


 
 Presumably any such change would be made backwards-compatible. So 
 Tuple.opIndex and Tuple.expand would still return elements in the order 
 specified by the user, even if that order is different from the internal 
 storage order.


Indeed, that's why I noted that the obvious way to achieve that does not 
work. Although some assumptions will break, for example, there might be 
code that assumes that tupleof does the same thing as expand.

I was thinking about e.g., manual cache optimization, but reducing size 
in the common case where such considerations are not made may well be 
more important. If it can be done at all; I am not currently aware of a 
workaround.
Jun 14 2020
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/14/20 3:36 PM, Timon Gehr wrote:

 On 14.06.20 20:25, Paul Backus wrote:

 On Sunday, 14 June 2020 at 16:26:17 UTC, Avrina wrote:

 The situation also applies to the only tuple implementation in D. If 
 you are proposing a new type with emphasis on reducing the footprint 
 of the tuple then I don't see a problem with that. Changing the 
 existing tuple implementation would be problematic.


 Presumably any such change would be made backwards-compatible. So 
 Tuple.opIndex and Tuple.expand would still return elements in the 
 order specified by the user, even if that order is different from the 
 internal storage order.


 
 Indeed, that's why I noted that the obvious way to achieve that does not 
 work. Although some assumptions will break, for example, there might be 
 code that assumes that tupleof does the same thing as expand.
 
 I was thinking about e.g., manual cache optimization, but reducing size 
 in the common case where such considerations are not made may well be 
 more important. If it can be done at all; I am not currently aware of a 
 workaround.


It's really easy if members in the layout are given internal names that 
include information about the original index.
Jun 14 2020
parent reply Max Samukha <maxsamukha gmail.com> writes:
On Sunday, 14 June 2020 at 23:30:03 UTC, Andrei Alexandrescu 
wrote:

 It's really easy if members in the layout are given internal 
 names that include information about the original index.


You can construct a list of member aliases in the original order 
and then 'alias this' that:

import std.meta;

struct Tuple(A...) {
     alias Reordered = AliasSeq!(A[1], A[2], A[0]);
     Reordered value;

     alias reordered = AliasSeq!(typeof(this).tupleof);
     alias original = AliasSeq!(reordered[2], reordered[0], 
reordered[1]);
     alias original this;
}

void main() {
     Tuple!(byte, int, short) t;

     static assert(is(typeof(t.tupleof) == AliasSeq!(int, short, 
byte)));

     static assert(is(typeof(t[0]) == byte));
     static assert(is(typeof(t[1]) == int));
     static assert(is(typeof(t[2]) == short));
}
Jun 15 2020
parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On Monday, 15 June 2020 at 13:34:18 UTC, Max Samukha wrote:

 On Sunday, 14 June 2020 at 23:30:03 UTC, Andrei Alexandrescu 
 wrote:

 It's really easy if members in the layout are given internal 
 names that include information about the original index.


 You can construct a list of member aliases in the original 
 order and then 'alias this' that:


typeof(t[0]) works fine, but reading or assigning to such a field 
will not work. For example:

void main() {
     Tuple!(byte, int, short) t;
     writeln(t[0]);
}


 test.d(57,23): Error: need `this` for `__value_field_2` of type 
 `byte`
Jun 15 2020
parent reply Max Samukha <maxsamukha gmail.com> writes:
On Monday, 15 June 2020 at 13:50:07 UTC, Andrej Mitrovic wrote:


 typeof(t[0]) works fine, but reading or assigning to such a 
 field will not work. For example:

 void main() {
     Tuple!(byte, int, short) t;
     writeln(t[0]);
 }


 test.d(57,23): Error: need `this` for `__value_field_2` of 
 type `byte`




It should work. This works:

void main() {
     Tuple!(byte, int, short) t;

     t[0] = 0;
     t[1] = 2;
     t[2] = 3;

     auto a0 = t[0];
     auto a1 = t[1];
}
}
Jun 15 2020
parent reply Max Samukha <maxsamukha gmail.com> writes:
On Monday, 15 June 2020 at 13:57:01 UTC, Max Samukha wrote:


 void main() {
     Tuple!(byte, int, short) t;
     writeln(t[0]);
 }


 test.d(57,23): Error: need `this` for `__value_field_2` of 
 type `byte`




 It should work. This works:

 void main() {
     Tuple!(byte, int, short) t;

     t[0] = 0;
     t[1] = 2;
     t[2] = 3;

     auto a0 = t[0];
     auto a1 = t[1];
 }
 }


I cannot reproduce the error. writeln(t[0]) works here: 
https://run.dlang.io/is/kz6lFc
Jun 15 2020
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 15.06.20 16:03, Max Samukha wrote:

 On Monday, 15 June 2020 at 13:57:01 UTC, Max Samukha wrote:
 

 void main() {
     Tuple!(byte, int, short) t;
     writeln(t[0]);
 }


 test.d(57,23): Error: need `this` for `__value_field_2` of type `byte`




 It should work. This works:

 void main() {
     Tuple!(byte, int, short) t;

     t[0] = 0;
     t[1] = 2;
     t[2] = 3;

     auto a0 = t[0];
     auto a1 = t[1];
 }
 }


 
 I cannot reproduce the error. writeln(t[0]) works here: 
 https://run.dlang.io/is/kz6lFc
 


Apparently, it has been fixed in 2.092. Nice!
Jun 15 2020
parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On Monday, 15 June 2020 at 14:18:38 UTC, Timon Gehr wrote:

 Apparently, it has been fixed in 2.092. Nice!


Oh wow that's fantastic. Does anyone know which changeset / PR 
fixed it?
Jun 15 2020
parent reply Max Samukha <maxsamukha gmail.com> writes:
On Monday, 15 June 2020 at 14:55:37 UTC, Andrej Mitrovic wrote:

 On Monday, 15 June 2020 at 14:18:38 UTC, Timon Gehr wrote:

 Apparently, it has been fixed in 2.092. Nice!


 Oh wow that's fantastic. Does anyone know which changeset / PR 
 fixed it?


The person who fixed that must be commended.
Jun 15 2020
parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On Monday, 15 June 2020 at 15:00:12 UTC, Max Samukha wrote:

 On Monday, 15 June 2020 at 14:55:37 UTC, Andrej Mitrovic wrote:

 On Monday, 15 June 2020 at 14:18:38 UTC, Timon Gehr wrote:

 Apparently, it has been fixed in 2.092. Nice!


 Oh wow that's fantastic. Does anyone know which changeset / PR 
 fixed it?


 The person who fixed that must be commended.


I think it's this one? https://github.com/dlang/dmd/pull/10702
Jun 15 2020
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/14/20 2:25 PM, Paul Backus wrote:

 On Sunday, 14 June 2020 at 16:26:17 UTC, Avrina wrote:

 The situation also applies to the only tuple implementation in D. If 
 you are proposing a new type with emphasis on reducing the footprint 
 of the tuple then I don't see a problem with that. Changing the 
 existing tuple implementation would be problematic.


 
 Presumably any such change would be made backwards-compatible. So 
 Tuple.opIndex and Tuple.expand would still return elements in the order 
 specified by the user, even if that order is different from the internal 
 storage order.


Indeed.
Jun 14 2020
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/14/20 12:26 PM, Avrina wrote:

 On Sunday, 14 June 2020 at 03:57:40 UTC, Andrei Alexandrescu wrote:

 On 6/13/20 11:55 PM, Avrina wrote:

 On Sunday, 14 June 2020 at 03:08:48 UTC, Andrei Alexandrescu wrote:

 On 6/13/20 7:30 PM, Timon Gehr wrote:

 Another question is if automatic packing is worth making the layout 
 harder to predict.


 I think so. Size does matter.


 If you are talking about implementing a tuple type into the language,


 negative


 
 The situation also applies to the only tuple implementation in D. If you 
 are proposing a new type with emphasis on reducing the footprint of the 
 tuple then I don't see a problem with that. Changing the existing tuple 
 implementation would be problematic.


No. There's no guarantee made by std.tuple as to layout. We can't be 
overly conservative for the sake of supporting code that assumes too much.
Jun 14 2020
prev sibling parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On Saturday, 13 June 2020 at 19:11:33 UTC, Andrei Alexandrescu 
wrote:

 https://github.com/ZigaSajovic/optimizing-the-memory-layout-of-std-tuple

 Would be interesting to adapt it for std.tuple.


I can't see any way of making indexing work *except* by adding a 
Get template inside the tuple.

Currently Tuple supports indexing via `tuple[2]` => gets you the 
third value with its own type.

We cannot use opIndex for this because the tuple can consist of 
multiple types, and index is a runtime parameter when opIndex is 
called.

Now if we had something like `staticOpIndex` in the language 
maybe it could work. I could envision it being something like 
this:

```
struct Tuple (T...)
{
     T t;
     auto staticOpIndex (size_t index)()  // CT param
     {
         return t[index];  // or the rearranged index if fields 
are re-ordered
     }
}
```
Jun 14 2020
parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On Monday, 15 June 2020 at 06:06:40 UTC, Andrej Mitrovic wrote:

 Currently Tuple supports indexing via `tuple[2]` => gets you 
 the third value with its own type.


It does this via `alias fields this;` basically.
Jun 14 2020