Re: Avoiding temporary tables

[Jay Carlson <nop@...>]

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

> On Jun 1, 2013, at 11:02 AM, David Favro <lua@meta-dynamic.com> 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..."]