​​Ускоряем 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

​​Итоги CodeRun Summer: 15 задач и 636 попыток решения

Финал CodeRun Summer Challenge выглядит аккуратно: 15 задач из 15 и третье место среди JavaScript-решений.

Но за рейтингом остались 636 отправок, 443 WebAssembly-модуля и 548 тысяч строк тестов и бенчмарков. Финальные 15 файлов заняли всего 1 142 строки. На одну строку решения пришлось около 480 строк экспериментов.

Сложнее всего сказать когда соревнование алгоритмов переросло в соревнование моделей и микрооптимизаций.

Немного сухой статистики

- 15 решенных задач, итоговое 3 место
- 1 задача с лучшим результатом, 39 мс
- Репозиторий весом 1,35 ГБ и 4 708 файлов.
- 199 052 строк на C
- 1210 сессий с агентами
- 8 852 044 861 чистых токенов без форка для сабагентов

Главное открытие: Accepted — не конец работы.

Интересные факты

Самая большая задач имеет 507 кандидатов и 232 092 строк исходников, а самая маленькая 16 файлов и 1 821 строку.

Для одной из задач пришлось создать 394 МБ тестовых данных.

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

Мои главные уроки

В начале я воспринимал задачу буквально: выбрал JS — значит решай на Pure JS. Но смена парсера, структур данных и алгоритмов не давали впечатляющих результатов. Опыт полезный, но слишком много попыток потрачено на такой принцип, а они были ограничены. Нельзя было пользоваться отправкой как способом подбора идей.

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

Изначально выстраивать идеальный сценарий с агентом, который начинает не с кода, а с условия: фиксирует контракт задачи, ограничивает рантайм. Затем строит оракул, тесты и воспроизводимый бенчмарк на точной версии Node.js. Каждая идея проверяется в отдельном кандидате, и до браузера доходит только вариант, который сохраняет корректность и стабильно выигрывает на нескольких профилях. После отправки агент сверяет результат с тем исходником, который действительно ушёл в судью. Так CodeRun становится финальной проверкой измеренного улучшения, а не дорогим генератором случайных чисел.

Wasm не оказался волшебной палочкой. Часто выигрыш съедала компиляция, иногда обмен с памятью.

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

Однажды Monaco склеил старый код с хвостом нового. Так выяснилось, что сверка исходника перед отправкой — тоже часть алгоритма.

В итоге сработал не один трюк, а смена процесса: замороженный контроль, проверка корректности, разные профили, одна гипотеза за эксперимент и отправка только при измеримом запасе.

---

#CodeRun #Challenge #JavaScript #Benchmark #8bitJS