Lua Challenge: Можете ли вы улучшить производительность реализации спектральной нормы?

Question

Lua в настоящее время является самым быстрым языком сценариев, и он не намного медленнее, чем C / C ++ для некоторых программ (на уровне пиджитов 1: 1), однако Lua показывает очень плохие результаты в нескольких тестах C /C++.

Одним из них является тест спектральной нормы (собственное значение с использованием метода мощности N = 5500), где он получает ужасное значение 1: 148

-- The Computer Language Shootout
-- http://shootout.alioth.debian.org/
-- contributed by Isaac Gouy, tuned by Mike Pall

local function A(i, j)   
    local ij = i + j   
    return 1.0 / (ij * (ij + 1) * 0.5 + i + 1) 
end

local function Av(n, x, y)   
    for i = 0, n - 1 do
        local a = 0
        for j = 0, n - 1 do 
            a = a + A(i,j) * x[j] 
        end
        y[i] = a   
    end 
end

local function Atv(n, x, y)   
    for i = 0, n - 1 do
        local a = 0
        for j = 0, n - 1 do 
            a = a + A(j,i) * x[j] 
        end
        y[i] = a   
    end 
end

local function AtAv(n, x, y, t)   
    Av(n, x, t)   
    Atv(n, t, y) 
end


local n = tonumber(arg and arg[1]) or 100 
local u, v, t = {}, {}, {} 
for i = 0, n - 1 do 
    u[i] = 1 
end

for i = 1, 10 do 
    AtAv(n, u, v, t) 
    AtAv(n, v, u, t) 
end

local vBv, vv = 0, 0 
for i = 0, n - 1 do  
    local ui, vi = u[i], v[i]   
    vBv = vBv + ui * vi   
    vv = vv + vi * vi 
end

io.write(string.format("%0.9f\n", math.sqrt(vBv / vv)))

Итак, как это можно оптимизировать (конечно, как и при любой оптимизации, вы должны измерить свою реализацию, чтобы убедиться, что она быстрее). И вам не разрешено изменять C-ядро Lua для этого или использовать LuaJit, чтобы найти способы оптимизации одного из слабых мест Lua.

Answer 1

Роберт Гулд:

Одним из них является тест спектральной нормы (собственное значение с использованием метода мощности N = 5500), где он получает ужасное значение 1: 148

Когда вы цитируете числа из тестовой игры, покажите, откуда взялись эти цифры, чтобы читатели имели некоторый контекст.

В этом случае вы, кажется, взяли числа, измеренные на четырехъядерной машине, где самые быстрые программы были переписаны для использования нескольких ядер. Вместо просмотра прошедшего времени сортируйте по времени процессора, и вы увидите, что соотношение уменьшится до 1: 24 .

Или посмотрите на медиану и квартили, чтобы получить лучшее представление о , как набор измерений C ++ сравнивается с набором измерений Lua .

Или есть целый набор измерений, где программы вынуждены использовать только одно ядро ​​- Lua по сравнению с C ++ - и если вы посмотрите на эти Lua пи-цифры программ вы увидите, что они используют библиотеку GNU GMP языка C.