Divide & Conquer divides, but doesn't conquer

[Andrei Alexandrescu]

On 5/24/20 8:44 PM, Timon Gehr wrote:
> On 25.05.20 01:40, Andrei Alexandrescu wrote:
>> ...
>>
>> So it seems divide et impera doesn't quite help with certain recursive 
>> templates.
> 
> Assuming the cost of a template instantiation is linear in the number of 
> template arguments, the first version has running time Θ(n log n) while 
> the second version has running time Θ(n²).

Of course. However, I'm assuming most of a template instantiation's cost 
is fixed.

There are other algorithms looking at in std.meta. Consider Reverse:

template Reverse(TList...)
{
     static if (TList.length <= 1)
     {
         alias Reverse = TList;
     }
     else
     {
         alias Reverse =
             AliasSeq!(
                 Reverse!(TList[$/2 ..  $ ]),
                 Reverse!(TList[ 0  .. $/2]));
     }
}

The recurrence formula for complexity is:

T(0) = k;
T(1) = k;
T(n) = 2 * T(n/2) + k

Again, I assume instantiating AliasSeq with two lists of any lengths has 
the same cost k. That makes complexity linear. So is the complexity of 
the simpler implementation:

template Reverse(TList...)
{
     static if (TList.length <= 1)
     {
         alias Reverse = TList;
     }
     else
     {
         alias Reverse =
             AliasSeq!(Reverse!(TList[1  .. $]), TList[0]);
     }
}

But this insantiates half the templates, so it goes easier on resources. 
This makes the use of the halving strategy not only an unnecessary 
distraction, but a less efficient choice.

There are other unnecessary (and/or unnecessarily baroque) artifacts in 
std.meta, such as EraseAllN. Far as I can tell it's unnecessary because 
NoDuplicates can be implemented without it (and if I'm not wrong, at the 
same complexity).

std.meta is due for a serious review.