Repository navigation
Article RUS
С операциями в javascript, требующими длительных вычислений и тормозящими компьютер, программисту приходится сталкиваться нечасто. Современные браузеры умеют максимально изолировать проявления эгоизма со стороны программы. Но когда дело все же доходит до того, что скрипт выполняется дольше, чем нужно, это видно сразу: страница перестает реагировать на прокрутку и наведение мышью, перемещение указателя мыши начинает запаздывать, а в крайних случаях, сам браузер сообщает вам, что выполнение скрипта занимает больше времени, чем предполагалось, и предлагает нам прервать его выполнение. В nodejs, кстати, все хуже: код выбивается в лидеры среди потребителей CPU и начинает безнаказанно тормозить компьютер. Такое поведение программы крайне нежелательно и каждый, программист или пользователь, безусловно страдал от этой проблемы.
Эта статья предназначена для программистов и посвящена описанию библиотеки, которая, по моему мнению, поможет элегантно обойти «тормоза» скрипта, а её использование – будет интуитивным и не потребует запоминания большого количества информации.
Сразу скажу, что если Вам неинтересно читать про предпосылки написания модуля, которому посвящена эта статья, то я приглашу Вас сразу ко второй части.
Итак, есть у нас проблема. Проблема «задумчивого скрипта». Как правило, она связана с обработкой длинного списка с большим количеством элементов, например, большим 10 000. Бывают и другие примеры. Я столкнулся с ней лет десять назад. Наш код должен был расставлять теги мягких переносов на странице в довольно длинном тексте. Текст был слов эдак на пять тысяч, переносов – раза в два-три больше. Мы были еще зелены: не знали про оптимизации при работе с DOM, вставку переносов производили шаг за шагом. В общем, страница «залипала» секунд на пять-десять при каждой загрузке. Сейчас мы стали старше и умнее, браузеры – быстрее, да и DOM мы умеем обновлять, как надо, грамотно. Но задачи, «вешающие» страницу, не исчезли. Например, два вложенных цикла для пробегания значений x и y от -10 до +10 с шагом в 0.1 – и вот вам кандидат в слоупоки. А если в теле цикла запланирован расчет функции для этих переменных, то подвисание практически гарантировано.
Решение данной проблемы, как многие согласятся со мной, у каждого сводилось к изобретению велосипеда. Вот и Незадачливый Программист Андрей совершает примерно следующие шаги при написании неподвисающего кода для обработки цикла из 40000, или (10 - (-10)) / 0.1) ^ 2, шагов ..
for (var y = -10; y < 10; y += .1) {
for (var x = -10; x < 10; x += .1) {
var t = x * x - y * y;
y = 2 * x * y;
x = t;
plot(x, y);
}
}Вначале он выносит тело цикла в отдельную функцию (например, doOperationFor(x, y)) и вызывает ее из тела setInterval, изменяя затем переменные цикла, и прерывая интервал, когда они достигнут граничных значений. Вот, например, так.
var x = -10, y = -10,
interval = setInternal(function(){
doOperationFor(x, y);
x += .1;
if (x > 10) {
x = -10;
y += .1;
if (y > 10) {
clearInterval(interval);
}
}
}, 0);Либо заворачивает тело цикла в именованную функцию и перезапускает ее через setTimeout до тех пор, пока переменные цикла не достигли граничных значений:
var x = -10, y = -10,
worker = function(){
doOperationFor(x, y);
x += .1;
if (x > 10) {
x = -10;
y += .1;
if (y > 10) {
return;
}
}
setTimeout(worker, 0);
};
setTimeout(worker, 0);Функция-параметр setInterval/setTimeout вызывается только тогда, когда браузер освободился от прочих процессов. Тем самым, исполнение долгих циклов не подвешивает программу.
Казалось бы, наш Незадачливый Программист Андрей справился с задачей, страница перестала подвисать. Однако общее время обработки цикла заметно выросло.
Накладные расходы на постановку задачи на исполнение через setTimeout/setInterval намного выше простого вызова функции.
Тогда Незадачливый Программист Андрей делает второй шаг в «изобретении велосипеда». Шаги, содержащиеся в функции, можно исполнить заново несколько раз, прежде чем поставить её в очередь на повторное исполнение.
Сколько раз это «несколько», конкретно? Тут программист решает либо навскидку: скажем, цикл из 150 шагов, а потом – перепостановка в очередь. Либо он подходит творчески. Тогда он дописывает три строчки кода, которые следили бы за тем, чтобы общее время выполнения функции по циклу не превышало установленного времени. Скажем, 100 миллисекунд. Подвисание браузера на 100 мс едва ли будет замечено пользователем. Страница не замрет. Между тем, за это время может быть выполнено 50-200 шагов цикла (!).
var x = -10, y = -10,
interval = setInternal(function(){
var timestamp = new Date(); // *** NEW
do { // *** NEW
doOperationFor(x, y);
x += .1;
if (x > 10) {
x = -10;
y += .1;
if (y > 10) {
clearInterval(interval);
return;
}
}
} while ((new Date() - timestamp) < 100); // *** NEW
}, 0);Итак, еще одна проблема решена. Скорость обработки возросла, лагов по-прежнему нет. Программист доволен собой и хочет, чтобы его решением воспользовались коллеги для выполнения собственных задач. Обобщение в первом приближении выглядит так:
// *** вынесли в именованную функцию
function nestedFor(xMin, xMax, xStep, // *** значения можно передавать,
yMin, yMax, yStep, // *** они больше не в хардкоде
operation, // *** сама операция также передается в виде ссылки на функцию
doneCallback, // *** окончание операции "зовет" колбэк, что важно для
batchMs){ // асинхронных задач
var x = xMin, y = yMin,
interval = setInternal(function(){
var timestamp = new Date();
do {
operation(x, y);
x += xStep;
if (x > xMax) {
x = xMin;
y += yStep;
if (y > yMax) {
clearInterval(interval);
doneCallback();
return;
}
}
} while ((new Date() - timestamp) < (batchMs || 100));
}, 0);
}Но как ни крути, такое решение пока не назовешь общим. Часть логики цикла осталась прочно привязанной к внутренностям nestedFor().
Незадачливый Программист Андрей понимает, что все переменные, используемые в действительно общей задаче, надо сгруппировать вместе, да так, чтобы к ним имели доступ и тело цикла, и логика проверки условий цикла и логика изменения переменных цикла, ко всем вместе. Его мысль цепляется за группировку всех переменных в объекте состояния, state. Операциям, которые изменяют переменные цикла, он повелевает быть в функции с именем updateFn. Логике проверки условий цикла – в функции conditionFn. А телу цикла – в функции bodyFn. Тогда получается такая картина:
// *** функция splitTask принимает..
function splitTask(state, // *** объект-состояние цикла, со всеми нужными данными
conditionFn, // *** функция с логикой проверки условий цикла
updateFn, // *** ф-ция с логикой изменения переменыых цикла
bodyFn, // *** ф-ция с логикой тела цикла
doneCallback, batchMs) {
var interval = setInternal(function(){
var timestamp = new Date();
do {
if (conditionFn(state)) { // после проверки условий..
bodyFn(state); // мы либо выполняем тело цикла и
updateFn(state); // изменяем переменные цикла
} else { // либо прерываем исполнение
clearInterval(interval);
if (doneCallback) doneCallback(state);
return;
}
} while ((new Date() - timestamp) < (batchMs || 100));
}, 0);
}Отделение конкретной задачи от логики обеспечения независающего процесса, похоже, закончено. Вот как будет выглядеть код первоначальной задачи, но сейчас уже использующий splitTask():
splitTask({
x: -10, xMin: -10, xMax: 10, xStep: .1,
y: -10, yMin: -10, yMax: 10, yStep: .1
},
function(state) {
state.x += state.xStep;
if (state.x > state.xMax) {
state.x = state.xMin;
state.y += state.yStep;
}
},
function(state) {
return (state.y <= state.yMax);
},
function(state) {
operation(state.x, state.y);
}
);Казалось бы, обобщенная реализация «неподвешивающего алгоритма» завершена. Но и сейчас можно найти ряд недостатков у этого кода:
- объект
stateв примере использования встречается 15(!) раз. Так и логики не разглядеть. - объявление этого
stateуж что-то сильно громоздко. Да еще и приходится переменным x и y присваивать те же значения, что и xMin и yMin соответственно. - при вызове
splitTask(..)надо запоминать порядок следования функций-параметров. Что идет раньше, проверка на условие или изменение переменных цикла? Хм. Уже не помню. - то, что у нас получилось, совсем не похоже на простой и понятный код:
// yMin, yMax, yStep, xMin, xMax, xStep, operation
for (var y = yMin; y < yMax; y += yStep) {
for (var x = xMin; x < xMax; x += xStep) {
operation(x, y);
}
}В самом деле, здесь прозрачно все - объявление переменных, их инициализация, условия цикла, изменения переменных цикла, да и само тело; и главное, каждому, кто посмотрит, понятно, что за чем следует.
Как же спроектировать такой удобный и понятный в использовании модуль? Чтобы было удобно передавать данные.. Чтобы задавать функцию-тело цикла.. Да так, чтобы она видела переданные данные, могла их менять и не требовала доступа к ним через объект (ни state, ни this).. Чтобы логика, определяющая, что достигнут конец цикла, не требовала много места и справлялась со своей задачей?
Каждый раз, будучи этим Незадачливым Программистом Андреем, я по-разному отвечал на эти вопросы и делал реализации, которыми так никогда и не оставался доволен. До тех пор, пока мне не пришла в голову мысль поставить все с головы на ноги. Так родилась библиотека crunchtask.
Библиотека CrunchTask для описания нетормозящей задачи-цикла опирается на основные части простого цикла for:
// на входе - очень длинный массив arr.
for (var i = 0, iMax = arr.length; i < iMax; i++) {
// инструкции;
}Итак, var i и var iMax – это объявление переменной(-ных) цикла (декларация переменных),
i = 0, iMax = arr.length – это инициализация (или первичное присвоение),
i < iMax – условие цикла,
i++ – изменение переменной цикла,
a // инструкции; – это тело цикла.
Объявление переменных цикла считается самой первой операцией. В javascript она производится даже раньше, чем начинается исполнение цикла, на этапе анализа всего исполняемого блока.
Затем, когда интерпретатор приступает к исполнению цикла, однократно исполняется логика инициализации переменных цикла.
Перед каждой итерацией выполняется вычисление условия цикла. Если результат вычисления является истинным, инструкции тела цикла выполняются. В противном случае выполнение цикла завершается.
После каждой итерации вычисляется выражение изменения переменной цикла.
Более того, как мы знаем из теории программирования, переменные цикла определены только в теле цикла и не существуют вне его.
Я вдохновился этими знаниями о составных частях цикла, чтобы описать цикл по-другому. Сравнивая эту реализацию с тем, к чему мы пришли в первой части, можно даже сказать не «по другому», а «шиворот-навыворот», или лучше - «с головы на ноги». Смотрите сами:
// описание задачи
var forTask = new CrunchTask(function(init, body){
// декларация:
var i, iMax;
init(function(arr){
// инициализация:
i = 0;
iMax = arr.length;
});
body(function(resolve){
// условие цикла:
if (i < iMax) return resolve();
// тело цикла:
// инструкции;
// изменение переменной цикла:
i++;
});
});Эту задачу-цикл можно выполнить с arr в качестве входных данных:
forTask.run(arr);а можно и с другими данными, например с arr2:
forTask.run(arr2);Их выполнение может совпасть по времени - как это бывает с асинхронными задачами. Ближайшая аналогия работы - это параллельные вычисления в тех языках, кторые поддерживают параллельное исполнение. Javascript его лишь эмулирует.
Название для библиотеки дали два слова - Crunch и Task. Первое слово, crunch, означает "дробить", - это как раз то, что делает эта библиотека: большой цикл дробится на элементарные части и исполняется пакетами по мере возможности. Crunch, также ассоциируется у меня с тем, что делал главный герой фильма "Теорема Зеро", - он "дробил сущности" ("crunch entities"). Второе слово, task, задача, ассоциативно отсылает к названию класса, представляющего собой асинхронную операцию в .Net Framework, - Task из пространства имен System.Threading.Tasks.
Собственно, разбивая выполнение цикла на части, мы переводим его в класс асинхронных задач. Таким образом, экземпляр класса CrunchTask - это описанная асинхронная задача, выполнение которой будет раздроблено на части.
Описывать задачу совсем несложно.
Асинхронная задача описывается так:
var task = new CrunchTask(/* descriptionFn */);А вызывается так:
task.run(args);Функция descriptionFn - ее лучше вписывать (inline) в виде аргумента к конструктору для наглядности (а не определять отдельно) - служит для предоставления общей области видимости для кода инициализации, кода описания тела, и кода завершения. И, конечно же, она предоставляет возможность определения этих трех важнейших шагов цикла: инициализации, тела цикла вместе с условиями цикла и изменением переменных цикла, а также финализации при помощи трех функций: initSetup, bodySetup и finallySetup, - передаваемых в descriptionFn в виде трех параметров: init, body, fin соответственно:
var task = new CrunchTask(function(init, body, fin){
// декларация переменных цикла
var x, y, xMin, xMax, yMin, yMax;
// описание инициализации: init(...);
// описание тела цикла: body(...);
// описание финализации: fin(...);
});Инициализация переменных цикла описывается так:
var task = new CrunchTask(function(init, body, fin){
var x, y, xMin, xMax, yMin, yMax;
// описание инициализации. initSetup принимает один параметр - initFn:
init(function(_xMin, _xMax, _yMin, _yMax){
xMin = _xMin; xMax = _xMax; yMin = _yMin; yMax = _yMax;
x = xMin;
y = yMin;
});
// описание тела цикла
// описание финализации
});Пользуясь тем, что из функции initFn, описанной inline, видны переменные из descriptionFn, фактические значения переменных цикла, переданные задаче в момент ее исполнения - task.run(-10, 10, -10, 10) - , могут быть присвоены уже объявленным переменным цикла.
Описание тела цикла ничуть не сложнее (как и описание финализации):
var task = new CrunchTask(function(init, body, fin){
var x, y, xMin, xMax, yMin, yMax;
init(function(_xMin, _xMax, _yMin, _yMax){
xMin = _xMin; xMax = _xMax; yMin = _yMin; yMax = _yMax;
x = xMin;
y = yMin;
});
// описание тела цикла.
// bodySetup принимает первым параметром bodyFn(resolve, reject, notify):
body(function(resolve /*, reject, notify*/){
// условие цикла
if ((x > xMax) && (y > yMax)) {
resolve();
return;
}
// operation
plot(x, y);
// измениение переменных цикла
x += .1;
if (x > xMax) {
x = xMin;
y += .1;
}
});
// описание финализации
fin(function(isSuccess){
// эта чать может пригодиться в диагностических целях или для "уборки"
});
});Все целиком: