[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Avoiding temporary tables
- From: David Favro <lua@...>
- Date: Sat, 01 Jun 2013 14:02:08 -0400
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 = 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