lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

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 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
   local function impl(t, visited, rtimes)
      local t_type = type(t)
      if t_type ~= "table" then
	 return t

      -- 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

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

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

      return r

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

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
      for k=1,math.random(level*20) do
	 t[k] = math.random(level)==1 and gen1(level-1) or tostring(k)
	 total = total + 1
      branches = branches + 1
      return t
   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
   return t

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:

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?