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

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