Иммутабельные структуры данных и оптимизация итераторов в JavaScript

Иммутабельные структуры данных и оптимизация итераторов в JavaScript

Разработка высоконагруженных серверных приложений на Node.js и в экосистеме браузерного JavaScript часто требует выхода за рамки встроенных массивов (Array) и базовых объектов (Object). Когда алгоритм работает с частыми операциями добавления и удаления элементов в начале или конце структур, стандартный динамический массив вызовет массовые сдвиги элементов и постоянные переалокации памяти.

Функциональные языки программирования (Lisp, Scheme) десятилетиями используют концепцию ConsList — неизменяемого (немутабельного) односвязного списка, состоящего из ячеек cons, где каждая ячейка содержит значение (value) и ссылку на следующий узел (next). Однако неадаптированный перенос этой модели в JavaScript сталкивается с характерными особенностями выполнения движка V8: накладными расходами на вызовы встроенных защитных методов и механизмом итерации через генераторы.

В этом материале разберем, как построить высокопроизводительный ConsList в JavaScript, почему отказ от Object.freeze в пользу приватных полей классов дает кратный прирост скорости, как движок V8 оптимизирует малые целые числа (Small Integers, Smi) и почему замена генераторов function* на прямые итераторы принципиальна для системного кода.

Концепция ConsList и замена Object.freeze

В учебных материалах по функциональному программированию наивная реализация ячейки ConsList в JavaScript обычно выглядит как замороженный объект:

// Наивная концептуальная реализация
function cons(value, next) {
  return Object.freeze({ value, next });
}

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

Однако вызов Object.freeze() — чрезвычайно медленная операция в V8. Движок отключает скрытые классы (Shape / Transition Chain) для замороженного объекта и переводит его в медленный режим словаря (Dictionary Mode).

Чтобы сохранить иммутабельность для внешнего кода и одновременно обеспечить максимальную скорость на уровне V8, наивный замороженный объект заменяется классом с приватными полями и только геттерами для чтения:

class Cons {
  #value;
  #next;
  #size;

  constructor(value, next = null) {
    this.#value = value;
    this.#next = next;
    this.#size = next === null ? 1 : next.#size + 1;
  }

  get value() {
    return this.#value;
  }

  get next() {
    return this.#next;
  }

  get size() {
    return this.#size;
  }
}

function cons(value, next) {
  return new Cons(value, next);
}

Такой подход сохраняет скрытый класс V8 единым для всех создаваемых ячеек, позволяя JIT-компилятору (TurboFan) генерировать инлайн-кеши (Inline Caches) для обращений к порядочным геттерам .value и .next. В бенчмарках создание ячеек через класс с приватными полями работает до 10 раз быстрее, чем вызов Object.freeze().

Механизм Small Integers (Smi) и оптимизация памяти в V8

Обратите внимание на поле #size в приведенной выше реализации Cons. В обычном коде добавочное числовое поле в каждом узле казалось бы лишним расходом памяти. Однако специфика управления памятью в движке V8 меняет эту оценку.

В V8 все значения представляются 64-битными указателями (Tagged Pointers). Чтобы не выделять память в куче (Heap Allocation) под каждое небольшое число, V8 использует оптимизацию Small Integers (Smi):

• Целые числа в диапазоне от -2^31 до 2^31 - 1 (для 32-битных Smi) или в пределах диапазонов предвыделенных таблиц (например, частые значения от 0 до 2048) хранятся прямо внутри самого указателя с младшим битом-тэгом 0.
• Для небольших положительных чисел V8 держит заранее закешированный диапазон значение-ссылок в памяти.

// Значение size для некрупных списков не выделяет память под объект Number.
// В байт-коде V8 размер представлен как direct 32-bit Smi pointer.
const list = cons("data", cons("head", null));
console.log(list.size); // 2 -> вычитывается прямо из Smi-регистра V8

Поскольку длины локальных иммутабельных списков обычно не превышают тысяч элементов, значение #size представляется как 32-битный Smi-указатель. В результате при вызове меток size V8 не производит выделения памяти под обертку Number, а при частой работе функции размещает эти значения непосредственно в регистрах процессора.

Реструктуризация итераторов: отказ от генераторов

Стандартный способ сделать структуру данных обходимой в цикле for...of — реализовать метод [Symbol.iterator]() через синтаксис функций-генераторов (function* и оператор yield):

// Медленный способ через генератор:
class ConsList {
  *[Symbol.iterator]() {
    let current = this;
    while (current !== null) {
      yield current.value;
      current = current.next;
    }
  }
}

В доменном коде приложения использование yield оправдано читаемостью. Однако в базовых платформах и библиотеках структур данных функции-генераторы создают заметный оверхед:

1. Вызов функции-генератора создает объект-состояние (Generator Object) и стек выполнения в куче.
2. Каждая итерация с yield требует переключения контекста генератора и возврата объекта вида { value, done }.

Для оптимизации прохода по ConsList и линейным структурам (Queue, Stack, Deque) метод [Symbol.iterator]() переписывается на явное создание объекта-итератора с ручным методом next():

class ConsIterator {
  #current;

  constructor(startNode) {
    this.#current = startNode;
  }

  next() {
    if (this.#current === null) {
      return { value: undefined, done: true };
    }
    const value = this.#current.value;
    this.#current = this.#current.next;
    return { value, done: false };
  }

  [Symbol.iterator]() {
    return this;
  }
}

class Cons {
  // ... свойства #value и #next ...

  [Symbol.iterator]() {
    return new ConsIterator(this);
  }
}

Преимущества прямого итератора:

• Отсутствие затрат на создание и остановку контекста генератора.
• Объявление [Symbol.iterator]() внутри самого класса итератора (возвращающего this) позволяет передавать один и тот же итератор в операции распаковки ([...iterator]) без лишних оберток.
• На тестах прохода большого количества узлов замена yield на прямой метод next() дает ускорение итерации на 10–20%.

Практическое применение: построение Queue, Stack и Deque

На базе ячейки Cons легко строятся более сложные линейные структуры данных без дублирования кода:

1. Stack (Стек): идеальное совпадение с ConsList. Операция push создает узел cons(newValue, currentHead), а pop возвращает парами [head.value, head.next].
2. Queue (Очередь): реализуется поверх двух ссылок на Cons-узлы (head и tail) с O(1) добавлением и удалением.
3. Deque (Двусторонняя очередь): объединяет прямые и обратные Cons-цепочки, позволяя добавлять и удалять элементы с обоих концов с сохранением структурного переиспользования памяти.

// Пример создания списка через вспомогательную фабрику
function list(...items) {
  let result = null;
  for (let i = items.length - 1; i >= 0; i--) {
    result = cons(items[i], result);
  }
  return result;
}

const numbers = list(1, 2, 3, 4, 5);
for (const num of numbers) {
  console.log(num); // 1, 2, 3, 4, 5
}

Главные выводы для разработчика

• Избегайте Object.freeze() при массовом создании объектов в горячих циклах — используйте классы ES6 с приватными полями (#field) и геттерами.
• Помните о механизме Smi (Small Integers) в V8: целые числа небольшого размера не вызывают алокаций в куче и работают со скоростью нативных указателей.
• В критичном к производительности платформенном коде заменяйте функции-генераторы yield на кастомные итераторы с методом next(). Это экономит до 20% ресурсов CPU при обходе структур данных.