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

Проблема


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


Суть


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

Решение


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

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

function f(args) 
{
     var self=this;
     var k=args.k;

     //вызываем себя же
     try
     {
         f({k:k+1});
     }
     catch(ex)
     {
          alert(k);
     }
}


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

function f(args) 
{
     var self=this;
     var k=args.k;
     
     //косвенно вызываем себя же, через посредника setTimeout
     setTimeout(function(){ f({k:k+1}) }, 0);
}

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

var max_call_i=300;
function f(args) 
{
     var self=this;
     var k=args.k;
     var call_i=args.call_i
     //alert(k);

     if (call_i>=max_call_i)
     {     
            //косвенно вызываем себя же, через посредника setTimeout
            setTimeout(function(){ f({k:k+1, call_i:call_i+1}) }, 0);
     }
     else
     {
           //напрямую вызываем себя же
           f({k:k+1, call_i:call_i+1});
     }
}


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

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

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

define([], function () 
{
        
	return
       {
		
		args:							//аргументы
		{
			indirect_call:
			{
				f_arr:[],
				msg_name:"indirect_call-message",
				handler_f:null,
			}
		},
		
		/*** работа с событиями ***/

		f_indirect_call:function(f)
		{
			var self=this;
			
			//если это первый вызов то создаем обработчик события и привязываем к window
			if (t_uti.f_is_empty(self.args.indirect_call.handler_f))
			{
				//создаем обработчик события
				self.args.indirect_call.handler_f=function(event) 
				{
					if (event.source == window && event.data == self.args.indirect_call.msg_name) 
					{
						event.stopPropagation();
						if (self.args.indirect_call.f_arr.length> 0) 
						{
							var f = self.args.indirect_call.f_arr.shift();
							f();
						}
					}
				}
				
				window.addEventListener("message", self.args.indirect_call.handler_f, true);
			}
			
			self.args.indirect_call.f_arr.push(f);
			window.postMessage(self.args.indirect_call.msg_name, "*");
		},
      };
});

