Lua Challenge: Можете ли вы улучшить производительность реализации mandelbrot? - PullRequest
Новая
       12

Lua Challenge: Можете ли вы улучшить производительность реализации mandelbrot?

10 голосов
/ 20 февраля 2009

Статус: Пока программа с лучшим ответом выполняется в 33% времени от оригинальной программы! Но, возможно, есть и другие способы его оптимизации.

Lua в настоящее время является самым быстрым языком сценариев, однако Lua показывает очень плохие результаты в нескольких тестах по сравнению с C / C ++.

Одним из них является тест Мандельброта (переносимый файл растрового изображения с набором Мандельброта N = 16 000), где он оценивается как ужасный 1: 109 (многоядерный) или 1:28 (одноядерный)

Поскольку дельта по скорости довольно велика, это хороший кандидат на оптимизацию. Также я уверен, что те, кто знают, кто такой Майк Палл, могут поверить, что невозможно оптимизировать это дальше, но это явно неправильно. Любой, кто провел оптимизацию, знает, что всегда можно сделать лучше. Кроме того, мне удалось добиться некоторой дополнительной производительности с помощью нескольких настроек, поэтому я знаю, что это возможно:) 

-- The Computer Language Shootout
-- http://shootout.alioth.debian.org/
-- contributed by Mike Pall

local width = tonumber(arg and arg[1]) or 100
local height, wscale = width, 2/width
local m, limit2 = 50, 4.0
local write, char = io.write, string.char

write("P4\n", width, " ", height, "\n")

for y=0,height-1 do
  local Ci = 2*y / height - 1
  for xb=0,width-1,8 do
    local bits = 0
    local xbb = xb+7
    for x=xb,xbb < width and xbb or width-1 do
      bits = bits + bits
      local Zr, Zi, Zrq, Ziq = 0.0, 0.0, 0.0, 0.0
      local Cr = x * wscale - 1.5
      for i=1,m do
        local Zri = Zr*Zi
        Zr = Zrq - Ziq + Cr
        Zi = Zri + Zri + Ci
        Zrq = Zr*Zr
        Ziq = Zi*Zi
        if Zrq + Ziq > limit2 then
          bits = bits + 1
          break
        end
      end
    end
    if xbb >= width then
      for x=width,xbb do bits = bits + bits + 1 end
    end
    write(char(255-bits))
  end
end

Итак, как это можно оптимизировать (конечно, как и при любой оптимизации, вы должны измерить свою реализацию, чтобы быть уверенным, что она быстрее). И вам не разрешено изменять C-ядро Lua для этого или использовать LuaJit, чтобы найти способы оптимизации одного из слабых мест Lua.

Редактировать: Назначить награду за это, чтобы сделать вызов более увлекательным.

Ответы [ 9 ]

7 голосов
/ 03 марта 2009

Проход 2, примерно на 30% лучше (на моей машине), чем у моего предыдущего. Основная экономия была получена благодаря развертыванию внутреннего цикла для амортизации накладных расходов.

Также включена (закомментирована) неудачная попытка сэкономить время путем раннего выхода (и установки черного пикселя), когда вы застряли в центральном кардиоиде. Это работает, но медленнее, независимо от того, как я его отжал.

Мне нужно бежать, но я оставлю прощальное предложение. Может быть возможна некоторая оптимизация за счет кодирования результатов по длине прогона (поэтому вместо сохранения набора разбитых на биты символов вы должны сохранить список (количество белых точек, количество черных точек, количество белых точек и т. Д.) ). Это будет:

  1. Уменьшить накладные расходы хранилища / GC
  2. Разрешить некоторую оптимизацию при генерации выходных данных (когда числа были >> 8)
  3. Разрешить некоторое обнаружение орбиты.

Не знаю, можно ли было бы закодировать его достаточно плотно, чтобы летать, но именно здесь я бы попробовал, если бы у меня было больше времени. 

-- The Computer Language Shootout
-- http://shootout.alioth.debian.org/
-- contributed by Mike Pall
-- with optimizations by Markus J. Q. (MarkusQ) Roberts

local width = tonumber(arg and arg[1]) or 100
local height, wscale = width, 2/width
local m, limit2 = 50, 4.0
local write, char = io.write, string.char

local h2 = math.floor(height/2)
local hm = height - h2*2
local top_half = {}

for y=0,h2+hm do
    local Ci = 2*y / height - 1
    local line = {""}
    for xb=0,width-1,8 do
        local bits = 0
        local xbb = xb+7
        for x=xb,xbb < width and xbb or width-1 do
            bits = bits + bits
            local Zr, Zi, Zrq, Ziq = 0.0, 0.0, 0.0, 0.0
            local Cr = x * wscale - 1.5
            local Zri = Zr*Zi
            for i=1,m/5 do
                Zr = Zrq - Ziq + Cr
                Zi = Zri + Zri + Ci
                Zri = Zr*Zi

                Zr = Zr*Zr - Zi*Zi + Cr
                Zi = 2*Zri +         Ci
                Zri = Zr*Zi

                Zr = Zr*Zr - Zi*Zi + Cr
                Zi = 2*Zri +         Ci
                Zri = Zr*Zi

                Zr = Zr*Zr - Zi*Zi + Cr
                Zi = 2*Zri +         Ci
                Zri = Zr*Zi

                Zr = Zr*Zr - Zi*Zi + Cr
                Zi = 2*Zri +         Ci
                Zri = Zr*Zi

                Zrq = Zr*Zr
                Ziq = Zi*Zi
                Zri = Zr*Zi
                if Zrq + Ziq > limit2 then
                    bits = bits + 1
                    break
                    end
                -- if i == 1 then
                --    local ar,ai       = 1-4*Zr,-4*Zi
                --    local a_r         = math.sqrt(ar*ar+ai*ai)
                --    local k           = math.sqrt(2)/2
                --    local br,bi2      = math.sqrt(a_r+ar)*k,(a_r-ar)/2
                --    if (br+1)*(br+1) + bi2 < 1 then
                --        break
                --        end
                --    end
                end
            end
        for x=width,xbb do 
            bits = bits + bits + 1 
            end
        table.insert(line,char(255-bits))
        end
    line = table.concat(line) 
    table.insert(top_half,line)
    end

write("P4\n", width, " ", height, "\n")
for y=1,h2+hm do
    write(top_half[y])
    end
for y=h2,1,-1 do
    write(top_half[y])
   end
3 голосов
/ 03 марта 2009

Итак, вот ~ 40% для начала: 

-- The Computer Language Shootout
-- http://shootout.alioth.debian.org/
-- contributed by Mike Pall

local width = tonumber(arg and arg[1]) or 100
local height, wscale = width, 2/width
local m, limit2 = 50, 4.0
local write, char = io.write, string.char

function addChar (line, c)
    table.insert(line, c)
    for i=table.getn(line)-1, 1, -1 do
        if string.len(line[i]) > string.len(line[i+1]) then
            break
            end
        line[i] = line[i] .. table.remove(line)
        end
    end

local h2 = math.floor(height/2)
local hm = height - h2*2
local top_half = {}
for y=0,h2+hm do
    local Ci = 2*y / height - 1
    local line = {""}
    for xb=0,width-1,8 do
        local bits = 0
        local xbb = xb+7
        for x=xb,xbb < width and xbb or width-1 do
            bits = bits + bits
            local Zr, Zi, Zrq, Ziq = 0.0, 0.0, 0.0, 0.0
            local Cr = x * wscale - 1.5
            for i=1,m do
                local Zri = Zr*Zi
                Zr = Zrq - Ziq + Cr
                Zi = Zri + Zri + Ci
                Zrq = Zr*Zr
                Ziq = Zi*Zi
                if Zrq + Ziq > limit2 then
                    bits = bits + 1
                    break
                    end
                end
            end
        for x=width,xbb do 
            bits = bits + bits + 1 
            end
        addChar(line,char(255-bits))
        end
    line = table.concat(line) 
    table.insert(top_half,line)
    end

write("P4\n", width, " ", height, "\n")
for y=1,h2+hm do
    write(top_half[y])
    end
for y=h2,1,-1 do
    write(top_half[y])
    end

- MarkusQ

2 голосов
/ 04 марта 2009

Я не знаю Lua, который так хорош для создания рабочего кода, но вы должны быть в состоянии значительно увеличить производительность Мандельброта, используя некоторые математические приемы. Было выдвинуто предложение об использовании симметрии для ускорения, с помощью этой оптимизации можно было бы сделать еще одно значительное улучшение:

Используйте рекурсивную функцию, которая использует прямоугольные координаты части Мандельброта. Затем он вычисляет значения на границах прямоугольников и на двух линиях, которые разбиваются посередине. После этого есть 4 под прямоугольника. Если один из них имеет все те же цвета пикселей границы, вы можете просто заполнить его этим цветом, если нет, то вы рекурсивно вызываете функцию в этой части.

Я искал другое объяснение этого алгоритма и нашел один здесь - вместе с хорошей визуализацией . Старая DOS-программа FRACTINT называет это оптимизацией «Тессеральным режимом».

2 голосов
/ 03 марта 2009

Теперь, когда есть хотя бы один ответ быстрее моего решения, я опубликую свой ответ 

-- The Computer Language Shootout
-- http://shootout.alioth.debian.org/
-- contributed by Mike Pall

local width = tonumber(arg and arg[1]) or 100
local height, wscale = width, 2/width
local m, limit2 = 50, 4.0
local write, char = io.write, string.char
local insert = table.insert
local results={}
write("P4\n", width, " ", height, "\n")

