10 сентября 2012 в 12:49

Отложенная обработка массива из песочницы

Однажды, при разработке сложного приложения на JavaScript-е возникла непреодолимая проблема — большой массив в Internet Explorer (далее IE). Так как я изначально проверял работу в Chrome, то не замечал каких-либо проблем при использовании массивов. Скажу больше — вложенные массивы не вызывали чувства страха. Chrome легко справлялся с трудными задачами. Однако IE, в очень жёсткой форме, указал на все мои огрехи и недостатки кода, особенно на обработку Больших массивов.

В двух словах


Разрабатываемое приложение должно было, в режиме реального времени, реагировать на события приходящие с сервера. Для этих целей воспользовались библиотекой Socket.IO, что позволило легко реализовать двухстороннее общение с сервером. При этом приложение также было завязано на сторонний сервис, к которому я имел доступ только через внешнее REST API.

Слабым звеном оказался большой цикл который должен был обрабатывать массив данных, полученные как раз со стороннего сервиса. При этом приходилось в цикле одновременно изменять DOM модель. В этих случаях IE уходил в состояние глубокой задумчивости и естественно рвал соединение. Чисто внешне это было неприемлемо — блокировка приложения и постоянно крутящийся значок загрузки не могли удовлетворить заказчика. Да, многие могут справедливо указать на большие затраты при изменении DOM модели. И должен вас заверить, что эта часть проблемы была решена выносом всех изменений за пределы цикла. Однако основная проблема — разрыв соединения при обработке массива осталась.

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

Алгоритм


Массив логически разбивается на несколько диапазонов, обработку каждого из которых производим с задержкой. Суть работы представлена на рисунке:



Таким образом имея единый глобальный массив Array функция обрабатывает его по частям, с заранее заданной задержкой. Для асинхронного язык, которым является JavaScript, данная техника позволяет разгрузить основной поток (так же один единственный) при обработки очень больших массивов.

Основное тело обработчика:
//Lazy array processing
/**
* Input parameters
* params = {
*   outerFuntion : function(array, start, stop),
*   mainArray: []
*   startIndex: Int,
*   stepRange Int,
*   timeOut: Int,
*   callback: function()
*}
*/
var lazyProcessing = function(params) {
    var innerFunction = (function(_) {
        return function() {
           var arrayLength = _.mainArray.length,
               stopIndex   = _.startIndex + _.stepRange;
            if(arrayLength < stopIndex) {
                _.outerFunction(
                       _.mainArray,
                       _.startIndex,
                       arrayLength - _.startIndex);
                if(_.callback != undefined) {
                    _.callback();
                }
                return;
            } else {
                _.outerFunction(
                       _.mainArray,
                       _.startIndex,
                       stopIndex);
                _.startIndex += _.stepRange;
                lazyProcessing(_);
            }
        }
    })(params);
   
    setTimeout(innerFunction, params.timeOut);
};
//Outer function works with mainArray in given range
var func = function(mainArray, start, stop) {
    //TODO: this should be everything you want to do with elements of
    for (var i = start; i < stop; ++i) {
        // do something
    }
};

В теле функции lazyProcessing создается локальная функция innerFunction, которая замыкает в себе полученные параметры params. Это позволяет каждый раз, при рекурсивном вызове функции lazyProcessing из себя, сохранять уникальные параметры.

Функция innerFunction возвращает безымянную функция, которая выполняет следующие достаточно простые действия:
  1. Проверяет достижение конца глобального массива
  2. Вызывает внешнюю функцию outerFuntion с различными значениям stop
  3. В случае достижения конца массива — вызывает callback функцию
  4. В противном случае рекурсивно вызывает lazyProcessing.

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

При достижении конца массива может быть вызвана callback функция, но это опционально.

За и против


Естественно в данном решении есть свои подводные камни и недостатки:
  1. Если установить stepRange минимальным, при достаточно большом mainArray массиве, можно банально «упасть» по переполнению стека
  2. Поток все же будет блокироваться при вызове внешней outerFunction. Т.е. быстродействие напрямую будет зависеть от алгоритма обработки элементов массива
  3. “Лапша” из вложенных и возвращаемых функций смотрится не очень дружественно

Вместе с тем, частичная обработка массива через равные промежутки времени — не блокирует поток выполнения программы. Что позволяет обрабатывать другие callback функции.

Полный работающий пример:
//Test array
var test = [];
for(var i = 0; i < 100000; ++i) {
    test[i] = i;
}
//Lazy array processing
/*
params = {
    outerFuntion : function(array, start, stop),
    mainArray: []
    startIndex: Int,
    stepRange Int,
    timeOut: Int,
    callback: function()
}
*/
var lazyProcessing = function(params) {
    var _params = params;
    var innerFunction = (function(_) {
        return function() {
            var arrayLength = _.mainArray.length,
                stopIndex   = _.startIndex + _.stepRange;
            if(arrayLength < stopIndex) {
                _.outerFunction(
                    .mainArray,
                    _.startIndex,
                    arrayLength - _.startIndex);
                if(_.callback != undefined) {
                    _.callback();
                }
                return;
            } else {
                _.outerFunction(
                    _.mainArray,
                    _.startIndex,
                    stopIndex);
                _.startIndex += _.stepRange;
                lazyProcessing(_);
            }
        }
    })(_params);
   
    setTimeout(innerFunction, _params.timeOut);
};
//Test function works with array
var func = function(mainArray, start, stop) {
    //TODO: this should be everything
    //you want to do with elements of mainArray
    var _t = 0;
    for (var i = start; i < stop; ++i) {
        mainArray[i] = mainArray[i]+2;
        _t += mainArray[i];
    }
};
lazyProcessing({
        outerFunction: func,
        mainArray: test,
        startIndex: 0,
        stepRange: 1000,
        timeOut: 100,
        callback: function() {
                    alert("Done");
                  }
        });



