Re: table library changes (was Re: table.new in 5.3?)

[Sean Conner <sean@...>]

It was thus said that the Great Tim Hill once stated:
> 
> table.insert() / table.remove() — While it’s easy to construct Lua
> functions that have equivalent functionality, I cannot see how you can
> argue that Lua could ALWAYS have “reasonable” performance when compared to
> C .. what if the table implementation changes to use (say) a red/black
> tree, which has vastly different performance characteristics?

  I don't think the implementation has anything to do with it.  But, in
order to bring some facts, here's one of those micro-benchmarks
(ubenchmark).  The code:

	-- ---------------------------------------------------
	-- sys.gettimeofday() returns the current time in microseconds.
	-- Code: https://github.com/spc476/lua-conmanorg/blob/master/src/sys.c
	-- ---------------------------------------------------

	sys = require "org.conman.sys"

	-- -----------------------------------------------
	-- number of iterations, so we have *something* to
	-- measure.
	-- -----------------------------------------------

	MAX = tonumber(arg[1]) or 10000

	-- -----------------------------------------------------------------
	-- This follows the C code (tinsert() from ltablib.c) as much as
	-- possible, hardcoded to the three-parameter variant.  We're doing
	-- worse case scenario here kids, constantly inserting something
	-- into the first position, so we need the three-parameter version.
	-- -----------------------------------------------------------------

	function insert(t,pos,v)
	  local e = #t + 1
	  if pos > e then e = pos end
	  for i = e , pos + 1, -1 do 
	    rawset(t,i,rawget(t,i-1))
	  end
	  rawset(t,pos,v)
	end

	-- -----------------------------------------------------------------
	-- create the table, and make sure we have no garbage laying about.
	-- -----------------------------------------------------------------
	t = {}

	collectgarbage('collect')
	collectgarbage('collect')
	collectgarbage('collect')

	-- Pure Lua

	zen = sys.gettimeofday()
	for i = 1 , MAX do
	  insert(t,1,i)   
	end
	now = sys.gettimeofday()
	print(now-zen)

	t = {}

	collectgarbage('collect')
	collectgarbage('collect')
	collectgarbage('collect')

	-- C

	zen = sys.gettimeofday()
	for i = 1 , MAX do
	  table.insert(t,1,i)
	end
	now = sys.gettimeofday()
	print(now-zen)

  Straightforward I say.  And now, the results:

[spc]lucy:/tmp>lua y.lua 100
0.0024449825286865
0.00029802322387695
[spc]lucy:/tmp>lua y.lua 1000
0.2425549030304
0.025020122528076
[spc]lucy:/tmp>lua y.lua 10000
23.719501972198
2.4551968574524

  Those times, by the way, are in seconds.  

  So, the pure Lua implementation really starts bogging down past 1,000
calls.  You might not notice a call here and there, but it does add up.

  -spc (Will profile for food ... )