Швидке клонування об'єктів JavaScript

cloneКлонування об'єктів JavaScript досить часта операція. На жаль, JS не надає швидких нативних методів для вирішення цього завдання.

Приміром, популярна Node.JS ORM Sequelize, яку ми використовуємо на backend-е нашого проекту, значно втрачає в продуктивності на предвыборке великого (1000+) кількості рядків, тільки на одному клонировании. Якщо разом з цим, наприклад, у бізнес-логікою використовувати метод
clone
відомої бібліотеки lodash — продуктивність падає в десятки разів.

Але, як виявилося, не все так погано і сучасні JS-движки, такі як, наприклад, JavaScript V8 Engine, можуть успішно справлятися з цим завданням, якщо правильно використовувати їх архітектурні рішення. Бажаючим дізнатися як клонувати 1 млн. об'єктів за 30 мс — ласкаво просимо під кат, всі інші можуть відразу подивитися реалізацію.

Відразу хочеться обмовитися, що на цю тему вже трохи писали. Колега з Хабра навіть робив нативне розширення node-v8-clone, але воно не збирається під свіжі версії ноди, сфера його застосування обмежена тільки бэкэндом, та й швидкість його нижче пропонованого рішення.

Давайте розберемося, на що витрачається процесорний час під час клонування — це дві основні операції виділення пам'яті і запис. В цілому, їх реалізації для багатьох JS-движків схожі, але далі піде мова про V8, як основного для Node.js. Насамперед, щоб зрозуміти, на що йде час, потрібно розібратися в тому, що з себе представляють об'єкти JavaScript.

Подання JavaScript об'єктів
JS дуже гнучкий мову програмування і його властивості об'єктів можуть додаватися на льоту, більшість JS-движків використовують хеш-таблиці для їх подання — це дає необхідну гнучкість, але уповільнює доступ до його властивостей, оскільки вимагає динамічного пошуку хеша в словнику. Тому оптимізаційний компілятор V8, в гонитві за швидкістю, може на льоту перемикатися між двома видами подання об'єкта — словниками (hash tables) і прихованими класами (fast, in-object properties).

V8 скрізь, де це можливо, намагається використовувати приховані класи для швидкого доступу до властивостей об'єкта, в той час як хеш-таблиці використовуються для представлення «складних» об'єктів. Прихований клас у V8 — це ніщо інше, як структура в пам'яті, яка містить таблицю дескрипторів властивостей об'єкта, його розмір і посилання на конструктор і прототип. Для прикладу, розглянемо класичне уявлення JS-об'єкта:
function Point(x, y) {
this.x = x;
this.y = y;
}

Якщо виконати
new Point(x, y)
— створиться новий об'єкт
Point
. Коли V8 робить це вперше, він створює базовий прихований клас
Point
, назвемо його
C0
для прикладу. Т. к. для об'єкта поки ще не визначено жодного властивості, прихований клас
C0
порожній.
C0

Виконання першого виразу
Point
(
this.x = x;
) створює нову властивість
x
об'єкт
Point
. При цьому, V8:

  • створює новий прихований клас
    C1
    ,
    C0
    , і додає
    C1
    інформацію про те, що в об'єкта є одна властивість
    x
    , значення якого зберігається в
    0
    (нульовому) офсеті об'єкта
    Point
    .
  • оновлює C0 записом про перехід (a class transition), яка інформує про те, що якщо властивість
    x
    додано в об'єкт описаний
    C0
    тоді прихований клас
    C1
    має використовуватися замість
    C0
    . Прихований клас об'єкта
    Point
    встановлюється в
    C1
    .
C1

Виконання другого виразу
Point
(
this.y = y;
) створює нову властивість
y
об'єкт
Point
. При цьому, V8:

  • створює новий прихований клас
    C2
    ,
    C1
    , і додає
    C2
    інформацію про те, що в об'єкта також є властивість
    y
    , значення якого зберігається в
    1
    (першому) офсеті об'єкта
    Point
    .
  • оновлює C1 записом про перехід, інформує про те, що якщо властивість
    y
    додано в об'єкт описаний
    C1
    тоді прихований клас
    C2
    має використовуватися замість
    C1
    . Прихований клас об'єкта
    Point
    встановлюється в
    C2
    .
C2

