​​Ускоряем O(N + T), не меняя Big O. Часть 4. Кэш, бакеты и упаковка событий

В предыдущей части мы сохранили компактный Int32Array и отдельно обработали редкие переполнения. Пришло время заняться оптимизацией времени выполнения.

Для каждой заявки мы имеем две операции:

diff[a] += s;
diff[f] -= s;

Всего две записи, как это ускорять и зачем?

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

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

diff[8]
diff[9_174_221]
diff[31]
diff[4_800_010]

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

Это ключевой нюанс, который не отражается в Big O и из-за асимптотики выглядит как привычное O(N).

Разбиваем шкалу на бакеты

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

const COORD_SHIFT = 11;
const COORD_SIZE = 1 << COORD_SHIFT; // 2048
const COORD_MASK = 2047;

Номер бакета вычисляется как point >>> 11, позиция внутри — как point & 2047.

Сначала мы только раскладываем события по бакетам. Затем каждый бакет обрабатывается по очереди: очищаем локальный массив, применяем события и проходим его префиксной суммой.

Локальный Float64Array на 2048 элементов занимает 2048 × 8 = 16384 байта и лучше помещается в кэш.

Одно число вместо объекта события

Миллионы объектов { point, delta }, которые мы создавали на этапе формирования списка событий для каждой заявки, означают аллокации, ссылки и работу сборщика мусора.

Координату внутри бакета и изменение можно объединить в один Int32:

const packed =
  (delta << COORD_SHIFT) |
  (point & COORD_MASK);

Распаковка:

const localPoint = packed & COORD_MASK;
const delta = packed >> COORD_SHIFT;

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

Почему delta помещается

Схема корректна благодаря ограничениям задачи. Максимальное s равно 1 000 000, а сдвиг влево на 11 бит эквивалентен умножению на 2^11 = 2048:

1 000 000 × 2048 = 2 048 000 000

Это меньше максимального значения Int32. Если сделать s больше, часть числа просто «обрежется» и потеряется. Поэтому такой способ упаковки безопасен только если заранее проверить, что значения не выходят за допустимые пределы.

Чанки вместо множества массивов

Количество событий в бакете заранее неизвестно. Если делать отдельный JavaScript-массив на каждый бакет, будет много аллокаций и лишняя нагрузка на сборщик мусора.

Поэтому используется один общий Int32Array и чанки фиксированного размера. Это похоже на ручной allocator:

- eventPool большой общий массив, в котором подряд лежат все события, разбитые на чанки фиксированного размера;
- eventNext хранит ссылки между чанками;
- eventHead и eventTail для каждого бакета указывают на первый и последний чанк в списке;
- eventUsed показывает, сколько элементов занято в чанке, чтобы понимать, когда нужно выделить новый.

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

Размер чанка выбран равным 512. На тот момент это был лучший компромисс между количеством связей и пустотами в конце чанков.

Результат

Итого всё те же O(N + T), но с более последовательным доступом к памяти.
Время уменьшилось с 1,589 до 0,922 секунды.

#JavaScript #CPUCache #DataOrientedDesign #BitPacking #TypedArray #Performance #CodeRun #8BitJS