​​Разбор mountState как точки входа в работу useState

Начнем с разбора “точки входа” в архитектуры Fiber и механики работы хуков.

Что делает mountState

При первом рендере компонента React вызывает mountState для инициализации хука. Немного упростим и уберем типизацию внутри исходной функции:

 js
function mountState(
  initialState
) {
  const hook = mountStateImpl(initialState);
  const queue = hook.queue;
  const dispatch = dispatchSetState.bind(
    null,
    currentlyRenderingFiber,
    queue,
  );
  queue.dispatch = dispatch;
  return [hook.memoizedState, dispatch];
}

Итак, функция mountState принимает исходное значение и возвращает массив из текущего состояния memoizedState (обратим внимание, что это просто название переменной, а не ее мемоизация в привычном понимании) и функции dispatch для его обновления.

Как создается хук

На первом шаге вызывается mountStateImpl, которая возвращает новый объект хука:

function mountStateImpl(initialState) {
  const hook = mountWorkInProgressHook();

  if (typeof initialState === 'function') {
    const initialStateInitializer = initialState;
    initialState = initialStateInitializer();
  }

  hook.memoizedState = initialState
  hook.baseState = initialState;

  const queue: UpdateQueue = {
    pending: null,
    lanes: NoLanes,
    dispatch: null,
    lastRenderedReducer: basicStateReducer,
    lastRenderedState: initialState,
  };

  hook.queue = queue;

  return hook;
}

Связанный список хуков

Хук создается в функции mountWorkInProgressHook:

function mountWorkInProgressHook() {
  const hook: Hook = {
    memoizedState: null,
    baseState: null,
    baseQueue: null,
    queue: null,
    next: null,
  };

  if (workInProgressHook === null) {
    currentlyRenderingFiber
      .memoizedState = hook
    workInProgressHook = hook;
  } else {
    workInProgressHook = hook
    workInProgressHook.next = hook;
  }
  return workInProgressHook;
}

Все хуки в компоненте организованы в связанный список.
Первый хук хранится в currentlyRenderingFiber.memoizedState, а каждый последующий хук доступен через свойство next предыдущего хука.

Хук хранит два значения: текущего сохраненного значения memoizedState и базового, из промежуточных вычислений, значения baseState.

Аналогично в хуке сохраняются две очереди. Основная очередь обновлений queue, которая содержит все новые обновления, добавленные с момента последнего рендера. Когда вы вызываете функцию-сеттер (например, setState), новое обновление добавляется в эту очередь. baseQueue - это очередь обновлений, которые были пропущены в предыдущем рендере из-за низкого приоритета. Эта очередь используется как отправная точка для следующего рендера.

Также объект хранит ссылку в next на следующий хук.

Вернемся к функции mountStateImpl, далее происходит проверка, является ли начальное значение функцией. Это и есть так называемая lazy initialization:

if (typeof initialState === 'function') {
  const initialStateInitializer = initialState;
  initialState = initialStateInitializer();
}

React сохраняет функцию в переменной initialStateInitializer, а затем вызывает её и присваивает результат переменной initialState. Таким образом, вместо самой функции в качестве начального состояния используется результат её выполнения.

После этого сохраняем исходное значение в memoizedState и baseState. Создаем новую запись в основной очереди и возвращаем hook. Обратим внимание, что React использует циклическую связанную очередь, но об этом в следующий раз.

Финальный шаг: создаем dispatch

В завершение работы mountState создается функция сеттер на основе функции dispatchSetState с использованием bind для привязки контекста из текущего узла fiber и очереди обновлений для этого узла.

const dispatch = dispatchSetState.bind(
  null,
  currentlyRenderingFiber,
  queue,
);

---

#React #Fiber #useState #mountState #Hooks #LazyInitialization #JavaScript #8bitJS

​​Разбор updateState как основного механизма обновления в useState

