miura1729の日記

luajitの実力

20:37 |

追記

LuaJITの作者Mike Pall氏より、twitterで次のようなアドバイスをいただきました。

1. No compiler is allowed to make this optimization. Floating-point arithmetic ist NOT associative.

2. Please use 'local' functions when publishing Lua benchmarks.

3. Please use the current version of LuaJIT.

訳(かなり怪しい)

1．このような最適化出来るコンパイラは無いよ。浮動小数点数の算術命令は結合的じゃないから

2. Luaのベンチマークを取るなら局所関数を使ってください

3. 最新バージョンのLuaJITを使ってください

そういうわけで、ベンチマークを取り直します。

ベンチマークをやり直しました。functionの前にlocalを入れて、LuaJITを最新にしています。Mike Pall氏には、ベンチマークのやり直しにあたりアドバイスをいただきました。ありがとうございます。

$ luajit -v

LuaJIT 2.0.1 -- Copyright (C) 2005-2013 Mike Pall. http://luajit.org/

最適化前

$ time luajit spline0.lua

real    0m1.275s
user    0m1.170s
sys     0m0.031s

最適化後

$ time luajit spline1.lua

real    0m0.806s
user    0m0.732s
sys     0m0.015s

最適化前が3%ほど速くなって最適化後との差が少し縮みました。JIT無しのLuaでの結果です。

$ time ./lua ../../luajit.org/spline0.lua

real    0m1.273s
user    0m1.185s
sys     0m0.045s

$ time ./lua ../../luajit.org/spline1.lua

real    0m0.327s
user    0m0.249s
sys     0m0.046s

追記終わり

それはあまりにもコンパイラの最適化に期待し過ぎです。実際に吐き出したコードを読んでみましょう。あなたがコンパイラの作者だったら、あなたがJITの作者だったら、入って来たコードから同じような最適化ができるでしょうか。まず無理です。どんな高度な最適化コンパイラも、所詮は人間の作ったコードです。コンパイラは神ではないのです。あくまでも人間の創りだした不完全な道具のひとつに過ぎません。

よくわかる最適化 (http://d.hatena.ne.jp/shi3z/20130502/1367490202) より

うう、luajitなら、luajitならやってくれる。と信じて確かめてみました。

結果、

最適化前

$ time luajit-2.0.0-beta10 spline0.lua

real    0m1.268s
user    0m1.200s
sys     0m0.016s

最適化後

$ time luajit-2.0.0-beta10 spline1.lua

real    0m0.795s
user    0m0.733s
sys     0m0.046s

理論値3倍のはずなのでかなり盛り返しています。

ちなみに、JIT無しのluaだとこんな感じ。

時間がかかってしょうがないのでループを1/100にしています。

最適化前

$ time ./lua ../../luajit.org/spline0.lua

real    0m1.309s
user    0m1.216s
sys     0m0.046s

最適化後

$ time ./lua ../../luajit.org/spline1.lua

real    0m0.331s
user    0m0.249s
sys     0m0.061s

ちゃんと、最適化は出来ているようです。

まとめ

　luajitはとても頑張っているが完璧ではない。

移植したソースコードです

最適化前

function catmullRom(p0, p1, p2, p3, t)
  local v0 = (p2 - p0) / 2.0
  local v1 = (p3 - p1) / 2.0
  return ((2.0 * p1 - 2.0 * p2) + v0 + v1) * t * t * t + 
          ((-3.0 * p1 + 3.0 * p2) - 2.0 * v0 - v1) * t * t + v0 * t + p1
end

function main(xp0, xp1, xp2, xp3, yp0, yp1, yp2, yp3, pp0, pp1, pp2, pp3)
  local d = math.sqrt((xp1 - xp2) * (xp1 - xp2) + (yp1 - yp2) * (yp1 - yp2))
  local num = math.ceil((d / 5.0) + 0.5)
  local x,y,p
  local invertNum = 1.0/num
  local deltaT = 0
  for i = 0, num do
    deltaT = deltaT + invertNum
    x = catmullRom(xp0,xp1,xp2,xp3, deltaT)
    y = catmullRom(yp0,yp1,yp2,yp3, deltaT)
    p = catmullRom(pp0,pp1,pp2,pp3, deltaT)
  end
end

for j = 0, 10000 do
  main(1.0, 100.0, 200.0, 200.0, 300.0, 100.0, 0.0, 200.0, 0.0, 100.0, 200.0, 300.0)
end

最適化後

function main(xp0, xp1, xp2, xp3, yp0, yp1, yp2, yp3, pp0, pp1, pp2, pp3)
local dx = xp1-xp2
local dy = yp1-yp2
local d = math.sqrt(dx*dx+dy*dy) 
local num = math.ceil((d*0.2) + 0.5)
local x,y,p
local invertNum = 1.0/num
local deltaT = 0
local xv0 = (xp2-xp0)*0.5
local xv1 = (xp3-xp1)*0.5
local xfact1=((xp1 - xp2)*2.0 + xv0 + xv1)
local xfact2=((xp2 - xp1)*3.0 - 2.0 * xv0 - xv1) 
local yv0 = (yp2-yp0)*0.5
local yv1 = (yp3-yp1)*0.5
local yfact1=((yp1 - yp2)*2.0 + yv0 + yv1)
local yfact2=((yp2 - yp1)*3.0 - 2.0 * yv0 - yv1) 
local pv0 = (pp2-pp0)*0.5
local pv1 = (pp3-pp1)*0.5
local pfact1=((pp1 - pp2)*2.0 + pv0 + pv1)
local pfact2=((pp2 - pp1)*3.0 - 2.0 * pv0 - pv1)
local xfact1n =0
local yfact1n =0
local pfact1n =0
local xFact1step = xfact1 * invertNum
local yFact1step = yfact1 * invertNum
local pFact1step = pfact1 * invertNum
  for i = 0, num do
     deltaT = deltaT + invertNum
     x =((xfact1n + xfact2) * deltaT + xv0) * deltaT + xp1
     y =((yfact1n + yfact2) * deltaT + yv0) * deltaT + yp1
     p =((pfact1n + pfact2) * deltaT + pv0) * deltaT + pp1
     xfact1n = xfact1n + xFact1step
     yfact1n = yfact1n + xFact1step
     pfact1n = pfact1n + xFact1step
  end
end

for j = 0, 1000000 do
  main(1.0, 100.0, 200.0, 200.0, 300.0, 100.0, 0.0, 200.0, 0.0, 100.0, 200.0, 300.0)
end