Repository files navigation

In this quoraanswere I wrote about javascript/python expressiveness vs Go/Rust/D/... performance.

As an example, I mentioned the "3 lines" haskell quick sort and wrote this javascript version

constsorted=([pivot, ...others])=>pivot===void0 ?[] :[    ...sorted(others.filter(n=>n<pivot)),pivot,    ...sorted(others.filter(n=>n>=pivot))];

This, of course, is not a "quick sort" because the original one is an "in place" algorithm that doesn't require additional memory space allocation. This is a functional oriented expression that exemplarizes how expressive a "functional" orientation can be (You "express" 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 bigger ones).

As an enthusiastic newbie to the "D" programming language, I thought that D could affort this expressiveness too...

D has no support for destructuring as javascript has (remember desorted([pivot, ...others])), but it haslambdas,map/filter/reduce support,array slices andarray concatenation that allows you to write easily a similar expression:

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

note: D notation allows to writefoo(a) asa.foo() ora.foo, this is the reason we can writesorted( array( something ) ) assomething.array.sorted

note:sorted is atemplated method (T is the type of the elements of the array): "under the scenes", D compiler detects if the final used type is comparable (i.e.: it is a class with aopCmp method, or it is a numerical type, or ...): yo don't need to tell that T extends something like"IComparable" because D libraries are not "interface" based: D prefers to use "conventions" and check them using instrospection at compile time (D developers write compile-time code and run-time code at the same time: D allows you to mix them naturally).

Seeing the similarities, I assume (I really don't know) that javascript and D versions are doing the same "under the scenes":

• The[...array1, ...array2, ...array3] javascript is equivalent to thearray1 ~ array2 ~ array3 D code. That is, a new array is being generated as a result of copying the elements of the original 3.
• The.filter!(...).array D code is using a "Range" to filter the elements and the ".array()" method to materialize the selected elements as an array. Internally, it is similar to the javascript code where.filter(...) iterates and selects the resulting elements and finally materializes the array

First surprise was Javascript (nodejs) version performs better than D (about20% faster for 1_000_000 random Float64 numbers).

• Javascript (node):1610 ms
• D (DMD compiler):2017 ms

Fortunately, D has 3 compilers: DMD (official reference compiler), GDC (GCC based compiler) and LDC (LLVM based compiler).

• D (LDC compiler):693 ms !!!

That's speed :-)

After some tests, I realized javascript destructuring [pivot,...others] caused a performance penalty and I rewrote to a more efficient version (very similar to D syntax)

constsorted=(xs)=>xs.length===0 ?[] :[].concat(sorted(xs.slice(1).filter(x=>x<xs[0])),xs[0],sorted(xs.slice(1).filter(x=>x>=xs[0])));

And the execution on 1 million floats reduced to921 ms!!! That's impressive :-O

I decided to write similar code in other languajes to compare.

In Python:

defsorted(xs):return []iflen(xs)==0else \sorted([xforxinxs[1:]ifx<xs[0]])+ \xs[0:1]+ \sorted([xforxinxs[1:]ifx>=xs[0]])

In Crystal:

defsorted(xs :Array(Float64)) :Array(Float64)returnxs.size ==0 ?[]ofFloat64  :sorted(x[1..].select{ |x|x <xs[0]}) +[xs[0]] +sorted(xs[1..].select{ |x|x >=xs[0]})end

In Julia (thanks toCamilo Chacón Sartori)

functionsorted(xs::Array{Float64, 1})::Array{Float64, 1}returnlength(xs)==0?Array{Float64, 1}():vcat(sorted([xfor xin xs[2:end]if x< xs[1]]),    xs[1],sorted([xfor xin xs[2:end]if x>= xs[1]])  )end

In Scala

defsorted( xs:List[Double] ):List[Double]=  xsmatch {caseNil=>List()case pivot:: rest=>      sorted( rest.filter( _< pivot ) )++List(pivot)++      sorted( rest.filter( _>= pivot ) )  }

In Nim

funcsorted[T](xs:seq[T]):seq[T]=if xs.len==0:@[]else:concat(    xs[1..^1].filter(x=>x<xs[0]).sorted,@[xs[0]],    xs[1..^1].filter(x=>x>=xs[0]).sorted  )

For better measurement:

• each test is internally ran 5 times, each time with a newly generated set of numbers (to avoid run-to-run optimization effects).
• Between compilers (or interpreters) tests, there is a pause of 30s to normalize system (Mainly CPU temperature)

The results, as CSV, are

compiler,lang,size,ms"ldc2","D",1000000,645"ldc2","D",1500000,978"ldc2","D",3000000,2013"ldc2","D",6000000,4165"crystal","Crystal",1000000,713"crystal","Crystal",1500000,1102"crystal","Crystal",3000000,2277"crystal","Crystal",6000000,4750"node","Javascript",1000000,904"node","Javascript",1500000,1384"node","Javascript",3000000,2977"node","Javascript",6000000,6117"nim","Nim",1000000,1038"nim","Nim",1500000,1564"nim","Nim",3000000,3352"nim","Nim",6000000,6951"scala","Scala",1000000,1524"scala","Scala",1500000,2537"scala","Scala",3000000,5741"scala","Scala",6000000,19819"dmd","D",1000000,1818"dmd","D",1500000,2773"dmd","D",3000000,5822"dmd","D",6000000,12123"julia","julia",1000000,3224"julia","julia",1500000,4648"julia","julia",3000000,9429"julia","julia",6000000,20264"python3","Python",1000000,4512"python3","Python",1500000,7339"python3","Python",3000000,17428"python3","Python",6000000,38981

Execution time histogram by array size:

Changing to logarithmic scale

I include the code to the 7 tests. Please, tell me if you see something we can improve:

• Avoid imperative instructions: "sorted" must be an unique expression or, at least, an unique "return ..." statement funcion.
• Of course, you can't use built-in library sort methods :-)
• Remember that this is not a quick-sort performance test (that, obviously, can be implemented in a more efficient way)

All tests have been executed on a Ubuntu 20.04 linux.

Tests requireNodejs,Python3,Julia,DMD/LDC for D,scala,Nim andCrystal compilers

• Nodejs: I use node 12.20 (seeNodeSource distributions for more information)
• Python3: Ubuntu comes withpython 3 preinstalled.
• Julia: It is available in apt and snap repositories. The apt version is newest (but not latest). Seedownload page for newest versions

$ sudo apt install julia

• DMD andLDC: They are available inapt andsnap repositories (seeguide ) . Becauseldc version is newest in snap, I use snap repos:

$ snap install dmd --classic$ snap install ldc2 --classic

• scala 2.11.12: It is availabe inapt repository

$ sudo apt install scala

• Crystal: It is availabe inapt andsnap repositories (seeguide for more information )

You can run all tests usingtest.sh

$ ./test.sh

If no want to generate aresult.csv file

$ ./test.sh| tee result.csv

If you prefer to run tests individually:

• D (LDC)

$ ldc2 -O5 -release -enable-cross-module-inlining --run sorted.d

• D (DMD)

$ dmd -O -release -run sorted.d

• Javascript

$ node sorted.js

• Crystal

$ crystal run sorted.cr --release

• Python

$ python3 -OO sorted.py

• Julia

julia -O3 --inline=yes --check-bounds=no sorted.jl

• Camilo Chacón Sartori For the Julia code
• Max Haughton For the proper DMD/LDC optimisation settings