How to best translate this C++ algorithm into D?

[logicchains via Digitalmars-d]

On Sunday, 8 June 2014 at 15:03:32 UTC, Joseph Rushton Wakeling 
via Digitalmars-d wrote:
> What compiler are you using?
>
> DMD will in general produce slower executables than LDC or GDC 
> -- about half as fast sounds quite plausible.  If your C++ code 
> is compiled with gcc or clang, you're not doing a fair 
> comparison.
>
> If you haven't already, try compiling with LDC or GDC, with 
> full-on -O -release -inline -noboundscheck options, and see how 
> that compares with the C++ code.

I was using ldc2, with -O5 -release -disable-boundscheck. I wrote 
a C translation of the C++ implementation that differs only in 
that it uses quicksort instead of whatever std::stable_sort uses, 
and it runs in around the same time as the D implementation for 
input 100 100 100 (around 90ms, compared to 65ms for C++), so I 
suspect the C++ sorting algorithm is just slightly faster for 
this use case.

Interestingly, when I increase the input to 400 or 500, while the 
C version retains the same speed ratio to the C++ one, the D 
version becomes around 3-4 times slower. I suspect this might be 
due to garbage collection, as putting everything into a hashmap 
then removing it again as a method to find the unique values 
probably generates a lot of garbage. Although I'd have assumed it 
was only O(N), compared to O(NlogN) for the sort+uniq method that 
the C and C++ versions use, so in that sense I'm surprised that 
the D version doesn't become comparatively faster as input 
increases.