Перейти к основному содержимому

Упорядочивание в V8

· 16 мин. чтения
Саймон Цюнд ([@nimODota](https://twitter.com/nimODota)), согласованный компаратор

Array.prototype.sort был одним из последних встроенных методов, реализованных на JavaScript с самохостингом в V8. Его портирование предоставило нам возможность экспериментировать с различными алгоритмами и стратегиями реализации, а затем наконец сделать его стабильным в V8 v7.0 / Chrome 70.

История​

Сортировка в JavaScript трудна. Этот блог пост рассматривает некоторые особенности взаимодействия алгоритма сортировки с языком JavaScript и описывает наш путь, чтобы перенести V8 на стабильный алгоритм и сделать производительность более предсказуемой.

При сравнении различных алгоритмов сортировки мы оцениваем их худшую и среднюю производительность, выраженную как ограничение на асимптотический рост (то есть обозначение “Big O”) либо операций с памятью, либо числа сравнений. Помните, что в динамических языках, таких как JavaScript, операция сравнения обычно значительно дороже, чем доступ к памяти. Это связано с тем, что сравнение двух значений во время сортировки обычно включает вызовы пользовательского кода.

Давайте посмотрим на простой пример сортировки чисел по возрастанию с использованием функции сравнения, предоставленной пользователем. Согласованная функция сравнения возвращает -1 (или любое другое отрицательное значение), 0 или 1 (или любое другое положительное значение), если два предоставленных значения меньше, равны или больше соответственно. Функция сравнения, которая не следует этому шаблону, является несогласованной и может иметь произвольные побочные эффекты, такие как изменение массива, который она должна отсортировать.

const array = [4, 2, 5, 3, 1];

function compare(a, b) {
  // Здесь может быть произвольный код, например, `array.push(1);`.
  return a - b;
}

// Обычный вызов сортировки.
array.sort(compare);

Даже в следующем примере могут происходить вызовы пользовательского кода. “По умолчанию” функция сравнения вызывает toString для обоих значений и делает лексикографическое сравнение строковых представлений.

const array = [4, 2, 5, 3, 1];

array.push({
  toString() {
    // Здесь может быть произвольный код, например, `array.push(1);`.
    return '42';
  }
});

// Сортировка без функции сравнения.
array.sort();

Больше забав с аксессорами и взаимодействием цепочки прототипов​

Это та часть, где мы покидаем спецификацию и отправляемся в «определяемое реализацией» поведение. Спецификация имеет целый список условий, которые, если выполняются, позволяют движку сортировать объект/массив по своему усмотрению — или не сортировать вообще. Движки должны следовать некоторым основным правилам, но все остальное остается на усмотрение разработчиков движков. С одной стороны, это дает разработчикам движков свободу экспериментировать с различными реализациями. С другой стороны, пользователи ожидают разумного поведения, даже если спецификация этого не требует. Это усложняется тем фактом, что «разумное поведение» не всегда просто определить.

Этот раздел показывает, что у Array#sort все еще есть аспекты, где поведение движков сильно отличается. Это сложные крайние случаи, и, как уже упоминалось выше, не всегда ясно, что «правильно». Мы настойчиво рекомендуем не писать такой код; движки не будут оптимизировать его.

Первый пример показывает массив с некоторыми аксессорами (т.е. геттерами и сеттерами) и «журнал вызовов» в различных JavaScript движках. Аксессоры — первая область, где результирующий порядок сортировки определяется реализацией:

const array = [0, 1, 2];

Object.defineProperty(array, '0', {
  get() { console.log('get 0'); return 0; },
  set(v) { console.log('set 0'); }
});

Object.defineProperty(array, '1', {
  get() { console.log('get 1'); return 1; },
  set(v) { console.log('set 1'); }
});

array.sort();

Вот вывод этого фрагмента кода в различных движках. Помните, что здесь нет “правильных” или “неправильных” ответов — спецификация оставляет это на усмотрение реализации!

// Chakra
get 0
get 1
set 0
set 1

// JavaScriptCore
get 0
get 1
get 0
get 0
get 1
get 1
set 0
set 1

// V8
get 0
get 0
get 1
get 1
get 1
get 0

#### SpiderMonkey
get 0
get 1
set 0
set 1

Следующий пример показывает взаимодействие с цепочкой прототипов. Ради сокращения не показываем журнал вызовов.

const object = {
 1: 'd1',
 2: 'c1',
 3: 'b1',
 4: undefined,
 __proto__: {
   length: 10000,
   1: 'e2',
   10: 'a2',
   100: 'b2',
   1000: 'c2',
   2000: undefined,
   8000: 'd2',
   12000: 'XX',
   __proto__: {
     0: 'e3',
     1: 'd3',
     2: 'c3',
     3: 'b3',
     4: 'f3',
     5: 'a3',
     6: undefined,
   },
 },
};
Array.prototype.sort.call(object);

Вывод показывает объект после сортировки. Опять же, здесь нет правильного ответа. Этот пример просто демонстрирует, насколько странным может быть взаимодействие между индексированными свойствами и цепочкой прототипов:

// Chakra
['a2', 'a3', 'b1', 'b2', 'c1', 'c2', 'd1', 'd2', 'e3', undefined, undefined, undefined]

// JavaScriptCore
['a2', 'a2', 'a3', 'b1', 'b2', 'b2', 'c1', 'c2', 'd1', 'd2', 'e3', undefined]

// V8
['a2', 'a3', 'b1', 'b2', 'c1', 'c2', 'd1', 'd2', 'e3', undefined, undefined, undefined]

// SpiderMonkey
['a2', 'a3', 'b1', 'b2', 'c1', 'c2', 'd1', 'd2', 'e3', undefined, undefined, undefined]

Что делает V8 до и после сортировки​

примечание

Примечание: Этот раздел был обновлен в июне 2019 года, чтобы отразить изменения в предварительной и постобработке Array#sort в V8 версии 7.7.

V8 выполняет один этап предварительной обработки перед фактической сортировкой и также один этап постобработки. Основная идея заключается в сборе всех значений, отличных от undefined, в временный список, сортировке этого временного списка, а затем записи отсортированных значений обратно в исходный массив или объект. Это освобождает V8 от необходимости взаимодействовать с аксессорами или цепочкой прототипов во время самой сортировки.

Спецификация ожидает, что Array#sort создаст порядок сортировки, который концептуально можно разбить на три сегмента:

  1. Все значения, кроме undefined, отсортированы относительно функции сравнения.
  2. Все значения undefined.
  3. Все дыры, то есть несуществующие свойства.

Фактический алгоритм сортировки нужно применить только к первому сегменту. Для этого V8 выполняет этап предварительной обработки примерно следующим образом:

  1. Пусть length будет значением свойства ”length” массива или объекта для сортировки.
  2. Пусть numberOfUndefineds будет равно 0.
  3. Для каждого value в диапазоне [0, length): a. Если value — дыра: ничего не делайте b. Если value равно undefined: увеличьте numberOfUndefineds на 1. c. В противном случае добавьте value во временный список elements.

После выполнения этих шагов все значения, отличные от undefined, помещаются во временный список elements. undefined просто подсчитываются, вместо того чтобы добавляться в elements. Как упоминалось выше, спецификация требует, чтобы undefined были отсортированы в конец. Однако значения undefined фактически не передаются предоставленной пользователем функции сравнения, поэтому мы можем просто подсчитывать количество undefined, которые встретились.

Следующий шаг — фактическая сортировка elements. См. раздел о TimSort для подробного описания.

После завершения сортировки отсортированные значения должны быть записаны обратно в исходный массив или объект. Этап постобработки состоит из трех фаз, которые обрабатывают концептуальные сегменты:

  1. Запишите все значения из elements в исходный объект в диапазоне [0, elements.length).
  2. Установите все значения из [elements.length, elements.length + numberOfUndefineds) в undefined.
  3. Удалите все значения в диапазоне [elements.length + numberOfUndefineds, length).

Шаг 3 необходим в случае, если исходный объект содержал дыры в диапазоне сортировки. Значения в диапазоне [elements.length + numberOfUndefineds, length) уже были перемещены в начало, и пропуск шага 3 приведет к дублированию значений.

История​

Array.prototype.sort и TypedArray.prototype.sort основывались на одной реализации Quicksort, написанной на JavaScript. Сам алгоритм сортировки довольно прост: основа — Quicksort с использованием Insertion Sort для коротких массивов (длина < 10). Insertion Sort также использовался, когда рекурсия Quicksort достигала подмассива длиной 10. Insertion Sort более эффективен для небольших массивов, поскольку Quicksort вызывается рекурсивно дважды после разделения. Каждый такой рекурсивный вызов имел накладные расходы на создание (и уничтожение) кадра стека.

Выбор подходящего опорного элемента имеет большое значение для Quicksort. V8 использует две стратегии:

  • Опорный элемент выбирался как медиана первого, последнего и третьего элемента подмассива, который сортируется. Для меньших массивов этот третий элемент просто является средним элементом.
  • Для больших массивов брался образец, затем сортировался, и медиана отсортированного образца служила третьим элементом в вышеприведенном расчете.

Одно из преимуществ Quicksort заключается в том, что он сортирует на месте. Накладные расходы памяти связаны с выделением небольшого массива для образца при сортировке больших массивов и логарифмическим использованием пространства стека. Недостатком является то, что это нестабильный алгоритм, и существует вероятность, что алгоритм приведет к худшему сценарию, когда QuickSort деградирует до 𝒪(n²).

Введение V8 Torque​

Как заядлый читатель блога V8, вы могли слышать о CodeStubAssembler или сокращенно CSA. CSA — это компонент V8, который позволяет нам писать низкоуровневый TurboFan IR напрямую на C++, который затем переводится в машинный код для соответствующей архитектуры, используя бэкенд TurboFan.

CSA широко используется для написания так называемых "быстрых путей" для встроенных функций JavaScript. Версия встроенной функции с быстрым путём обычно проверяет, соблюдаются ли определенные инварианты (например, отсутствие элементов в цепочке прототипов, отсутствие аксессоров и т. д.) и затем использует более быстрые и специфические операции для реализации функциональности встроенной функции. Это может привести к времени выполнения, которое на порядок быстрее, чем более универсальная версия.

Недостаток CSA заключается в том, что его можно считать языком ассемблера. Управление потоком представлено с использованием явных labels и gotos, что делает реализацию более сложных алгоритмов в CSA трудной для чтения и склонной к ошибкам.

И вот появляется V8 Torque. Torque — это специализированный язык программирования с синтаксисом, напоминающим TypeScript, который в настоящее время использует CSA как единственную цель компиляции. Torque позволяет практически тот же уровень управления, что и CSA, но при этом предлагает конструкции более высокого уровня, такие как циклы while и for. Кроме того, он строго типизирован и в будущем будет включать проверки безопасности, такие как автоматические проверки выхода за пределы массива, предоставляя инженерам V8 более сильные гарантии.

Первыми крупными встроенными функциями, которые были переписаны с использованием V8 Torque, стали TypedArray#sort и Dataview операции. Обе функции также служили целью предоставления отзывов разработчикам Torque о том, какие языковые функции необходимы и какие идиомы следует использовать для эффективного написания встроенных функций. На момент написания несколько встроенных функций JSArray были перенесены из их исходной JavaScript-реализации с fallback в Torque (например, Array#unshift), а другие были полностью переписаны (например, Array#splice и Array#reverse).

Перенос Array#sort в Torque​

Начальная версия Torque для Array#sort была практически прямым портом JavaScript-реализации. Единственным отличием было то, что вместо использования метода выборки для больших массивов третий элемент для вычисления опорного элемента выбирался случайным образом.

Это работало достаточно хорошо, но, поскольку всё еще использовалась быстрая сортировка (Quicksort), Array#sort оставалась нестабильной. Запрос на стабильную версию Array#sort является одним из старейших тикетов в трекере ошибок V8. Эксперименты с Timsort на следующем этапе дали несколько преимуществ. Во-первых, нам понравилось, что он стабильный и предлагает хорошие гарантии алгоритмов (подробнее см. следующий раздел). Во-вторых, Torque всё ещё находился в стадии разработки, и реализация такой сложной встроенной функции, как Array#sort с использованием Timsort, принесла множество полезных отзывов, повлиявших на Torque как язык.

Timsort​

Timsort, первоначально разработанный Тимом Питерсом для Python в 2002 году, можно описать как адаптивный стабильный вариант сортировки слиянием (Mergesort). Хотя детали довольно сложны и лучше всего описаны самим автором или на странице Википедии, основы легко понять. В то время как Mergesort обычно работает рекурсивно, Timsort работает итеративно. Он обрабатывает массив слева направо и ищет так называемые паспады (runs). Паспа — это просто последовательность, которая уже отсортирована. Это включает последовательности, которые отсортированы "в неправильном порядке", так как такие последовательности могут быть просто перевёрнуты, чтобы сформировать паспу. В начале процесса сортировки определяется минимальная длина паспы, которая зависит от длины входного массива. Если Timsort не может найти естественные паспы минимальной длины, паспа "создаётся искусственно" с использованием сортировки вставками (Insertion Sort).

Найденные таким образом паспы отслеживаются с использованием стека, который запоминает начальный индекс и длину каждой паспы. Время от времени паспы в стеке объединяются, пока не останется только одна отсортированная паспа. Timsort старается поддерживать баланс при решении, какие паспы объединить. С одной стороны, нужно стараться объединять паспы как можно раньше, так как данные этих пасп имеют высокий шанс уже находиться в кэше; с другой стороны, объединять лучше поздно, чтобы воспользоваться шаблонами в данных, которые могут появиться. Для достижения этого Timsort поддерживает два инварианта. Предполагая, что A, B и C — это три верхние паспы:

  • |C| > |B| + |A|
  • |B| > |A|

Стек пасп до и после объединения A с B

На изображении показан случай, когда |A| > |B|, поэтому B объединяется с меньшей из двух пасп.

Обратите внимание, что Timsort объединяет только последовательные паспы, это необходимо для поддержания стабильности, иначе равные элементы будут перемещаться между паспами. Также первый инвариант гарантирует, что длина паспы растёт как минимум так же быстро, как числа Фибоначчи, что дает верхнюю границу размера стека пасп, когда мы знаем максимальную длину массива.

Теперь можно видеть, что уже отсортированные последовательности сортируются за 𝒪(n), поскольку такой массив приведет к единственной паспе, которую не нужно объединять. Худший случай — 𝒪(n log n). Эти свойства алгоритма, вместе со стабильной природой Timsort, были одними из причин, почему в итоге мы выбрали Timsort вместо Quicksort.

Реализация Timsort в Torque​

Встроенные функции обычно имеют разные пути выполнения, которые выбираются во время выполнения в зависимости от различных переменных. Наиболее общий вариант может обрабатывать любой тип объекта, независимо от того, является ли он JSProxy, имеет перехватчики или требует поиска в цепочке прототипов при получении или установке свойств. Общий путь, как правило, медленнее в большинстве случаев, так как ему нужно учитывать все возможные случаи. Но если мы заранее знаем, что объект для сортировки — это простой JSArray, содержащий только числа Smis, все эти дорогостоящие операции [[Get]] и [[Set]] можно заменить на простые операции загрузки и хранения в FixedArray. Основным отличием является ElementsKind.

Теперь задача заключается в том, как реализовать быстрый путь. Основной алгоритм остается неизменным для всех случаев, но способ доступа к элементам меняется в зависимости от ElementsKind. Один из способов добиться этого — направлять на правильный “аксессор” на каждой точке вызова. Представьте переключатель для каждой операции “загрузки”/“сохранения”, где мы выбираем другую ветку в зависимости от выбранного быстрого пути.

Другое решение (и это был первый пробованный подход) — просто копировать весь встроенный механизм для каждого быстрого пути и вставлять правильный метод доступа для загрузки/сохранения. Этот подход оказался неприемлемым для Timsort, так как это большой встроенный механизм, и создание копии для каждого быстрого пути потребовало бы 106 КБ в общей сложности, что слишком много для одного встроенного механизма.

Окончательное решение слегка отличается. Каждая операция загрузки/сохранения для каждого быстрого пути помещена в свой собственный “мини-встроенный механизм”. См. пример кода, который показывает операцию “загрузки” для FixedDoubleArray.

Load<FastDoubleElements>(
    context: Context, sortState: FixedArray, elements: HeapObject,
    index: Smi): Object {
  try {
    const elems: FixedDoubleArray = UnsafeCast<FixedDoubleArray>(elements);
    const value: float64 =
        LoadDoubleWithHoleCheck(elems, index) otherwise Bailout;
    return AllocateHeapNumberWithValue(value);
  }
  label Bailout {
    // На этапе предварительной обработки все дыры удалены путем сжатия всех элементов
    // в начале массива. Обнаружение дыры означает, что функция cmp или
    // ToString изменяет массив.
    return Failure(sortState);
  }
}

Для сравнения, самая общая операция “загрузки” — это просто вызов GetProperty. Но хотя вышеупомянутый вариант создает эффективный и быстрый машинный код для загрузки и преобразования числа, GetProperty является вызовом другого встроенного механизма, который потенциально может включать поиск в цепочке прототипов или вызов функционального аксессора.

builtin Load<ElementsAccessor : type>(
    context: Context, sortState: FixedArray, elements: HeapObject,
    index: Smi): Object {
  return GetProperty(context, elements, index);
}

Быстрый путь затем просто становится набором указателей на функции. Это означает, что нам нужна только одна копия основного алгоритма, при этом все соответствующие указатели функций задаются один раз заранее. Хотя это значительно сокращает требуемое пространство для кода (до 20k), это происходит за счет косвенной ветвления на каждой точке доступа. Это даже ухудшается благодаря недавним изменениям в использовании встроенных механизмов.

Состояние сортировки​

На изображении выше показано “состояние сортировки”. Это FixedArray, который отслеживает все необходимые параметры во время сортировки. Каждый раз при вызове Array#sort такое состояние сортировки выделяется. Записи с 4 по 7 — это набор указателей на функции, обсуждаемых выше, которые составляют быстрый путь.

Встроенный механизм “check” используется каждый раз, когда мы возвращаемся из пользовательского кода JavaScript, чтобы проверить, можем ли мы продолжать текущий быстрый путь. Для этого используются “начальная карта приемника” и “начальная длина приемника”. Если пользовательский код изменил текущий объект, мы просто прекращаем выполнение сортировки, сбрасываем все указатели на их самые общие версии и начинаем процесс сортировки заново. “Статус сбоя” в слоте 8 используется для сигнала об этом сбросе.

Запись “compare” может указывать на два разных встроенных механизма. Один вызывает предоставленную пользователем функцию сравнения, а другой реализует сравнение по умолчанию, которое вызывает toString для обоих аргументов, а затем выполняет лексикографическое сравнение.

Остальные поля (за исключением идентификатора быстрого пути) специфичны для Timsort. Стек выполнения (описанный выше) инициализируется размером 85, что достаточно для сортировки массивов длиной 264. Временный массив используется для объединения выполнений. Он увеличивается до необходимого размера, но никогда не превышает n/2, где n — размер входного массива.

Баланс производительности​

Перенос сортировки с реализованного на основе JavaScript на Torque сопровождается компромиссами по производительности. Так как Array#sort теперь написан на Torque, это статически компилируемый кусок кода, что позволяет создавать быстрые пути для определенных ElementsKinds, но он никогда не будет таким быстрым, как высоко оптимизированная версия TurboFan, использующая обратную связь по типам. С другой стороны, в случаях, когда код недостаточно «горяч», чтобы оправдать JIT-компиляцию, или вызов является мегаморфным, мы вынуждены использовать интерпретатор или медленную/общую версию. Парсинг, компиляция и возможная оптимизация версии JavaScript также представляют собой накладные расходы, которые не требуются в реализации Torque.

Хотя подход Torque не обеспечивает такого же пикового уровня производительности при сортировке, он предотвращает резкие падения производительности. Результатом является более предсказуемая производительность сортировки по сравнению с предыдущей. Учтите, что Torque находится в стадии активного развития, и помимо целевой поддержки CSA, он может начать поддерживать TurboFan в будущем, что позволит осуществлять JIT-компиляцию кода, написанного на Torque.

Микробенчмарки​

Перед началом работы над Array#sort мы добавили множество различных микробенчмарков, чтобы лучше понять, какой будет влияние переосуществления. На первом графике представлен «обычный» случай использования сортировки различных ElementsKinds с пользовательской функцией сравнения.

Имейте в виду, что в этих случаях JIT-компилятор может проделать большую работу, поскольку сортировка – это почти все, что мы делаем. Это также позволяет оптимизирующему компилятору встроить функцию сравнения в версию JavaScript, в то время как мы испытываем накладные расходы на вызов встроенной функции в JavaScript в случае Torque. Тем не менее, мы показываем лучшие результаты практически во всех случаях.

На следующем графике показано влияние Timsort на обработку массивов, которые уже полностью сортированы или содержат подпоследовательности, уже отсортированные одним способом или другим. На графике используется Quicksort в качестве базовой линии и показано ускорение от Timsort (до 17× в случае «DownDown», где массив состоит из двух обратно отсортированных последовательностей). Как видно, за исключением случайных данных, Timsort показывает лучшие результаты во всех остальных случаях, несмотря на то, что мы сортируем PACKED_SMI_ELEMENTS, где Quicksort превзошел Timsort в вышеупомянутом микробенчмарке.

Benchmark для веб-инструментов​

Бенчмарк веб-инструментов представляет собой набор рабочих нагрузок для инструментов, обычно используемых веб-разработчиками, таких как Babel и TypeScript. На графике используется JavaScript Quicksort в качестве базовой линии и сравнивается ускорение от Timsort с ним. Почти во всех тестах мы сохраняем ту же производительность, за исключением chai.

Бенчмарк chai проводит треть времени внутри одной функции сравнения (вычисление расстояния между строками). Бенчмарк представляет собой тест-набор самого chai. Ввиду данных, Timsort в данном случае требует больше сравнений, что оказывает значительное влияние на общее время выполнения, так как такая большая часть времени тратится внутри этой функции сравнения.

Влияние на память​

Анализ снимков V8 heap при просмотре примерно 50 сайтов (как на мобильных устройствах, так и на настольных компьютерах) не показал никаких регрессий или улучшений по памяти. С одной стороны, это удивительно: переход от Quicksort к Timsort ввел необходимость в использовании временного массива для объединения прогонов, который может быть значительно больше, чем временные массивы, используемые для выборки. Однако эти временные массивы очень краткосрочны (только на время вызова sort) и могут быстро выделяться и освобождаться в новой области V8.

Вывод​

В целом, мы чувствуем себя намного увереннее в отношении алгоритмических свойств и предсказуемого поведения производительности Timsort, реализованного в Torque. Timsort доступен начиная с V8 v7.0 и Chrome 70. Желаем удачной сортировки!