Lua+FFI vs. JavaScript

    SmallPic

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

    В прошлый раз я сравнивал 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.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 22

      –7
      Идиотское название, если честно. Или там действительно какой-то FFI?
        0
          0
          Аргументируйте.
            +1
            Ссылочку выше дали. Ну или en.wikipedia.org/wiki/Foreign_function_interface.

            Кусок из поста, который ввел меня в заблуждение
            >> Это расширение называется FFI

            Это не расширение так называется, которое позволяет делать быстрые malloc, а технология написания расширений. В том числе и вот того, которое в статье приведено.
          0
          Уверен, и в Джаваскрипте есть куда оптимизировать)
            +4
            Почему бы вам не выложить всё это на ГитХаб?
              0
              Зачем? Это же простой пример рейтрейсера который можно написать за полдня.
                +10
                У вас есть пример Рейтрейсера на JS + два примера на Lua. К примеру, я бы зашёл и обнаружил, что вы пошли очень неоптимальным путём в JS и повысил бы скорость с 20к до 50к, потом кто-то бы добавил код на Java, которая выдает 60к и т.д.

                В конце концов, если это просто простой пример рейтрейсера, то зачем его вообще делать? ;)

                Я бы посмотрел на исходники в удобном виде.
                  +6
                  Если это выложить не гитхаб, то через некоторое время у вас будет полноценный рендер на javascript
                    0
                    Так это же отлично!
              0
              Вот теперь я доволен результами теста. Спасибо =)
                +3
                Чем вы довольны? Тем, что в Lua оказались серьезные проблемы с массивами/аллокацией, которых удается избежать даже в джаваскрипте, при том, что в последнем внешне массивы устроены также (массив — одновременно hash)? И что эти проблемы лечатся только низкоуровневыми хаками?

                Вообще крайней странная идея совмещать вектор и хэш, зачем это надо было — неизвестно, а к чему приводит — вот, хорошо видно.
                  0
                  Идея, может быть, неортодоксальная, но работает отлично.

                  Просто не нужно её насиловать.

                  Если пишете код на Луа, нужно писать код на Луа, а не имитировать яваскрипт и удивляться, почему всё так плохо работает.
                +2
                А что мешает преаллоцировать массивы в JavaScript и использовать там же иные оптимизации?
                  0
                  Выложите трейсеры в GitHub-репозиторий.
                    0
                    Ок.
                      +1
                      Git-git ура!
                  +3
                  читерство :-)

                  в браузерах есть webgl typed arrays (new Float64Array(length)), но Crankshaft их еще не оптимизирует, но будет.
                    0
                    Lua даже не знает, что индексы массива — числа в диапазоне 1..n, а значения — целые числа, поэтому ему приходится рассчитывать на худший вариант когда однажды в массив запишут вот так:

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


                    Это, мягко говоря, неверно. В реализации таблиц в Луа есть оптимизация для поддержки массивов с целочисленными ключами. С этим там хорошо и быстро.
                      0
                      Другое дело, что хранить массив пикселей в луашной таблице — в принципе странное решение.

                      Если нужно работать с такого рода вещами (и нет под рукой LuaJIT b6), нужно писать модуль на C. Это — нормально и ожидаемо.
                        0
                        А держать каждый пиксель как подтаблицу — тем более странное решение.
                      0
                      Обсуждение предыдущей статьи в официальной рассылке Луа: thread.gmane.org/gmane.comp.lang.lua.general/75252

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

                      Самое читаемое