Когда я вижу пост на подобную тему в любой социальной сети, под ним почти всегда оказывается множество комментов вот такого типа:
-
Зачем это нужно знать, если есть встроенные методы сортировки?
-
Зачем изобретать велосипед заново?
-
Это нужно, чтобы пройти собеседование, объективно больше незачем это знать
-
В "любой движок 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, у всех странных кейсов в этом языке есть объяснение
-
Изучайте технологии, которые вы используете
-
Читайте официальную документацию
-
Следите за тем, что появляется в новых версиях
-
Не думайте, что уже все сделано и придумано, и вам нужно только использовать готовые решения
