May 25, 2020 Re: Divide & Conquer divides, but doesn't conquer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On 5/24/2020 8:10 PM, Andrei Alexandrescu wrote: > I see, thanks. So we don't waste time on this point again: https://github.com/dlang/phobos/pull/7497 |
May 26, 2020 Re: Divide & Conquer divides, but doesn't conquer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Adam D. Ruppe | On Monday, 25 May 2020 at 20:50:19 UTC, Adam D. Ruppe wrote: > On Monday, 25 May 2020 at 17:08:32 UTC, Max Samukha wrote: >> Precalculated length is Adam's > > I stole it from Stefan too IIRC. Preallocating buffers for CTFE is not a new idea, but the string counter hack was new to me. > > The way I see it, it is all just D community knowledge. A lot of the things I know just come from helping other users through their problems too - they point out something that is cool or is broken and by working on it together we both learn. Agree. |
May 27, 2020 Re: Divide & Conquer divides, but doesn't conquer | ||||
---|---|---|---|---|
| ||||
Posted in reply to FeepingCreature | On Monday, 25 May 2020 at 05:59:41 UTC, 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.
Thank u so much for taking time to help.
|
May 27, 2020 Re: Divide & Conquer divides, but doesn't conquer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Stefan Koch | On Monday, 25 May 2020 at 21:29:00 UTC, Stefan Koch wrote:
> How much of a deal is 100% ? Enough to talk about including ... ?
How would a type function compare to S... ? Ideally we'd just use a type function.
|
May 27, 2020 Re: Divide & Conquer divides, but doesn't conquer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nick Treleaven | On Wednesday, 27 May 2020 at 19:05:51 UTC, Nick Treleaven wrote:
> On Monday, 25 May 2020 at 21:29:00 UTC, Stefan Koch wrote:
>> How much of a deal is 100% ? Enough to talk about including ... ?
>
> How would a type function compare to S... ? Ideally we'd just use a type function.
It's gonna be a while until they can be used.
For that usecase you couldn't use a typefunction at all.
type functions don't work on values.
|
May 27, 2020 Re: Divide & Conquer divides, but doesn't conquer | ||||
---|---|---|---|---|
| ||||
Posted in reply to Stefan Koch | On Wednesday, 27 May 2020 at 20:20:37 UTC, Stefan Koch wrote:
> On Wednesday, 27 May 2020 at 19:05:51 UTC, Nick Treleaven wrote:
>> On Monday, 25 May 2020 at 21:29:00 UTC, Stefan Koch wrote:
>>> How much of a deal is 100% ? Enough to talk about including ... ?
>>
>> How would a type function compare to S... ? Ideally we'd just use a type function.
>
> It's gonna be a while until they can be used.
> For that usecase you couldn't use a typefunction at all.
> type functions don't work on values.
Assuming you mean the benchmark I posted.
|
Copyright © 1999-2021 by the D Language Foundation