Re: How to clone a table in LJ2-friendly way?

["Dimiter \"malkia\" Stanev" <malkia@...>]

Hi Alex,

I haven't thought much about optimizing deep-copying, but I got 
intrigued. Couldn't there be done something so that less values are kept 
in visited, at expense of latency in detecting the cycles? I've 
implemented something quickly here, but I think it's bit fishy - trying 
to prove it myself (not very good at comp.science). I got little 
improvement, over your algorithm, but not significant, and haven't 
looked at all if it's LJ2-friendly.

This would definitely be keeping me all day busy :), I've already 
started looking how other dynamic languages implement that.

Here is my version, and not directly related to your question, but it's 
also bit faster in lua too:

local tclone2
do
   local function impl(t, visited, rtimes)
      local t_type = type(t)
      if t_type ~= "table" then
	 return t
      end

      -- Don't remember all visited[t] levels
      -- Just remember every once in a 128 times
      -- If there is a recursion it'll still be detected
      -- But 128 stack levels deeper
      assert(not visited[t], "recursion detected (with some latency)")

      if rtimes == 128 then
	 rtimes = 1
	 visited[t] = t
      end

      local r = { }
      for k, v in pairs(t) do
	 r[impl(k, visited, rtimes+1)] = impl(v, visited, rtimes+1)
      end

      if rtimes == 1 then
	 visited[t] = nil
      end

      return r
   end

   tclone2 = function(t)
		return impl(t, {}, 1)
	     end
end

tclone 	2.51308900
tclone2	1.82312800
tclone 	2.50615200
tclone2	1.21087800
tclone 	2.50573100
tclone2	1.48040100

This is something that I've used to generate nodes, not very clever 
either :) - also produces very different results (lua vs luajit) I guess 
due to the math.random() distribution.

local function gen1(is_recursive, level)
   local total, branches = 0, 0
   local function gen1(level)
      local t = {}
      local level = level or 7
      if level <= 1 then
	 return t
      end
      for k=1,math.random(level*20) do
	 t[k] = math.random(level)==1 and gen1(level-1) or tostring(k)
	 total = total + 1
      end
      branches = branches + 1
      return t
   end
   local t = gen1(level)
   print('total',total, 'branches',branches)
   if( is_recursive ) then
      for k1,v1 in pairs(t) do
	 if type(v1) == "table" then
	    for k2,v2 in pairs(v1) do
	       v1[k2] = t
	       -- We need just one recursive entry
	       return t
	    end
	 end
      end
   end
   return t
end

Thanks,
Dimiter "malkia" Stanev.


On 8/20/11 3:13 AM, Alexander Gladysh wrote:
> Hi, list!
>
> Apologies if this question was asked before. If so, please point me in
> the right way.
>
> I have a code that clones tables a lot. I want to make that code run faster.
>
> Looks like LuaJIT 2 does not like our implementation of table clone
> (or copy) function:
>
> https://github.com/lua-nucleo/lua-nucleo/blob/master/lua-nucleo/table-utils.lua#L282-306
>
> When I run luajit2 -jv -jdump on the code, it complains a lot about
> that trace being blacklisted.
>
> So, I have two questions:
>
> 1. What is the modern way to profile with LJ2? Is there some
> description on how to analyze -jdump output? (I think that maybe I
> seen one here in the Lua ML, but I lost the link. Can it be included
> into some LJ2 FAQ or something? Sorry for being lazy.)
>
> 2. How to write a table clone function with a contract, similar to our
> tclone(), that would be more LJ2-friendly?
>
> Thanks,
> Alexander.