Хабрахабр

[Из песочницы] Кротовые норы в 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. По факту компьютер смотрит на число в двоичном виде и просто берет последние n бит. Такое вычисление произвести гораздо проще, если число кратно 2 (2 ^ n) b 16384 это 2 ^ 14.

353 500 в бинарном представлении будет выглядеть как 1010110010011011100. Для примера: что будет происходить при выполнении такой операции 353 500 % 16 384? Поскольку 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-ёх кратное увеличение производительности по сравнению с первым запуском.

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

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

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

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

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

function copy (input, output)
}

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

// давайте выделим два 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()

5 сек. На моем компьютере программа выполнилась за ~7. Используя 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 кратный прирост скорости.

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

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

Существует еще много подобных кротовых нор. Использование кротовых нор, приведенных выше, поможет Вам сделать тонны реальных алгоритмов намного быстрее. Мы можем использовать этот метод для множества интересных алгоритмов. Мой фаворит — Math.clz32 — метод, возвращающий 32 битном число с ведущим 0. Я использовал его для ускорения реализации битовых полей в 4 раза, что привело к снижению расхода памяти также в 4 раза и позволило мне в некоторых ситуациях сортировать числа намного быстрее.

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

S.: P.

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть