optimization - imagenes - Lua Challenge: ¿Puedes mejorar el rendimiento de la implementación de mandelbrot?

fractales en la naturaleza

Question

Estado: ¡hasta ahora el programa de la mejor respuesta se ejecuta en el 33% del tiempo del programa original! Pero probablemente aún haya otras formas de optimizarlo.

Lua es actualmente el lenguaje de scripting más rápido que existe, sin embargo, Lua obtiene resultados realmente malos en algunos puntos de referencia contra C / C ++.

Una de ellas es la prueba de mandelbrot (Generar conjunto de mapa de bits portátil Generar Mandelbrot N = 16,000), donde obtiene un horrible 1: 109 (Núcleo múltiple) o 1:28 (Núcleo único)

Dado que el Delta en velocidad es bastante grande, este es un buen candidato para optimizaciones. También estoy seguro de que quienes saben quién es Mike Pall pueden creer que no es posible optimizar esto más, pero eso es descaradamente erróneo. Cualquiera que haya hecho optimizaciones sabe que siempre es posible hacerlo mejor. Además logré obtener un rendimiento extra con algunos ajustes, así que sé que es posible :)

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

Entonces, ¿cómo podría optimizarse esto? (Por supuesto, como con cualquier optimización, debe medir su implementación para asegurarse de que sea más rápida). Y no se te permite alterar el C-core de Lua por esto, ni usar LuaJit, se trata de encontrar maneras de optimizar uno de los puntos débiles débiles de Lua.

Editar: Poner un Bounty en esto para hacer el desafío más divertido.

Answer 1

Robert Gould> Uno de ellos es la prueba de mandelbrot (Generate Mandelbrot establece un archivo de mapa de bits portátil N = 16,000), donde obtiene un puntaje horrible de 1: 109

Cuando citas números del juego de puntos de referencia, muestra de dónde provienen esos números para que los lectores tengan algún contexto.

En este caso, parece que ha tomado números medidos en la máquina quadcore donde los programas más rápidos han sido reescritos para explotar múltiples núcleos. En lugar de mirar el tiempo transcurrido, ordena por tiempo de CPU y verás que la relación cae a 1:28 .

O mire la mediana y los cuartiles para obtener una mejor impresión de cómo se compara el conjunto de mediciones C ++ con el conjunto de mediciones Lua .

O hay un conjunto completo de mediciones en las que los programas se ven obligados a usar solo un núcleo: Lua en comparación con C ++ , y si observan esos programas de Lua pi-digits verán que usan la biblioteca GNU GMP de lenguaje C.

Answer 2

Ahora que hay al menos una respuesta más rápida que mi solución, publicaré mi respuesta

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

El truco es almacenar valores en una tabla antes de enviarlos a la salida. Algo tan simple como esto redujo el tiempo de ejecución al 58%.

Answer 3

Así que aquí está ~ 40% para empezar:

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

Answer 4

El siguiente paso que hice fue almacenar en caché las cosas que se calcularon una y otra vez, y reemplazar bit + bit a bit * 2, estas simples optimizaciones son bastante poderosas ...

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

Esta optimización hace que el programa se ejecute en el 34% del tiempo del original, pero la optimización de Markus Q sigue venciendo a la mía;)

Answer 5

Este fue otro intento, pero resultó ser más lento que el acceso local a las variables (imaginé que usar un entorno limpio habría hecho que fuera más rápido encontrar las variables, pero no fue así, los registros virtuales locales son ligeramente más rápidos). redujo el tiempo de ejecución al 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))

Answer 6

No sé que Lua sea tan bueno para producir código de trabajo, pero debería poder aumentar mucho el rendimiento de Mandelbrot usando algunos trucos matemáticos. Hubo una sugerencia sobre el uso de la simetría para acelerarlo, otra gran mejora podría hacerse usando esta optimización:

Use una función recursiva que usa coordenadas rectangulares de una porción de Mandelbrot. Luego calcula los valores en las líneas de borde de los rectángulos y las dos líneas que se dividen en el medio. Después de esto, hay 4 sub-rectángulos. Si una de ellas tiene todos los mismos colores de píxeles de borde, simplemente puede llenarlo con este color, de lo contrario, recursivamente llama a la función en esta parte.

Busqué otra explicación de este algoritmo y encontré uno aquí , junto con una buena visualización . El viejo programa de DOS FRACTINT llama a esta optimización "modo Tesseral".

Answer 7

Pase 2, aproximadamente un 30% mejor (en mi máquina) que mi anterior. El ahorro principal vino de desenrollar el lazo interno para amortizar la sobrecarga.

También se incluye (comentada) es un intento abortado de ahorrar tiempo al salir temprano (y establecer el píxel en negro) cuando está atrapado en el cardioide central. Funciona, pero es más lento no importa cómo lo activé.

Tengo que correr, pero dejaré una sugerencia de despedida. Puede haber alguna optimización posible mediante la longitud de ejecución de la codificación de los resultados (por lo que en lugar de guardar un montón de caracteres cargados de bits, se guardaría una lista (número de puntos blancos, número de puntos negros, cantidad de puntos blancos, etc.) ) Esto sería:

1. Reduce el almacenamiento / sobrecarga del GC
2. Permitir algunas optimizaciones en la generación de salida (cuando los números eran >> 8)
3. Permite alguna detección de órbita.

No tengo idea si podría codificarse lo suficiente como para volar, pero ahí es donde probaría si tuviera más tiempo.

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

Answer 8

En el juego de puntos de referencia, el tiempo transcurrido se ha reducido de 674 a 211 al generar más procesos para utilizar los núcleos disponibles .

Answer 9

¿Por qué usar la variable local Zri? Es posible evitar su uso reordenando las siguientes dos declaraciones:

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

También es posible usar la verificación de periodicidad simple, pero la aceleración depende de m. Cuanto mayor es la "m", mejor es la aceleración obtenida de la comprobación de periodicidad.