lua-users home
lua-l archive

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

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