On Saturday, 25 April 2020 at 09:33:19 UTC, Walter Bright wrote:
> On 4/24/2020 1:55 PM, Walter Bright wrote:
>> Another approach to resolving the original problem (template instantiation bloat) is for the compiler to recognize templates like AliasSeq as "special" and implement them directly.
>> 
>> For example, AliasSeq is defined as:
>> 
>>    template AliasSeq(TList...) { alias AliasSeq = TList; }
>> 
>> This pattern is so simple it can be recognized by the compiler. (Having std.meta.AliasSeq being a special name known to the compiler is not necessary.)
>
> Giving this a try:
>
> https://github.com/dlang/dmd/pull/11057

Nice to see the idea applied. Can you give numbers, i.e from benchmarks ?

On Saturday, 25 April 2020 at 09:33:19 UTC, Walter Bright wrote:
> On 4/24/2020 1:55 PM, Walter Bright wrote:
>> Another approach to resolving the original problem (template instantiation bloat) is for the compiler to recognize templates like AliasSeq as "special" and implement them directly.
>> 
>> For example, AliasSeq is defined as:
>> 
>>    template AliasSeq(TList...) { alias AliasSeq = TList; }
>> 
>> This pattern is so simple it can be recognized by the compiler. (Having std.meta.AliasSeq being a special name known to the compiler is not necessary.)
>
> Giving this a try:
>
> https://github.com/dlang/dmd/pull/11057

This is supposed to make using staticMap cheap?

On Saturday, 25 April 2020 at 09:35:45 UTC, user1234 wrote:
> On Saturday, 25 April 2020 at 09:33:19 UTC, Walter Bright wrote:
>> On 4/24/2020 1:55 PM, Walter Bright wrote:
>>> Another approach to resolving the original problem (template instantiation bloat) is for the compiler to recognize templates like AliasSeq as "special" and implement them directly.
>>> 
>>> For example, AliasSeq is defined as:
>>> 
>>>    template AliasSeq(TList...) { alias AliasSeq = TList; }
>>> 
>>> This pattern is so simple it can be recognized by the compiler. (Having std.meta.AliasSeq being a special name known to the compiler is not necessary.)
>>
>> Giving this a try:
>>
>> https://github.com/dlang/dmd/pull/11057
>
> Nice to see the idea applied. Can you give numbers, i.e from benchmarks ?

this is for the following code:

---
template Add3(alias y)
{
    enum Add3 = y + 3;
}

enum x = staticMap!(Add3,
AliasSeq!(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, /*goes towards 4096*/); // this line was abbreviated.
);
pragma(msg, x.length + x[$-1]);

dmd fresh from walters branch release build with ldmd(ldc) 1.20
time:
0m0.230s
time for a fresh dmd build under the same condtions with that patch reverted:
0m0.265s
time for doing it with our "..." patch:
0.030s

these numbers are just a best out of 3 messurement so please only see them as a rough guide.

On Friday, 24 April 2020 at 22:21:31 UTC, Walter Bright wrote:
> On 4/24/2020 1:55 PM, Walter Bright wrote:
>> How are things like this expressed in mathematics?
>
> I did a little research:
>
>     ∀xP(x)
>
> means:
>
>     for all x in P(x)
>
> or in ... notation:
>
>     P(x...)

This notation describes a proposition as in propositional calculus. It is not something one would you to describe a „static map“ of tuples.

In order to use the typical mathematical notation, we first need to understand what a tuple is in mathematics. Typically this terminology is used for an element of a product of specific objects. For example, let’s consider \R^2 (2 dimensional vector space with real-valued entries), which is the product of \R and \R. The elements of \R^2 can be called 2-tuples. You can write it as (x_1, x_2) \in \R^2. Now the number of factors can be something different than 2 of course. In fact it doesn't need to be finite, but as D only supports finite tuples (as of now), let's only consider a finite number of factors for now. Also the factors do not need to be the same. So let n \in \N (i.e. n is a Natural number), then consider the finite set M:= /{1, ..., n/}. For each m \in M, let A_m some object (for understanding, you can consider it to be a set, or a vector space, but it can be a lot of different things). Then the product of those A_m is written as \prod_{m \in M} A_m. An element of this product can be called an n-tuple (there are n entries) and is written as (a_m)_{m \in M}. Now suppose that we have a map f, that can be applied to each of the factors of the product and we want to create a new tuple by applying f to each of its entries. We would write the new tuple as (f(a_m))_{m \in M}. As you can see, there is no „expansion“ or anything, it is just a declarative description of how the tuple looks after „mapping“.

