As mentioned in a post a couple days ago, the Holy Grail cleanup algorithm cwal has been searching for since almost two years was validated today :-D. The original algorithm, as described in the prior post, is in place and (with only a small bit of pointer fudgery) cleans up all script-unreachable values. This operation is more time-expensive than a sweep-up (potentially by orders of magnitude), but it is "complete," in that it cleans up any values in the current scope which a script cannot see. (Sidebar: that could be bad for C-side bindings if they're not careful to ensure that sure their Value instances are reachable via a variable reference. FIXME: we need a safe place to stash such values outside of a script's visibility. That said, all the current native plugins react just fine to this change, but i can conceive code which would be ill-behaved.)

Anyway...

Tonight i replaced th1ish's auto-sweep (which runs every few expressions, when it is safe to do so) with the vacuum algorithm and, after some relatively small amount of debuggering, it's working beautifully. All existing unit tests still run, and even valgrind is happy (which is the real test, as the engine is a huge nest of pointers doing all sorts of tricky things).

Interestingly, only about 1 in 15 vacuums actually cleans up more values than a sweep operation does (peaking at just over 2 times as many more in some of the existing unit tests). Because sweeping is much cheaper than vacuuming, this implies that further optimization is in order to use sweep most of the time and run a vacuum only occasionally (say once in 5-10 sweep-ups or so). The peak memory usage is, for these test scripts, practically unchanged (+/- 500 bytes, depending on the script), arguing for sweep over vacuum (since sweeping is much cheaper), but vacuuming can catch all those pesky cycles. (That said, for the types of scripts th1ish is really intended for (library test script bindings), vacuuming should never be necessary. But it's fun to work on nonetheless.)

However, those optimizations are for tomorrow evening. Tonight, i celebrate!

In parting: an example of what this means. Consider this code (which is real th1ish code, by the way):

var obj = object{} // refcount == 1
obj.(obj) = obj // refcount == 3 (var + key + value)
unset obj // refcount == 2 and value is orphaned, not reachable

The new algorithm is capable of weeding out and destroying all such unreachable values, while leaving all reachable values intact. The algorithm can be summarized in these steps:

A) create a new temp scope

B) fiddle with bits to make the new scope look like the parent of the current scope (as opposed to its child, which it normally would be).

C) copy all declared variables from current scope to temp scope. Because the temp scope "looks older," the variables, and all values reachable via them, are moved into the temp scope.

D) clean up the current scope, freeing any remaining values it owns (temporaries and orphaned values).

E) fiddle with bits to make the new scope look like the child of the current scope.

F) copy all declared variables from the new scope to the current scope. This does the reverse of (C), moving the values back into their original owning scope.

That's it!

Due to side-effects of the lifetime tracking mechanism, that moves all reachable values (variables and anything they reference) around while removing any temporaries and orphaned cyclic structures, which get cleaned up in step (D).

Happy Hacking!