Pull to refresh
76.38
Ростелеком
Крупнейший провайдер цифровых услуг и решений

Нестабильная сортировка в JavaScript

Reading time 3 min
Views 5.2K

Когда я вижу пост на подобную тему в любой социальной сети, под ним почти всегда оказывается множество комментов вот такого типа:

  • Зачем это нужно знать, если есть встроенные методы сортировки?

  • Зачем изобретать велосипед заново?

  • Это нужно, чтобы пройти собеседование, объективно больше незачем это знать

  • В "любой движок javascript" работают не дураки, и уже сделали все как нужно

И сам я раньше считал так же, пока не пришел в одну из команд Ростелеком ИТ frontend-разработчиком. Вместе мы набрели на очень интересный кейс: нужно было создать виджет, который мог бы встраиваться в информационные системы всех наших макрорегиональных филиалов и упрощать работу операторов по подбору оптимального тарифа.

Сразу к делу

Как думаете, что произойдет после выполнения данного кода? ​

Кажется, что ничего странного, но есть нюансы.

Случай номер раз

Сделали задачу, техническое решение, код, unit-тесты. По бизнес-процессу тоже все хорошо. При поверхностном тестировании проблем не нашли. Но когда дело дошло до авто-тестов, начались странности. Конфигурация, которую просчитывал Node.js 10, в основном отдавала корректный результат, но иногда конфигурация отличалась. Что усложняло процесс поиска проблемы, учитывая, что в режиме отладки конфигурация отдавалась всегда корректной. А еще у одних членов команды некорректная конфигурация воспроизводилась, а у других — нет. И мы сделали вывод, что в старой версии, наверное, баг, и решили обновить версию на более новую.

После длительного поиска проблемы в коде ошибка не была найдена. Тестирование проекта на разных Node показало, что при запуске проекта на Node, начиная с версии 11, ответ был всегда стабильным. Что и послужило решением этой проблемы. Версия Node была обновлена до 12, и проблема исчезла.

Случай номер два

На этот раз конфигурации отличались уже в разных версиях браузера: в Google Chrome 80 был корректный результат, а в его 69 версии — нет. И тут нам стало интересно, почему же конфигурация отличается. 

  • Увидел, что версии отличаются

  • Открыл Release notes Google Chrome 

  • Обнаружил, что Google Chrome 69 —это последняя сборка, где используется 6-я версия V8

  • Открыл Release notes V8

  • И начал просматривать все статьи между 6 и 7 версией V8

Спустя некоторое время я наткнулся на статью Getting things sorted in V8, в которой говорится, что с 7-й версии V8 переходит на стабильный алгоритм сортировки TimSort, вместо предыдущего нестабильного QuickSort. И тут сразу стало понятно, что никакой магии нет, и все эти баги из-за нестабильной сортировки.

Нюансы сортировки

Сортировка в Node.js 10.22 (движок V8 v6.8) QuickSort.​

​Как видите, массив из первого скриншота изменил порядок, хотя функция сравнения всегда возвращала 0.

Сортировка в Node.js 14.5 (движок V8 v7.0) TimSort.​

​На этот раз сортировка уже не изменила данные.

Как дальше жить

И что же в итоге получается? То, что у клиентов могут быть разные результаты работы нашего кода в зависимости от типа сортировки используемого движка JavaScript. И если с Node.js переход на новую версию решит проблему, то заставить всех пользователей сделать то же самое со своими браузерами не получится. 

Есть несколько разных решений, которые подойдут для конкретных кейсов. В нашем случае мы решили использовать реализацию алгоритма BlockSort (wikisort). Да, реализация работает медленнее, чем нативная сортировка браузера, но зато теперь я уверен в стабильности результата сортировки там, где это необходимо.

Сравнение разных вариантов решения с нативной реализацией

Мы решили сравнить:

  • lodash.sortby

  • WikiSort javascript адаптация (WikiSort)

  • QuickSort нативная реализация V8 (node.js 10.22.0)

  • TimSort нативная реализация V8 (node.js 14.5.0)

В ходе теста было создано 10 массивов со случайным сортируемым значением, в каждом из которых было по 100 тысяч объектов. 

​Из этого графика можно сделать вывод: после оптимизаций, которые провел движок V8, сортировка WikiSort не уступает нативной реализации TimSort, хотя при первых сортировках разница довольно заметная. А вот lodash я бы не стал советовать. 

Посмотреть результаты теста подробнее можно тут sort-test-js, а исходный код тут — Tihon-Ustinov/sort-test-js

Где стабильно?

версия

дата релиза

движок JavaScript

стабильность

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

-

Выводы

  • Не верьте в «магию JavaScript», у всех странных кейсов в этом языке есть объяснение

  • Изучайте технологии, которые вы используете

  • Читайте официальную документацию

  • Следите за тем, что появляется в новых версиях

  • Не думайте, что уже все сделано и придумано, и вам нужно только использовать готовые решения

Tags:
Hubs:
+8
Comments 29
Comments Comments 29

Articles

Information

Website
www.company.rt.ru
Registered
Founded
Employees
over 10,000 employees
Location
Россия
Representative
Анастасия М.