lua-users home
lua-l archive

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

Here is a little bit more optimized version.
assert evalutes first, then checks, so it's probably better to check then call error, or assert (if required by testing tools)
the function is one level less recursive - I do check for k,v being tables before calling impl() - it gives some speedup (lua and luajit) 

But I think the memory allocator is here at blame, but I can't be sure.

local tclone5
do
  local function impl(t, visited, rtimes)
     if visited[t] then
	error( "recursion detected" )
     end

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

    local r = { }

    for k, v in pairs(t) do
       if type(k) == "table"  then
	  if type(v) == "table" then
	     r[impl(k, visited, rtimes+1)] = impl(v, visited, rtimes+1)
	  else
	     r[impl(k, visited, rtimes+1)] = v
	  end
       elseif type(v) == "table" then
	  r[k] = impl(v, visited, rtimes+1)
       else
	  r[k] = v
       end
    end

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

    return r
  end

  tclone5 = function(t)
	      if type(t)=="table" then
		 return impl(t, {}, 1)
	      else
		 return t
	      end
	   end
end

On 8/20/11 4:29 PM, Dimiter "malkia" Stanev wrote:

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.