for y=0,height-1 do
  local Ci = 2*y / height - 1
  for xb=0,width-1,8 do
    local bits = 0
    local xbb = xb+7
    for x=xb,xbb < width and xbb or width-1 do
      bits = bits + bits
      local Zr, Zi, Zrq, Ziq = 0.0, 0.0, 0.0, 0.0
      local Cr = x * wscale - 1.5
      for i=1,m do
        local Zri = Zr*Zi
        Zr = Zrq - Ziq + Cr
        Zi = Zri + Zri + Ci
        Zrq = Zr*Zr
        Ziq = Zi*Zi
        if Zrq + Ziq > limit2 then
          bits = bits + 1
          break
        end
      end
    end
    if xbb >= width then
      for x=width,xbb do bits = bits + bits + 1 end
    end
    insert(results,(char(255-bits)))
  end
end
write(table.concat(results))

Хитрость заключается в сохранении значений в таблице перед отправкой их на выход. Что-то простое уменьшило время выполнения до 58%.

1 голос
/ 19 мая 2009

Зачем использовать локальную переменную Zri? Можно избежать его использования, переупорядочив следующие два оператора:

Zi = 2 * Zr * Zi + Ci Zr = Zrq - Ziq + Cr

Также можно использовать простую проверку периодичности, но ускорение зависит от m. Чем больше значение «m», тем лучше ускорение при проверке периодичности.

1 голос
/ 01 апреля 2009
0 голосов
/ 03 марта 2009

Это была еще одна попытка, но она оказалась медленнее, чем локальный доступ к переменным (я предполагал, что использование чистой среды ускорило бы поиск переменных, но это было не так, виртуальные регистры локального интерфейса немного быстрее) Это снизило время выполнения до 41%. 

local env={}
env.width = tonumber(arg and arg[1]) or 100
env.height = env.width
env.wscale = 2/env.width
env.m = 50
env.limit2 = 4.0
env.write = io.write
env.char = string.char
env.results={}
env.height_minus_one = env.height - 1
env.width_minus_one = env.width -1
env.insert = table.insert

setfenv(function()
    write("P4\n", env.width, " ", env.height, "\n")
    for y=0,height_minus_one do
      local Ci = 2*y / height_minus_one
      for xb=0,width_minus_one,8 do
        local bits = 0
        local xbb = xb+7
        for x=xb,xbb < width and xbb or width_minus_one do
          bits = bits *2
          local Zr, Zi, Zrq, Ziq = 0.0, 0.0, 0.0, 0.0
          local Cr = x * wscale - 1.5
          for i=1,m do
            local Zri = Zr*Zi
            Zr = Zrq - Ziq + Cr
            Zi = Zri + Zri + Ci
            Zrq = Zr*Zr
            Ziq = Zi*Zi
            if Zrq + Ziq > limit2 then
              bits = bits + 1
              break
            end
          end
        end
        if xbb >= width then
          for x=width,xbb do bits = bits *2 + 1 end
        end
        insert(results,(char(255-bits)))
      end
    end
end,env)()

io.write(table.concat(env.results))
0 голосов
/ 03 марта 2009

Следующим шагом, который я сделал, было кэширование материала, который вычислялся снова и снова, и замена бит + бит на бит * 2. Эти простые оптимизации довольно мощные ... 

local width = tonumber(arg and arg[1]) or 100
local height, wscale = width, 2/width
local m, limit2 = 50, 4.0
local write, char = io.write, string.char
local results={}
write("P4\n", width, " ", height, "\n")
local height_minus_one = height - 1
local width_minus_one = width -1

for y=0,height_minus_one do
  local Ci = 2*y / height_minus_one
  for xb=0,width_minus_one,8 do
    local bits = 0
    local xbb = xb+7
    for x=xb,xbb < width and xbb or width_minus_one do
      bits = bits *2
      local Zr, Zi, Zrq, Ziq = 0.0, 0.0, 0.0, 0.0
      local Cr = x * wscale - 1.5
      for i=1,m do
        local Zri = Zr*Zi
        Zr = Zrq - Ziq + Cr
        Zi = Zri + Zri + Ci
        Zrq = Zr*Zr
        Ziq = Zi*Zi
        if Zrq + Ziq > limit2 then
          bits = bits + 1
          break
        end
      end
    end
    if xbb >= width then
      for x=width,xbb do bits = bits *2 + 1 end
    end
    table.insert(results,(char(255-bits)))
  end
end
write(table.concat(results))

Эта оптимизация заставляет программу работать в 34% времени от оригинала, но оптимизация Markus Q по-прежнему превосходит мою;)

0 голосов
/ 21 февраля 2009

Роберт Гулд> Одним из них является тест Мандельброта (переносимый файл растрового изображения с набором Мандельброта N = 16 000), где он получает ужасное значение 1: 109

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

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

Или посмотрите на медиану и квартили, чтобы получить лучшее представление о , как набор измерений C ++ сравнивается с набором измерений Lua .

Или существует целый набор измерений, где программы вынуждены использовать только одно ядро ​​- Lua по сравнению с C ++ - и если вы посмотрите на эти Lua пи-цифры программ вы увидите, что они используют библиотеку GNU GMP языка C.

...