Tail call benchmarks

[David Given <dg@...>]

So I hacked up some simple benchmarks to actually measure how fast tail
recursion is. The answers are rather interesting. I enclose the program
and the full results, but in summary the following appears to be true:

- on stock Lua, a tail call is much faster than a non-tail call ---
~100ns as opposed to 150ns. On LuaJIT 1.1.4 it's ~10ns vs ~20ns.

- A tail call passing 0, 1 or 2 parameters costs pretty much the same.
On stock Lua, additional parameters cost ~10ns each. On LuaJIT it costs
a little more, but not much.

- LuaJIT with the JIT *off* is slightly but consistently faster than
stock Lua --- benchmarks complete in about 95% of the time.

- The absolute cost of doing a tail call compared to doing actual work
is quite small.

The interesting case is the following two test functions, which simulate
doing actual work:

local q
local function decision()
	if ((q % 2) == 0) then
		q = q - 1
	else
		q = q * 3
	end
end

local function decision_sub() q = q - 1 end
local function decision_mul() q = q * 3 end
local function decision_tail()
	if ((q % 2) == 0) then
		return decision_sub()
	else
		return decision_mul()
	end
end

On my system, with LuaJIT, decision_tail() takes about 10-15ns longer to
run than decision(). This is a *very small number*, and is probably less
than my stupid little benchmark can actually measure reliably. But it
does seem to lend itself to the idea that I can use tail calls as a form
of sanitised goto without incurring too much performance overhead.

Full results follow:

             terp     off     on
nop           713     674     485
notail        820     779     506
tail          787     761     500
tail1arg      820     763     498
tail2arg      809     767     511
tail3arg      821     780     560
tail4arg      838     787     522
tail5arg      847     799     539
tail6arg      860     836     530
decision      870     835     513
decisiontail  949     918     528

terp = Lua 5.1.3 interpreter
off = LuaJIT 1.1.4 with -O2 -j off
on = LuaJIT 1.1.4 with -O2 -j on (and a slight tweak to make it
        precompile the program)

-- 
┌─── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ───── http://www.cowlark.com ─────
│
│ "People who think they know everything really annoy those of us who
│ know we don't." --- Bjarne Stroustrup

Attachment: bench.lua.gz
Description: GNU Zip compressed data

Attachment: signature.asc
Description: OpenPGP digital signature