Divide & Conquer divides, but doesn't conquer
FeepingCreature
feepingcreature at gmail.com
Mon May 25 05:59:41 UTC 2020
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.
More information about the Digitalmars-d
mailing list