Перевод maximum call stack size exceeded

Вопрос пользователя Анатолий Ферисов в уроке «Диспетчеризация по типу. Аддитивность.», курс «JS: Программирование, управляемое данными»

Подскажите в чем проблема?

RangeError: Maximum call stack size exceeded

Бесконечная рекурсия. Терминальное условие никогда не выполняется.

Почему бесконечная? Есть терминальное условие:

и если нашли совпадение:

Есть шаг по рекурсии:

Передаем список, проходим по его елементам, если находим совпадение возвращаем, если нет то проходим до конца списка и возвращаем null. Такой алгоритм у функции.

Только работают они неправильно: RangeError: Maximum call stack size exceeded вот это надпись вам прямо говорит, о том что стек вызовов закончился. Проверяйте как работает ваша функция на тех входных данных, которые есть в тестах (а не на тех которые вы используете для тестирования)

Вот 3 дня на эту функцию(getMethod = (obj, methodName) => <>) смотрю и не пойму что нет так. Да я понимаю что RangeError: Maximum call stack size exceeded что это переполнения стека. Но почему оно происходит? Я проверял во время запуска функции в нее передается:

obj который равен : (SimpleCard, (Бул-Катосова награда издёвки, 7)) или другой (Тип, (название карыты, урон)).

methodName который равен: getName или damage.

methods к этому моменту содержит список: [(Тип,(имя_функции, функция)), . . ]

В функции getMethod Я прохожусь по methods и проверяю если obj(тип) === methods(тип), и methodName === methods(имя_функции), то возвращаю methods(функцию). Если совпадений не было то возращаю null.

Может я не там смотрю? Или getMethod должен не функцию возвращать? Но судя по логике да и теории он правильно работает и тут писали что он функцию должен вернуть.

Такие вещи нужно отлаживать. Ставьте вывод в консоль всех переменных и смотрите как они меняются. В этом выводе будет ответ, вы обязательно увидите то значение которое либо не меняется либо меняется неправильно.

Все прошел :). Проблема была в интефейсе card.js и в том как там были реализованы функции getName и damage. Поставил фигурные скобки, а тело функции написал в сокращенном виде без return. Мда столько дней убил на это 🙂

Мда, потратил столько часов, изучил задачу досконально, мысленно прошел по каждой строчке кода пытаясь понять где косяк, и в итоге фигурные скобки без return. Просто нет слов. Иногда лучше сразу заходить в обсуждения)

Источник

Переполнение стека вызовов JavaScript, SetTimeout и снижение производительности AJAX

Проблема

Некоторое время назад в работе над клиентской (javascript) частью движка josi возникла, кстати, достаточно часто встречающаяся проблема переполнения стека:
Uncaught RangeError: Maximum call stack size exceeded (google chrome)
В статье рассматривается решение без использования setTimout или setInterval.

Причина такого поведения известна и понятна, и в той или иной форме всегда вызвана следующим. Классическая(прямая) рекурсия порождает цепочку последовательных вызовов, что соответственно ведет к наполнению стека вызовов, однако, стек вызовов браузера достаточно мал, в chrome на момент тестирования это 500 вызовов, в safari, если не ошибаюсь, тоже. В любом случае- это предельное значение, а значит его можно превысить и получить exception. Естественно, столь долгое выполнение кода не желательно в принципе, и этого стоит избегать. И все же лично мне не хочеться полагаться на удачу, не смотря на то, что ситуация в которой пришлось столкнуться с проблемой на продакшен возникнуть не должна, я потратил время на изучение данного вопроса.

Решение

Классическим решением (имею ввиду подавляющее количество статей предлагающих его) является использование косвенной рекурсии посредством: setTimeout либо setInterval.

В качестве примера приведу простенькую рекурсивную функция, единственное назначение которой рано или поздно вернуть Вам предел размера стека вместе с exeption о превышении этого предела…

та же бесполезная функция, но теперь теоретически бесконечная, разве что k переполнится

Текущая функция сразу завершается за счет использования для рекурсии посредника setTimout, а следующий вызов выполняется по событию.
Отрицательной стороной такого подхода является его крайне низкая производительность, несмотря на то, что мы указываем нулевую задержку. Вызвана функция будет в зависимости от браузера в среднем не раньше чем через 10 мс. Но ведь мы боремся с превышением стека вызовов, а значит наша функция вызывается сотни раз, что означает потерю в производительности

