В конце прошлого года я решил развить концепцию, которую я использовал в проекте imaginegenerator, который я написал в студенчестве. То приложение принимало 3 JavaScript выражения для каждого канала (RGB) и для каждой точки изображения с разными значениями переменных выполняло эти выражения, вычисляя цвет этой точки. Не смотря на то, что по понятным причинам рендеринг картинки таким способом требовал некоторое время, сам по опыт интересный в плане эксперимента над тем, как можно преобразовывать формулы в картинки. По сути, это похоже на то, как работают шейдеры в видеокартах, за исключением того, что сам по себе код гораздо тормознее, чем нативный и не параллелится. «Expression-Picturizer» является продолжением этой идеи.
Мотивация
JavaScript это хорошо, но хотелось бы иметь специальный язык выражений, для которого было бы легко написать программу транслятор в нативный код, или как в случае с Expression-Picturazer в JVM байткод, который оптимизировался бы JIT компиляцией. С одной стороны, я понимал, что на CPU я не могу превзойти скорость рендера, который я мог бы достичь на видеокарте при помощи шейдеров либо CUDA, однако такой цели у меня и не стояло. Я хотел достичь достойной производительности на CPU. Причем если это удастся достичь на чистой JVM безо всяких JNI вызовов в нативный код, то хороший результат будет более впечатляющим. Таким образом, список требований у меня был такой:
- В программе должен быть транслятор из формулы, написанной в математической нотации, в код.
- Генерированный код не должен или должен по минимуму содержать паттерны, которые общепринято негативно влияют на производительность — аллокации объектов, частый вызов методов, хранение промежуточных результатов в виде объектов. В конечном итоге для генерированного кода был выбран интерфейс, который принимает массив int значений для записи туда результата работы алгоритма.
- По этой же причине недопустим любой частый интероп между рантаймами, вроде JS-C, JS-Java, Java-C и так далее.
- Должна быть возможность сделать многопоточную отрисовку. Хотя в данный момент Expression-Picturizer умеет делать рендеринг только в один поток, архитектурно нет ограничений сделать это в несколько потоков. Во всей программе нет точек синхронизации, которые бы помешали эффективно разбить задачу на части и выполнить в параллель. Напротив, если используется JavaScript, то сам рантайм в JavaScript не потокобезопасен, не параллелится и в принципе не имеет никаких средств для синхронизации потоков. Единственный способ использовать много потоков с JavaScript — это создать много экземпляров среды выполнения JavaScript.
- Поскольку структуры в JVM недоступны, а аллоцировать объекты нельзя, вычисления для каждого канала должны быть независимы с использованием примитивов.
Архитектура
Приблизительно последний год или два, мне нравится функциональный подход к описанию программы. В действительности часто для описания программ удобно использовать модель, представляющую программу как цепочку преобразований над данными, которая в процессе применения множества операций преобразуют данные из того, что подается на входе в то, что программа выдает на выходе. И Expression-Picturizer, мне кажется, не исключение.
Давайте попробуем рассмотреть программу с точки зрения потока данных, который трансформирует формулу в картинку:
- На входе в программу подается текстовое представление формулы, которую пользователь вводит через GUI.
- Парсер преобразует текстовое представление формулы во внутреннее представлений дерева операций. Сначала используется парсер, который генерирован из грамматики языка выражений при помощи ANTLR, затем получившееся дерево трансформируется в дерево операций, с использованием шаблона «Посетитель».
- В дальнейшем дерево операции изменяется при помощи различных преобразований. Основные преобразования перечислены в объекте Mappings. Порядок применения преобразований виден в функции compileExpression. Сначала применяются общие преобразования, затем преобразование общего дерева в деревья специфичные для каждого цветового канала. В конце деревья каждого цветового канала редуцируются с целью уменьшения числа операций.
- Кодогенератор создает класс, который реализует интерфейс Renderer. Сама внутренняя анатомия собирается в классе RendererDump. Внутри метода render создается цикл, который проходит по всему массиву, выполняет выражения и сохраняет цвета. А генерация вставляемого кода из деревьев операций происходит в TreeBasedCG. В JVM используется стек машина. Это означает, что для того, чтобы произвести операцию нужно сначала положить значения в стек, а затем произвести операцию. В своем роде, это похоже на код в императивном стиле, который выложен в стиле обратной польской записи. К счастью, используя шаблон посетитель, преобразовать деревья в обратную польскую запись не сложнее, чем в выражения в обычной нотации(в обычной нотации даже сложнее, поскольку обратная польская запись позволяет не обращать внимания на приоритет операторов). Другое дело, если бы мне пришлось вместо стека операндов использовать именные регистры процессора.
- Программа загружает генерированный класс, создает его инстанс и приводит к интерфейсу Renderer, для того, чтобы можно было использовать генерированный код.
- У полученного объекта вызывается метод render. Получившийся массив записывается в AWT объект BufferedImage.
В итоге, после прохождения через весь поток данных, у нас эта математическая формула становится картинкой.