优化 – Lua挑战：可以提高mandelbrot实现的性能吗？

状态：到目前为止,最好的答案程序在原始程序的33％的时间内执行！但是可能还有其他方法可以优化它.

Lua目前是最快的脚本语言,但是Lua在C/C++的几个基准中得分真的很差.

其中之一是Mandelbrot测试(生成Mandelbrot设置便携式位图文件N = 16,000),其中可怕的1：109(多核)或1:28(单核)

由于三角洲的速度相当大,这是优化的好选择.另外我确信那些知道迈克·帕尔(Mike Pall)的人可能会相信没有可能进一步优化这一点的人,但这是公然的错误.任何做过优化的人都知道总是可以做得更好.此外,我做了一些额外的表现,通过一些调整,所以我知道它可能:)

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

那么这样做可以如何进行优化(当然,与任何优化一样,您必须测量实现以确保更快).你不能改变Lua的C核心,或者使用LuaJit来寻找优化Lua弱点的方法.

编辑：将赏金放在这里,使挑战更有趣.

通过2,比以前更好约30％(在我的机器上)主要的储蓄来自内循环的展开,以摊销开销.

还包括(注释掉)是一个中止的尝试,当你被困在中心心脏中时,提前退出(&设置像素黑色)来节省时间.它的作品,但它是更慢,无论我如何摆弄它.

我必须跑,但我会留下一个分开的建议.可能通过运行长度编码结果可能会有一些优化(因此,不需要保存一堆点缀的字符,您将保存列表(白点数,黑点数,白点数等) ).这个会：

>减少存储/ GC开销
>对输出生成进行一些优化(当数字>> 8时)
>允许一些轨道检测.

不知道如果它可以被编码得足够紧,以便飞行,但是如果我有更多的时间,那我将尝试下一步.

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