Вернемся к разбору принципов работы useState. Следующим шагом рассмотрим updateState. Каждый раз, когда компонент обновляет свое состояние через useState, React вызывает функцию updateState.

Исходный код updateState

Заглянем в исходный код:

function updateState<S>(
  initialState: (() => S) | S,
): [S, Dispatch<BasicStateAction<S>>] {
  return updateReducer(
    basicStateReducer,
    initialState
  );
}

Сама функция выглядит просто и является обёрткой над updateReducer. В неё мы передаем "базовый" reducer и исходные данные. В результате возвращается кортеж из текущего состояния и функции dispatch, она же setState.

basicStateReducer: поддержка двух вариантов обновления

Главный "секрет" работы setState скрывается в basicStateReducer, который позволяет устанавливать новое состояние как для простых значений, так и для функции.

function basicStateReducer<S>(state: S, action: BasicStateAction<S>): S {
  return 
    typeof action === 'function' 
      ? action(state)
      : action;
}

Таким образом, мы можем писать два варианта кода:

const [count, setCount] = 
  useState(0);
setCount(5);
setCount(prev => prev + 1);

При этом, если передать функцию, то она вызывается с текущим состоянием внутри action(state).

Функция updateReducer

Вернемся к основной функции updateReducer:

function updateReducer<S, I, A>(
  reducer: (S, A) => S,
  initialArg: I,
  init?: (I) => S,
): [S, Dispatch<A>] {
  const hook = 
    updateWorkInProgressHook();
  return updateReducerImpl(
    hook,
    currentHook,
    reducer
  );
}

Обратим внимание, что она служит точкой входа как для useState, так и для useReducer (к которому мы вернёмся позже, надеюсь скоро). Такое объединение позволяет обрабатывать очереди обновлений через единый слой API.

Итак, updateReducer принимает функцию reducer, начальные аргументы (передаются для совместимости интерфейса) и необязательную функцию инициализации; однако при вызове из updateState последний параметр не используется.

Функция выполняет два ключевых действия:

Создаёт копию «рабочего/чернового» хука (work‑in‑progress), позволяя React мутировать данные в фазе рендера, не затрагивая уже зафиксированные (мемоизированные) значения.

Передаёт данные на обработку в функцию updateReducerImpl, которая получает рабочий хук, текущий хук и reducer. Реализация updateReducerImpl вычисляет приоритет «полос движения» (lanes) и решает, можно ли отложить обновление компонента.

А дальше?

Но перед тем как изучать ключевые функции современной архитектуры React, предлагаю сделать небольшой шаг вглубь архитектурных паттернов React.

---

#React #Fiber #useState #updateState #Hooks #ConcurrentMode #8bitJS

​​Hoisting в JavaScript: миф о «поднятии» или реальная механика движка

Как часто на собеседованиях вам задавали классический вопрос: «Что такое hoisting?»

Не растерявшись, мы обычно отвечаем: «Это поднятие переменных и функций наверх их области видимости». Интервьюер одобрительно кивает, и мы идём дальше.

Но действительно ли движок переписывает код и «перемещает» объявления? На самом деле это лишь метафора, упрощающая объяснение, но не отражающая реальную механику. В этой статье разберём, что говорит об этом спецификация ECMAScript и как это реализовано во внутренностях V8.

Если открыть учебники и статьи, почти всегда можно встретить объяснение в стиле: «JavaScript поднимает объявление переменной или функции в начало области видимости». Пример из таких источников:

function foo() {
  console.log('1:', a)
  a = 42
  console.log('2:', a)
  var a
}

// 1: undefined
// 2: 42

Затем идёт иллюстрация «как будто движок переписал код» и добавил объявление в начало:

function scope() {
  var a // hoisting
  console.log('1:', a)
  a = 42
  console.log('2:', a)
}

TL;DR

Сегодня разберём:

