​​HeapNumber в V8. Как хранятся числа вне Smi. Теория часть 1

Продолжим рассматривать способы хранения чисел во время выполнения кода внутри V8. Когда движок сталкивается с числом, выходящим за пределы диапазона Smi, он создаёт HeapNumber — полноценный объект в куче.

Что такое HeapNumber

HeapNumber — это 64-битное число с плавающей точкой, завёрнутое («упакованное») в объект на куче. Такое представление часто называют boxed double, поскольку значение double не может храниться напрямую в регистрах или указателях и оборачивается (boxing) в отдельную структуру с типовой информацией (Map) и полем для самого значения.

Когда возникает HeapNumber

Любые JavaScript Number, выходящие за пределы Smi-диапазона: содержащие дробную часть, ±Infinity, NaN, −0, а также любые результаты арифметических операций, приводящие к потере точности, переполнению или переходу в формат double (например, деление двух целых чисел с нецелым результатом).

Внутреннее устройство HeapNumber

Обратимся к исходникам:
- src/objects/heap-number.h
- src/objects/primitive-heap-object.h

Сам класс HeapNumber наследуется от PrimitiveHeapObject. Чтобы отделить «примитивы-объекты» (числа, BigInt, WasmNumber, String, но не Smi) от обычных JavaScript-объектов (таких как JSArray, JSFunction и т.д.), в V8 ввели промежуточный абстрактный класс PrimitiveHeapObject.

Он не содержит собственных полей или методов — его задача типизации. Это маркер, который позволяет компилятору и внутренним шаблонам V8 статически проверять, что конкретный класс представляет примитивное значение, не содержит тегированных ссылок (tagged pointers).

В V8 64-битное значение внутри double обрабатывается как два 32-битных слова. Это позволяет повысить эффективность операций, особенно на архитектурах с ограниченной поддержкой 64-битных инструкций или в оптимизированных путях компиляции.

| high word | low word |
|(32 бита) |(32 бита) |
| ----------------- | ---------------|
| S (1 бит) | M-high (20 бит)|
| E (11 бит) | |
| M-low (32 бита) | |

Обозначения:
- S — знаковый бит (1 = отрицательное значение)
- E — экспонента (11 бит)
- M — мантисса (52 бита в сумме)

Это деление соответствует стандарту IEEE-754 и отражает, как double хранится в памяти. Такое представление упрощает доступ к частям числа для анализа, компиляции и оптимизаций.

Помним и про порядок байт (endianness). Чаще используется Little-endian (x86-64, ARM64): нижнее слово хранится по меньшему адресу. Но есть и Big-endian

Внутреннее устройство констант

Для работы с HeapNumber V8 определяет несколько констант и масок:

Маска для извлечения знакового бита из старшего 32-битного слова. Если бит установлен, число отрицательное:

static const uint32_t kSignMask = 0x80000000u;  
// 10000000 00000000 00000000 00000000

Маска для извлечения всех 11 бит экспоненты из старшего слова:

static const uint32_t kExponentMask = 0x7ff00000u;
// 01111111 11110000 00000000 00000000

Маска для извлечения верхних 20 бит мантиссы из старшего слова (остальные 32 бита мантиссы находятся в младшем слове):

static const uint32_t kMantissaMask = 0xfffffu;
// 00000000 00001111 11111111 11111111

К интересному можно отнести проверку на Infinity и NaN

static const int kInfinityOrNanExponent =          
    (kExponentMask >> kExponentShift) - kExponentBias;

Проверка на Infinity и NaN важна, потому что эти значения имеют одинаковую структуру на уровне IEEE-754: у них устанавливаются все биты экспоненты (11 битов равны 1), но различаются значения мантиссы:
- Если экспонента максимальна, а мантисса = 0, то это ±Infinity.
- Если экспонента максимальна, а мантисса ≠ 0 — это NaN.

---

#V8 #JavaScript #HeapNumber #IEEE754 #JSразбор

​​🧵 Как работает useState внутри React?

Каждый раз когда мы пишем код:

const [count, setCount] = useState(0)

Под капотом React запускается целый механизм отслеживания состояния, основанная на структуре Fiber и связанном списке хуков. Эта архитектура позволяет React помнить значения между рендерами и обновлять только нужные части интерфейса.

Но для начала давайте посмотрим на основую реализацию хука в файле ReactHooks.js 

 javascript
export function useState<S>(
  initialState: (() => S) | S,
): [S, Dispatch<BasicStateAction<S>>] {
  const dispatcher = resolveDispatcher();
  return dispatcher.useState(initialState);
}

Это публичное API хука useState. На входе — начальное значение initialState, которое может быть значением или функцией.

Через resolveDispatcher() получаем текущий диспетчер (ReactCurrentDispatcher.current) — объект, содержащий реализацию хуков для текущей фазы работы React.

