Avoiding temporary tables

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Avoiding temporary tables

Dirk Laurie-2
I have an application in which new tables tend to get created
unnecessarily.

E.g.

    myfunc(x)

returns a table with the same keys as x. When called with
an anonymous table, e.g.

   myfunc{1,2,3,4,5}

it is OK to modify the table and return it, but when called with
a table that already has a name, one must make a new copy
in case that name is referenced later.

Is there a way of diagnosing this difference?

Reply | Threaded
Open this post in threaded view
|

Re: Avoiding temporary tables

Enrico Colombini
On 01/06/2013 13.24, Dirk Laurie wrote:

> E.g.
>
>      myfunc(x)
>
> returns a table with the same keys as x. When called with
> an anonymous table, e.g.
>
>     myfunc{1,2,3,4,5}
>
> it is OK to modify the table and return it, but when called with
> a table that already has a name, one must make a new copy
> in case that name is referenced later.
>
> Is there a way of diagnosing this difference?

I don't know if it's possible to tell them apart, but if your
non-literal tables are created by code you could mark them with a
special field (e.g. dup_me=true) or with an empty metatable if they have
none, or reference them from a table.
(not very elegant and not always applicable, I know)

--
   Enrico

Reply | Threaded
Open this post in threaded view
|

Re: Avoiding temporary tables

Luis Carvalho
In reply to this post by Dirk Laurie-2
> I have an application in which new tables tend to get created
> unnecessarily.
>
> E.g.
>
>     myfunc(x)
>
> returns a table with the same keys as x. When called with
> an anonymous table, e.g.
>
>    myfunc{1,2,3,4,5}
>
> it is OK to modify the table and return it, but when called with
> a table that already has a name, one must make a new copy
> in case that name is referenced later.
>
> Is there a way of diagnosing this difference?

A simple solution is to add a parameter that specifies if you want a copy or
not:

local _myfunc = myfunc
myfunc = function (x, copy)
  return _myfunc(copy and copy(x) or x)
end

Cheers,
Luis

--
Computers are useless. They can only give you answers.
                -- Pablo Picasso

--
Luis Carvalho (Kozure)
lua -e 'print((("[hidden email]"):gsub("(%u+%.)","")))'

Reply | Threaded
Open this post in threaded view
|

Re: Avoiding temporary tables

Javier Guerra Giraldez
On Sat, Jun 1, 2013 at 1:01 PM, Luis Carvalho <[hidden email]> wrote:
> A simple solution is to add a parameter that specifies if you want a copy or
> not:
>
> local _myfunc = myfunc
> myfunc = function (x, copy)
>   return _myfunc(copy and copy(x) or x)
> end


what i do sometimes is to add an optional argument for the copy:

myfunc = function (in, dst)
  dst = dst or in
  .... do all work, reading parameters from in, writing to dst
  return dst
end


so, it's used like:

result = myfunc{a,b,c}
-- result is the same table, no allocations

or:

obj = {a,b,c}
myfunc(obj)
-- obj is modified in place

or:

obj = {a,b,c}
result = myfunc(obj, {})
-- result is the new table allocated just before calling
-- obj is not modified


or:

result = myfunc({a,b,c},{d,e})
-- result is a new table, with some 'default' results



--
Javier

Reply | Threaded
Open this post in threaded view
|

Re: Avoiding temporary tables

Jay Carlson
In reply to this post by Dirk Laurie-2
On Jun 1, 2013, at 7:24 AM, Dirk Laurie wrote:

>  When called with
> an anonymous table, e.g.
>
>   myfunc{1,2,3,4,5}
>
> it is OK to modify the table and return it, but when called with
> a table that already has a name, one must make a new copy
> in case that name is referenced later.
>
> Is there a way of diagnosing this difference?

No. Values do not have names; variables do.

I think you want something else: Do I hold the last reference to this table?

This is very useful knowledge in some situations. The MOO language's lists (and strings) are immutable. The language defines mutation-like syntax as sugar for creating fresh lists. So

  lst[1] = 2;

is the same as

  lst = listsub(lst, 1, 2)

If lst is, for example, 16384 elements long--perhaps to contain Apple II firmware or something--the simple implementation involves cloning lst, mutating the copy, setting the variable, and freeing the old lst if no other references exist. So setting all of the elements is O(n^2) since the list is copied n times.

