Как стать автором
Обновить
2772.68
Рейтинг
Маклауд
Облачные серверы на базе AMD EPYC

Стек вызовов JavaScript и ещё большая магия

МаклаудJavaScriptПрограммированиеСовершенный код


В начале апреля на хабре была опубликована статья «JavaScript: Стек вызовов и магия его размера» — её автор пришёл к выводу, что каждый кадр стека занимает (72 + 8 * число_локальных_переменных) байтов: «Получается, что мы посчитали все верно и можем утверждать, что размер пустого ExecutionStack в Chrome равен 72 байтам, а размер коллстэка — чуть меньше одного мегабайта. Отличная работа!»

Для затравки — немного изменим код, использованный AxemaFr для экспериментов:

{let i = 0;

const func = () => {
  i += 1.00000000000001;
  func();
};

try {
  func();
} catch (e) {
  console.log(i);
}}

Вместо 1 теперь на каждом шаге прибавляем чуточку больше, и в результате вместо 13951 получаем 12556.000000000002 — как будто бы в функции добавилась локальная переменная!

Повторим вопросы, которыми задавался Senior Frontend Developer AxemaFr: «Почему же так? Что изменилось? Как понять, посмотрев на функцию, сколько раз она может выполниться рекурсивно?!»

Готовим инструменты


В командной строке Chrome можно передавать аргументы для JS-движка; в частности, можно поменять и размер стека с 984 КБ на любой другой ключом --js-flags=--stack-size=.

Разобраться в том, сколько стека требуется каждой функции, нам поможет ключ --print-bytecode, уже упоминавшийся ранее. Не упоминалось то, что отладочный вывод направляется в stdout, которого у Chrome под Windows тупо нет, потому что он скомпилирован как GUI-приложение. Исправить это несложно: сделайте копию chrome.exe, и в своём любимом hex-редакторе исправьте байт 0xD4 со значения 0x02 на 0x03 (тем, кто с hex-редактором не дружит, этот байт поможет исправить скрипт на Python). Но если вы прямо сейчас читаете эту статью в Chrome, и просто запустите исправленный файл — предположим, что вы назвали его cui_chrome.exe — то откроется новое окно в уже существующем экземпляре браузера, и аргумент --js-flags будет проигнорирован. Чтобы запустить новый экземпляр Chrome, нужно передать ему какую-нибудь новую --user-data-dir:
cui_chrome.exe --no-sandbox --js-flags="--print-bytecode --print-bytecode-filter=func" --user-data-dir=\Windows\Temp

Без --print-bytecode-filter вы утонете в километровых дампах байткода функций, встроенных в Chrome.

После запуска браузера откройте консоль разработчика и введите код, использованный AxemaFr:

{let i = 0;

const func = () => {
  i++;
  func();
};

func()}

Ещё до того, как вы нажмёте на Enter, в консольном окне позади Chrome появится дамп:
[generated bytecode for function: func (0x44db08635355 <SharedFunctionInfo func>)]
Parameter count 1
Register count 1
Frame size 8
   36 S> 000044DB086355EE @    0 : 1a 02             LdaCurrentContextSlot [2]
         000044DB086355F0 @    2 : ac 00             ThrowReferenceErrorIfHole [0]
         000044DB086355F2 @    4 : 4d 00             Inc [0]
         000044DB086355F4 @    6 : 26 fa             Star r0
         000044DB086355F6 @    8 : 1a 02             LdaCurrentContextSlot [2]
   37 E> 000044DB086355F8 @   10 : ac 00             ThrowReferenceErrorIfHole [0]
         000044DB086355FA @   12 : 25 fa             Ldar r0
         000044DB086355FC @   14 : 1d 02             StaCurrentContextSlot [2]
   44 S> 000044DB086355FE @   16 : 1b 03             LdaImmutableCurrentContextSlot [3]
         000044DB08635600 @   18 : ac 01             ThrowReferenceErrorIfHole [1]
         000044DB08635602 @   20 : 26 fa             Star r0
   44 E> 000044DB08635604 @   22 : 5d fa 01          CallUndefinedReceiver0 r0, [1]
         000044DB08635607 @   25 : 0d                LdaUndefined
   52 S> 000044DB08635608 @   26 : ab                Return
Constant pool (size = 2)
Handler Table (size = 0)
Source Position Table (size = 12)