If you want a similar notation that’s „common“ in programming languages, (list) comprehensions is what is closest. E.g. in python, you can do the following:

my_tuple = (1, 2, 3, 4)
my_mapped_tuple = (f(i) for i in my_tuple)

On Saturday, 25 April 2020 at 09:35:45 UTC, user1234 wrote:
> On Saturday, 25 April 2020 at 09:33:19 UTC, Walter Bright wrote:
>> On 4/24/2020 1:55 PM, Walter Bright wrote:
>>> Another approach to resolving the original problem (template instantiation bloat) is for the compiler to recognize templates like AliasSeq as "special" and implement them directly.
>>> 
>>> For example, AliasSeq is defined as:
>>> 
>>>    template AliasSeq(TList...) { alias AliasSeq = TList; }
>>> 
>>> This pattern is so simple it can be recognized by the compiler. (Having std.meta.AliasSeq being a special name known to the compiler is not necessary.)
>>
>> Giving this a try:
>>
>> https://github.com/dlang/dmd/pull/11057
>
> Nice to see the idea applied. Can you give numbers, i.e from benchmarks ?

this is for the following code:

---
import std.meta;
alias big_seq = AliasSeq!(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, /*goes towards 4096*/); // this line was abbreviated.
version(dotdotdot)
{
    enum x = (big_seq + 3)...;
}
else
{
    template Add3(alias y)
    {
        enum Add3 = y + 3;
    }

    enum x = staticMap!(Add3, big_seq);
}

pragma(msg, x.length + x[$-1]);

dmd fresh from walters branch release build with ldmd(ldc) 1.20
time:
0m0.230s
time for a fresh dmd build under the same conditions with that patch reverted:
0m0.270s
time for doing it with our "..." patch:
0m0.030s

these numbers are just a best out of 3 measurement so please only see them as a rough guide.

On 4/25/2020 3:06 AM, Stefan Koch wrote:
> template Add3(alias y)
> {
>      enum Add3 = y + 3;
> }
> 
> enum x = staticMap!(Add3,
> AliasSeq!(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, /*goes towards 4096*/); // this line was abbreviated.
> );
> pragma(msg, x.length + x[$-1]);
> 
> dmd fresh from walters branch release build with ldmd(ldc) 1.20
> time:
> 0m0.230s
> time for a fresh dmd build under the same condtions with that patch reverted:
> 0m0.265s
> time for doing it with our "..." patch:
> 0.030s
> 
> these numbers are just a best out of 3 messurement so please only see them as a rough guide.

Thank you. Though I don't see how the ... thing would speed up AliasSeq, it would speed up the staticMap.

On 4/25/2020 2:49 AM, Stefan Koch wrote:
> This is supposed to make using staticMap cheap?

No. It's to make AliasSeq cheap, to remove motivation for making a special syntactic construct for creating a tuple.

Your benchmark shows indeed it has that effect, though you didn't test a version that had both your ... and my AliasSeq folded in. That result would be interesting.

There may be some other common template patterns amenable to compiler shortcuts.

