Code runtime

Andrei Alexandrescu via Digitalmars-d digitalmars-d at puremagic.com
Sun Jun 5 23:25:19 PDT 2016


On 6/6/16 1:12 AM, H. S. Teoh via Digitalmars-d wrote:
> On Sun, Jun 05, 2016 at 10:29:09PM +0000, extrawurst via Digitalmars-d wrote:
> [...]
>> I never used those methods neither in D nor in C++ but I have a gut
>> feeling it is the nextPermutation method in phobos, allocating
>> internally
>
> I wrote nextPermutation. It does not allocate.
>
> For performance, I recommend using gdc or ldc. It is not dmd's strength.

FWIW:

* gdc should be used when benchmarking to ensure comparable backends.

* Just looked at std.permutation 
(https://github.com/dlang/phobos/blob/cdc8218e9840353f6ed79f00a63280c3002b198f/std/algorithm/sorting.d#L2786), 
looks good but operates on complex compound ranges so it puts more 
pressure on the optimizer. Compare to C++'s std::next_permutation 
(http://stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation) 
which directly bumps iterators etc. We also have trouble because of 
ranges' much discussed difficulties with iterators pointing somewhere 
inside them (e.g. we need an extra counter n).

A specialization of nextPermutation for random-access ranges should pay 
off here.


Andrei



More information about the Digitalmars-d mailing list