Divide & Conquer divides, but doesn't conquer

[Timon Gehr]

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.