- Hoisting — это не перенос строк кода, а ранняя регистрация привязок до исполнения.
- var создаётся в контексте и инициализируется undefined.
- let/const регистрируются, но попадают в TDZ (Temporal Dead Zone) до инициализации (ранний доступ → ReferenceError).
- Function Declarations поднимаются в виде готовых функций (их можно вызывать до места объявления).
- В V8 это реализовано через вызов Runtime::kDeclareGlobals и видно по инструкциям байткода (LdaTheHole, ThrowReferenceErrorIfHole).

---

Концептуальный разбор процессов

JS‑движок выполняет код в две стадии:

Creation Phase

Фаза создания Execution Context. Иногда её называют Memory Creation Phase или Compile Phase. Во время этой фазы:

- создаются Execution Context, Variable Environment и Lexical Environment;

- для var создаются mutable bindings и сразу инициализируются undefined;

- для let/const создаются bindings, но они остаются неинициализированными (значение the‑hole, TDZ);

- Function Declarations получают готовый объект функции.

Execution Phase

Фаза построчного выполнения кода.

Важно: термины фаз — это лишь распространённые формулировки. В спецификации описаны алгоритмы вроде FunctionDeclarationInstantiation и операции с Environment Records (CreateMutableBinding, InitializeBinding, CreateImmutableBinding и т.д.).

Примеры кода и байткод V8

Ниже рассмотрим, как это выглядит в байткоде.

Важно: в байткоде вы не всегда увидите явное LdaUndefined для var. Ignition при создании кадра (frame) заранее заполняет регистры и слоты значением undefined.

var

Пример:

function demoVar() {
  console.log(a) // [1]
  var a = 10     // [2]
  console.log(a) // [3]
}

Байткод функции (индексы слотов опущены для простоты):

[generated bytecode for function: demoVar]
@0  : LdaGlobal [0]
@3  : Star2
@4  : GetNamedProperty r2, [1]
@8  : Star1
@9  : CallProperty1 r1, r2, r0
@14 : LdaSmi [10]
@16 : Star0
@17 : LdaGlobal [0]
@20 : Star2
@21 : GetNamedProperty r2, [1]
@25 : Star1
@26 : CallProperty1 r1, r2, r0
@31 : LdaUndefined
@32 : Return

Constant pool:
  0: <String[7]: #console>
  1: <String[3]: #log>

Разбор:

@0 LdaGlobal [0] — загрузить из constant pool console.

@3 Star2 — сохранить в регистр r2.

@4 GetNamedProperty r2, [1] — получить свойство log. acc = console.log

@8 Star1 — сохранить функцию в r1.

@9 CallProperty1 r1, r2, r0 — вызвать console.log(a). В регистре r1 мы храним функцию console.log, а в r2 reciever console (аналог this для вызова). Так как регистр r0 (переменная a) ещё не инициализирован в теле, он равен undefined.

@14 LdaSmi [10] — загрузить число 10 в аккумулятор

@16 Star0 — сохранить в r0, инициализация a = 10.

@17…@26 — повторный вызов console.log(a), теперь r0 = 10.

@31 LdaUndefined — подготовка значения возврата по умолчанию.

@32 Return — возврат из функции.

To be continue...

---
#JavaScript #Hoisting #V8 #ExecutionContext #TDZ #TemporalDeadZone #Interview #8BitJS

​​Hoisting в JavaScript: let и function

В первой части мы разобрали, как работает hoisting у var: переменная получает undefined ещё на этапе создания контекста, и поэтому доступ к ней до присвоения не вызывает ошибку. Теперь давайте посмотрим, чем отличается поведение let.

let

function demoLet() {
  console.log(b) // [1]
  let b = 10     // [2]
  console.log(b) // [3]
}

Байткод функции (сокращённо, с пометками строк):

[generated bytecode for function: demoLet]
;; Инициализация переменной b
@0 : LdaTheHole
@1 : Star0

