Divide & Conquer divides, but doesn't conquer

[Andrei Alexandrescu]

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.