Комментарии 40
размер коллстэка в Chrome равен… 1002128 байтов. Это почти один мегабайт
Я старый фортранист и рекурсивные функции практически не использую, поэтому интересуюсь только в порядке ликбеза: а чем определяется размер коллстека, доступного для exe-шника? Это прошивается в exe-файле или зависит от среды, в которой он исполняется? Например, на моем компе аналогичный тест показывает, что программе на фортране по умолчанию доступен стек 64 Мб. Если этот же exe-шник запустить на другом компе, то может ли там доступный коллстек оказаться, например, вдвое меньше? Или можно ожидать, что раз программа запускается, то те же самые 64Мб у нее всегда будут?
Такие вопросы уже задавали в интернете, и не раз. Начать цепочку сообщений на эту тему можно тут.
Вкратце — размер зависит от окружения, в котором запускается приложение.
а чем определяется размер коллстека, доступного для exe-шника?
Как правило — полем в заголовке exe-шника.
Но к JS это не будет иметь никакого отношения, потому что там речь о стеке VM, выделенном самим JS-движком, а не о стеке exe-шника, выделенном ОС. Например, при запуске Chrome можно передать ему размер стека для JS.
Мой любимый способ засрать стек — это использовать rest оператор:
const max = Math.max( ... numbers ) 
а вот типичный фронтэнд разработчик скорее всего задает себе подобные вопросы впервые
Как вы быстро весь фронт-енд отправили в подмастерья одним предложением. Но спорить с этим трудно.
Сколько нам (js-ерам) открытий чудных.xexex
А для чего вы задаете этот вопрос, какая польза от этого вопроса и ответа на него? Я б не стал углубляться в это. Если задача завалить кандидата, то наверно js это самое лучшее, что можно придумать. Я не имею ничего против данной статьи (прочел, классно, через месяц забуду, может быть когда то вспомню), но я против бесполезных вопросов на собесе.
Думаю к этому материалу стоит еще добавить то, что следует понимать, как работает Event Loop по части микрозадач, чтобы не получить бесконечную блокировку, которая как раз и может приводить к "RangeError: Maximum call stack size exceeded. " или к полному зависанию вкладки в виду бесконечного решения микрозадач, порождаемых в каллбеках
Все-таки разбивать один большой кусок логики на несколько маленьких, выполняя каждую маленькую задачку как макротаску, это довольно стандартный вариант действий. Возможно сделаю отдельную статью на эту тему, если она интересна.
Я видел уйму людей, которые очень слабо понимают, как это под капотом работает, и почти не видят разницы между setTimeout и await someAsyncCall(...). + недавно много ходил по собесам, и нормальные вопросы по event loop'у, мне задали 4 в 4х фирмах из 20, на позицию сеньер фронтенд разраба. Отличная тема для обсуждения
Э… А вы уверены, что для переменной типа Number в стеке выделяется именно 8 байт? Я вот лично нет: всё же это не статически типизированный язык, сейчас это переменная типа number, а потом ей где-то присвоили строку.
Надо исходники v8 смотреть.
Спасибо.
Интересно – это всегда строго так? А после того, как отработает оптимизирующий компилятор? А если код – WebAssembly?
x может быть только Number», ему достаточно наблюдения «последние 600613 разов в переменной x был Number, наверное и в следующие разы там будет Number».Это означает, что в прологе каждой оптимизированной функции проверяются все использованные допущения по поводу типов, и если что-то не сходится, то оптимизированная функция стирается, и в дальнейшем выполняется интерпретатором байткода (до новой оптимизации с новыми статистиками).
Это означает, что размер и формат стекового кадра должен быть одинаковым что для оптимизированной функции, что для неоптимизированной — потому что при любом вызове она может превратиться из одной своей формы в другую.
Подробности есть на ponyfoo.com/articles/an-introduction-to-speculative-optimization-in-v8#excurse-value-representation
Там подтверждается, что на стеке возможны только два формата значений — int32, дополненные нулями до 64 бит, и 64-битные указатели в кучу.
pointer — это usize (machine-dependent).
f64 (double) — это 8 байт. Все числа в js — это f64, так что 8.
А вот с символами интересно. В JS они вообще есть?
Я про то, что в стек наверняка не сами числа кладутся, а указатели на них (банально: одну из локальных переменных захватываем в какие-нибудь функции, сохраняем их, а из нашей функции выходим: созданные функции уже не могут ссылаться на стек).
Вон, и tyomitch выше говорит, что там указатели.
JS хранит числа на куче? Ну и бездна...
JS – очень простой язык. Поддерживающий при этом такую мощную концепцию, как замыкания. Тут довольно сложно уйти от хранения на куче.
copy-значения на куче? И что они там рассказывают про скорость?
А в том самом Execution Context, о котором в статье есть упоминание.
const func = (x) => { i++; func(); }; — отрабатывает 12564 раза, как если бы добавилась локальная переменнаяconst func = () => { i++; func(1); }; — отрабатывает 11422 раза, как будто бы фактический параметр занимает вдвое больше места, чем локальная переменнаяconst func = (x) => { i++; func(1); }; — отрабатывает те же самые 11422 раза
Ясное дело, чем больше каждый вызов отъедает стек, тем быстрее он кончится.
Минимизировать-оптимизировать для рекурсии можно вплоть до того, что для каждого вызова в стеке будет только адрес возврата.
Но так как практической информации он не несёт, то и нет проблемы развернуть такую рекурсию в цикл и не транжирить память.
Есть редкие исключения, когда каждый вызов генерирует уникальные данные необходимые всем последующим вызовам. Но и тут можно передавать эти данные не через стек, а выделять для них память другими способами.
Минимизировать-оптимизировать для рекурсии можно вплоть до того, что для каждого вызова в стеке будет только адрес возврата.
Но так как практической информации он не несёт, то и нет проблемы развернуть такую рекурсию в цикл и не транжирить память.
Конечно же нет: адрес возврата несёт критически важную информацию.
Вот конкретный пример — кривая Гильберта в черепашьей графике; я нарочно выбрал рекурсивную функцию, у которой нет ни параметров, ни локальных переменных — в стековом кадре только адрес возврата.
Хотите развернуть эту рекурсию в цикл? Попробуйте.
function hilbert_curve() {
if (!level--)
return level++;
t.Turn(angle);
angle = -angle;
hilbert_curve();
angle = -angle;
t.Move(step);
t.Turn(-angle);
hilbert_curve();
t.Move(step);
hilbert_curve();
t.Turn(-angle);
t.Move(step);
angle = -angle;
hilbert_curve();
angle = -angle;
t.Turn(angle);
level++;
}
Хотите развернуть эту рекурсию в цикл? Попробуйте.
Да, в подобных случаях без стека и адреса возврата никак.
Тут просто делаем то же самое, что делается на рекурсивном вызове. Запилили "последовательность инструкций", и "изменение указателя на текущую инструкцию".
https://codepen.io/alexandroppolus/pen/WNROrGe
var actions = [
function() {
t.Turn(angle);
angle = -angle;
},
function() {
angle = -angle;
t.Move(step);
t.Turn(-angle);
},
function() {
t.Move(step);
},
function() {
t.Turn(-angle);
t.Move(step);
angle = -angle;
},
function() {
angle = -angle;
t.Turn(angle);
}
];
function hilbert_curve_nr(level) {
var stack = [];
var pointer = 0;
while (pointer < actions.length) {
actions[pointer++]();
if (pointer < actions.length) {
if (stack.length < level) {
stack.push(pointer);
pointer = 0;
}
} else if (stack.length) {
pointer = stack.pop();
}
}
}
hilbert_curve_nr(4);Но полно случаев, когда стек не нужен, там всё совсем легко делается только циклом. И это далеко не только хвостовая рекурсия. Разворачивается и одинокий рекурсивный вызов в середине функции, и даже некоторые множественные вызовы (например Фибоначчи, в общем где можно мемоизировать).
вчетверо быстрее
Слегка допилил, теперь на макбуке в хроме и сафари нерекурсивный вариант чуть быстрее рекурсивного
function hilbert_curve_nr2(level) {
var angle = 90;
var stack = new Int32Array(level + 1);
var stackLength = 0;
var pointer = 0;
var ACTIONS_LEN = 5;
while (pointer < ACTIONS_LEN) {
switch (pointer) {
case 0:
t.Turn(angle);
angle = -angle;
break;
case 1:
angle = -angle;
t.Move(step);
t.Turn(-angle);
break;
case 2:
t.Move(step);
break;
case 3:
t.Turn(-angle);
t.Move(step);
angle = -angle;
break;
case 4:
angle = -angle;
t.Turn(angle);
}
++pointer;
if (pointer < ACTIONS_LEN) {
if (stackLength < level) {
stack[stackLength] = pointer;
++stackLength;
pointer = 0;
}
} else if (stackLength) {
pointer = stack[--stackLength];
}
}
}
(Если верно понимаю, то и памяти этот вариант занимает вдвое меньше, а с Int8Array занимал бы ещё меньше — без ущерба скорости.)
Думаю, вы можете написать на тему рекурсии в JS более полезный хабратопик, чем этот :)
Взял Int32Array, потому что вроде как (в теории) это должно быть быстрее — целочисленные переменные js хранит как int32, и будет складывать как есть. Хотя разница там копеечная. Даже если обычный массив делать, незаметно.
По теме вряд ли скажу что-то новое. Переделка рекурсии в цикл+стек расписана много где, в том числе у Кнута, Вирта и других классиков… А вот в этом топике я с удивлением узнал, что только на Execution Stack (без локальных переменных) требуется целых 72 байта. Просто не представляю, что там хранить. Ну адрес возврата, 8 байт. А остальное?
По теме вряд ли скажу что-то новое. Переделка рекурсии в цикл+стек расписана много где, в том числе у Кнута, Вирта и других классиков…
Интересно не как это осуществимо в принципе, а какие выигрыши и проигрыши даёт в конкретной среде выполнения — очевидно, что где-нибудь в Си выигрыши и проигрыши будут иными.
на Execution Stack (без локальных переменных) требуется целых 72 байта. Просто не представляю, что там хранить. Ну адрес возврата, 8 байт. А остальное?
Указатель на
this, указатель на «лексический контекст» (всё связывание в JS — позднее), base pointer для восстановления стека вызовов (для отладчика и Error.stack), сохранённые регистры (байткод V8 — регистровый)?С экспериментальными данными всё сходится.
Думаю, следует упомянуть о такой штуке, как оптимизация хвостовой рекурсии. Да, в Chrome ее сейчас нет, но так было не всегда и, вполне возможно, изменится в будущем. Суть оптимизации состоит в том, что VM может в некоторых случаях развернуть рекурсию в плоскую итерацию, но для этого рекурсивный вызов должен быть последним:
function tailRecursiveFactorial(number, result = 1) {
if(number === 1) {
return result;
} else {
return tailRecursiveFactorial(number - 1, result * number);
}
}К тому же, есть один браузер, который поддерживает Tail Recursion Calls и это Safari.
На stackoverflow также обсуждался этот вопрос: https://stackoverflow.com/questions/42788139/es6-tail-recursion-optimisation-stack-overflow
Оптимизация была в Node.js 6.x: https://stackoverflow.com/questions/23260390/node-js-tail-call-optimization-possible-or-not
Теперь, подставив N = 72 в самое первое уравнение, получим, что размер коллстэка в Chrome равен… 1002128 байтов. Это почти один мегабайт.
Какой смысл ломиться в открытую дверь?
github.com/v8/v8/blob/master/src/common/globals.h#L85
// Slightly less than 1MB, since Windows' default stack size for
// the main execution thread is 1MB for both 32 and 64-bit.
#define V8_DEFAULT_STACK_SIZE_KB 984
JavaScript: Стек вызовов и магия его размера