Привет, Хабр! Представляю вашему вниманию перевод статьи "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 или произойдёт четырёхкратное кратное увеличение производительности по сравнению с первым запуском. И все это за счет понимания того как компьютер работает.
Умные компиляторы или 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-битном двоичном представлении числа. Мы можем использовать этот метод для множества интересных алгоритмов. Я использовал его для ускорения реализации битовых полей в 4 раза, что привело к снижению расхода памяти также в 4 раза и позволило мне в некоторых ситуациях сортировать числа намного быстрее.
Понимание основных принципов работы компьютера позволяет писать наиболее быстрые программы, которые нам нужны. Эти знания имеют значения даже тогда, когда вы пишете на таком языке высокого уровня как JavaScript.
P. S.:
Отдельное спасибо за помощь в переводе и корректировке перевода Переверзевой Ольге
Комментарии (27)
mwizard
30.10.2018 11:18+1Когда-то это называлось «дырявой абстракцией», а предлагаемые лайфхаки — «преждевременной оптимизацией». Также вы забыли упомянуть, что сам Number является по спецификации числом с плавающей точкой двойной точности, и для double-ов деление на 15000 ничем принципиально не отличается от деления на степень двойки, так же как и не определены битовые операции.
Но так как VM использует внутренние оптимизации представления вида «считать беззнаковым 32-битным целым, пока не будет доказано обратное», это сработает. Так что тут «кротовьи норы» второго порядка.
Стоит ли их использовать? Я бы сказал, что нет. Код должен быть читабельным и понятным другому инженеру, который ничего не знает о вашем продукте. И только если результат читабельного кода медленный, и только если профилировщик покажет, что узкое место — конкретно в операции остатка от деления, то только тогда следует придумывать оптимизации.ReklatsMasters
30.10.2018 11:58если профилировщик покажет
О каком таком профилировщике для js, который укажет именно на операцию остатка от деления, вы говорите? Я использую
perf, и он ничего подобного не показывает. Вот сравните 2 результата профайлера, в каком из них вы видите просадки от операции остатка от деления?
до оптимизаций98,60% node perf-6945.map [.] LazyCompile:* /home/blah/dev/before.js:1 0,05% node node [.] _ZN2v88internal7Scanner4ScanEv 0,05% node node [.] _ZN2v88internal7Scanner28ScanIdentifierOrKeywordInnerEPNS1_12LiteralScopeE 0,03% node node [.] _ZN2v88internal6String17CalculateLineEndsENS0_6HandleIS1_EEb 0,03% node perf-6945.map [.] Handler:UnknownBytecodeHadlerZenitchik
30.10.2018 12:45Код должен быть читабельным и понятным другому инженеру, который ничего не знает о вашем продукте.
Но знает язык на должном уровне, согласны? И, очевидно, примерно помнит, чему равны степени двойки.
Я к тому, что приведённые примеры — не ухудшают читаемости кода. Для программиста число 65536 должно быть не более «магическим», чем 1000. А что память быстрее всего копировать блоками, равными разрядности шины — это общеизвестный факт.
funca
30.10.2018 20:16Про преждевременные оптимизации и читабельность твердят на каждом шагу. Как будто это что-то плохое. В результате имеем тонны тормозных решений просто потому, что инженеры с умным видом сцат писать иначе.
DistortNeo
30.10.2018 23:58и для double-ов деление на 15000 ничем принципиально не отличается от деления на степень двойки
Нет разницы только в процессорах последних поколений:
https://www.agner.org/optimize/instruction_tables.pdf
ReklatsMasters
30.10.2018 11:21Матиас очень любит делать хардкорные вещи. Одна из последних его вещей — json парсер на чистом js, который кратно быстрее стандартного. Если вы тоже любите оптимизации, то подписаться на его гитхаб однозначно.
Dreyk
30.10.2018 11:37это интересные знания, если хочется получше разобраться, как работает движок. но «не пытайтесь повторить это дома». даже если это и даёт прирост в скорости (что само по себе не известно, нужно ли вашему приложению) — поддерживаемости коду это точно навредит
impwx
30.10.2018 11:51Зачем вводить новый термин «кротовая нора», когда на самом деле это просто оптимизация? Чтобы звучало модно, стильно, молодежно?
speshuric
30.10.2018 13:56+2Wormholes же в оригинале. И картинка намекает, а перевод не очень удачный. Wormholes в данном случае типа залез в чёрную дыру тут, а вылез в 100 млн парсеков (за 1000 лет до рождения). Червоточины, возможно, было бы точнее и понятнее
impwx
30.10.2018 14:08Это не претензия к переводчику, а вопрос по существу. Что из описанного в статье нельзя было считать обычной оптимизацией?
speshuric
30.10.2018 14:26+3Все являются, конечно. Главная идея статьи (поста в блоге в оригинале) в последней фразе. Перефразируя "JS такой высокоуровневый, а битовые хаки для оптимизации все равно работают".
khim
30.10.2018 17:23+1Почти всё. Тот факт, что операции с «нетипизированными данными», которые на самом деле «Number», которые типа как «double», но на самом деле «uint32» и оптимизатор про это знает — очень серьёзно опирается на реализацию многих вещей.
То есть фактически подобные вещи «пробивают» все мнгочисленные слои абстракций, которые пытаются сделать вид, что JS — это такая себе сущность, описанная в спецификации… и никакого отношения к ассемблеру не имеет… а оказывается, что нет — таки имеет…speshuric
30.10.2018 23:11И что характерно, на самом деле многие скриптовые/высокоуровневые языки такими "битовыми" хаками особо не пооптимизируешь. Вот из того, что помню
- SQL — за современный Postgres с Jit не скажу, но в MS SQL Server/MySQL/Oracle/PostgreSQL разница на уровне погрешности.
- VB/VBS/VBA. Некоторые приемы работают, но только при строгой типизации. Variant или работа с COM мгновенно съедают разницу.
- 1С — там арифметика на своём "особенном" числовом типе. Этот тип раз в 100 медленнее Int32. Сдвигов и битовой логики нет.
- Powershell — с ним смешно. Я лет 6 назад с удивлением обнаружил, что типизированные переменные медленнее нетипизированных. Там просто при каждом присваивании для типизированных переменных происходит принудительное приведение к типу.
- Bash, cmd — не найти разницу
Да и JS стал таким чувствительным к битовым хакам примерно с появлением "дерзкого" V8, потом остальные стараются догнать (кто не верит — ставьте виртуалку с IE6 и проверьте).
funca
30.10.2018 20:27Если вы привыкли видеть сквозь синтаксис Javascript макроассемблер, то конечно ни чего необычного. Просто обычно вопросы оптимизации замыкаются на языка и библиотек (for-of vs .forEach(), DOM vs jQuery и т.п.). smile)
Merteg
30.10.2018 14:10Умные компиляторы или VМ способны производить такую оптимизацию превращая за кулисами операцию получения остатка в побитовую операцию и обратно. По факту последняя V8 Javascript VM (не реализовано в NodeJS) делает именно так.
NodeJS 11 вышла и там апдейт V8 до последней версии, может уже и реализовано.
eatmore
30.10.2018 21:42Функция
copy(та, которая используетFloat64Array) иногда копирует данные неправильно. Даже если длина массива делится на 8. Это хороший пример того, как "умная" оптимизация может приводить к появлению трудно обнаруживаемых ошибок.ReklatsMasters
30.10.2018 23:20А можно пример? Ни разу не натыкался на неправильное копирование.
eatmore
31.10.2018 00:16+1Под спойлером — пример массива, который копируется неправильно. Но я предлагаю перед тем, как заглядывать туда, попробовать найти проблему самостоятельно.
Кодlet input = new Uint8Array(8).fill(255); let output = new Uint8Array(8); copy(input, output); console.log(input, output);
ОбъяснениеПри декодировании данных как
Float64, получается значениеNaN. Это единственное значение, у которого есть несколько различный представлений (хотя значения+0и-0выглядят как равные для операторов==и===, они являются различными). Согласно стандарту, в JavaScript все значения NaN неразличимы:
The Number type has exactly 18437736874454810627 (that is, 264?253+3) values, representing the double-precision 64-bit format IEEE 754-2008 values as specified in the IEEE Standard for Binary Floating-Point Arithmetic, except that the 9007199254740990 (that is, 253?2) distinct “Not-a-Number” values of the IEEE Standard are represented in ECMAScript as a single special NaN value. (Note that the NaN value is produced by the program expression
NaN.) In some implementations, external code might be able to detect a difference between various Not-a-Number values, but such behaviour is implementation-dependent; to ECMAScript code, all NaN values are indistinguishable from each other.При кодировании в байты, скорее всего, будет использоваться не то представление NaN, которое было в исходном массиве (стандарт не указывает, какое именно нужно использовать, так что результат зависит от реализации), поэтому скопированные данные не будут совпадать с исходными.
Zenitchik
31.10.2018 14:05Спасибо!
Нутром чуял, что нельзя байтовый массив безболезненно в массив Float-ов сконвертить… Не знал почему, но со времён школы и QBasic-а натыкался на порчу данных при этом процессе.
vitaliy2
31.10.2018 14:32В js появляется BigInt64Array (пока спецификация не введена, поэтому не во всех браузерах, и скорость не мерял; ну и конечно же предложенный TypedArray.prototype.set лучше).
CoolCmd
31.10.2018 16:04несколько лет назад (еще до появления asm.js) сравнивал скорость копирования, и на некоторых браузерах UInt32Array был быстрее, чем Float64Array.
ArsenAbakarov
Полезно знать и держать в закладках!
Но, помните, преждевременная оптимизация — зло