Lua挑战：你能提高曼德博集合实现的性能吗？

当您引用基准测试中的数字时，请说明这些数字来自何处，以便读者有一些上下文。其中之一是 Mandelbrot 测试（生成 Mandelbrot 集可移植的位图文件 N=16,000），在这个测试中，它的得分为可怕的 1:109。

在这种情况下，您似乎采用了在四核机器上测得的数字，其中最快的程序已经被重新编写以利用多个核。不要考虑经过的时间按 CPU 时间排序，你会看到比例降至 1:28。

或者查看中位数和四分位数，以更好地了解一组 C++ 测量值与一组 Lua 测量值相比的情况。

或者有一整套测量，其中程序被强制使用一个核 - Lua 与 C++ 的比较 - 如果您查看这些 Lua 的 pi-digits 程序，您会看到它们使用 C 语言 GNU GMP 库。

以下是程序代码，用于计算Mandelbrot集合的二进制输出。

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

现在至少有一个比我的解决方案更快的回答，所以我会发表我的答案

-- 电脑语言竞赛
-- http://shootout.alioth.debian.org/
-- 由Mike Pall提供

local width = tonumber（ARG和ARG [1]）或100
local height，wscale =宽度，2 /宽度
local m，limit2 = 50,4.0
local write，char = IO.Write，String.Char
local insert = table.insert
local results = {}
Write（“P4 \n”，宽度，“”，高度，”\n“）

for y = 0，height-1 do
  local Ci = 2 * y / height-1
  for xb = 0，宽度-1，8 do
    local bits = 0
    local xbb = xb + 7
    for x = xb，xbb <宽度和xbb或宽度-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执行位=位+位+1结束
    end
    insert（results，（CHAR（255位）））
  end
end
Write（Table.concat（results））

诀窍是在将表中的值发送到输出之前将其存储到表中。 简单的东西减少了运行时间的58％。

接下来我做的是将反复计算的内容缓存起来，并将 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％，但Markus Q的优化仍然胜过我的 ;)

这是另一次尝试，但它比访问本地变量慢（我想使用干净的环境会更快地找到变量，但事实并非如此，本地的虚拟寄存器略快），这将运行时降至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))

Pass 2, 比之前我的代码快了大约30%（在我的机器上）。这个优化的主要作用来自于展开内部循环以摊销开销。

在代码中还包含了（被注释掉的）一个试图通过在中央心形曲线被卡住时提前结束计算并把像素设为黑色来节省时间的尝试。尽管可以实现，但无论我如何调整，它都变得更慢了。

我得走了，但我会给出一个离别建议。通过运行长度编码结果（所以不是保存一堆二进制转换的字符，而是保存一个列表，例如：白点数量、黑点数量、白点数量等等）可能存在某些优化：

1. 减少存储/GC开销
2. 允许在生成输出时进行一些优化（当数字>>8时）
3. 允许一些轨道检测。

不知道它是否可以编写得紧密到能够运行，但如果我有更多时间，我会尝试这个方向。。

```

我不太会 Lua 编写可用的代码，但你可以使用一些数学技巧大大提高曼德布洛特性能。有人建议使用对称性加快它的速度，另一个很大的改进可以使用以下优化：

使用递归函数使用 Mandelbrot 部分的矩形坐标。然后计算矩形边界线和中间分裂的两条线的值。完成后，有 4 个子矩形。如果其中一个具有所有相同的边框像素颜色，您可以只需将其填充为这个颜色，如果不是，则在此部分上递归调用函数。

我搜索了另一个解释此算法的网址并找到了一个这里 - 以及一个不错的 可视化。旧的 DOS 程序 FRACTINT 称此优化为“Tesseral mode”。

在 benchmark game 中，通过产生更多的进程来利用可用的核心，已经将经过的时间从674秒减少到211秒。

为什么要使用本地变量 Zri？通过重新排列下面的两个语句，可以避免使用它：

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

也可以使用简单的周期性检查，但速度的提高取决于 m。m 越大，通过周期性检查获得的速度提升就越好。