Node-TimSort Performance with Node.js v4

Node-TimSort is a Javascript implementation of the TimSort algorithm developed by Tim Peters, that showed to be incredibly fast on top of Node.js v0.12.7 (article here). Node-TimSort is avalaible on Github, npm and bower.

Given the (not so) recent update of Node.js to version 4 I decided to benchmark the module against Node’s latest release (v4.1.1). Results follow in table:

Execution Time (ns) Speedup
Array Type Length TimSort.sort array.sort
Array Length TimSort array.sort Speedup
Random 10152948043.14
10016091568753.53
10001999857042143.52
10000252806091256513.61
Descending 10109236803.37
10025033179912.70
10001182154391246.01
1000098039776884779.24
Ascending 10103020622.00
10021953063513.95
1000871550212657.61
10000726857581941104.31
Ascending + 3 Rand Exc 10148925031.68
1004064312307.68
10001364751535837.76
10000106676754956670.77
Ascending + 10 Rand End 10154331622.05
1006596346575.25
10002212150159522.67
10000127955724045956.59
Equal Elements 10106421722.04
100208966453.18
10007640424215.55
10000597373925806.57
Many Repetitions 10150131832.12
10018723371641.98
10002520435598942.22
10000322443076724012.38
Some Repetitions 10157832602.07
10018486367321.99
10002485995440632.19
10000327207475903672.32

Even with version 4.1.1 TimSort.sort is faster than array.sort on any of the tested array types. In general, the more ordered the array is the better TimSort.sort performs with respect to array.sort (up to 100 times faster on already sorted arrays).

Once again, the data also depend on the machine on which the benchmark is run. I strongly encourage you to clone the repository and run the benchmark on your own setup with:

npm run benchmark
comments powered by Disqus