Диспетчер — объект, который содержит реализацию всех хуков для текущей фазы работы компонента (mount/update/rerender).

React использует разные диспетчеры в зависимости от контекста:

- При первом рендере — mountState
- При обновлении — updateState
- При повторном рендере — rerenderState

Пока опустим реализацию каждого, но важно: создаётся новый hook, который попадает в связанный список хуков, хранящийся в поле memoizedState текущей fiber node.

👉 Почему порядок хуков важен? 
React полагается на порядок вызова хуков, чтобы правильно связать текущий hook с соответствующим fiber. Именно поэтому нельзя вызывать хуки внутри условий или циклов.

На этапе монтирования useState создаёт редьюсер basicStateReducer:

ReactFiberHooks.js

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

Базовый редьюсер показывает, как обрабатываются обновления состояния:

- Если мы передаете функцию setState(prev => prev + 1) она вызывается с предыдущим состоянием

- Если вы передаете значение setState(42) оно становится новым состоянием

Вводный итог

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

1. Ленивая инициализация — функция инициализации вызывается только один раз, при первом рендере.
2. Пакетная обработка — несколько вызовов setState могут быть объединены в одно обновление.
3. Изолированность — каждый вызов useState создаёт отдельный hook, независимо от других.
4. Стабильная функция обновления — setState сохраняет идентичность между рендерами.

useState — это удобный интерфейс, построенный на связке: Fiber + очередь хуков + диспетчер. В следующих постах мы разберём реализацию setState и напишем простую версию useState для лучшего понимания.

---

#React #Hooks #useState #Fiber #Frontend #JavaScript #8bitJS

​​Как работает useState. Упрощенная реализация

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

Для начала нам нужны глобальные переменные:

let currentlyRenderingComponent = null;
let currentHookIndex = 0;
const componentHooks = new Map();
let pendingUpdates = [];

currentlyRenderingComponent указывает на компонент, который сейчас рендерится.
currentHookIndex отслеживает порядок хуков внутри компонента.
componentHooks связывает компоненты с их хуками.
pendingUpdates имитирует очередь на обновление.

Теперь создадим необходимые структуры данных:

class Hook {
  constructor(initialState) {
    this.memoizedState = initialState;
    this.baseState = initialState;
    this.queue = [];
  }
}

class Update {
  constructor(action) {
    this.action = action;
    this.next = null;
  }
}

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

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

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

function getOrCreateHook(index) {
  let hooks = componentHooks
    .get(currentlyRenderingComponent);
  
  if (!hooks) {
    hooks = [];
    componentHooks
      .set(currentlyRenderingComponent, hooks);
  }
  
  if (index >= hooks.length) {
    hooks.push(new Hook());
  }

  return hooks[index];
}

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

function dispatchAction(component, hook, action) {
  const update = new Update(action);
  hook.queue.push(update);
  
  if (!pendingUpdates.includes(component)) {
    pendingUpdates.push(component);
  }
  
  scheduleUpdate();
}

Функция dispatchAction имитирует поведение setState: она создает объект обновления, добавляет его в очередь соответствующего хука и инициирует обновление компонента.
В упрощенном понимании scheduleUpdate имитирует постановку задач на выполнение через отложенный render с setTimeout.

Реализация useState:

function useState(initialState) {
  const hook = getOrCreateHook(currentHookIndex++);

  if (hook.queue.length) {
    let next = hook.baseState;
    for (const item of hook.queue)
      next = typeof item.action === "function" 
     ? item.action(next)
  : item.action;
    hook.queue.length = 0;
    hook.memoizedState = next;
    hook.baseState = next;
  } else if (hook.memoizedState === undefined) {
    const value =
      typeof initialState === "function"
     ? initialState()
     : initialState;
    hook.memoizedState = value;
    hook.baseState = value;
  }

  const owner = currentlyRenderingComponent;
  const dispatch = (action) => dispatchAction(owner, hook, action);

  return [hook.memoizedState, dispatch];
}

Сначала получаем хук по текущему индексу — если такого еще нет, он создается. 
Проверяем очередь хуков, если в ней накопились обновления, они применяются одно за другим: если обновление — это функция, то она вызывается с текущим значением, иначе используется переданное значение напрямую. После обработки обновлений очередь очищается, и новое значение сохраняется как актуальное состояние. 

Если это первый вызов useState и хук еще не был инициализирован, то начальное состояние устанавливается из initialState — это может быть как значение, так и функция (ленивая инициализация). 

Затем создается функция dispatch, связанная с текущим компонентом и конкретным хуком, чтобы при вызове setState обновлялось только нужное состояние. В конце возвращается пара, аналогичная настоящему useState: текущее значение состояния и функция для его обновления.

---
#React #Hooks #useState #Fiber #Frontend #JavaScript #8bitJS

​​Разбор 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

​​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

​​Ускоряем 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. Часть 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