Divide & Conquer divides, but doesn't conquer

[Andrei Alexandrescu]

On 5/24/20 10:32 PM, Steven Schveighoffer wrote:
> 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

I see, thanks.