Как изменится дамп, если строчку i++; заменить на i += 1.00000000000001;?
[generated bytecode for function: func (0x44db0892d495 <SharedFunctionInfo func>)]
Parameter count 1
Register count 2
Frame size 16
   36 S> 000044DB0892D742 @    0 : 1a 02             LdaCurrentContextSlot [2]
         000044DB0892D744 @    2 : ac 00             ThrowReferenceErrorIfHole [0]
         000044DB0892D746 @    4 : 26 fa             Star r0
         000044DB0892D748 @    6 : 12 01             LdaConstant [1]
         000044DB0892D74A @    8 : 35 fa 00          Add r0, [0]
         000044DB0892D74D @   11 : 26 f9             Star r1
         000044DB0892D74F @   13 : 1a 02             LdaCurrentContextSlot [2]
   37 E> 000044DB0892D751 @   15 : ac 00             ThrowReferenceErrorIfHole [0]
         000044DB0892D753 @   17 : 25 f9             Ldar r1
         000044DB0892D755 @   19 : 1d 02             StaCurrentContextSlot [2]
   60 S> 000044DB0892D757 @   21 : 1b 03             LdaImmutableCurrentContextSlot [3]
         000044DB0892D759 @   23 : ac 02             ThrowReferenceErrorIfHole [2]
         000044DB0892D75B @   25 : 26 fa             Star r0
   60 E> 000044DB0892D75D @   27 : 5d fa 01          CallUndefinedReceiver0 r0, [1]
         000044DB0892D760 @   30 : 0d                LdaUndefined
   68 S> 000044DB0892D761 @   31 : ab                Return
Constant pool (size = 3)
Handler Table (size = 0)
Source Position Table (size = 12)

Теперь разберёмся, что поменялось и почему.

Исследуем примеры


Все опкоды V8 описаны в github.com/v8/v8/blob/master/src/interpreter/interpreter-generator.cc
Первый дамп расшифровывается так:
LdaCurrentContextSlot [2]           ; a := context[2]
ThrowReferenceErrorIfHole [0]       ; if (a === undefined)
                                    ;   throw("ReferenceError: %s is not defined", const[0])
Inc [0]                             ; a++
Star r0                             ; r0 := a
LdaCurrentContextSlot [2]           ; a := context[2]
ThrowReferenceErrorIfHole [0]       ; if (a === undefined)
                                    ;   throw("ReferenceError: %s is not defined", const[0])
Ldar r0                             ; a := r0
StaCurrentContextSlot [2]           ; context[2] := a
LdaImmutableCurrentContextSlot [3]  ; a := context[3]
ThrowReferenceErrorIfHole [1]       ; if (a === undefined)
                                    ;   throw("ReferenceError: %s is not defined", const[1])
Star r0                             ; r0 := a
CallUndefinedReceiver0 r0, [1]      ; r0()
LdaUndefined                        ; a := undefined
Return

Последний аргумент опкодов Inc и CallUndefinedReceiver0 задаёт feedback slot, в котором для оптимизатора накапливается статистика об использованных типах. На семантику байткода это не влияет, так что нас сегодня совсем не интересует.

Под дампом есть приписка: «Constant pool (size = 2)» — и действительно видим, что в байткоде используются две строки — "i" и "func" — для подстановки в сообщение исключения, когда символы с такими именами undefined. Есть приписка и над дампом: «Frame size 8» — в соответствии с тем, что в функции используется один регистр интерпретатора (r0).

Стековый кадр нашей функции состоит из:

  • единственного аргумента this;
  • адреса возврата;
  • числа переданных аргументов (arguments.length);
  • ссылки на constant pool c используемыми строками;
  • ссылки на context с локальными переменными;
  • ещё трёх указателей, нужных движку; и наконец,
  • места для одного регистра.

Итого 9*8=72 байта, как синьор AxemaFr и вычислил.

Из семи перечисленных слагаемых, теоретически, меняться могут три — число аргументов, наличие constant pool, и число регистров. Что у нас получилось в варианте с 1.00000000000001?

LdaCurrentContextSlot [2]      ; a := context[2]
ThrowReferenceErrorIfHole [0]  ; if (a === undefined)
                               ;   throw("ReferenceError: %s is not defined", const[0])
Star r0                        ; r0 := a
LdaConstant [1]                ; a := const[1]
Add r0, [0]                    ; a += r0
Star r1                        ; r1 := a
                               ; ...дальше как раньше

Во-первых, прибавляемая константа заняла третье место в constant pool; во-вторых, для её загрузки понадобился ещё один регистр, так что стековый кадр функции вырос на 8 байтов.

Если не использовать в функции именованные символы, то можно обойтись без constant pool. На github.com/v8/v8/blob/master/src/execution/frame-constants.h#L289 описан формат стекового кадра V8 и указано, что когда constant pool не используется, то размер стекового кадра сокращается на один указатель. Как в этом удостовериться? На первый взгляд кажется, что функция, не использующая именованные символы, не может быть рекурсивной; но взгляните-ка:

{let i = 0;

function func() {
  this()();
};

const helper = () => (i++, func.bind(helper));

try {
  helper()();
} catch (e) {
  console.log(i);
}}

[generated bytecode for function: func (0x44db0878e575 <SharedFunctionInfo func>)]
Parameter count 1
Register count 1
Frame size 8
   37 S> 000044DB0878E8DA @    0 : 5e 02 02 00       CallUndefinedReceiver1 <this>, <this>, [0]
         000044DB0878E8DE @    4 : 26 fa             Star r0
   43 E> 000044DB0878E8E0 @    6 : 5d fa 02          CallUndefinedReceiver0 r0, [2]
         000044DB0878E8E3 @    9 : 0d                LdaUndefined
   47 S> 000044DB0878E8E4 @   10 : ab                Return
