Фракталы — использование Web Workers API

Общее описание сайта и математическая теория здесь.

После того, как определен способ вычисления функции f (за счет синтаксического разбора), остается вычислить «скорость убегания» P(z, f) для комплексных чисел z, соответствующих отдельным пикселям изображения. Наиболее простой способ вычислений — цикл по всем пикселям. Фатальный недостаток этого метода состоит в том, что подсчеты занимают существенное время (порядка нескольких секунд или десятков секунд), и во время выполнения цикла браузер перестает отвечать на внешние раздражители, что, разумеется, неприемлемо. К счастью, для этой проблемы есть решение — современные браузеры (Firefox, Chrome, IE 10+) поддерживают выполнение JavaScript-кода в фоновых потоках выполнения.

Фоновые потоки исполнения определяются классом Worker. Для обмена данными между фоновыми потоками и основной нитью выполнения JavaScript используются сообщения — произвольные объекты JavaScript (ограничения при передаче данных все же присутствуют; о них — чуть позже). Разделяемой памяти между различными потоками выполнения не существует: все данные при передаче клонируются. Это заметно упрощает задачу синхронизации ценой увеличения потребляемой памяти.

Контекст выполнения в фоновых потоках отличается от контекста основной нити выполнения JavaScript (то есть переменной window). Вместо этого используется экземпляр интерфейса WorkerGlobalScope. Таким образом, возможности фоновых потоков несколько ограничены: в них, например, недоступны элементы HTML-документа; зато можно загружать другие сценарии JS и делать асинхронные HTTP-запросы. Детальное описание инструментов, доступных в фоновых потоках, есть на сайте MozDev. Для задачи рисования фракталов потоки подходят хорошо: в вычислениях используется встроенная арифметика JavaScript.

Для создания потока требуется указать JavaScript-файл, код из которого будет исполняться (дополнительные JS-файлы, если требуется, можно загрузить в этом файле при помощи глобальной функции importScripts). Для обмена сообщениями используются две глобальные функции в контексте фоновых потоков и соответствующие методы класса Worker:

  • postMessage(obj) — передает произвольные клонируемые данные JavaScript (например, число, строку или объект Object) между потоками.
  • onmessage(event) — обрабатывает поступающие из других потоков данные. event — это объект со следующими полями:
    • поле data содержит переданные данные;
    • поле target равняется передавшему данные потоку.

Простейший пример, в котором фоновый поток используется для сложения чисел:

Более полезный пример с использованием нескольких фоновых потоков:

Для того чтобы понять, для какого набора чисел фоновый поток вычислил сумму, нужно усложнить структуру передаваемых сообщений. Основной поток передает вместе с числами идентификатор — номер набора в векторе addSamples. После выполнения вычислений фоновый поток возвращает сумму вместе с этим идентификатором.

Структура сообщений

Во многих задачах, в частности для построения фракталов, имеет смысл передавать фоновым потокам несколько типов сообщений.

В начале вычислений надо передать информацию о вычисляемой функции f и другие параметры (граничное расстояние D, максимальное количество итераций N, прямоугольник в пространстве комплексных чисел, для которого производятся вычисления). Эта информация одинакова для всех обрабатываемых точек, так что дублировать ее не имеет смысла. При этом f не получается передать в виде экземпляра класса Function, так как функции в JavaScript не клонируются; надо использовать полученную в результате синтаксического разбора обратную польскую запись и список переменных / чисел.

Другой тип сообщений необходим для вычисления значений P(z, f) для некоторого набора точек z. Из-за того, что точек много (около миллиона для более-менее приличного размера изображения), отправлять сообщение для каждой из них по отдельности неразумно; лучше вычислять значение P(z, f) по строкам или столбцам изображения. В таком случае каждое сообщение можно задавать единственным числом — индексом строки или столбца. Ответное сообщение, отправляемое фоновым потоком выполнения, содержит массив со значениями функции P.

Унификация с выполнением в основном потоке

Для отладки и в качестве запасного варианта имеет смысл оставить возможность производить вычисления в основном потоке. Для этого можно объявить в основном сценарии фонового потока класс, копирующий функциональность Worker:

Если сценарий используется в фоновом потоке, то методы класса привязываются к глобальным функциям:

Этот же сценарий можно использовать в основном потоке (загрузив его, например, в HTML):

Контроль хода вычислений

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

У пользователя также должна быть возможность прервать вычисления. Для поддержки прерывания надо изменить организацию передачи сообщений: единственный способ отменить обработку сообщений в фоновом потоке после его ссылки — остановить поток с помощью метода terminate и при новых вычислениях создать его заново. Это плохая практика, так как остановленные потоки не сразу высвобождают оперативную память. Более разумно отсылать сообщения потокам по одному каждый раз, когда очередная порция данных им обработана.

Если во время выполнения вычислений меняются исходные данные (например, в результате действий пользователя), вычисления надо начинать заново. Для того чтобы различать результаты вычислений, которые соответствуют актуальным и устаревшим входным данным, достаточно передавать с сообщениями специальную переменную — идентификатор запуска (например, целое число). Если возвращенные данные имеют идентификатор, отличный от текущего, их можно игнорировать. Та же переменная служит для прерывания вычислений: достаточно присвоить ему специальное значение, не встречающееся среди «реальных» идентификаторов запуска.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *