Unstable sorting in JavaScript

When I see a post on a similar topic on any social network, there are almost always a lot of comments of this type under it:

  • Why do you need to know this if there are built-in sorting methods?

  • Why reinvent the wheel?

  • It is necessary to pass an interview, objectively there is no need to know it anymore

  • In “any javascript engine” they are not stupid, and have already done everything right

And I myself used to think the same way until I came to one of the Rostelecom IT teams as a frontend developer. Together we came across a very interesting case: it was necessary to create a widget that could be built into the information systems of all our macro-regional branches and simplify the work of operators in selecting the optimal tariff.

Straight to the point

What do you think will happen after this code is executed? In the meantime, there is no need to know about it. ”

It seems that nothing strange, but there are nuances.

Case number times

We made a problem, technical solution, code, unit tests. The business process is fine too. On surface testing, no problems were found. But when it came to auto tests, the oddities began. The configuration that Node.js 10 was calculating generally gave the correct output, but sometimes the configuration was different. That complicated the process of finding the problem, given that in debug mode, the configuration was always given correct. And some team members reproduced the incorrect configuration, while others did not. And we concluded that there was probably a bug in the old version, and decided to update the version to a newer one.

After a long search for the problem in the code, the error was not found. Testing the project on different Nodes showed that when starting a project on Node, starting with version 11, the answer was always stable. Which was the solution to this problem. Node version was updated to 12 and the problem went away.

Case number two

This time, the configurations were different in different versions of the browser: in Google Chrome 80 the result was correct, but in its 69 version it was not. And then we wondered why the configuration was different.

  • Saw the versions are different

  • Opened Google Chrome Release notes

  • Found that Google Chrome 69 is the last build using V8 6

  • Opened Release notes V8

  • And started looking through all the articles between 6 and 7 version V8

After a while, I came across an article Getting things sorted in V8, which says that from 7th version V8 is switching to a stable sorting algorithm TimSort, instead of the previous unstable QuickSort… And then it immediately became clear that there was no magic, and all these bugs were due to unstable sorting.

Sorting nuances

Sorting in Node.js 10.22 (V8 engine v6.8) QuickSort

As you can see, the array from the first screenshot has been reordered, although the compare function always returned 0.

Sorting in Node.js 14.5 (V8 engine v7.0) TimSort

This time, the sort did not change the data anymore.

How to live further

And what is the result? That clients may have different results from our code depending on the sorting type of JavaScript engine used. And if the transition to the new version solves the problem with Node.js, then it will not work to force all users to do the same with their browsers.

There are several different solutions to suit specific cases. In our case, we decided to use the implementation of the algorithm BlockSort (wikisort)… Yes, the implementation is slower than the browser’s native sort, but now I am confident in the stability of the sorting result where necessary.

Comparison of different solution options with native implementation

We decided to compare:

  • lodash.sortby

  • WikiSort javascript adaptation (WikiSort)

  • QuickSort native V8 implementation (node.js 10.22.0)

  • TimSort native V8 implementation (node.js 14.5.0)

During the test, 10 arrays were created with a random sorted value, each of which contained 100 thousand objects.

In the meantime, there is no need to know about it. ”

From this graph, we can conclude: after the optimizations performed by the V8 engine, sorting WikiSort not inferior to native implementation TimSort, although the difference is quite noticeable during the first sorts. But lodash I would not recommend it.

You can view the test results in more detail here sort-test-js, and the source code is here – Tihon-Ustinov / sort-test-js

Where is it stable?

version

date of release

JavaScript engine

stability

Node.js

11.0.0

2018-10-23

V8 7.0.276.28

+

Node.js

10.22.0

2020-07-21

V8 6.8.275.32

Google chrome

70.0.3538

2018-10-16

V8 7.0.276

+

Google chrome

69.0.3497

2018-09-04

V8 6.9.427

conclusions

  • Do not believe in the “magic of JavaScript”, all strange cases in this language have an explanation

  • Explore the technologies you use

  • Read the official documentation

  • Keep track of what’s coming in new versions

  • Do not think that everything has already been done and invented, and you only need to use ready-made solutions

Similar Posts

Leave a Reply Cancel reply