Constant pool (size = 0)
Handler Table (size = 0)
Source Position Table (size = 8)

Цель — «Constant pool (size = 0)» — достигнута; но переполнение стека, как и раньше, происходит через 13951 вызов. Это значит, что даже когда constant pool не используется, стековый кадр функции всё равно содержит указатель на него.

А удастся ли добиться меньшего размера стекового кадра, чем вычисленное AxemaFr минимальное значение? —да, если внутри функции не использовать ни один регистр:
{function func() {
  this();
};

let chain = ()=>null;
for(let i=0; i<15050; i++)
  chain = func.bind(chain);

chain()}

[generated bytecode for function: func (0x44db08c34059 <SharedFunctionInfo func>)]
Parameter count 1
Register count 0
Frame size 0
   25 S> 000044DB08C34322 @    0 : 5d 02 00          CallUndefinedReceiver0 <this>, [0]
         000044DB08C34325 @    3 : 0d                LdaUndefined
   29 S> 000044DB08C34326 @    4 : ab                Return
Constant pool (size = 0)
Handler Table (size = 0)
Source Position Table (size = 6)

(При этом цепочка из 15051 вызова уже приводит к «RangeError: Maximum call stack size exceeded».)

Таким образом, вывод синьора AxemaFr о том, что «размер пустого ExecutionStack в Chrome равен 72 байтам», успешно опровергнут.

Уточняем предсказания


Мы можем утверждать, что минимальный размер стекового кадра для JS-функции в Chrome равен 64 байтам. К этому нужно прибавить по 8 байтов за каждый объявленный формальный параметр, ещё по 8 байтов за каждый фактический параметр сверх числа объявленных, и ещё по 8 байтов за каждый использованный регистр. По регистру отводится для каждой локальной переменной, для загрузки констант, для обращения к переменным из внешнего контекста, для передачи фактических параметров при вызовах, и т.д. Точное число использованных регистров по исходному тексту на JS вряд ли возможно определить. Стоит отметить, что интерпретатор JS поддерживает неограниченное число регистров — они не имеют отношения к регистрам процессора, на котором интерпретатор выполняется.

Теперь понятно, почему:
  • добавление неиспользуемого формального параметра (func = (x) => { i++; func(); };) потребляет столько же памяти, как дополнительная локальная переменная;
  • передача необъявленного фактического параметра (func = () => { i++; func(1); };) потребляет вдвое больше памяти, чем дополнительная локальная переменная — потому что для передачи понадобился дополнительный регистр:
    [generated bytecode for function: func (0x44db08e12da1 <SharedFunctionInfo func>)]
    Parameter count 1
    Register count 2
    Frame size 16
       34 S> 000044DB08E12FE2 @    0 : 1a 02             LdaCurrentContextSlot [2]
             000044DB08E12FE4 @    2 : ac 00             ThrowReferenceErrorIfHole [0]
             000044DB08E12FE6 @    4 : 4d 00             Inc [0]
             000044DB08E12FE8 @    6 : 26 fa             Star r0
             000044DB08E12FEA @    8 : 1a 02             LdaCurrentContextSlot [2]
       35 E> 000044DB08E12FEC @   10 : ac 00             ThrowReferenceErrorIfHole [0]
             000044DB08E12FEE @   12 : 25 fa             Ldar r0
             000044DB08E12FF0 @   14 : 1d 02             StaCurrentContextSlot [2]
       39 S> 000044DB08E12FF2 @   16 : 1b 03             LdaImmutableCurrentContextSlot [3]
             000044DB08E12FF4 @   18 : ac 01             ThrowReferenceErrorIfHole [1]
             000044DB08E12FF6 @   20 : 26 fa             Star r0
             000044DB08E12FF8 @   22 : 0c 01             LdaSmi [1]
             000044DB08E12FFA @   24 : 26 f9             Star r1
       39 E> 000044DB08E12FFC @   26 : 5e fa f9 01       CallUndefinedReceiver1 r0, r1, [1]
             000044DB08E13000 @   30 : 0d                LdaUndefined
       48 S> 000044DB08E13001 @   31 : ab                Return
    Constant pool (size = 2)
    Handler Table (size = 0)
    Source Position Table (size = 12)
  • изменение в предыдущем примере добавляемого значения на 1.00000000000001 не влияет на размер стекового кадра — потому что один и тот же r1 используется и для загрузки константы, и для передачи фактического параметра.


Теги:javascriptмагияпрограммированиерасследования
Хабы: Маклауд JavaScript Программирование Совершенный код
Всего голосов 25: ↑19 и ↓6 +13
Просмотры4.3K

Похожие публикации

Лучшие публикации за сутки

Информация

Дата основания
Местоположение
Россия
Сайт
macloud.ru
Численность
11–30 человек
Дата регистрации
Представитель
Mikhail

Блог на Хабре