On Monday, 25 May 2020 at 16:46:16 UTC, Timon Gehr wrote:
> On 25.05.20 18:04, Andrei Alexandrescu wrote:
>> [...]
>
> QoI. The original `static foreach` implementation in my compiler frontend runs in linear time, even though it is implemented in a very similar way. Note that even `iota(n).array` has superlinear running time with DMD's CTFE.
>
> [...]

What do you do about the scopes?

On Monday, 25 May 2020 at 16:57:48 UTC, Stefan Koch wrote:
> On Monday, 25 May 2020 at 16:46:16 UTC, Timon Gehr wrote:
>> On 25.05.20 18:04, Andrei Alexandrescu wrote:
>>> [...]
>>
>> QoI. The original `static foreach` implementation in my compiler frontend runs in linear time, even though it is implemented in a very similar way. Note that even `iota(n).array` has superlinear running time with DMD's CTFE.
>>
>> [...]
>
> What do you do about the scopes?

Can't they be elided if the body contains no declarations?

On Monday, 25 May 2020 at 16:07:06 UTC, Andrei Alexandrescu wrote:

>
> So it seems a mixin-based version + Max's precalculated length = win!

Precalculated length is Adam's, and the link is to his blog. I should have stated that clearly in my post. Sorry.

On 25.05.20 18:57, Stefan Koch wrote:
> On Monday, 25 May 2020 at 16:46:16 UTC, Timon Gehr wrote:
>> On 25.05.20 18:04, Andrei Alexandrescu wrote:
>>> [...]
>>
>> QoI. The original `static foreach` implementation in my compiler frontend runs in linear time, even though it is implemented in a very similar way. Note that even `iota(n).array` has superlinear running time with DMD's CTFE.
>>
>> [...]
> 
> What do you do about the scopes?

Nothing special. Why would I have to?

On Monday, 25 May 2020 at 17:16:12 UTC, Timon Gehr wrote:
> On 25.05.20 18:57, Stefan Koch wrote:
>> On Monday, 25 May 2020 at 16:46:16 UTC, Timon Gehr wrote:
>>> On 25.05.20 18:04, Andrei Alexandrescu wrote:
>>>> [...]
>>>
>>> QoI. The original `static foreach` implementation in my compiler frontend runs in linear time, even though it is implemented in a very similar way. Note that even `iota(n).array` has superlinear running time with DMD's CTFE.
>>>
>>> [...]
>> 
>> What do you do about the scopes?
>
> Nothing special. Why would I have to?

You need a manifest constant for you IV (induction variable), no?
Which would clash with the one previously introduced.

On 25.05.20 19:21, Stefan Koch wrote:
> On Monday, 25 May 2020 at 17:16:12 UTC, Timon Gehr wrote:
>> On 25.05.20 18:57, Stefan Koch wrote:
>>> On Monday, 25 May 2020 at 16:46:16 UTC, Timon Gehr wrote:
>>>> On 25.05.20 18:04, Andrei Alexandrescu wrote:
>>>>> [...]
>>>>
>>>> QoI. The original `static foreach` implementation in my compiler frontend runs in linear time, even though it is implemented in a very similar way. Note that even `iota(n).array` has superlinear running time with DMD's CTFE.
>>>>
>>>> [...]
>>>
>>> What do you do about the scopes?
>>
>> Nothing special. Why would I have to?
> 
> You need a manifest constant for you IV (induction variable), no?
> Which would clash with the one previously introduced.
> 

Sure, so I create one forwarding scope per iteration. This is not particularly expensive, it's constant overhead per iteration.

On Monday, 25 May 2020 at 17:23:50 UTC, Timon Gehr wrote:
> On 25.05.20 19:21, Stefan Koch wrote:
>> On Monday, 25 May 2020 at 17:16:12 UTC, Timon Gehr wrote:
>>> On 25.05.20 18:57, Stefan Koch wrote:
>>>> On Monday, 25 May 2020 at 16:46:16 UTC, Timon Gehr wrote:
>>>>> [...]
>>>>
>>>> What do you do about the scopes?
>>>
>>> Nothing special. Why would I have to?
>> 
>> You need a manifest constant for you IV (induction variable), no?
>> Which would clash with the one previously introduced.
>> 
>
> Sure, so I create one forwarding scope per iteration. This is not particularly expensive, it's constant overhead per iteration.

