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

Question

Lua в настоящее время является самым быстрым языком для написания сценариев, и его не так много медленнее, чем C/C++ для некоторых программ (на уровне при выполнении pidgits 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-core Lua для этого, или использовать LuaJit, о том, как найти способы оптимизации одной из слабых слабых точек Lua.

Answer 1

Роберт Гулд:

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

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

В этом случае вы, кажется, взяли числа, измеренные на машине quadcore, где самые быстрые программы были переписаны для использования нескольких ядер. Вместо того, чтобы смотреть на прошедшее время sort by CPU time and you'll see the ratio drop to 1:24.

Или посмотрите на медианную и квартили, чтобы получить лучшее впечатление от how the set of C++ measurements compares to the set of Lua measurements.

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