2007年05月12日 - 氾濫原

Lua 末尾再帰最適化

subtech

03:34

Lua は末尾再帰最適化を行う。ってマニュアルに書いてあるんだけど、ホントカヨーって思って調べてみた。

function pow(x, n)
	if n == 1 then return x end

	return x * pow(x, n-1)
end

function pow_tail(x, n)
	local function pow_f (c, r)
		if c == 0 then
			return r
		else
			return pow_f(c - 1, x * r)
		end
	end

	return pow_f(n, 1)
end

-- print(     pow(2, 1000000000))
-- print(pow_tail(2, 1000000000))

pow は普通の再帰で pow_tail が末尾再帰ばーじょん
pow のほうを実行すると

lua: math1.lua:7: stack overflow
stack traceback:
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        ...
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:7: in function 'pow'
        math1.lua:22: in main chunk
        [C]: ?

でエラー

pow_tail を実行中に途中で C-c で止めると

^Clua: interrupted!
stack traceback:
        math1.lua:15: in function <math1.lua:11>
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        ...
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        (tail call): ?
        math1.lua:23: in main chunk
        [C]: ?

と tail call でスタック情報が消えて ? になってることがわかる。

❤️ 投げ銭する

Lua math ライブラリが遅い?

subtech

03:35

math ライブラリが遅いって聞いたけど

#!lua
# math1.lua
for i = -5000000, 5000000 do
	math.abs(i)
end

#!lua
# mathrep.lua
function abs(i)
	if i < 0 then return -i else return i end
end

for i = -5000000, 5000000 do
	abs(i)
end

#!lua
# math2.lua
abs = math.abs
for i = -5000000, 5000000 do
	abs(i)
end

$ repeat 5 time lua -v math1.lua
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.68s user 0.02s system 99% cpu 2.719 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.68s user 0.01s system 99% cpu 2.710 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.68s user 0.01s system 99% cpu 2.712 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.68s user 0.01s system 99% cpu 2.711 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.68s user 0.01s system 99% cpu 2.711 total

$ repeat 5 time lua -v mathrep.lua
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v mathrep.lua  2.51s user 0.02s system 98% cpu 2.562 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v mathrep.lua  2.52s user 0.02s system 99% cpu 2.548 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v mathrep.lua  2.51s user 0.01s system 99% cpu 2.545 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v mathrep.lua  2.52s user 0.01s system 99% cpu 2.547 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v mathrep.lua  2.51s user 0.01s system 99% cpu 2.547 total

$ repeat 5 time lua -v math2.lua
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.17s user 0.01s system 99% cpu 2.195 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.17s user 0.01s system 99% cpu 2.192 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.17s user 0.01s system 99% cpu 2.198 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.17s user 0.01s system 99% cpu 2.191 total
Lua 5.1.1  Copyright (C) 1994-2006 Lua.org, PUC-Rio
lua -v math1.lua  2.17s user 0.01s system 99% cpu 2.193 total

結論：(少なくとも Mac 上の 5.1.1 の math.abs については) テーブルのキーをひくのがおそいだけで、関数自体は math のほうが高速

❤️ 投げ銭する