Кротовые норы в JavaScript

Привет, Хабр! Представляю вашему вниманию перевод статьи "Wormholes in JavaScript" автора Mathius Buus.

Компьютеры — интересные машины. В теории они представляются нам идеальными механическими математиками работающими с цифрами и хорошо выполняющими операции сложения, умножения и вычитания.

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

Если мы знаем на что способен компьютер, мы можем использовать кратчайшие пути или кротовые норы, чтобы сделать наши программы намного быстрее, чем мы ожидали.

Кротовая нора в операции получения остатка от деления

Что конкретно это означает? Давайте посмотрим на примере: представим, что мы хотим реализовать кольцевой список. Кольцевой список — это список с фиксированным размером, в котором вставки большие, чем размер списка, перемещаются в начало списка и по кругу. Кольцевые списки очень удобны для многих вещей — таких как сбор статистики за определенные интервалы времени, буферизация данных и многое другое, но посмотрите на эту реализацию:

const list = new Array(15000) function set (i, item) {   // Оператор % - деление по модулю, возвращает остаток от деления   // числа слева от него на число справа   // использование этого оператора здесь, привязывает цикл с переменной i к размеру списка   list[i % list.length] = item }

Как быстро выполняется этот код? Давайте запустим простой тест на скорость

console.time() for (var i = 0; i < 1e9; i++) {   set(i, i) } console.timeEnd() 

На моем компьютере это заняло ~4 сек на 1 млрд вставок. Неплохо.

Однако, давайте применим вычислительную кротовую нору и изменим размер массива на магическое число:

// Изменим размер списка с 15000 на 16384 const list = new Array(16384)  function set (i, item) {   // Оператор % - деление по модулю, возвращает остаток от деления   // числа слева от него на число справа   // использование этого оператора здесь, привязывает цикл с переменной i к размеру списка   list[i % list.length] = item } 

Попытаемся запустить тест на производительность снова. На моем компьютере тест выполнился за ~1.5 сек. Более чем двукратное увеличение за счет простого изменения размера. Для того чтобы понять почему так происходит, мы должны понимать следующее, под капотом компьютер работает с числами с основанием 2. Это важно знать если мы получаем остаток от деления (операция %). Такое вычисление произвести гораздо проще, если число кратно 2 (2 ^ n) b 16384 это 2 ^ 14. По факту компьютер смотрит на число в двоичном виде и просто берет последние n бит.

Для примера: что будет происходить при выполнении такой операции 353 500 % 16 384? 353 500 в бинарном представлении будет выглядеть как 1010110010011011100. Поскольку 16384 == 2 ^ 14 — нам необходимо взять последние 14 бит — 10101 (10010011011100) или 9 346.

Мы можем использовать это знание применительно к другой кротовой норе. Для компьютера очень просто и быстро брать последние n бит. По факту, необходимо всего лишь произвести бинарное и (операция &) с числом (2 ^ n) — 1

const list = new Array(16384)  function set (i, item) {   // Использование быстрого оператора &(бинарное И) вместо % с длиной списка 2 ^ n   list[i & (list.length - 1)] = i }

Запустив снова тест производительности на моем компьютере мы увидим, что время исполнения снизиться до ~1s или произойдёт 4-ёх кратное увеличение производительности по сравнению с первым запуском. И все это за счет понимания того как компьютер работает.

Умные компиляторы или VМ способны производить такую оптимизацию превращая за кулисами операцию получения остатка в побитовую операцию и обратно. По факту последняя V8 Javascript VM (не реализовано в NodeJS) делает именно так.

Числовые кротовые норы

Другой полезной кротовой норой является понимание того как работает чтение и запись чисел. Помните как мы использовали 32-битные компьютеры и как получили 64 бита? А до 32-ух бит у нас было 16 бит. Что конкретно это значит? Обычно мы думаем об этом так — как много оперативной памяти у нас есть на компьютере. 2 ^ 32 = 4294967296 или 4 Гб, что означает что мы можем получить доступ только к 4 Гб памяти на 32-битном компьютере. Когда мы пишем JS программу нам обычно не нужно думать об этом, поскольку мы обычно не используем столько памяти.

Однако очень важно понимать различие между 32- и 64-битными компьютерами. С тех пор как процессоры получили 64-битные регистры на 64 -битных компьютерах совершение операций стали в 2 раза быстрее чем на 32 битных компьютерах, где вы имели только 32-битные регистры.

Как же мы можем использовать информацию об этой кротовой норе?
Давайте напишем простую программу, которая копирует один Uint8Array в другой. Если вы не знакомы с Unit8Arrays — они очень схожи с Buffers в NodeJS, или просто "чистой" памятью.

function copy (input, output) {   // для простоты предположим input.length <= output.length   for (var i = 0; i < input.length; i++) {     // копируем каждое 8-разрядное число (byte)     output[i] = input[i]   } }

Снова давайте измерим скорость, запустив тест производительности.

// давайте выделим два 1MB Uint8Arrays для нашего теста производительности const input = new Uint8Array(1024 * 1024) const output = new Uint8Array(1024 * 1024)  console.time() for (var i = 0; i < 1e4; i++) {   copy(input, output) } console.timeEnd() 

На моем компьютере программа выполнилась за ~7.5 сек. Как мы можем использовать кротовую нору для ускорения? Используя Uint8Array мы копируем только 8 бит за один раз, но имея 64-битный компьютер — мы можем копировать 64 бита информации за то же время. Мы можем сделать это в JavaScript, преобразовав наш Uint8Array в Float64Array перед копированием, что нам не будет ничего стоить.

function copy (input, output) {   // для простоты предположим input.length <= output.length    // на вход и выход в виде 64-разрядных чисел   // здесь мы фактически используем числа с плавающей запятой,    // тк каждое из них принимает 64-разрядное представление   // когда BigInts оптимизирован в JavaScript, мы можем использовать BigInt64Array.    const input64 = new Float64Array(input.buffer, input.byteOffset, input.length / 8)   const output64 = new Float64Array(output.buffer, output.byteOffset, output.length / 8)    for (var i = 0; i < input64.length; i++) {     // копируем каждое 64-разрядное число      output64[i] = input64[i]   } } 

Запустив тесты производительности снова мы получим время выполнения равное 1 сек, что дает 8 кратный прирост скорости.

Для копирования приемлемым решением будет использование array.set(otherArray) метода для Uint8Array, что дает нам копирование в нативном коде — что намного быстрее, чем любые другие кротовые норы. Для справки это даст результат в ~ 0.2 сек исполнения в нашем тесте на моем компьютере, что в 5 раза быстрее чем предыдущее решение.

Галактика JavaScript полна кротовых нор

Использование кротовых нор, приведенных выше, поможет Вам сделать тонны реальных алгоритмов намного быстрее. Существует еще много подобных кротовых нор. Мой фаворит — Math.clz32 — метод, возвращающий 32 битном число с ведущим 0. Мы можем использовать этот метод для множества интересных алгоритмов. Я использовал его для ускорения реализации битовых полей (https://github.com/mafintosh/fast-bitfield) в 4 раза, что привело к снижению расхода памяти также в 4 раза и позволило мне в некоторых ситуациях сортировать числа намного быстрее (https://github.com/mafintosh/value-sort).

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

P. S.:

Отдельное спасибо за помощь в переводе и корректировке перевода Переверзевой Ольге