Lua Challenge: Можете ли вы улучшить производительность реализации мандельбротов?
Статус: Пока лучшая программа ответа выполняется в 33% времени оригинальной программы! Но, вероятно, есть и другие способы его оптимизации.
В настоящее время Lua является самым быстрым языком сценариев, однако Lua очень плохо оценивает несколько тестов по сравнению с C/С++.
Один из них - тест mandelbrot (создайте переносимый файл растрового файла Mandelbrot N = 16 000), где он набирает ужасные 1:109 (многоядерные) или 1:28 (одноядерные)
Поскольку Delta в скорости довольно велика, это хороший кандидат для оптимизации. Кроме того, я уверен, что некоторые из тех, кто знает, кто из Майка Палла, могут поверить, что это невозможно оптимизировать это дальше, но это вопиюще неправильно. Любой, кто сделал оптимизацию, знает, что всегда можно сделать лучше. Кроме того, мне удалось получить дополнительную производительность с несколькими настройками, поэтому я знаю, что это возможно:)
-- 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
Итак, как это можно было бы оптимизировать (конечно, как и при любой оптимизации, вам нужно будет измерить вашу реализацию, чтобы быть уверенным в ее быстроте). И вам не разрешено изменять C-core Lua для этого или использовать LuaJit, чтобы найти способы оптимизации одной из слабых слабых точек Lua.
Изменить: Помещение Bounty на этом, чтобы сделать вызов более увлекательным.
Ответы
Ответ 1
Пройдите 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
Ответ 2
Итак, здесь ~ 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
Ответ 3
Теперь, когда есть хотя бы один ответ быстрее моего решения, я отправлю свой ответ
-- 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%.
Ответ 4
Я не знаю, что Lua хорошо работает с рабочим кодом, но вы должны сильно увеличить производительность Mandelbrot, используя некоторые математические трюки. Было высказано предположение об использовании симметрии, чтобы ускорить его, еще одно значительное улучшение можно было бы сделать с помощью этой оптимизации:
Используйте рекурсивную функцию, которая использует прямоугольные координаты части Мандельброта. Затем он вычисляет значения в границах прямоугольников и две линии, которые расщепляются посередине. После этого есть 4 суб-прямоугольника. Если у одного из них есть все одинаковые цвета пикселя границы, вы можете просто заполнить его этим цветом, если нет, вы рекурсивно вызываете функцию на этой части.
Я искал другое объяснение этого алгоритма и нашел здесь здесь - наряду с приятным визуализация. Старая программа DOS FRACTINT называет это оптимизация "Tesseral mode".
Ответ 5
В игровой игре прошедшее время было уменьшено с 674 до 211, путем создания большего количества процессов для использования доступных ядер.
Ответ 6
Зачем использовать локальную переменную Zri? Можно избежать его использования, переупорядочив следующие два утверждения:
Zi = 2 * Zr * Zi + Ci
Zr = Zrq - Ziq + Cr
Также можно использовать простую проверку периодичности, но ускорение зависит от m. Чем больше "m", тем лучше ускорение, полученное при проверке периодичности.
Ответ 7
Роберт Гулд > Один из них - тест mandelbrot (сгенерируйте переносимый файл растрового файла Mandelbrot N = 16 000), где он наносит ужасный 1:109
Когда вы приводите цифры из теста тестов, пожалуйста, покажите, откуда эти цифры, поэтому у читателей есть определенный контекст.
В этом случае вы, кажется, приняли числа, измеренные на четырехъядерном компьютере, где самые быстрые программы были переписаны для использования нескольких ядер. Вместо того, чтобы смотреть на прошедшее время сортировать по времени процессора, и вы увидите, что отношение падает до 1:28.
Или посмотрите на медианную и квартили, чтобы получить лучшее впечатление от того, как набор измерений С++ сравнивается с набором измерений Lua.
Или существует целый набор измерений, где программы вынуждены использовать только одно ядро - Lua по сравнению с С++ - и если вы возьмете посмотрите те Lua pi-digits программы, вы увидите, что они используют библиотеку GNU GMP на языке C.
Ответ 8
Следующий шаг, который я сделал, - это кеш файл, который был подсчитан много раз, и заменить бит + бит на бит * 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 по-прежнему проигрывает мою;)
Ответ 9
Это была еще одна попытка, но оказалось, что она медленнее, чем локальный доступ к переменным (я предполагал, что использование чистой среды ускорило бы поиск переменных, но это было не так, локальные виртуальные регистры немного быстрее). Это привело к сокращению времени выполнения до 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))
