Проблема Lua: можно ли улучшить производительность mandelbrot реализации?

Таким образом, вот ~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

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

-- 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%.

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

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

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

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

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

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

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

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

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

Следующий шаг, который я сделал, был кэшем материал, который был вычислен много раз, и замена bit+bit к bit*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% времени оригинала, но оптимизацию Q Markus все еще шахта ;) удара

Это было другой попыткой, но это оказалось медленнее, чем локальный доступ переменных (я предположил использовать чистую среду, сделает его быстрее для нахождения переменных, но это не имело место, виртуальные регистры местного жителя немного быстрее), Это понизило время выполнения до 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))

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

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

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