;; [1] console.log(b)
@2 : LdaGlobal [0]
@5 : Star2
@6 : GetNamedProperty r2, [1]
@10 : Star1
@11 : Ldar r0
@13 : ThrowReferenceErrorIfHole [2]
@15 : CallProperty1 r1, r2, r0

;; [2] let b = 10
@20 : LdaSmi [10]
@22 : Star0

;; [3] console.log(b)
@23 : LdaGlobal [0]
@26 : Star2
@27 : GetNamedProperty r2, [1]
@31 : Star1
@32 : CallProperty1 r1, r2, r0

;; Завершение функции
@37 : LdaUndefined
@38 : Return

Constant pool:
  0: <String[7]: #console>
  1: <String[3]: #log>
  2: <String[1]: #b>

Разбор:

- @0 LdaTheHole — слот b помечается как TheHole (TDZ).
- @1 Star0 — сохранить TheHole в r0.
- @2…@15 — первая попытка обращения к b, выбрасывается ReferenceError на шаге @13.
- @20 LdaSmi [10] — загрузить константу 10.
- @22 Star0 — присвоение r0 = 10 (инициализация b).
- @23…@32 — второй вызов console.log(b), теперь r0 = 10.
- @37 LdaUndefined — подготовка значения возврата.
- @38 Return — возврат из функции.

TDZ

Механизм Temporal Dead Zone (TDZ) реализован через несколько этапов:

- На первом этапе переменная получает специальное значение TheHole с помощью инструкции LdaTheHole. Это внутренний маркер движка V8, который обозначает «неинициализированное лексическое связывание (binding)». В отличие от undefined, это значение не доступно из JavaScript напрямую.

Любопытно, в байткоде инициализация let и var выражается загрузкой служебных констант (LdaTheHole и LdaUndefined) в аккумулятор и фактически должны иметь равную цену.

- При обращении к такой переменной движок выполняет ThrowReferenceErrorIfHole. Если в слоте всё ещё лежит TheHole, выбрасывается синхронный ReferenceError.
- После инициализации значение TheHole в слоте заменяется на реальное значение.

Таким образом, TDZ гарантирует, что доступ к let/const до инициализации невозможен, и это обеспечивается связкой LdaTheHole + ThrowReferenceErrorIfHole.

function

functionDecl(); [1]
function functionDecl() {
  console.log("functionDecl ran"); [2]
}

Байткод верхнего уровня:

@6  : CallRuntime [DeclareGlobals], r1-r2
@11 : LdaGlobal [1]
@14 : Star1
@15 : CallUndefinedReceiver0 r1

Constant pool (size = 2)
 0: <FixedArray[2]>
 1: <String[12]: #functionDecl>

Разбор:

- @6 CallRuntime [DeclareGlobals] — на глобальном уровне регистрируются все var и Function Declarations.
- @11 LdaGlobal [1] — загрузить функцию из глобального объекта.
- @14 Star1 — запись функции в регистр r1
- @15 CallUndefinedReceiver0 r1 — выполнить вызов без явного this.

Байткод для самой функции functionDecl:

[generated bytecode for function: functionDecl]
@0  : LdaGlobal [0]
@3  : Star1
@4  : GetNamedProperty r1, [1]
@8  : Star0
@9  : LdaConstant [2]
@11 : Star2
@12 : CallProperty1 r0, r1, r2
@17 : LdaUndefined
@18 : Return

Constant pool:
  0: <String[7]: #console>
  1: <String[3]: #log>
  2: <String[16]: #functionDecl ran>

Разбор:

- @0 LdaGlobal [0] — загрузить глобальный объект console.
- @3 Star1 — сохранить console в r1 (receiver).
- @4 GetNamedProperty r1 [1] — получить свойство log у console. acc = console.log.
- @8 Star0 — сохранить функцию console.log в r0 (callee).
- @9 LdaConstant [2] — загрузить строковую константу "functionDecl ran".
- @11 Star2 — сохранить аргумент в r2.
- @12 CallProperty1 r0, r1, r2 — вызвать console.log (callee = r0, receiver = r1, arg = r2).
- @17 LdaUndefined — подготовить значение возврата.
- @18 Return — возврат из функции functionDecl.