Ben Jackson implemented a bunch of optimizations to recognize this situation and mutate lst in place if it's the last reference. Note that in loop bodies, if you didn't have the last reference initially, you will have the last reference after the first iteration's copy.

I came across another situation where this is useful: lazy XML->LOM parsing. If a program drops the last reference to a subtree, any remaining XML yet to be parsed in that tree cannot affect the future of the program. The XML parser can go into a fast-forward mode, lexing but ignoring the contents of everything until the close tag. http://lua-users.org/wiki/LazyKit (although I probably should see if I have a releasable 5.2 version of that nine-year-old code....)

I don't know how expensive it would be to ask for the GC's help in answering "is this the last reference". This is one of the few times reference-counting implementations win.

Jay
Reply | Threaded
Open this post in threaded view
|

Re: Avoiding temporary tables

Jay Carlson
On Jun 1, 2013, at 11:36 AM, Jay Carlson wrote:

> On Jun 1, 2013, at 7:24 AM, Dirk Laurie wrote:
>
>> When called with
>> an anonymous table, e.g.
>>
>>  myfunc{1,2,3,4,5}
>>
>> it is OK to modify the table and return it, but when called with
>> a table that already has a name, one must make a new copy
>> in case that name is referenced later.
>>
>> Is there a way of diagnosing this difference?
>
> No. Values do not have names; variables do.
>
> I think you want something else: Do I hold the last reference to this table?

[...]

> I don't know how expensive it would be to ask for the GC's help in answering "is this the last reference". This is one of the few times reference-counting implementations win.

Oh, oops. In this case you don't need to ask the GC. The compiler can know the only reference to the table being constructed is the one being passed to myfunc.

Jay
Reply | Threaded
Open this post in threaded view
|

Re: Avoiding temporary tables

David Favro
On 06/01/2013 11:39 AM, Jay Carlson wrote:
> Oh, oops. In this case you don't need to ask the GC. The compiler can know the only reference to the table being constructed is the one being passed to myfunc.

It seems to me that it knows at the place where the call takes place, but
not inside the function, which is I think where Dirk was interested.


Reply | Threaded
Open this post in threaded view
|

Re: Avoiding temporary tables

David Favro
In reply to this post by Jay Carlson
On 06/01/2013 11:36 AM, Jay Carlson wrote:

> I think you want something else: Do I hold the last reference to this table?
>
> This is very useful knowledge in some situations. The MOO language's lists (and strings) are immutable. The language defines mutation-like syntax as sugar for creating fresh lists. So
>
>    lst[1] = 2;
>
> is the same as
>
>    lst = listsub(lst, 1, 2)
>
> If lst is, for example, 16384 elements long--perhaps to contain Apple II firmware or something--the simple implementation involves cloning lst, mutating the copy, setting the variable, and freeing the old lst if no other references exist. So setting all of the elements is O(n^2) since the list is copied n times.
>
> Ben Jackson implemented a bunch of optimizations to recognize this situation and mutate lst in place if it's the last reference. Note that in loop bodies, if you didn't have the last reference initially, you will have the last reference after the first iteration's copy.

This comes up often when creating "Copy-On-Write" implementations of objects
that want mutable semantics but also the ability to efficiently make and
pass around copies that may never get modified, e.g. string classes in C++.

> I came across another situation where this is useful: lazy XML->LOM parsing. If a program drops the last reference to a subtree, any remaining XML yet to be parsed in that tree cannot affect the future of the program. The XML parser can go into a fast-forward mode, lexing but ignoring the contents of everything until the close tag. http://lua-users.org/wiki/LazyKit (although I probably should see if I have a releasable 5.2 version of that nine-year-old code....)
>
> I don't know how expensive it would be to ask for the GC's help in answering "is this the last reference". This is one of the few times reference-counting implementations win.

