optimization - Lua挑战: Can you improve the mandelbrot implementation’s performance?

Question

状态:到目前为止，最佳答案的程序执行时间是原始程序的 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 的一个弱点。

编辑:为此设置赏金以使挑战更有趣。

Answer 1

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