​​Как V8 работает с числами. Small Integer теория

В JavaScript по спецификации все числа (number) — это 64-битные числа с плавающей запятой (IEEE-754 Double). Но внутри V8 используется множество стратегий, чтобы сделать работу с числами быстрее. Одна из таких — Smi (Small Integer).

Что такое Smi

Smi — это способ представления небольших целых чисел без выделения памяти в куче:

- Smi хранятся прямо в указателе
- Могут занимать 31 бит (на 32-битных системах) или 32 бита (на 64-битных системах)
- Диапазон значений для 64 битной системы: от -2^31 до 2^31 - 1.

Формат хранения для разных систем:

// для 32-битной системы
[31 bit signed int] 0
// для 64-битной системы
[32 bit signed int] [31 bit zero padding] 0

Smi всегда заканчивается нулевым битом (LSB = 0) — это так называемый тег-бит, отличающий Smi от указателей на другие объекты, у которых LSB = 1. Подробнее об этом в теме Tagged Pointer.

Заглянем в исходники V8

Формат Smi описан в исходниках:

- smi.h
- v8-internal.h

Первое на что можно обратить внимание, задание alias для типа Number.

using Number = Union<Smi, HeapNumber>;

Отмечу, что несколькими строками ниже, лежит всеми любимая путаница про "примитивные типы". Однако, как в исходном коде, так и в спецификации, упоминаются primitive value.

// A primitive JavaScript value, which excludes JS objects.
using JSPrimitive =
  Union<Smi, HeapNumber, BigInt, String, Symbol, Boolean, Null, Undefined>;

И можно найти константы для работы с тегом плюс маску для проверки:

// Tag information for Smi.
const int kSmiTag = 0; // значение тега для Smi (малых целых чисел)
const int kSmiTagSize = 1; // размер тега в битах (1 бит)
const intptr_t kSmiTagMask = (1 << kSmiTagSize) - 1; // маска для выделения тега из указателя (равна 1)

### Как определяется диапазон значений Smi

Границы Smi заданы так:

static const int kSmiMinValue =
  (static_cast<unsigned int>(-1)) << (kSmiValueSize — 1);
static const int kSmiMaxValue = -(kSmiMinValue + 1);

Как это соответствует -2³¹ и 2³¹-1? Разберёмся с этим по порядку.

Для получения значения kSmiValueSize нам снова необходимо обратиться к коду.

Мы видел, что класс Smi статичный

class Smi : public AllStatic

Это означает, что его нельзя создать через new и в классе будут только статичные методы.

Обратимся к определению struct SmiTagging. В коде их две для разных платформ и в них же записан enum с необходимыми константами. kSmiShiftSize - на сколько бит сдвигается значение и kSmiValueSize количество битов, выделенных под значением. В структуру же передается размер указателя в байтах 4 (32 бита) или 8 (64 бита).

struct SmiTagging<4> {
 enum { kSmiShiftSize = 0, kSmiValueSize = 31 };
 ...
}

struct SmiTagging<8> {
 enum { kSmiShiftSize = 31, kSmiValueSize = 32 };
 ...
}

И так мы получаем формулу для 64 битной системы:

(static_cast<unsigned int>(-1)) << (32 - 1)

Сначала выполняется cast значения -1 к беззнаковому виду и становится 0xFFFFFFFF (все 32 бита равны 1). Для понимания можно ознакомиться с представлением отрицательных целых чисел в беззнаковом виде (Two's complement).
После этого сдвигаем на 31 бит:

0xFFFFFFFF << 31
10000000 00000000 00000000 00000000
0x80000000 = 2147483648

Получаем значением int (знаковое), то минимальная граница smi чисел равна -2147483648. Убираем знак и добавляем 1 и получаем верхнюю границу 2147483647

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

Smi:

- не требуют аллокации памяти
- не создают объект HeapNumber
- позволяют JIT-компилятору делать простые арифметические операции без проверок

Это особенно важно внутри циклов или горячих участков кода. Рассмотрим это в практической части в новых постах.

---

#V8 #JavaScript #Smi #Performance #JSразбор

​​Self-host Obsidian Sync

Введение

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

Поделюсь небольшим туториалом по запуску self-hosted Obsidian Sync.

Почему именно self-host? Да, у Obsidian есть собственная система синхронизации, но она становится дорогой, если у вас несколько хранилищ. Самой простой альтернативой я пользовался iCloud-папкой, но когда в деле участвуют 5–6 устройств, обязательно где-то возникнет конфликт версий. К тому же синхронизация через iCloud — не самая надёжная и удобная.

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

- синхронизация через Git;
- собственный сервер для синхронизации (self-host).

Git отлично подходит для резервного копирования и контроля версий, но если хочется просто нажать одну кнопку или получить Live Sync — лучше использовать отдельный сервер. Лично я использую Git как резервную копию раз в несколько дней/недель. А ещё — приятно немного повозиться с настройкой, чтобы потом почувствовать удовлетворение от результата.

Обзор плагина для синхронизации

Сам плагин и инструкции к нему можно найти по ссылке.

Self-hosted LiveSync — это плагин для синхронизации, разработанный сообществом. Он работает на всех платформах, поддерживающих Obsidian, и может использовать такие серверные решения, как CouchDB.

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

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

Настройка

Первым делом определяемся, нужно ли нам собственное доменное имя. Если да — покупаем его или используем альтернативу, такую как Cloudflared Tunnel. Обратите внимание: если вы планируете синхронизацию с мобильными устройствами, наличие доменного имени и SSL-сертификата обязательно.

Следующее необходимое условие — наличие VPS. К сожалению, self-host без собственного сервера не обойтись. К счастью, можно найти недорогие или даже бесплатные варианты (например, гуглим «Cloud Evolution Free Tier»).

Итак, у нас есть домен, сервер и выделенный IP. Теперь самое время прописать A-записи в DNS: одну для @, одну для www и CNAME-запись для www со значением основного домена.

Теперь переходим к самому интересному.

Устанавливаем Docker и Docker Compose на сервере. Ссылка на официальный сайт.

Создаём на сервере все нужные файлы:

obsidian-sync/
│
├── docker-compose.yml
├── secrets/
│   ├── couchdb_user
│   └── couchdb_password
├── traefik/
│   ├── traefik.yml
│   └── acme.json
├── couchdb-data
└── couchdb-etc

Создание файлов и продолжение поста в комментариях
---

#obsidian #selfhost #livesync #docker #traefik #couchdb

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

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