www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Dude about ~ array concatenation performance

reply ddcovery <antoniocabreraperez gmail.com> writes:
Yesterday I really shocked when, comparing one algorithm written 
in javascript and the equivalent in D, javascript performed 
better!!!

The idea is to translate the "3 lines sort" in haskell to 
Javascript and D (with the limitations of each language).  This 
is not a quick sort test, but a "expressiveness" example of 
functional orientation:  you "declare" that the sorted version of 
an array is, given one of it's elements, the sorted version of 
the smaller ones, plus the item, plus the sorted version of the 
greater ones.

In javascript

const sorted = ([pivot, ...others]) => pivot === void 0 ? [] : [
   ...sorted(others.filter(v => v < pivot)),
   pivot,
   ...sorted(others.filter(v => v >= pivot))
];

In D

T[] sorted(T)(T[] values)
{
   return values.length == 0 ? [] :
     sorted(values[1 .. $].filter!(v => v < values[0]).array()) ~
     items[0 .. 1] ~
     sorted(values[1 .. $].filter!(v => v >= values[0]).array());
}

With 1 million Double numbers (generated randomly):
   Javascript (node 12): 1507 ms
   DMD: 2166 ms

With 6 million Double numbers
   Javascript (node 12): 10776 ms
   DMD: 15243 ms

You can find more detains in 
https://github.com/ddcovery/expressive_sort

I will really appreciate some improvements... the only "rule" is 
that "sorted" must be written, preferably,  as a single 
expression ("declarative" way, avoiding imperative instructions) 
and, of course, you can't use the native library "sort" methods 
:-) ).
Dec 01 2020
next sibling parent ddcovery <antoniocabreraperez gmail.com> writes:
On Tuesday, 1 December 2020 at 22:49:55 UTC, ddcovery wrote:

 Yesterday I really shocked when, comparing one algorithm 
 written in javascript and the equivalent in D, javascript 
 performed better!!!

 [...]


Sorry about title  (may be "doubt" :-/ )
Dec 01 2020
prev sibling next sibling parent reply Max Haughton <maxhaton gmail.com> writes:
On Tuesday, 1 December 2020 at 22:49:55 UTC, ddcovery wrote:

 Yesterday I really shocked when, comparing one algorithm 
 written in javascript and the equivalent in D, javascript 
 performed better!!!

 [...]


Use ldc, rdmd can invoke it for you. DMD's optimizer is not even 
close to as advanced as a modern JavaScript engine's - that's why 
we use it for fast build times instead of performance.
Dec 01 2020
parent reply ddcovery <antoniocabreraperez gmail.com> writes:
On Tuesday, 1 December 2020 at 23:43:31 UTC, Max Haughton wrote:

 On Tuesday, 1 December 2020 at 22:49:55 UTC, ddcovery wrote:

 Yesterday I really shocked when, comparing one algorithm 
 written in javascript and the equivalent in D, javascript 
 performed better!!!

 [...]


 Use ldc, rdmd can invoke it for you. DMD's optimizer is not 
 even close to as advanced as a modern JavaScript engine's - 
 that's why we use it for fast build times instead of 
 performance.


Impressive performance increase:

$ ldc2 -O -release  --run sorted.d

1.0M: 810 ms
1.5M: 1324 ms
3.0M: 2783 ms
6.0M: 5727 ms

Thanks Max
Dec 01 2020
parent Max Haughton <maxhaton gmail.com> writes:
On Wednesday, 2 December 2020 at 00:08:55 UTC, ddcovery wrote:

 On Tuesday, 1 December 2020 at 23:43:31 UTC, Max Haughton wrote:

 On Tuesday, 1 December 2020 at 22:49:55 UTC, ddcovery wrote:

 Yesterday I really shocked when, comparing one algorithm 
 written in javascript and the equivalent in D, javascript 
 performed better!!!

 [...]


 Use ldc, rdmd can invoke it for you. DMD's optimizer is not 
 even close to as advanced as a modern JavaScript engine's - 
 that's why we use it for fast build times instead of 
 performance.


 Impressive performance increase:

 $ ldc2 -O -release  --run sorted.d

 1.0M: 810 ms
 1.5M: 1324 ms
 3.0M: 2783 ms
 6.0M: 5727 ms

 Thanks Max


I've written a github issue on your repository with flags to get 
the most out of LLVM.
Dec 01 2020
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Dec 01, 2020 at 10:49:55PM +0000, ddcovery via Digitalmars-d-learn
wrote:

 Yesterday I really shocked when, comparing one algorithm written in
 javascript and the equivalent in D, javascript performed better!!!


[...]

 With 1 million Double numbers (generated randomly):
   Javascript (node 12): 1507 ms
   DMD: 2166 ms
 
 With 6 million Double numbers
   Javascript (node 12): 10776 ms
   DMD: 15243 ms


Yeah, when it comes to performance-related things, don't bother with
DMD.  Its optimizer is known to have limitations, and IME consistently
produces code that underperforms LDC-generated code by about 20-30%,
sometimes even as high as 40%.

For performance comparisons, always use GDC/LDC.


T

-- 
If you're not part of the solution, you're part of the precipitate.
Dec 01 2020
parent ddcovery <antoniocabreraperez gmail.com> writes:
On Wednesday, 2 December 2020 at 06:31:49 UTC, H. S. Teoh wrote:

 On Tue, Dec 01, 2020 at 10:49:55PM +0000, ddcovery via 
 Digitalmars-d-learn wrote:

 Yesterday I really shocked when, comparing one algorithm 
 written in javascript and the equivalent in D, javascript 
 performed better!!!


 [...]

 With 1 million Double numbers (generated randomly):
   Javascript (node 12): 1507 ms
   DMD: 2166 ms
 
 With 6 million Double numbers
   Javascript (node 12): 10776 ms
   DMD: 15243 ms


 Yeah, when it comes to performance-related things, don't bother 
 with DMD.  Its optimizer is known to have limitations, and IME 
 consistently produces code that underperforms LDC-generated 
 code by about 20-30%, sometimes even as high as 40%.

 For performance comparisons, always use GDC/LDC.


 T


After applying adecuate parametrization (thanks to Max Haughton 
for the tips), LDC generated code is running almost 3 times 
faster than DMD one!!!
Dec 02 2020