Lua+FFI vs. JavaScript

Эта небольшая заметка не претендует на звание статьи.

В прошлый раз я сравнивал LuaJIT 2.0 Beta 5 и JavaScript в различных браузерах на примере простого рейтрейсера. Результат сравнения: JavaScript в Chrome набрал 20,000 RPS и занял 1-ое место, а LuaJIT — 5,000 RPS и последнее место.

С выходом LuaJIT 2.0 Beta 6 ситуация изменилась: Lua легко вышел на первое место обогнав Chrome. Посмотрим как это получилось.



Представьте, что у вас есть большой массив который нужно заполнить числами. Как вы это сделаете? Вот пример реализации на Lua:

a = {}
for i = 1, n do
  a[i] = i*i - 0.5
end

Для больших n это работает очень медленно: Lua не знает заранее какого размера будет массив и потому вынужден увеличивать размер этого массива динамически. Lua даже не знает, что индексы массива — числа в диапазоне 1..n, а значения — целые числа, поэтому ему приходится рассчитывать на худший вариант когда однажды в массив запишут вот так:

a['qqq'] = {red = 1, green = 0.5, blue = 0.8}

Эта универсальность тормозит программу. Хочется как то сообщить Lua, что у нас есть массив вида «double a[n]». Стандартными средствами Lua это сделать нельзя, но к Lua можно дописать расширение — язык это позволяет — и получить то что нужно. Это расширение называется FFI. Вот как решается проблема с массивом:

ffi = require'ffi'
a = ffi.new('double[?]', 1 + n)
for i = 1, n do
  a[i] = i*i
end

Это простое изменение кода в разы увеличивает скорость и в разы сокращает память. Как раз то, что нужно для рейтрейсера.

Предыдущий рейтрейсер хранил в памяти таблицу состоящую из цветов — маленьких таблиц с трёмя полями. Через каждый пиксель запускался луч, вычислялся его цвет и этот цвет попадал в таблицу. Это выглядело примерно так:

pixels = {}

for x = 1, width do
	for y = 1, height do
		local color = raytrace(x, y)
		pixels[y*width + x] = color
	end
end

Во время работы эта таблица пикселей росла, время добавления нового элемента тоже росло, а скорость рейтрейсера падала. Результат — 5,000 RPS (лучей в секунду) и последнее место.

С появлением FFI стало возможным представить таблицу pixels в виде массива, заранее выделив память. Алгоритм стал таким:

ffi = require'ffi'
pixels = ffi.new('float[?]', width*height*3)
i = 0

for y = 1, height do
	for x = 1, width do
		local color = raytrace(x, y)
		
		pixels[i + 0] = color[1]
		pixels[i + 1] = color[2]
		pixels[i + 2] = color[3]
		
		i = i + 3
	end
end

Код стал немного длиннее чем раньше, но зато в других местах код упростился: например сохранять в BMP файл такой массив проще. Эта простая оптимизация даёт три вещи:

1. Объём памяти сокращается до 25 мегабайт и не растёт во время работы.
2. Скорость рейтрейсера не зависит от размера получаемой картинки.
3. Скорость возрастает до 40,000 RPS

Для сравнения: лучший результат прошлого сравнения — JavaScript+Chrome — получил 20,000 RPS и потратил 150 Мб памяти.

Ниже результаты теста частично взятые из прошлого сравнения. Программы рейтрейсили одну и ту же сцену на экран 1000×1000 пикселей пропуская по 3 луча через каждый пиксель.

LuaJIT	40,000 RPS	25 Mb
Chrome	20,400 RPS	150 Mb
Opera	15,700 RPS
Firefox	9,300 RPS
Explorer	9,000 RPS

Осталось сказать, что рейстрейсер на Lua я написал прямолинейно и он при каждой операции над векторами (сложение, умножение на число) создаёт новый вектор с результатом. Эта куча постоянно создаваемых векторов создаёт работу сборщику мусора. Если не создавать лишних векторов, то скорость рейтрейсера ещё увеличится.

Рейтрейсер о котором я говорил лежит здесь. Запускать командой «luajit main.lua». Версия luajit не ниже 2.0 Beta 6.