To Be Countinue.. в следующий раз подробнее посмотрим на реализацию TDZ в v8

---
#JavaScript #Hoisting #V8 #TDZ #TemporalDeadZone #Interview #8BitJS

​​Разностные массивы

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

Последние пару лет я старался начать утро с "разгона" на дейликах, но не тех, что вам ставят в календарь на 10 утра, а с задачами на LeetCode. Несколько раз даже попытался порешать контесты, но необходимость просыпаться в воскресенье в 5 утра, чтобы успеть к началу, быстро развеяли надежды на высокий рейтинг (да-да, еще есть biweekly, но сейчас не об этом).

Ладно, хватит лирики.

Вчера (пока писал -- уже позавчера позавчера) на daily попалась любопытная задача, которая использует префиксные суммы не для подсчета сумм на отрезках, а для применения большого числа операций за один проход.

Increment Submatrices by One

Дана матрица n × n, заполненная нулями, и список запросов формата [row1, col1, row2, col2]. Каждый такой запрос увеличивает на 1 значения во всех ячейках подматрицы от (row1, col1) до (row2, col2) включительно. Нужно вернуть итоговую матрицу после применения всех запросов.

Добавим визуальный пример

Начальная матрица 3x3 и запросы [0,0,1,1] и [1,1,2,2]

[0 0 0]
[0 0 0]
[0 0 0]

После первого запроса [0,0 → 1,1]:

[1 1 0]
[1 1 0]
[0 0 0]

После второго запроса [1,1 → 2,2]:

[1 1 0]
[1 2 1]
[0 1 1]

Решение в лоб (brute-force)

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

Код примерно такой:

for (const [row1, col1, row2, col2] of queries) {
  for (let row = row1; row <= row2; row++) {
    for (let col = col1; col <= col2; col++) {
      matrix[row][col] += 1;
    }
  }
}

Итого в худшем случае мы можем получить O(q * n * n)

Отложенная симуляция

Для упрощения вложенности нам не следует обновлять каждую позицию, вместо этого мы можем поставить операции для старта и финиша. Для примера рассмотрим не всю матрицу, а только первую строку.
У нас есть запрос, который должен увеличить на 1 колонки с индексом 0 и 1. Значит старт у нас в нулевом индексе, и в это колонку мы записываем +1. Теперь нам нужно найти финиш, т.е. установить в колонке обратную операцию, у нас это -1. Так как первый запрос изменял только нулевой и первый столбец, то финиш у нас на 2 столбце. Столбец с индексом 1 никак не изменяется.

Исходный массив

[0 0 0 0]

Применяем запрос на увеличение [0, 1] для упрощения только col1 и сol2.

[+1 0 -1 0]

Берем второй запрос на увеличение [1, 2]

// исходная строка
[+1 0 -1 0]
// изменения
[ . +1 0 -1]
// результат
[+1 +1 -1 -1]

А теперь один раз пробегаем префиксной суммой по результату и полностью восстанавливаем массив с учетом всех операций

// массив операций
[+1 +1 -1 -1]
// восстановленный массив
[1 2 1 0]

Теперь остается лишь применить это для всей матрицы проходя по каждой из ее строк.

Сложность решения будет:
1. обработка всех запросов. Худший случай O(query * row)
2. восстановление всей матрицы O(rol * col)

Итого получается O(q * r + r * c)

Почему это работает

Мы устанавливаем границу влияния со стартом и финишем, то при проходе префиксом значение проставляется всем элементам от старта до финиша.

Применени в реальных задачах

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

---
#JavaScript #LeetCode #PrefixSum #DifferenceArrays #Algorithm #8BitJS

​​Что пошло не так в React Server Components и чему из этого стоит научиться

Последние пару дней во всех фронтенд-пабликах пролетела новость: в React нашли критическую уязвимость с оценкой CVSS 10.0. Она позволяет получить удаленное выполнение кода на сервере. В списках пострадавших оказались все кто используют и/или поддерживают React Server Components (RSC).

Но мне захотелось разобраться с инженерной точки зрения, что же именно оказалось сломано внутри React и почему это вообще стало возможно. А главное, понять, чему мы можем научиться из этого кейса как разработчики, даже если не используем RSC.

Небольшое отступление.

В рамках PR с закрытием уязвимости было решено сделать рефакторинг. И справедливо было подмечено

With this combined commit, people now have to go through a >1500 line patch to try to understand the security relevant changes.

Что за уязвимость

CVE-2025-55182 - критическая уязвимость в React Server Components, которая позволяет, отправив специально сформированный запрос, добиться удаленного выполнения кода на сервере.

В коде было обнаружены три основные причины уязвимости:

1. Несимметричность в плане защиты между кодом клиентской и серверной реализацией
2. Небезопасная десериализация данных Flight-протокола на сервере
3. Незащищенное разрешение модулей и экспортов

Немного контекста

React Server Components

Основная идея состоит в том, что сервер может сам рендерить дерево компонентов, может делать запросы в БД и API. Клиент же получает поток (stream) данных о дереве, а не готовый HTML. React на стороне клиента постепенно собирает готовый результат из данных от сервера и клиентских компонентов.

Flight-протокол

Внутренний протокол React для передачи данных в RSC между клиентом и сервером. Простыми словами, сервер кодирует состояние дерева, ссылки на компоненты, промисы в поток байтов. Со стороны клиента поток читает декодер ReactFlightClient и восстанавливает исходные данные. Аналогично со стороны сервера есть декодер ReactFlightReplyServer, который обрабатывает обратные данные от пользователя.

Разберемся в коде

Рассмотрим на практике два ключевых участка, которые стали причиной уязвимости.

Prototype pollution в ReactFlightReplyServer

Внутри серверного декодера есть функция reviveModel в связке с getOutlineModel, которые рекурсивно обходят данные и "оживляет" их в обычные JS структуры.

Упростим:

function reviveModel(...) {
 ...
 if (typeof value === 'object' && value !== null) {
  ...
  for (const key in value) {
   // hasOwnProperty проверка для защиты от вызова унаследованных ключей
   if (hasOwnProperty.call(value, key)) {
    ...
    // добавили проверку на __proto__
    if (newValue !== undefined || key === '__proto__') {
            value[key] = newValue;
   }
  }
 }
}

requireModule и доверие к экспорту

В RSC есть функция requireModule(metadata) для бандлеров, которая по metadata.id находит модуль и по metadata.name выбирает нужный экспорт.

export function requireModule<T>(metadata: ClientReference<T>): T {
  const moduleExports = parcelRequire(metadata[ID]);
  return moduleExports[metadata[NAME]];
}

Сервер слишком доверяет экспортируемому модулю, поэтому могут сработать запросы вида:

{
 "id": "foo",
 "name": "__proto__"
}

Из-за чего можно было использовать имя экспорта, которого нет в модуле, но существующего в цепочке прототипов.

Для закрытия уязвимости для экспорта добавили проверку

if (hasOwnProperty.call(moduleExports, metadata[NAME])) {
    return moduleExports[metadata[NAME]];
}

Итого

Как мы смогли увидеть, в уязвимости нет каких-то хитростей React, а используется довольно распространенная проблема доверия к данных при десериализации.

Что важного мы можем вынести для себя:

Никогда не доверяйте структуре данных от пользователя. Для защиты фильтруем все опасные ключи из прототипирования (__proto__, constructor, prototype) и/или добавляем подход allowlist для ключей. Для конструкции for...in используем hasOwnProperty.

#8BitJS #React #CVE #security #RSC

​​Ускоряем O(N + T), не меняя Big O. Часть 1. Разностный массив — это только начало

На прошлой неделе просочился черновик, самые внимательные успели увидеть «исходники» не в 8-битном формате. Теперь же пора восстановиться по-настоящему.

Сегодня тема особенно интересная. Многие видели, слышали, а может, и участвовали в CodeRun Summer от нашей любимой алгоритмической компании. Но в этот раз цель не просто решить задачу, а сделать это максимально эффективно.

И что может быть эффективнее, чем JavaScript?

Начнем нашу историю с первой задачи (спойлер: решений не будет, пока идет соревнование). Итак, прокат велосипедов. Классическая задача на планирование ресурсов или же интервальная задача.

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

Решение в лоб

Можно для каждой заявки пройти по всему интервалу и прибавить s:

for (const [a, f, s] of rentals) {
  for (let time = a; time < f; time++) {
    bikes[time] += s;
  }
}

В худшем случае почти каждая заявка занимает всю временную шкалу.

Ограничения ясно показывают, почему решение в лоб не подойдет: N и T могут достигать 10 миллионов.

Получаем сложность O(N × T) и надежный способ познакомиться с Time Limit.

Вспоминаем разностный массив

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

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

После обработки всех заявок один раз пройдем по массиву и восстановим значения префиксной суммой:

let current = 0;
let answer = 0;

for (let time = 0; time < T; time++) {
  current += diff[time];

  if (current > answer) {
    answer = current;
  }
}

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

Этот паттерн я уже подробнее разбирал в статье Разностные массивы. Там же есть визуальный пример такой отложенной симуляции.

Сложность нового решения складывается из обработки N заявок — O(N) и восстановления временной шкалы — O(T).

Итого — O(N + T).

Теперь же нажимает Submit и идет пить кофе, получаем базовое решение 1.589 секунды.

В следующей части начнем с простого вопроса: зачем хранить числа в восьми байтах, если почти все они помещаются в четыре?

И почему попытка сэкономить память внезапно превращает положительные числа в отрицательные.

#JavaScript #NodeJS #Algorithms #DifferenceArray #Performance #CodeRun #8BitJS

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

​​Ускоряем O(N + T), не меняя Big O. Часть 3. Как оставить четыре байта и не сломать ответ

Во второй части мы попытались заменить Float64Array на более компактный Int32Array и уменьшили размер разностного массива с 80 до 40 МБ.

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

Теперь перед нами стоит задача оставить экономию по памяти, но реализовать безопасное решение.

Разделяем число на две части

Полный диапазон 32-битного знакового целого у нас равен:

const INT_MIN = -2147483648;
const INT_MAX = 2147483647;
const INT_RANGE = 4294967296; // 2 ** 32

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

При обновлении сначала вычисляем новое значение как обычный JavaScript Number:

const next = diff[index] + delta;

Пока результат находится внутри диапазона Int32, ничего дополнительного не требуется:

if (next >= INT_MIN && next <= INT_MAX) {
  diff[index] = next;
}

Если значение вышло за границу, определяем количество переходов через полный 32-битный диапазон:

const carry = Math.floor(
  (next - INT_MIN) / INT_RANGE
);

diff[index] = next - carry * INT_RANGE;
correctionCounts[index] += carry;

В основной ячейке всегда остается значение, которое помещается в Int32.

Например, число 2 147 483 648 (выходи за границу на 1) представляется так:

-2147483648 + 1 × 4294967296

Во время финального прохода исходное значение восстанавливается:

-2147483648 + 4294967296 = 2147483648

Основной массив занимает четыре байта на элемент, но итоговые вычисления выполняются как JavaScript Number и сохраняют большие значения.

Ленивое выделение памяти

Можно было бы сразу создать два массива, но при T = 10 000 000 это снова около 80 МБ.

Так как на большинстве входных данных переполнения отдельных ячеек вообще не происходит. Мы можем создать correctionCounts только после первого реального переполнения.

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

Итог

Удалось сохранить компактный Int32Array, не потеряв корректность вычислений. Разделили значения на базову часть и перенос. Обработали переполнение и восстановление отдельно.

Алгоритм остался прежним O(N + T), но память используется эффективнее.

Что дальше

Несмотря на улучшения, остается проблема с записью событий в большой массив по почти случайным адресам, что плохо влияет на производительность.

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

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

​​Итоги 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

​​Ускоряем O(N + T), не меняя Big O. Часть 5. Зачем здесь WebAssembly

После реализации бакетов с показателем benchmark 0,922 секунды, остается два варианта:

1. продолжать бороться с огромным JavaScript файлом;
2. перенести самый горячий участок в WebAssembly.

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

Сразу обращаем внимание, что WebAssembly — не кнопка «сделать быстро/хорошо». Если просто переписать медленный алгоритм на C и собрать его в Wasm, плохая асимптотика и неудачный доступ к памяти никуда не исчезнут.

В нашем случае основная работа по структуре данных и алгоритму уже сделана, а WebAssembly понадобится поверх.

Что осталось в JavaScript

JavaScript превратился в небольшой wrapper:

const fs = require('fs');

const memory = new WebAssembly.Memory({
  initial: 6000,
  maximum: 6000,
});

const module = new WebAssembly.Module(binary);
const instance = new WebAssembly.Instance(module, {
  env: { memory },
});

const { solve } = instance.exports;

На стороне JS осталось создать память, загрузить Wasm-модуль, прочитать stdin и вывести результат. Парсер, построение бакетов и поиск максимума выполняются уже внутри WebAssembly.

Почему типы имеют значение

В JavaScript одна переменная может в разное время содержать значения разных типов. V8 хорошо оптимизирует стабильный код, но для этого сначала должен собрать информацию о его поведении, построить предположения и предусмотреть откат на более общий путь. В WebAssembly тип каждой операции указан заранее, благодяря этому компилятор заранее знает форму данных и операций.

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

Ручная раскладка памяти

Вместо отдельных аллокаций Wasm-версия заранее вычисляет адрес каждой структуры. Для упакованных событий используется uint32, для текущей суммы и ответа int64.

Упрощённо это можно представить так:

uint32_t *pool = arena;
uint32_t *next = pool + pool_length;
uint32_t *head = next + chunk_count;
uint32_t *tail = head + bucket_count;
int64_t *local = align8(tail + bucket_count);

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

Почему ответ возвращается как BigInt

Экспортируемая функция возвращает int64. В JavaScript такое значение представляется как BigInt:

const answer = solve(offset, length);
process.stdout.write(answer.toString());

Максимальный ответ может выходить за диапазон int32, а внутри Wasm текущая сумма остаётся настоящим 64-битным целым числом.

Преобразование в строку выполняется только один раз перед выводом результата.

Первый результат

Версия, которая читала весь вход непосредственно в WebAssembly.Memory, достигла примерно 0,710 секунды. По сравнению с предыдущими 0,922 секунды это уже заметный выигрыш.

Однако у решения появился существенный недостаток, связанный с увеличенным потреблением памяти. Под вход заранее резервировалось около 270 МБ, а вся линейная память состояла из 6000 страниц WebAssembly (разберем страницы и почему они равны 64 КиБ подробнее в следующей статье. Сейчас можно вернуться к коду JS выше и увидеть выделение памяти initial: 6000):

6000 × 64 КиБ ≈ 375 МиБ

Мы ускорили вычисления, но по-прежнему держали весь stdin в памяти.

---

#JavaScript #WebAssembly #WASM #MemoryLayout #Parser #Performance #CodeRun #8BitJS