On Saturday, 25 April 2020 at 10:11:08 UTC, Stefan Koch wrote:
> On Saturday, 25 April 2020 at 09:35:45 UTC, user1234 wrote:
>> On Saturday, 25 April 2020 at 09:33:19 UTC, Walter Bright wrote:
>>> On 4/24/2020 1:55 PM, Walter Bright wrote:
>>>> Another approach to resolving the original problem (template instantiation bloat) is for the compiler to recognize templates like AliasSeq as "special" and implement them directly.
>>>> 
>>>> For example, AliasSeq is defined as:
>>>> 
>>>>    template AliasSeq(TList...) { alias AliasSeq = TList; }
>>>> 
>>>> This pattern is so simple it can be recognized by the compiler. (Having std.meta.AliasSeq being a special name known to the compiler is not necessary.)
>>>
>>> Giving this a try:
>>>
>>> https://github.com/dlang/dmd/pull/11057
>>
>> Nice to see the idea applied. Can you give numbers, i.e from benchmarks ?
>
> this is for the following code:
>
> ---
> import std.meta;
> alias big_seq = AliasSeq!(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, /*goes towards 4096*/); // this line was abbreviated.
> version(dotdotdot)
> {
>     enum x = (big_seq + 3)...;
> }
> else
> {
>     template Add3(alias y)
>     {
>         enum Add3 = y + 3;
>     }
>
>     enum x = staticMap!(Add3, big_seq);
> }
>
> pragma(msg, x.length + x[$-1]);
>
> dmd fresh from walters branch release build with ldmd(ldc) 1.20
> time:
> 0m0.230s
> time for a fresh dmd build under the same conditions with that patch reverted:
> 0m0.270s
> time for doing it with our "..." patch:
> 0m0.030s
>
> these numbers are just a best out of 3 measurement so please only see them as a rough guide.

I misspoke.
I had the tests in two different files at first and they were doing diffrent things.
When ... has to actually create the tuple our time is 0m0.210s

Let me post a version which is slightly more careful.

import std.meta;

import big_alias_seq;

// it's an aliasSeq containing the integers from 0 to 4095 inclusive)

version(dotdotdot)
{
    mixin("enum x = (big_seq + 3)....length;");
}
else
{
     template Add3(alias y)
     {
        enum Add3 = y + 3;
     }

     enum x = staticMap!(Add3, big_seq).length;
}

pragma(msg, x);

Walters patch: 0m0.169s
Without Walters Patch: 0m0.177s
DotDotDot version: 0m0.024s

output for all 3 versions is:
4096LU

On Saturday, 25 April 2020 at 10:11:08 UTC, Stefan Koch wrote:
> On Saturday, 25 April 2020 at 09:35:45 UTC, user1234 wrote:
>> [...]
>
> this is for the following code:
>
> ---
> import std.meta;
> alias big_seq = AliasSeq!(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, /*goes towards 4096*/); // this line was abbreviated.
> version(dotdotdot)
> {
>     enum x = (big_seq + 3)...;
> }
> else
> {
>     template Add3(alias y)
>     {
>         enum Add3 = y + 3;
>     }
>
>     enum x = staticMap!(Add3, big_seq);
> }
>
> pragma(msg, x.length + x[$-1]);
>
> dmd fresh from walters branch release build with ldmd(ldc) 1.20
> time:
> 0m0.230s
> time for a fresh dmd build under the same conditions with that patch reverted:
> 0m0.270s
> time for doing it with our "..." patch:
> 0m0.030s
>
> these numbers are just a best out of 3 measurement so please only see them as a rough guide.

ok, thanks.

But i'd like to say that Walter's PR doesnt interfere with the project presented in this topic. Maybe we can get Walter improvment quickly merged and then later yours as well, as it is more complex.

On Saturday, 25 April 2020 at 10:27:19 UTC, Walter Bright wrote:
> On 4/25/2020 2:49 AM, Stefan Koch wrote:
>> This is supposed to make using staticMap cheap?
>
> No. It's to make AliasSeq cheap, to remove motivation for making a special syntactic construct for creating a tuple.
>
> Your benchmark shows indeed it has that effect, though you didn't test a version that had both your ... and my AliasSeq folded in. That result would be interesting.
>
> There may be some other common template patterns amenable to compiler shortcuts.

As I've said before: AliasSeq is not the slow part.
As long as we don't create many templates they can be as expensive as they want to be.
Of course a speedup is always appreciated and I so no reason not to merge your PR.