Створення прихованого класу, кожен раз коли додається нове властивість може бути не ефективним, але т. до. для нових екземплярів цього ж об'єкта приховані класи буду переиспользованны — V8 страется використовувати їх замість словників. Механізм прихованих класів допомагає уникнути пошуку по словнику при доступі до властивостям, а також дозволяє використовувати різні оптимізації засновані на класах, в т. ч. inline caching.

У зв'язку з цим, ідеальним об'єктом для компілятора буде об'єкт — з конструктором в якому чітко визначений набір властивостей, не змінюється в процесі виконання. Тому найважливішою оптимізацією для прискорення доступу до властивостей об'єктів при клонуванні є правильне опис його конструктора. Другою важливою частиною є безпосередньо оптимізація самого процесу читання-запису, про що і піде мова далі.

Динамічна генерація коду
V8 компілює JavaScript код безпосередньо в машинний під час першого виконання, без проміжного коду або інтерпретатора. Доступ до властивостей об'єктів при цьому оптимізується inline cache-м, машинні інструкції якого V8 може змінювати прямо під час виконання.

Розглянемо читання властивості об'єкта, протягом початкового виконання коду, V8 визначає його поточний прихований клас і оптимізує майбутні звернення до нього, пророкуючи що в цій секції коду об'єкти будуть з тим же прихованим класом. Якщо V8 вдалося передбачити коректно, то значення властивості присвоює (або виходить) однією операцією. Якщо ж вірно передбачити не вдалося, V8 змінює код і видаляє оптимізацію.

Для прикладу, візьмемо JavaScript код отримує властивість
x
об'єкта
Point
:
point.x

V8 генерує наступний машинний код для читання
x
:
# ebx = the point object
cmp [ebx,<hidden class offset>],<cached hidden class>
jne <inline cache miss>
mov eax,[ebx, <cached x offset>]

Якщо прихований клас об'єкта не відповідає закешированному, виконання переходить до коду V8 який обробляє відсутність inline cache-а змінює його. Якщо ж класи відповідають, що відбувається в більшості випадків значення властивості
x
просто виходить в одну операцію.

При обробці безлічі об'єктів з однаковим прихованим класом досягаються ті ж переваги, що і у більшості статичних мов. Комбінація використання прихованих класів для доступу до властивостей об'єктів і використання кешу значно збільшує продуктивність JavaScript-коду. Саме цими оптимизациями ми і скористаємося для прискорення процесу клонування.

Клонування
Як ми з'ясували з теорії вище, клонування буде найбільш швидким якщо виконується дві умови:
  • всі поля об'єкта описані в конструкторі використовуються приховані класи, замість режиму словника (хеш-таблиці)
  • явно перераховані всі поля для клонування — присвоювання проходить в одну операцію завдяки використанню inline cache-а
Іншими словами, для швидкого клонування об'єкта
Point
нам потрібно створити конструктор, який приймає об'єкт цього типу і створює на його основі новий:
function Clone(point) {
this.x = point.x;
this.y = point.y;
}
var clonedPoint = new Clone(point);

В принципі і все, якщо б не одне але — писати такі конструктори для всіх видів об'єктів в системі досить накладно, так само, об'єкти можуть мати складну вкладену структуру. Для того щоб спростити роботу з цими оптимизациями мною була написана бібліотека створює конструктори клонування для переданого об'єкта будь-якої вкладеності.

Принцип роботи бібліотеки дуже проста — вона отримує на вхід об'єкт, генерує за його структурі конструктор клонування, який надалі можна використовувати для клонування об'єктів цього типу.
var Clone = FastClone.factory(point);
var clonedPoint = new Clone(point);

Функція генерується через eval і операція це не дешева, тому перевага в продуктивності досягаються в основному при необхідності повторного клонування об'єктів з однаковою структурою. Результати порівняльного тесту продуктивності за допомогою benchmark.js:
бібліотека операцій/сек.
FastClone 16 673 927
Object.assign 535 911
lodash 66 313
JQuery 62 164
Исходники тесту — jsfiddle.net/volovikov/thcu7tjv/25
В цілому, ми отримуємо такі ж результати на реальній системі, клонування прискорюється в 100 — 200 разів на об'єктах з повторюваною структурою.

Спасибі за увагу!

Бібліотека — github.com/ivolovikov/fastest-clone

Матеріали по темі:
jayconrod.com/posts/52/a-tour-of-v8-object-representation
developers.google.com/v8/design
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.