I think that the need [if it exists, and I'm not saying that it does] would
be better satisfied not by providing the reference count directly to the
application code, but by supporting the desired operation directly, e.g. a
table.shallow_clone() operation, which in addition to providing a more
efficient implementation of a table-copy operation than can currrently be
done without access to the internals, could also have an option to simply
return the original if it is single-referenced.

Another detail that's not clear (to me, since I don't know the internals of
Lua's GC/reference-counter) is whether a table-literal as
function-call-argument actually keeps a reference that is not freed until
after the function-call completes; if so, then the table inside the function
might have two references, one for the parameter variable and one for the
argument value.

-- David


Reply | Threaded
Open this post in threaded view
|

Re: Avoiding temporary tables

Jay Carlson

On Jun 1, 2013, at 2:02 PM, David Favro wrote:

> On 06/01/2013 11:36 AM, Jay Carlson wrote:
> [last reference]
>> I came across another situation where this is useful: lazy XML->LOM parsing. If a program drops the last reference to a subtree, any remaining XML yet to be parsed in that tree cannot affect the future of the program. The XML parser can go into a fast-forward mode, lexing but ignoring the contents of everything until the close tag. http://lua-users.org/wiki/LazyKit (although I probably should see if I have a releasable 5.2 version of that nine-year-old code....)
>>
>> I don't know how expensive it would be to ask for the GC's help in answering "is this the last reference". This is one of the few times reference-counting implementations win.
>
> I think that the need [if it exists, and I'm not saying that it does] would be better satisfied not by providing the reference count directly to the application code, but by supporting the desired operation directly, e.g. a table.shallow_clone() operation, which in addition to providing a more efficient implementation of a table-copy operation than can currrently be done without access to the internals, could also have an option to simply return the original if it is single-referenced.

Yes. That seems like a very nice operation to have for some programming styles. The trivial implementation always fails to guarantee uniqueness and thus does the shallow copy unconditionally.

The shallow copy operator doesn't help with early bailout on lazy table construction though. I mention this case because reflection on reachability is useful in control flow beyond the shallow copy optimization.

> Another detail that's not clear (to me, since I don't know the internals of Lua's GC/reference-counter) is whether a table-literal as function-call-argument actually keeps a reference that is not freed until after the function-call completes; if so, then the table inside the function might have two references, one for the parameter variable and one for the argument value.

I don't think it matters. The implementation can cheat and can't be caught, except through use of debug.*, or by having the called function set up a finalizer on the input table. I don't think there is a guarantee the parameter won't be finalized before return.

Jay


Reply | Threaded
Open this post in threaded view
|

Re: Avoiding temporary tables

Tim Hill
In reply to this post by David Favro

On Jun 1, 2013, at 11:02 AM, David Favro <[hidden email]> wrote:

Ben Jackson implemented a bunch of optimizations to recognize this situation and mutate lst in place if it's the last reference. Note that in loop bodies, if you didn't have the last reference initially, you will have the last reference after the first iteration's copy.

This comes up often when creating "Copy-On-Write" implementations of objects that want mutable semantics but also the ability to efficiently make and pass around copies that may never get modified, e.g. string classes in C++.

Trouble is, both shallow clone and copy-on-write are awkward to implement in a GC model. An optimized shallow clone that didn't do the clone if there is only one reference essentially implies a garbage collect (read: expensive) in order to determine the reachability of the table.

Copy-on-write implies a level of indirection, whereby the "real" table is accessed indirectly by referenced intermediaries, as it is necessary to keep track on which variables reference which (phantom) copy of the table, so that when a write finally occurs, the two sets of references can be split appropriately. And actually, if you are careful, you can implement this in Lua using metatables.

--Tim

Reply | Threaded
Open this post in threaded view
|

Re: Avoiding temporary tables

Jay Carlson

On Jun 1, 2013, at 6:32 PM, Tim Hill wrote:

> On Jun 1, 2013, at 11:02 AM, David Favro <[hidden email]> wrote:
>
>>> Ben Jackson implemented a bunch of optimizations to recognize this situation and mutate lst in place if it's the last reference. Note that in loop bodies, if you didn't have the last reference initially, you will have the last reference after the first iteration's copy.
>>
>> This comes up often when creating "Copy-On-Write" implementations of objects that want mutable semantics but also the ability to efficiently make and pass around copies that may never get modified, e.g. string classes in C++.
>
> Trouble is, both shallow clone and copy-on-write are awkward to implement in a GC model. An optimized shallow clone that didn't do the clone if there is only one reference essentially implies a garbage collect (read: expensive) in order to determine the reachability of the table.

The predicate needed is "may be indirectly reachable", which "only" requires a generational GC cycle in order to answer "no" sometimes. So it's not totally unthinkable to enlist the collector. The collector would need another state to mark the nursery roots with: "half a mark" for directly referenced from a single stack slot. Reaching the value again would upgrade the half-mark to a normal mark. So in

  x = {"multiple references"}
  y = {x, "last reference"}

the table x points to will get a full mark during the scan of the contents of the table y points to. After that pass, y's table itself will only have half a mark, answering the question. (Caller and callee need some care, but I'm too sleepy to figure it out.)  Around this point, you repeat that the GC sounds very expensive relative to the cost of just creating the garbage table in a loop, and I agree. :-)

