Node-TimSort Performance with Node.js v4

27 Sep 2015

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	Speedup
Array	Length	TimSort	array.sort	Speedup
Random	10	1529	4804	3.14
	100	16091	56875	3.53
	1000	199985	704214	3.52
	10000	2528060	9125651	3.61
Descending	10	1092	3680	3.37
	100	2503	31799	12.70
	1000	11821	543912	46.01
	10000	98039	7768847	79.24
Ascending	10	1030	2062	2.00
	100	2195	30635	13.95
	1000	8715	502126	57.61
	10000	72685	7581941	104.31
Ascending + 3 Rand Exc	10	1489	2503	1.68
	100	4064	31230	7.68
	1000	13647	515358	37.76
	10000	106676	7549566	70.77
Ascending + 10 Rand End	10	1543	3162	2.05
	100	6596	34657	5.25
	1000	22121	501595	22.67
	10000	127955	7240459	56.59
Equal Elements	10	1064	2172	2.04
	100	2089	6645	3.18
	1000	7640	42421	5.55
	10000	59737	392580	6.57
Many Repetitions	10	1501	3183	2.12
	100	18723	37164	1.98
	1000	252043	559894	2.22
	10000	3224430	7672401	2.38
Some Repetitions	10	1578	3260	2.07
	100	18486	36732	1.99
	1000	248599	544063	2.19
	10000	3272074	7590367	2.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

Marco Ziccardi

Node-TimSort Performance with Node.js v4