Divide & Conquer divides, but doesn't conquer

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Mon May 25 15:59:57 UTC 2020


On 5/25/20 1:59 AM, FeepingCreature wrote:
> On Sunday, 24 May 2020 at 23:40:48 UTC, Andrei Alexandrescu wrote:
>> Consider staticMap's current version (there are a few upcoming changes 
>> that don't change the point):
>>
>> ...
>>
>> 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:
>> ...
>> 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.
> 
> To add to the good previous points: the divide-and-conquer strategy can 
> take advantage of caching for the leaf instantiations with one 
> parameter. That is, 8 template instantiations can trivially be reused, 
> and the others can sometimes be reused if they hit a common subtree. The 
> linear instantiation can only be reused once or twice at the very end.

Not sure I understand. A,...,H are assumed to be distinct. The number of 
templates generated is the same regardless of memoization.


More information about the Digitalmars-d mailing list