This is the kind of thing where the compiler can help a lot since it knows any {} is fresh. There's so much literature on single static assignment, I'd assume somebody has solved precisely this problem...somewhere.

Backing up a minute, the motivation for this optimization is circular. There seems little demand for the optimization because little code is written in the shallow_copy-everything style. None of this will affect shootout code because shootout code has already had all its garbage removed. If I had $20,000 of lua.tar.gz complexity budget, I'd spend it on Unicode instead.

IIRC luajit does some kinds of unboxing like this already. It has visibility from the callpoint "dothing({1,2,3})" into the body of dothing and knows whether the argument escapes. If luajit's already doing it, I'm tempted not to think about it much, aside from wistfully saying, "it would be nice if my weirdo lazy structures could do this".

> Copy-on-write implies a level of indirection, whereby the "real" table is accessed indirectly by referenced intermediaries, as it is necessary to keep track on which variables reference which (phantom) copy of the table, so that when a write finally occurs, the two sets of references can be split appropriately.

Yeah, with mutable data, this game is over. One way of looking at the shallow_copy() optimization is that it works because we know that anything taking the fastpath is never written to again, so we don't have to worry about not issuing a new identity for it. But that is a little like saying the parrot will not move again because it's nailed to the perch.

Jay

["It's pining for Erlang--" "It's joined the Choir Immutable! This is an ex-table!" "...well, I'd better replace it, then..."]
Reply | Threaded
Open this post in threaded view
|

Re: Avoiding temporary tables

Tim Hill

On Jun 1, 2013, at 7:50 PM, Jay Carlson <[hidden email]> wrote:
>
> Yeah, with mutable data, this game is over. One way of looking at the shallow_copy() optimization is that it works because we know that anything taking the fastpath is never written to again, so we don't have to worry about not issuing a new identity for it. But that is a little like saying the parrot will not move again because it's nailed to the perch.
>
Actually as I noted it's not that hard to do a "poor mans" copy-on-write in Lua:

-- Simple copy-on-write for tables (demo). Use newcow() to convert a
-- regular table to a COW table, or to clone a COW table. Regular tables
-- should have one reference only. Note that this could be made safer by
-- having newcow() convert the existing table to a COW and create the
-- shadow table, but this would involve the very copy we are trying to avoid.

do
local cowmeta = {
        __index = function(t, k) return t._shadow[k] end,
        __newindex = function(t, k, v)
                for kc, vc in pairs(t._shadow) do rawset(t, kc, vc) end
                setmetatable(t, nil)._shadow = nil
                rawset(t, k, v)
        end
}

--//// newcow(): Convert regular table to COW table
-- t Table to convert (or existing COW to make a clone)
-- returns COW table (or clone of COW table)
function newcow(t)
        return setmetatable({ _shadow = (getmetatable(t) == cowmeta) and (t._shadow) or (t)}, cowmeta)
end
end

t1 = newcow{ a=1, b=2, c=3 }
t2 = newcow(t1)
print(t1.a, t2.a)
t1.a = 10 -- Clone happens here (copy-on-write)
print(t1.a, t2.a)

This code is far from perfect, for example it requires that you don't try to bypass the COW table references (this can be fixed by making newcow() convert the existing table in-place to a COW, but that would requires the shallow copy we're trying to avoid). However, it DOES meet the needs of the original poster, which is to allow a function that does not clone tables where that is not necessary.

--Tim