​​Ускоряем O(N + T), не меняя Big O. Часть 2. Четыре байта, которые могут изменить результат

В первой части мы получили решение через разностный массив со сложностью O(N + T) и результатом 1,589 секунды.

Big O отвечает на вопрос, как растет количество работы. Но внутри алгоритма куда более важную часть играют размер одной записи в памяти, количество временных объектов, случайные обращения к большому массиву, стоимость разбора входных данных.

Теперь посмотрим не на количество операций, а на то, что именно лежит в памяти.

В JavaScript все обычные числа имеют тип Number. По спецификации это 64-битные числа с плавающей точкой IEEE 754.

Внутри V8 их представление может меняться: небольшие целые числа могут храниться как Smi, а остальные — как HeapNumber. Об этом подробнее писал ранее: Как V8 работает с числами. Small Integer теория и HeapNumber в V8. Как хранятся числа вне Smi. Теория часть 1

Но у TypedArray правила проще:

- Int32Array хранит ровно 32-битные знаковые целые;
- Float64Array хранит 64-битные числа с плавающей точкой.

При T = 10 000 000 только сам разностный массив занимает примерно:

Int32Array 4 байта на одну запись и для всего массива около 40 МБ
Float64Array8 байт на одну запись и для всего массива около 80 МБ

В два раза меньше памяти означает, что через иерархию кэшей процессора приходится протаскивать меньше данных.

Выбор очевиден, но есть небольшое «но».

Переполнение

По условию одна заявка содержит не больше 1 000 000 велосипедов. Такое значение спокойно помещается в Int32.

Но в одной точке разностного массива могут встретиться миллионы одинаковых событий:

diff[a] += s;

Отдельное значение s помещается в 32 бита, а их сумма — уже нет.

Int32Array не бросает ошибку и не превращает значение в обычный Number. При записи он просто оставляет младшие 32 бита:

const values = new Int32Array(1);

values[0] = 2_147_483_647;
values[0] += 1;

console.log(values[0]);
// -2147483648

Мы прибавили единицу к положительному числу и получили отрицательное — произошло переполнение.

Для JavaScript Number это все еще безопасное целое значение, но для одной ячейки Int32Array — уже нет.

Подведем итог

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

Мы уменьшили размер массива в два раза, но столкнулись с проблемой переполнения. И это отличный пример того, как низкоуровневые детали могут незаметно повлиять на корректность результата.

Любые оптимизации всегда требуют баланса между скоростью и памятью.

—-

#JavaScript #V8 #TypedArray #Int32Array #Overflow #Performance #CodeRun #8BitJS