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