Lua Challenge: Can you improve the spectral-norm implementation’s performance?

Question

Lua is currently the fastest scripting language out there, and its not so much slower than C/C++ for some sort of programs (on par when doing pidgits 1:1), however Lua scores really bad in a few benchmarks against C/C++.

One of those is the spectral-norm test (Eigenvalue using the power method N=5,500 ), where it scores a horrible 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)))

So how could this be optimized (of course as with any optimization you have to measure your implementation to be sure its faster). And you aren't allowed to alter the C-core of Lua for this, or use LuaJit, its about finding ways to optimizing one of Lua's weak weak points.

Answer 1

Robert Gould > One of those is the spectral-norm test (Eigenvalue using the power method N=5,500 ), where it scores a horrible 1:148

When you quote numbers from the benchmarks game please show where those numbers come from so readers have some context.

In this case you seem to have taken numbers measured on the quadcore machine where the fastest programs have been re-written to exploit multiple cores. Instead of looking at elapsed time sort by CPU time and you'll see the ratio drop to 1:24.

Or look at the median and quartiles to get a better impression of how the set of C++ measurements compares to the set of Lua measurements.

Or there's a whole set of measurements where programs are forced to use just one core - Lua compared with C++ - and if you take a look at those Lua pi-digits programs you'll see that they use the C language GNU GMP library.