Поделиться публикацией

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

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

    0
    Спасибо, отличное изыскание, расскажите, а где у вас может случится подобная рекурсия, которая переполняет стек, очень интересно.
      0
      Не знаю как написать об этом в двух словах, когда разбирался с багом, долго не мог найти что приводило к переполнению.
      Вообщем был разработан асинхронный шаблонизатор для проекта josi (как раз планирую статью о технике которую использовал при его написании).
      В предыдущей версии в основе лежал цикл, который перебирал символы шаблона, выискивал включения, и заменял на что нужно, ну вообщем как обычно.
      Появилась идея — добавить возможность, во время парсинга шаблона, подгружать динамически другие шаблоны, и включать, после обработки, в текущий, что то вроде include php. При это необходимо обеспечить ассинхронность естественно. В этом случае обычный цикл пришлось заменить рекурсивным вызовом по fdone (завершению подгрузки запрошенного шаблона), с передачей текущего контекста парсинга. Учитывая при этом накладные расходы фреймворка (+3 последовательных вызова служебных функций), для парсинга сложного шаблона порой требовалось сделать и 700 и более вызовов, что и приводило к проблеме.
        0
        700 и более вызовов, как-то на мой взгляд прям много, хотел бы я посмотреть на такой шаблон и особенно смущает — «В предыдущей версии в основе лежал цикл, который перебирал символы шаблона, выискивал включения, и заменял на что нужно, ну вообщем как обычно.», как-то не выглядит это обычным для шаблонизатора.
        PS извиняюсь за назойливость и занудство, но думаю не только мне будет интересно узнать подробности.
          0
          Я только рад обсудить этот вопрос!
          В предыдущей версии в основе лежал цикл, который перебирал символы шаблона, выискивал включения, и заменял на что нужно, ну вообщем как обычно.
          — здесь я конечно хватил немного. Я имел ввиду, что принцип обработки шаблона так или иначе связан с перебором символов содержимого, по крайней мере, я не могу назвать какой либо другой возможный принцип поиска, допустим необходимого нам символа в тексте, без использования каких либо техник индексации и тд. Как правило(по крайней мере я бы точно сделал так), используется конструкция вида:

          eval_str=exp_str.replace(/(#[^#]+#)/g, f_var_replacer).
          

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

          Теперь что касается семи ста вызовов. Если честно, хотел бы расписать все по полочкам, с самого начала. Проект активно развивается и, сейчас, я наконец таки взялся за написание общедоступной документации. Где хочу расписать архитектуру, в том числе шаблонизатор, поскольку в него я вложил очень много труда. Конечно, я не претендую, на оригинальность, или самое лучшее решение, но удалось сделать то, что было запланировано, и это работает!
          700 вызовов, это не чистая цифра, и складывается она из 1 вызова эффективной функции, +3 накладных (диспетчер задач). Отсюда и цифра. Реально это 150-200 вызовов. В результате оптимизации число накладных вызовов было снижено до 2.
          Я не хочу углубляться в подробности отрывочно, поскольку не удастся передать суть, и обосновать те или иные решения… Статьи уже в работе. Буду рад если информация покажется Вам интересной и принесет пользу!
            0
            Да-да, обязательно буду ждать статью, а лучше несколько!
            0
            По хорошему большинство вызовов должно происходить один раз при компиляции шаблона.
            Интересно было бы взглянуть на код шаблонитизатора, сравнить с существующими.
              0
              Код тоже выложу, нужно над ним немного поработать, почистить. Когда начинал работу, еще не использовал CVS — много дублирующихся методов: f_1, f_2 и тд.
        0
        Ух, как же я соскучился по js-хакам… Давно не попадалось ничего подобного, спасибо автору!
          0
          Спасибо! Буду рад если пригодится!
          +2
          Ведь любая рекурсия в цикл разворачивается, зачем эти извращения?
            0
            В цикл нельзя привнести асинхронность. Именно этот фактор, заставил искать другое решение. И, да, очень согласен, если конечно верно понял Вашу мысль, — необходимо и достаточно! Этим принципом руководствуюсь в работе. Приведенное решение нужно тогда и только тогда, когда мы в целевой (рекурсивной) функции имеем конструкцию? результат выполнения которой возвращается в calback. В этом случае цикл нам не подходит, именно поэтому было применено это решение…
              +1
              В рекурсию тоже нельзя внести асинхронность. В любом случае «цикл» на SetTimeout вполне работает и без рекурсии.
                0
                Если не трудно приведите пример.
                Bижу это так:

                function f(args)
                {
                	var some_var1=args.some_var1;
                	var some_var2=args.some_var2;
                	...
                	var i=args.i;
                	
                	//куча полезного кода
                	
                	setTimeout(f(
                	{
                		i:i++,
                		some_var1:new_val,
                		some_var2:new_val2,
                		...
                	}),0);
                	
                }
                


                В любом случае это не цикл while…
            0
            Просветите, а что такое «AMD модуль»?
            0
            Только надо учесть, что в данном случае, функция из синхронной превращается в асинхронную. И результат придется получать в колбеке.
              0
              Да. Именно это и требуется. Код в котором применялась конструкция, полностью асинхронный, те все эффективные функцию имеют определенную сигнатуру, и обязаны поддерживать асинхронность.
              +1
              В свое время для асинхронной эвалюации абстрактного синтаксического дерева, я также искал решение данной проблемы, в результате набрел вот на это: 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();
              	}
              
                0
                Вместо list instanceof Array, лучше писать Array.isArray(list)
                  +1
                  Во — первых isArray присутствует лишь в последних версиях браузеров, во — вторых isArray это вызов метода (хоть и нативного), я думаю он будет немного медленнее чем обработка конструкции instanceof.
                    0
                    Если принимать первый аргумент, значит надо отказаться и от Object.keys (поддержка которого почти совпадает с поддержкой Array.isArray). А в подтверждение преимущества в производительности синтетические тесты.
                  0
                  У этого решения та-же проблема, с которой столкнулся автор статьи: высокой вероятность переполнения стека.
                  0
                  Автор, спасибо за статью. Суть вынес и сохраню: во избежание переполнения стека, организовывать рекурсию через триггер событий.
                    0
                    Рад, что мой опыт принес пользу!
                    0
                    Кажется, вместо setTimeout можно было использовать более продвинутую альтернативу в виде window.requestAnimationFrame с деградацией до setTimeout, задержка на косвенный вызов значительно снизится.
                      0
                      Спасибо за информацию! Буду тестировать этот вариант, обновлю статью для более полной картины…

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

                    Самое читаемое