PS. Пользователь zimorodok скинул замечательный пример — такой же по духу и по сути. Не могу не добавить его.
Проход по массиву с callback-ом для каждого элемент с возможностью задавать timeOut:
/*
example of use
var arr = ['masha','nadya', 'elena'];
iterate_async(arr, function (el, index, arr) {
    console.log(el + ' is #' + (index + 1));
}, 99);
*/
function iterate_async (arr, callback, timeout) {
	var item_to_proceed;

	item_to_proceed = 0;
	(function proceed_next () {
		if (item_to_proceed < arr.length) {
			setTimeout(function () {
				callback.call(arr, arr[item_to_proceed], item_to_proceed, arr);
				item_to_proceed += 1;
				proceed_next();
			}, timeout || 50);
		}
	}());
}
+4
5185
42
MaxAmon 1,0 G+

Комментарии (14)

0
spmbt, #
В 2 словах, если задача на JS занимает много времени выполнения, разбиваем её на части?
Действительно ли падает по переполнению из-за малого (нулевого) timeOut или, всё же, из-за малого stepRange, а timeOut ==0 допустимо? И какая версия IE?
–1
MaxAmon, #
1. Да! Разбиваем на подзадачи и каждую вызываем асинхронно (в случае если основная задача «не прерываемая», например — цикл).
2. Вы правы! Строго говоря — падает при малом stepRange, т.е. timeOut можно выставлять в 0.
3. IE 7 и 8
+1
spmbt, #
Про таймаут как раз был основной вопрос, потому что выставление 200мс показалось странным и была мысль: неужели какому-то старому IE это критично? Разбивание JS на части — это обычная практика давать допуск рендереру DOM и аяксу периодический доступ к обработке, и в ней достаточно указывать паузу в 0 мс (или символические 1 мс), а далее движок скрипта сам разбирается, какие задачи выполнять и какие минимальные паузы он может себе позволить.
0
MaxAmon, #
Тоже верно. Приложения в основном стараются проектировать так, что бы можно было логически разбить JS на части. Каждая часть становиться «чистой» функцией.
А вот когда проектное решение хромает на обе ноги, и от него уже нельзя отказаться, приходится придумывать подобное этому — постепенную (последовательную) обработку цельного массива данных через равные (>0) тайм-ауты.
200мс — поставлено для наглядности.
0
qw1, #
Эх, если бы кто в js реализовал такую магию, как «async» в C#5, когда встречается фунция Sleep (или любая другая псевдо-блокирующая), текущая функция бы прерывалась и возвращала управление главному потоку, а после завершения псевдо-блокирующей операции (для sleep — сигнал таймера), выполнение бы продолжалось с точки прерывания без потери контекста.
0
MuLLtiQ, #
JavaScript асинхронен и однопоточен — там не нужна функция Sleep
0
qw1, #
Значит, идея не понята :)
Идея в том, что пишешь алгоритм как обычно.
Но если встречается Sleep(x), то на этом функция завершается, а остаток заворачивается в аргумент setTimeout(x).
Вот такой синтаксический сахарочек, прозрачно для программера.
0
MuLLtiQ, #
Ах, ну в этом случае да :)
+1
tenshi, #
nin-jin.github.com/article/article_fiber/article_fiber.doc.xml
работает в мозилле (с типом «application/javascript;version=1.7») и хроме (при включённом «экспериментальном JavaScript»)
осталось дождаться пока генераторы появятся в остальных браузерах
0
MuLLtiQ, #
> Вместе с тем, частичная обработка массива через равные промежутки времени — не блокирует основной поток выполнения программы. Что позволяет обрабатывать другие callback функции.

Нет в JavaScript потоков. И основного потока нет. Есть только текущий «контекст» исполнения — асинхронные обработчики выстраиваются в очередь и ждут пока он не закончит свою работу и переключится на следующий.
0
MaxAmon, #
Да, получилось не корректно. Словосочетание «основной поток» подразумевает что есть и не «основные». Спасибо исправил.
0
jazzz13, #
Однако основная проблема — разрыв соединения при обработке массива осталась.
Скажите, а если делать временные промежутки обработки еще короче, соединение все таки можно спасти?

PS. При прочтении я ошибочно думал, что задача — отсортировать массив, поэтому долго не мог понять, как Вы это сделали…
0
MaxAmon, #
Временные промежутки можно делать короче. Однако, думаю вы не правильно поняли — первоначально в коде был большой массив, внутри которого так же было много тяжелых действий. Когда IE начинал обрабатывать его, он мог «заморозиться» на неопределенное количество секунд, что чудесным образом приводило к разрыву соединения. При окончании цикла, начиналась свистопляска с пере-подключением и перерисовкой интерфейса. Одним словом — это критическое место в программе приводило к абсолютно не корректному поведению приложения.
Большой временной промежуток был специально поставлен, что бы массив (скорость обработки которого была не критична) обрабатывался очень редко и очень медленно — имулируя работу в background-е.
Таким способом отсортировать массив думаю можно, хотя это потребует некоторых изменений.
0
zimorodok, #
Решал подобную задачу.
Функция отрисовки путей на гуглокарте подвешивала браузер для более 20 путей. Тогда для того, чтобы давать интерфейсу отрисовываться, написал асинхронный итератор по массиву. И применял его для массивов более 15 элементов.

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