Divide & Conquer divides, but doesn't conquer

[Walter Bright]

On 5/25/2020 9:46 AM, Timon Gehr 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.
> 
> 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.

This is worth looking in to. I've had customers tell me they don't use static 
foreach due to performance problems.