1 с на каждые 100 вызовов. Детальное тестирование нашел тут.
Самое простое, что пришло в голову — организовать симбиоз из попеременного использования прямого и косвенного вызовов, чтобы при достижении некоторого значения счетчика прерывать стек косвенным вызовом. Отчасти такое решение сейчас и используется. Но здесь тоже все не так просто, особенно если рекурсия представлена петлей из нескольких функций.
Вот простенький пример отражающий суть такого решения:

В моем коде проблема возникла в шаблонизаторе, который как раз незадолго до этого был переписан согласно новой парадигме. Не хотелось отказываться от принятой архитектуры. В тоже время реальное падение производительности составило 20-30% — что было просто чудовищно. Предложенное выше решение тоже не идеал: сохранялось падение производительности на 5-7%. Это меня не устроило: много гуглил, и напал на то, что нужно.
А это тест от туда же, из которого видно что, предложенный подход, в сравнении с setTimeout 0, гораздо более производительный, что на практике дало не более 3% падения производительности в моем случае…

Данное решение основано на связке window.postMessage и element.addEventListener, для меня достаточно кроссбраузерно (ie8+).

Я переработал функцию из приведенной выше статьи в AMD модуль. Возможно, кому-то это будет полезным…

Редакторский дайджест

Присылаем лучшие статьи раз в месяц

Скоро на этот адрес придет письмо. Подтвердите подписку, если всё в силе.

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

Падение Stack Overflow: что случилось

Stack Overflow вывел из Vim уже больше миллиона пользователей

Анализ рекомендаций книг для разработчиков со Stack Overflow средствами Python

Средняя зарплата в IT

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Комментарии 29

В предыдущей версии в основе лежал цикл, который перебирал символы шаблона, выискивал включения, и заменял на что нужно, ну вообщем как обычно.

— здесь я конечно хватил немного. Я имел ввиду, что принцип обработки шаблона так или иначе связан с перебором символов содержимого, по крайней мере, я не могу назвать какой либо другой возможный принцип поиска, допустим необходимого нам символа в тексте, без использования каких либо техник индексации и тд. Как правило(по крайней мере я бы точно сделал так), используется конструкция вида:

Где, f_var_replacer возвращает некоторое значение, помещаемое на место того что нам нужно заменить. Однако, насколько я знаю regexp — это конечный автомат, который так или иначе выполняет полный перебор всех символов в один проход.
Раньше с целью лучшего понимания, а теперь скорее с целью получения большего контроля над процессом, я выполняю данную операцию вручную — те в цикле перебираю символы строки, задавая на входе набор состояний, в которых может находится парсер, и обрабатываю текст. Не ручаюсь за производительность, решения. К сожалению в потоке работы, так и не протестировал (но обязательно сделаю) скорость работы regexp и реализованного алгоритма (думаю regexp безоговорочно выиграет, поскольку свой подход считаю очень примитивным).

Теперь что касается семи ста вызовов. Если честно, хотел бы расписать все по полочкам, с самого начала. Проект активно развивается и, сейчас, я наконец таки взялся за написание общедоступной документации. Где хочу расписать архитектуру, в том числе шаблонизатор, поскольку в него я вложил очень много труда. Конечно, я не претендую, на оригинальность, или самое лучшее решение, но удалось сделать то, что было запланировано, и это работает!
700 вызовов, это не чистая цифра, и складывается она из 1 вызова эффективной функции, +3 накладных (диспетчер задач). Отсюда и цифра. Реально это 150-200 вызовов. В результате оптимизации число накладных вызовов было снижено до 2.
Я не хочу углубляться в подробности отрывочно, поскольку не удастся передать суть, и обосновать те или иные решения… Статьи уже в работе. Буду рад если информация покажется Вам интересной и принесет пользу!

Если не трудно приведите пример.
Bижу это так:

В любом случае это не цикл while…

В свое время для асинхронной эвалюации абстрактного синтаксического дерева, я также искал решение данной проблемы, в результате набрел вот на это: zef.me/3420/async-foreach-in-javascript и по мотивам сделал свой собственный вариант forEachAsync:

500 вызовов это более чем достаточно, с огромным запасом.
Если учесть что рекурсия оправдана лишь там где идет ветвление.
Ведь не зря существует такое понятие как Хвостовая оптимизация рекурсии, ее смысл в том, что последний рекурсивный вызов функцией самой себя ВСЕГДА может (и по хорошему должен) быть повешен на цикл. Исходя из этого если у вас ветвление к примеру всего 2 рекурсивных вызова с глубиной стека 500, то функция отработает 2**500 раз (это число со 150 десятичными нулями) Т.е. глубина стека для рекурсивного алгоритма это 500я степень какого то коэффициента ветвления, поэтому это Очень много. Даже если представить странный случай «разреженной рекурсии» где второй вызов случается всего в 10% случаев — количество вызовов будет числом с 20ю нулями.
Т.о. проблема не в том, что стек мал. Да пусть он хоть стремится к бесконечности, если рекурсия была бы действительно оправдана, время выполнения вашего алгоритма было бы астрономическим… Вы просто используете рекурсию в алгоритме в котором она является антипатерном.

И «рекурсивный вызов» в setTimeout’е это не рекурсия, потому что это не «вызов», а «добавление события» в eventloop, это совершенно архитектурно разные вещи, вы просто тянете «визуально рекурсивный» паттерн туда где он не нужен. Есть async идеально подходящий для этого. Для кроссбраузерности есть промисы (которые в крайнем случае прекрасно полифилятся на callback’ах).

Если у вас проблема с переполнением стека, при дебаге оправданных рекурсивных функций можно добрасывать в параметр функции maxCallLength=const уменьшая его на каждый вызов. И обрабатывая кейс когда он стал нулевым. В иных случаях если при рекурсии происходит переполнение — у вас что то не так с алгоритмом.

tl;dr что было актуально раньше — не актуально сейчас.

Не смешивайте две стороны: рекурсия как организация обработки данных и рекурсия как способ управления потоком исполнения.
Рекурсивные алгоритмы могут быть реализованы по-разному, и сохранение контекста в стек с передачей управления в функцию — только одна из реализаций. Как Вы заметили, некоторые рекурсивные функции легко представляются в виде цикла. Как говорилось в одном коане, цикл — это рекурсия для бедных. Обычно, говоря о хвостовой рекурсии, понимают оптимизацию, производимую компилятором.
В статье рассматриваются рекурсивные функции с хвостовой рекурсией, производящие только побочные эффекты, но в принципе можно распространить на любые функции-продолжения, а также на циклы.

Насколько я понимаю, все Ваши расчёты исходят из того, что рекурсивная функция не содержит продолжений, то есть мы не можем прямолинейно размотать рекурсивное исполнение функции в цикл. А это именно тот случай, который рассматривается в статье. Впрочем, в Ваших расчётах не учитывается рекурсия с переменной глубиной вызовов, например, обход в глубину графа с радиусом >500, в котором общее число вызовов примерно равен числу вершин.

Замечу, что истинная ценность метода состоит не в обходе ограничения глубины стека, а в разбиении вычислений на несколько частей, переход между которыми включал прерывание вычислений. В те годы вычисления в основном потоке напрочь блокировал интерактивность интерфейса и это было критично для тяжелых вычислений, проводимых в цикле или рекурсией (см. например, комментарий, который о вычислении в цикле)

И «рекурсивный вызов» в setTimeout’е это не рекурсия, потому что это не «вызов», а «добавление события» в eventloop, это совершенно архитектурно разные вещи

Техника, описанная в статье, конечно, для этого не подходит, но допустим, Вам нужно обойти граф и для этого Вы составили функцию, которая оказалась по всем формальным критериям, рекурсивной. Далее Вы её как-то реализовали в коде. Какая разница, как там под капотом это будет реализовано: через стек, циклом или событиями eventloop? JS увы, требует в коде явно решать такие вопросы, которые большинству программистов не интересны.
Наконец, мы же справедливо можем назвать рекурсивной любую функцию, в теле которой упоминается она сама.

Есть async идеально подходящий для этого. Для кроссбраузерности есть промисы (которые в крайнем случае прекрасно полифилятся на callback’ах).

В 2013 промисов в действующем стандарте ES5 не было, async/await (которые суть сахар над промисами) тем более. С промисами же решение становится почти тривиальным.

Надо отметить, что в настоящее время задача неактуальна, а решение — тем более. Так что предлагаю с уважением похоронить статью.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Источник

Поделиться с друзьями
admin
Оцените автора
( Пока оценок нет )
Как переводится?
Adblock
detector