Divide & Conquer divides, but doesn't conquer

[Steven Schveighoffer]

On 5/24/20 9:48 PM, Andrei Alexandrescu wrote:
> Another one:
> 
> template Filter(alias pred, TList...)
> {
>      static if (TList.length == 0)
>      {
>          alias Filter = AliasSeq!();
>      }
>      else static if (TList.length == 1)
>      {
>          static if (pred!(TList[0]))
>              alias Filter = AliasSeq!(TList[0]);
>          else
>              alias Filter = AliasSeq!();
>      }
>      else
>      {
>          alias Filter =
>              AliasSeq!(
>                  Filter!(pred, TList[ 0  .. $/2]),
>                  Filter!(pred, TList[$/2 ..  $ ]));
>      }
> }
> 
> Why cut the problem size in half if it doesn't improve complexity?

Because it doesn't work for large sets unless you do this.

If you do a "linear" recursive template, it fails after about 1000 
levels. A divide-and-conquer will not get that deep.

So in essence, it's a solution for a compiler restriction, not for 
performance.

-Steve