Divide & Conquer divides, but doesn't conquer

[Andrei Alexandrescu]

Consider staticMap's current version (there are a few upcoming changes 
that don't change the point):

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

In the instantiation staticMap!(pred, A, B, C, D, E, F, G, H), recursion 
will instantiate:

staticMap!(pred, A, B, C, D)
staticMap!(pred, A, B)
staticMap!(pred, A)
staticMap!(pred, B)
staticMap!(pred, C, D)
staticMap!(pred, C)
staticMap!(pred, D)
staticMap!(pred, E. F, G, H)
staticMap!(pred, E, F)
staticMap!(pred, E)
staticMap!(pred, F)
staticMap!(pred, G, H)
staticMap!(pred, G)
staticMap!(pred, H)

Total: 15 instantiations including original. This is because a full tree 
with 8 leaves is being created. Generally, a tree with N leaves has 
about 2N - 1 nodes total (exactly so when N is a power of 2).

The more naive version would simply use linear decomposition:

template staticMap(alias F, T...)
{
     static if (T.length == 0)
     {
         alias staticMap = AliasSeq!();
     }
     else
     {
         alias staticMap =
             AliasSeq!(
                 F!(T[0]),
                 staticMap!(F, T[1 .. $]));
     }
}

There' no more need to handle the 1-element case, which is already a 
plus. But that's not the topic here. The instantiations created are:

staticMap!(pred, B, C, D, E, F, G, H)
staticMap!(pred, C, D, E, F, G, H)
staticMap!(pred, D, E, F, G, H)
staticMap!(pred, E, F, G, H)
staticMap!(pred, F, G, H)
staticMap!(pred, G, H)
staticMap!(pred, H)

Total: 8 instantiations including original. That's about half the 
current number of instantiations.

So it seems divide et impera doesn't quite help with certain recursive 
templates.