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