• Subject: Re: How to clone a table in LJ2-friendly way?
• From: "Dimiter \"malkia\" Stanev" <malkia@...>
• Date: Sat, 20 Aug 2011 18:03:46 -0700

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

```
```

```
```

```