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

Question

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

Одним из них является тест fannkuch (индексированный доступ к крошечной целочисленной последовательности), где он получает ужасный результат 1: 148

-- The Computer Language Benchmarks Game
-- http://shootout.alioth.debian.org/
-- contributed by Mike Pall

local function fannkuch(n)
  local p, q, s, odd, check, maxflips = {}, {}, {}, true, 0, 0
  for i=1,n do p[i] = i; q[i] = i; s[i] = i end
  repeat
    -- Print max. 30 permutations.
    if check < 30 then
      if not p[n] then return maxflips end  -- Catch n = 0, 1, 2.
      io.write(unpack(p)); io.write("\n")
      check = check + 1
    end
    -- Copy and flip.
    local q1 = p[1]             -- Cache 1st element.
    if p[n] ~= n and q1 ~= 1 then       -- Avoid useless work.
      for i=2,n do q[i] = p[i] end      -- Work on a copy.
      for flips=1,1000000 do            -- Flip ...
    local qq = q[q1]
    if qq == 1 then             -- ... until 1st element is 1.
      if flips > maxflips then maxflips = flips end -- New maximum?
      break
    end
    q[q1] = q1
    if q1 >= 4 then
      local i, j = 2, q1 - 1
      repeat q[i], q[j] = q[j], q[i]; i = i + 1; j = j - 1; until i >= j
    end
    q1 = qq
      end
    end
    -- Permute.
    if odd then
      p[2], p[1] = p[1], p[2]; odd = false  -- Rotate 1<-2.
    else
      p[2], p[3] = p[3], p[2]; odd = true   -- Rotate 1<-2 and 1<-2<-3.
      for i=3,n do
    local sx = s[i]
    if sx ~= 1 then s[i] = sx-1; break end
    if i == n then return maxflips end  -- Out of permutations.
    s[i] = i
    -- Rotate 1<-...<-i+1.
    local t = p[1]; for j=1,i do p[j] = p[j+1] end; p[i+1] = t
      end
    end
  until false
end

local n = tonumber(arg and arg[1]) or 1
io.write("Pfannkuchen(", n, ") = ", fannkuch(n), "\n")

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

Answer 1

Роберт Гулд> Одним из них является тест fannkuch (индексированный доступ к крошечной целочисленной последовательности), где он оценивается ужасно 1: 148

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

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

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

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