Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 29
Спасибо, отличное изыскание, расскажите, а где у вас может случится подобная рекурсия, которая переполняет стек, очень интересно.
Не знаю как написать об этом в двух словах, когда разбирался с багом, долго не мог найти что приводило к переполнению.
Вообщем был разработан асинхронный шаблонизатор для проекта josi (как раз планирую статью о технике которую использовал при его написании).
В предыдущей версии в основе лежал цикл, который перебирал символы шаблона, выискивал включения, и заменял на что нужно, ну вообщем как обычно.
Появилась идея — добавить возможность, во время парсинга шаблона, подгружать динамически другие шаблоны, и включать, после обработки, в текущий, что то вроде include php. При это необходимо обеспечить ассинхронность естественно. В этом случае обычный цикл пришлось заменить рекурсивным вызовом по fdone (завершению подгрузки запрошенного шаблона), с передачей текущего контекста парсинга. Учитывая при этом накладные расходы фреймворка (+3 последовательных вызова служебных функций), для парсинга сложного шаблона порой требовалось сделать и 700 и более вызовов, что и приводило к проблеме.
Вообщем был разработан асинхронный шаблонизатор для проекта josi (как раз планирую статью о технике которую использовал при его написании).
В предыдущей версии в основе лежал цикл, который перебирал символы шаблона, выискивал включения, и заменял на что нужно, ну вообщем как обычно.
Появилась идея — добавить возможность, во время парсинга шаблона, подгружать динамически другие шаблоны, и включать, после обработки, в текущий, что то вроде include php. При это необходимо обеспечить ассинхронность естественно. В этом случае обычный цикл пришлось заменить рекурсивным вызовом по fdone (завершению подгрузки запрошенного шаблона), с передачей текущего контекста парсинга. Учитывая при этом накладные расходы фреймворка (+3 последовательных вызова служебных функций), для парсинга сложного шаблона порой требовалось сделать и 700 и более вызовов, что и приводило к проблеме.
700 и более вызовов, как-то на мой взгляд прям много, хотел бы я посмотреть на такой шаблон и особенно смущает — «В предыдущей версии в основе лежал цикл, который перебирал символы шаблона, выискивал включения, и заменял на что нужно, ну вообщем как обычно.», как-то не выглядит это обычным для шаблонизатора.
PS извиняюсь за назойливость и занудство, но думаю не только мне будет интересно узнать подробности.
PS извиняюсь за назойливость и занудство, но думаю не только мне будет интересно узнать подробности.
Я только рад обсудить этот вопрос!
Где, f_var_replacer возвращает некоторое значение, помещаемое на место того что нам нужно заменить. Однако, насколько я знаю regexp — это конечный автомат, который так или иначе выполняет полный перебор всех символов в один проход.
Раньше с целью лучшего понимания, а теперь скорее с целью получения большего контроля над процессом, я выполняю данную операцию вручную — те в цикле перебираю символы строки, задавая на входе набор состояний, в которых может находится парсер, и обрабатываю текст. Не ручаюсь за производительность, решения. К сожалению в потоке работы, так и не протестировал (но обязательно сделаю) скорость работы regexp и реализованного алгоритма (думаю regexp безоговорочно выиграет, поскольку свой подход считаю очень примитивным).
Теперь что касается семи ста вызовов. Если честно, хотел бы расписать все по полочкам, с самого начала. Проект активно развивается и, сейчас, я наконец таки взялся за написание общедоступной документации. Где хочу расписать архитектуру, в том числе шаблонизатор, поскольку в него я вложил очень много труда. Конечно, я не претендую, на оригинальность, или самое лучшее решение, но удалось сделать то, что было запланировано, и это работает!
700 вызовов, это не чистая цифра, и складывается она из 1 вызова эффективной функции, +3 накладных (диспетчер задач). Отсюда и цифра. Реально это 150-200 вызовов. В результате оптимизации число накладных вызовов было снижено до 2.
Я не хочу углубляться в подробности отрывочно, поскольку не удастся передать суть, и обосновать те или иные решения… Статьи уже в работе. Буду рад если информация покажется Вам интересной и принесет пользу!
В предыдущей версии в основе лежал цикл, который перебирал символы шаблона, выискивал включения, и заменял на что нужно, ну вообщем как обычно.— здесь я конечно хватил немного. Я имел ввиду, что принцип обработки шаблона так или иначе связан с перебором символов содержимого, по крайней мере, я не могу назвать какой либо другой возможный принцип поиска, допустим необходимого нам символа в тексте, без использования каких либо техник индексации и тд. Как правило(по крайней мере я бы точно сделал так), используется конструкция вида:
eval_str=exp_str.replace(/(#[^#]+#)/g, f_var_replacer).
Где, f_var_replacer возвращает некоторое значение, помещаемое на место того что нам нужно заменить. Однако, насколько я знаю regexp — это конечный автомат, который так или иначе выполняет полный перебор всех символов в один проход.
Раньше с целью лучшего понимания, а теперь скорее с целью получения большего контроля над процессом, я выполняю данную операцию вручную — те в цикле перебираю символы строки, задавая на входе набор состояний, в которых может находится парсер, и обрабатываю текст. Не ручаюсь за производительность, решения. К сожалению в потоке работы, так и не протестировал (но обязательно сделаю) скорость работы regexp и реализованного алгоритма (думаю regexp безоговорочно выиграет, поскольку свой подход считаю очень примитивным).
Теперь что касается семи ста вызовов. Если честно, хотел бы расписать все по полочкам, с самого начала. Проект активно развивается и, сейчас, я наконец таки взялся за написание общедоступной документации. Где хочу расписать архитектуру, в том числе шаблонизатор, поскольку в него я вложил очень много труда. Конечно, я не претендую, на оригинальность, или самое лучшее решение, но удалось сделать то, что было запланировано, и это работает!
700 вызовов, это не чистая цифра, и складывается она из 1 вызова эффективной функции, +3 накладных (диспетчер задач). Отсюда и цифра. Реально это 150-200 вызовов. В результате оптимизации число накладных вызовов было снижено до 2.
Я не хочу углубляться в подробности отрывочно, поскольку не удастся передать суть, и обосновать те или иные решения… Статьи уже в работе. Буду рад если информация покажется Вам интересной и принесет пользу!
По хорошему большинство вызовов должно происходить один раз при компиляции шаблона.
Интересно было бы взглянуть на код шаблонитизатора, сравнить с существующими.
Интересно было бы взглянуть на код шаблонитизатора, сравнить с существующими.
Ух, как же я соскучился по js-хакам… Давно не попадалось ничего подобного, спасибо автору!
Ведь любая рекурсия в цикл разворачивается, зачем эти извращения?
В цикл нельзя привнести асинхронность. Именно этот фактор, заставил искать другое решение. И, да, очень согласен, если конечно верно понял Вашу мысль, — необходимо и достаточно! Этим принципом руководствуюсь в работе. Приведенное решение нужно тогда и только тогда, когда мы в целевой (рекурсивной) функции имеем конструкцию? результат выполнения которой возвращается в calback. В этом случае цикл нам не подходит, именно поэтому было применено это решение…
Просветите, а что такое «AMD модуль»?
Только надо учесть, что в данном случае, функция из синхронной превращается в асинхронную. И результат придется получать в колбеке.
В свое время для асинхронной эвалюации абстрактного синтаксического дерева, я также искал решение данной проблемы, в результате набрел вот на это: zef.me/3420/async-foreach-in-javascript и по мотивам сделал свой собственный вариант forEachAsync:
function forEachAsync(list, iterator, ret) {
if (!(list instanceof Object)) return ret();
var keys, key, length, last;
var i = -1, calls = 0, looping = false;
if (list instanceof Array) {
length = list.length;
} else {
keys = Object.keys(list);
length = keys.length;
}
last = length - 1;
var resume = function() {
calls += 1;
if (looping) return;
looping = true;
while (calls > 0) {
calls -= 1, i += 1;
if (i === length) return ret();
key = (keys ? keys[i] : i);
iterator(list[key], function(stop) {
if (stop === true) ret();
else resume();
}, key, i, last);
}
looping = false;
};
resume();
}
Вместо list instanceof Array, лучше писать Array.isArray(list)
У этого решения та-же проблема, с которой столкнулся автор статьи: высокой вероятность переполнения стека.
Автор, спасибо за статью. Суть вынес и сохраню: во избежание переполнения стека, организовывать рекурсию через триггер событий.
Кажется, вместо setTimeout можно было использовать более продвинутую альтернативу в виде window.requestAnimationFrame с деградацией до setTimeout, задержка на косвенный вызов значительно снизится.
500 вызовов это более чем достаточно, с огромным запасом!!!
Если учесть что рекурсия оправдана лишь там где идет ветвление.
Ведь не зря существует такое понятие как Хвостовая оптимизация рекурсии, ее смысл в том, что последний рекурсивный вызов функцией самой себя ВСЕГДА может (и по хорошему должен) быть повешен на цикл. Исходя из этого если у вас ветвление к примеру всего 2 рекурсивных вызова с глубиной стека 500, то функция отработает 2**500 раз (это число со 150 десятичными нулями) Т.е. глубина стека для рекурсивного алгоритма это 500я степень какого то коэффициента ветвления, поэтому это Очень много. Даже если представить странный случай «разреженной рекурсии» где второй вызов случается всего в 10% случаев — количество вызовов будет числом с 20ю нулями.
Т.о. проблема не в том, что стек мал. Да пусть он хоть стремится к бесконечности, если рекурсия была бы действительно оправдана, время выполнения вашего алгоритма было бы астрономическим… Вы просто используете рекурсию в алгоритме в котором она является антипатерном.
И «рекурсивный вызов» в setTimeout'е это не рекурсия, потому что это не «вызов», а «добавление события» в eventloop, это совершенно архитектурно разные вещи, вы просто тянете «визуально рекурсивный» паттерн туда где он не нужен. Есть async идеально подходящий для этого. Для кроссбраузерности есть промисы (которые в крайнем случае прекрасно полифилятся на callback'ах).
Если у вас проблема с переполнением стека, при дебаге оправданных рекурсивных функций можно добрасывать в параметр функции maxCallLength=const уменьшая его на каждый вызов. И обрабатывая кейс когда он стал нулевым. В иных случаях если при рекурсии происходит переполнение — у вас что то не так с алгоритмом.
Если учесть что рекурсия оправдана лишь там где идет ветвление.
Ведь не зря существует такое понятие как Хвостовая оптимизация рекурсии, ее смысл в том, что последний рекурсивный вызов функцией самой себя ВСЕГДА может (и по хорошему должен) быть повешен на цикл. Исходя из этого если у вас ветвление к примеру всего 2 рекурсивных вызова с глубиной стека 500, то функция отработает 2**500 раз (это число со 150 десятичными нулями) Т.е. глубина стека для рекурсивного алгоритма это 500я степень какого то коэффициента ветвления, поэтому это Очень много. Даже если представить странный случай «разреженной рекурсии» где второй вызов случается всего в 10% случаев — количество вызовов будет числом с 20ю нулями.
Т.о. проблема не в том, что стек мал. Да пусть он хоть стремится к бесконечности, если рекурсия была бы действительно оправдана, время выполнения вашего алгоритма было бы астрономическим… Вы просто используете рекурсию в алгоритме в котором она является антипатерном.
И «рекурсивный вызов» в setTimeout'е это не рекурсия, потому что это не «вызов», а «добавление события» в eventloop, это совершенно архитектурно разные вещи, вы просто тянете «визуально рекурсивный» паттерн туда где он не нужен. Есть async идеально подходящий для этого. Для кроссбраузерности есть промисы (которые в крайнем случае прекрасно полифилятся на callback'ах).
Если у вас проблема с переполнением стека, при дебаге оправданных рекурсивных функций можно добрасывать в параметр функции maxCallLength=const уменьшая его на каждый вызов. И обрабатывая кейс когда он стал нулевым. В иных случаях если при рекурсии происходит переполнение — у вас что то не так с алгоритмом.
tl;dr что было актуально раньше — не актуально сейчас.
Не смешивайте две стороны: рекурсия как организация обработки данных и рекурсия как способ управления потоком исполнения.
Рекурсивные алгоритмы могут быть реализованы по-разному, и сохранение контекста в стек с передачей управления в функцию — только одна из реализаций. Как Вы заметили, некоторые рекурсивные функции легко представляются в виде цикла. Как говорилось в одном коане, цикл — это рекурсия для бедных. Обычно, говоря о хвостовой рекурсии, понимают оптимизацию, производимую компилятором.
В статье рассматриваются рекурсивные функции с хвостовой рекурсией, производящие только побочные эффекты, но в принципе можно распространить на любые функции-продолжения, а также на циклы.
Насколько я понимаю, все Ваши расчёты исходят из того, что рекурсивная функция не содержит продолжений, то есть мы не можем прямолинейно размотать рекурсивное исполнение функции в цикл. А это именно тот случай, который рассматривается в статье. <off>Впрочем, в Ваших расчётах не учитывается рекурсия с переменной глубиной вызовов, например, обход в глубину графа с радиусом >500, в котором общее число вызовов примерно равен числу вершин.</off>
Замечу, что истинная ценность метода состоит не в обходе ограничения глубины стека, а в разбиении вычислений на несколько частей, переход между которыми включал прерывание вычислений. В те годы вычисления в основном потоке напрочь блокировал интерактивность интерфейса и это было критично для тяжелых вычислений, проводимых в цикле или рекурсией (см. например, комментарий, который о вычислении в цикле)
Наконец, мы же справедливо можем назвать рекурсивной любую функцию, в теле которой упоминается она сама.
Надо отметить, что в настоящее время задача неактуальна, а решение — тем более. Так что предлагаю с уважением похоронить статью.
Не смешивайте две стороны: рекурсия как организация обработки данных и рекурсия как способ управления потоком исполнения.
Рекурсивные алгоритмы могут быть реализованы по-разному, и сохранение контекста в стек с передачей управления в функцию — только одна из реализаций. Как Вы заметили, некоторые рекурсивные функции легко представляются в виде цикла. Как говорилось в одном коане, цикл — это рекурсия для бедных. Обычно, говоря о хвостовой рекурсии, понимают оптимизацию, производимую компилятором.
В статье рассматриваются рекурсивные функции с хвостовой рекурсией, производящие только побочные эффекты, но в принципе можно распространить на любые функции-продолжения, а также на циклы.
Насколько я понимаю, все Ваши расчёты исходят из того, что рекурсивная функция не содержит продолжений, то есть мы не можем прямолинейно размотать рекурсивное исполнение функции в цикл. А это именно тот случай, который рассматривается в статье. <off>Впрочем, в Ваших расчётах не учитывается рекурсия с переменной глубиной вызовов, например, обход в глубину графа с радиусом >500, в котором общее число вызовов примерно равен числу вершин.</off>
Замечу, что истинная ценность метода состоит не в обходе ограничения глубины стека, а в разбиении вычислений на несколько частей, переход между которыми включал прерывание вычислений. В те годы вычисления в основном потоке напрочь блокировал интерактивность интерфейса и это было критично для тяжелых вычислений, проводимых в цикле или рекурсией (см. например, комментарий, который о вычислении в цикле)
И «рекурсивный вызов» в setTimeout'е это не рекурсия, потому что это не «вызов», а «добавление события» в eventloop, это совершенно архитектурно разные вещиТехника, описанная в статье, конечно, для этого не подходит, но допустим, Вам нужно обойти граф и для этого Вы составили функцию, которая оказалась по всем формальным критериям, рекурсивной. Далее Вы её как-то реализовали в коде. Какая разница, как там под капотом это будет реализовано: через стек, циклом или событиями eventloop? JS увы, требует в коде явно решать такие вопросы, которые большинству программистов не интересны.
Наконец, мы же справедливо можем назвать рекурсивной любую функцию, в теле которой упоминается она сама.
Есть async идеально подходящий для этого. Для кроссбраузерности есть промисы (которые в крайнем случае прекрасно полифилятся на callback'ах).В 2013 промисов в действующем стандарте ES5 не было, async/await (которые суть сахар над промисами) тем более. С промисами же решение становится почти тривиальным.
Надо отметить, что в настоящее время задача неактуальна, а решение — тем более. Так что предлагаю с уважением похоронить статью.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Переполнение стека вызовов JavaScript, SetTimeout и снижение производительности AJAX