Since Forwarding scopes where not in the language before you introduced static if.
Could you give a quick explanation how they work?

On 25.05.20 19:25, Stefan Koch wrote:
> On Monday, 25 May 2020 at 17:23:50 UTC, Timon Gehr wrote:
>> On 25.05.20 19:21, Stefan Koch wrote:
>>> On Monday, 25 May 2020 at 17:16:12 UTC, Timon Gehr wrote:
>>>> On 25.05.20 18:57, Stefan Koch wrote:
>>>>> On Monday, 25 May 2020 at 16:46:16 UTC, Timon Gehr wrote:
>>>>>> [...]
>>>>>
>>>>> What do you do about the scopes?
>>>>
>>>> Nothing special. Why would I have to?
>>>
>>> You need a manifest constant for you IV (induction variable), no?
>>> Which would clash with the one previously introduced.
>>>
>>
>> Sure, so I create one forwarding scope per iteration. This is not particularly expensive, it's constant overhead per iteration.
> 
> Since Forwarding scopes where not in the language before you introduced static if.
> Could you give a quick explanation how they work?
> 

It's a scope that forwards new symbols to its parent scope on insertion. This way, each iteration of the `static foreach` will have its own local scope with distinct loop variables, but any declarations that are generated in the `static foreach` body will skip this scope and instead populate the parent scope. (As an experiment, the original implementation also had `__local` declarations to insert symbols into the local scope without forwarding.)

On 5/25/20 12:07 PM, Stefan Koch wrote:
> On Monday, 25 May 2020 at 16:04:24 UTC, Andrei Alexandrescu wrote:
>> On 5/25/20 3:15 AM, Max Samukha wrote:
>>> On Monday, 25 May 2020 at 06:18:13 UTC, FeepingCreature wrote:
>>>
>>>> static foreach and stringof were used so I didn't have to pull in `format` or `to!string`, which had issues in std.meta.
>>>>
>>>> I'm seeing some improvement over 2.086 at least; it should be about equivalent to the hand-unrolled version in master.
>>>
>>> How could you miss the state-of-the-art?) Preallocate the result string and use the string counter hack!
>>> http://dpldocs.info/this-week-in-d/Blog.Posted_2020_05_11.html#dmd-and-static-foreach 
>>>
>>
>> static foreach is quadratic? Is this a matter of principle, or QoI?
> 
> Yes it is.
> I did present this fact at the pre-event to Dconf 2018.
> 
> As for your other question it's both. The QoI is not stellar.
> But it is fundamentally limited by having to create independent scopes.

How do you mean that? static foreach does not create a scope.

On 5/25/20 12:46 PM, Timon Gehr wrote:
> On 25.05.20 18:04, Andrei Alexandrescu wrote:
>> On 5/25/20 3:15 AM, Max Samukha wrote:
>>> On Monday, 25 May 2020 at 06:18:13 UTC, FeepingCreature wrote:
>>>
>>>> static foreach and stringof were used so I didn't have to pull in `format` or `to!string`, which had issues in std.meta.
>>>>
>>>> I'm seeing some improvement over 2.086 at least; it should be about equivalent to the hand-unrolled version in master.
>>>
>>> How could you miss the state-of-the-art?) Preallocate the result string and use the string counter hack!
>>> http://dpldocs.info/this-week-in-d/Blog.Posted_2020_05_11.html#dmd-and-static-foreach 
>>
>>
>>
>> static foreach is quadratic? Is this a matter of principle, or QoI?
>>
> 
> QoI. The original `static foreach` implementation in my compiler frontend runs in linear time, even though it is implemented in a very similar way. Note that even `iota(n).array` has superlinear running time with DMD's CTFE.
> 
> The implementation of `static foreach` in DMD is based on lowering, and the existing "tuple" foreach implementation. I suspect the culprit for bad performance for very large `static foreach` is a slow expression "tuple" implementation, but I am not sure.
> Therefore, maybe performance could be improved by modifying the foreach expansion code such that it can accept a CTFE array instead of an expression tuple. One could also add a special-case implementation for range `static foreach` to work around inefficient CTFE.

Thank you! It would be great if you could contribute or shepherd a contribution to dmd. Anything quadratic fails at scale.