Re: D compile time algorithms implementation

[Timon Gehr]

On 04/20/2013 08:07 AM, khurshid wrote:
I just have read from github  std.variant, std.typetuple, etc. source
codes.
And I have a question.
Why more linear algorithms implemented with O(N^2) ?
example: staticMap,  it doesnot compiled  more 500 arguments.
although, following version compiled for more than 32768 arguments:
template staticMap2(alias F, T...)
{
         static if (T.length == 0)
         {
                 alias TypeTuple!() staticMap2;

         }
         else static if (T.length == 1)
         {
                 alias TypeTuple!(F!(T[0])) staticMap2;
         }
         else
         {
                 alias TypeTuple!( staticMap2!(F, T[0..$/2]),
staticMap2!(F,
T[$/2..$]))  staticMap2;
         }
}

FWIW I think the O(N^2) behaviour is a limitation of the compiler 
implementation (I think ropes might be a better data structure than 
arrays to back compiler tuples.)