Incremental mark-and-sweep

[beevik]

Apologies for asking here if this is not the correct place.

In your memory guidelines, you discuss the possibility of future work on an incremental mark-and-sweep algorithm for garbage collection. Have you given this any further thought? We're seeing significant pauses due to garbage collection in our applications and would probably benefit from something other than a stop-the-world GC.

[svaarala]

This is a good place to ask re: development directions etc :)

I've done a few incremental mark-and-sweep experiments - it's (naturally) feasible but not a trivial feature because it affects all pointer maintenance code, and adds some cost over refcounting. I'd personally prefer to have both refcounting and incremental mark-and-sweep, because the snappy memory behavior of refcounting is generally quite nice. But, there's no immediate work on implementing incremental mark-and-sweep at present.

At present, you can do the following:

• Ensure objects are refcounting friendly, i.e. don't contain loops. This is obviously not always possible.
• If memory is not a bottleneck resource and objects with loops are not created at a high rate, you can disable voluntary mark-and-sweep (it will still get triggered on allocation failures, as "emergency GC"). This is quite typical for e.g. games.

[beevik]

Thanks for the response. I'm not surprised that adding an incremental or generational garbage collector is a lot of work.

Another question. How does ref-counting reduce the need to traverse objects during mark-and-sweep? Does the mark-and-sweep algorithm somehow ignore objects that can be garbage collected by ref-counting?

[fatcerberus]

With refcounting enabled, Duktape frees the object as soon as its refcount hits 0 (for local temporary objects that aren't assigned to anything else this can be as soon as they go out of scope), so the mark-and-sweep algorithm never even sees it. It goes a long way in reducing GC pauses, as you can imagine.

[beevik]

@fatcerberus I see. But any objects that haven't been garbage collected (by refcounting) by the time mark-and-sweep happens will need to be considered by the mark-and-sweep algorithm, correct? In other words, the mark-and-sweep algorithm needs to examine the reachability of all known objects, not merely a subset of them.

[fatcerberus]

Indeed. Refcounting doesn’t preclude the need for mark-and-sweep, it just lightens the load by freeing things inline when they can be proven by refcounting alone to be unreachable.

Note that refcount collection can be cascading: if an object is freed by refzero, objects it references are decremented and may be freed at the same time.

[fatcerberus]

As an addendum to the above: in practice the only time refcounting can’t prove an object to be unreachable once it goes out of scope is in the case of cycles (circular references).

[svaarala]

@beevik re:

But any objects that haven't been garbage collected (by refcounting) by the time mark-and-sweep happens will need to be considered by the mark-and-sweep algorithm, correct? In other words, the mark-and-sweep algorithm needs to examine the reachability of all known objects, not merely a subset of them.

That's unfortunately correct: there's no easy to way to foresee which objects will need mark-and-sweep (i.e. will participate in a loop) and an object may enter a loop and exit a loop several times during its lifecycle. The only certain case is where a refcount drops to zero.

So my ideal GC mechanism would:

• Use refcounting for snappy memory behavior in most cases, with predictability as to when that happens (= loop free objects).
• Use incremental GC in the background to recover memory smoothly in the background, with the amount of work done on GC controllable by the application, e.g. more work could be done when lower on memory.
• Use a stop-the-world emergency GC when out of memory and out of other options. Internally this could be just an incremental GC executed for long enough, with no execution activity in-between.

Regarding your use case, is it feasible to disable DUK_USE_VOLUNTARY_GC and request manual GC in suitable locations (say when entering menus, etc)? This depends quite heavily on the application at hand: e.g. if a lot of function objects are created all the time it may not be feasible because (Ecmascript) function objects are unfortunately in a reference loop via their automatic .prototype object.

[fatcerberus]

@svaarala There was talk a while back about doing something to deal with the function prototype cycle issue... are there still plans for such an improvement?

[svaarala]

I'll probably try that before rewriting the GC at some point. It would make the function .prototype a virtual property that gets only actually created when accessed (often it's never accessed). But it wouldn't change the big picture, one would still have objects in loops for other reasons.

[fatcerberus]

Yes, I’m aware—it’s an inherent limitation of reference counting. It’s just that since it’s a language with first-class functions it’d be nice to have temporary functions be able to participate in refzero collection. Especially since Duktape doesn’t yet support arrow functions.

[svaarala]

Agreed, it would be nice, and it's a common request in very low memory targets. One reason is that with pool-based allocators one tries to always serve allocations from pools with as closely matching size as possible. The delay introduced by mark-and-sweep may mean that a larger-than-necessary pool size is used (meaning some memory is temporarily wasted) because some garbage has not yet been freed. There's another solution to this problem, though, and that is to allow the allocator to signal back "I can perform this allocation but it will be suboptimal" which would allow a mark-and-sweep to be performed (at least once in a while) before settling on a suboptimal allocation. Currently an allocation either succeeds or fails, which doesn't provide a way for the allocator signal back anything about memory pressure.

[beevik]

Regarding your use case, is it feasible to disable DUK_USE_VOLUNTARY_GC and request manual GC in suitable locations (say when entering menus, etc)? This depends quite heavily on the application at hand: e.g. if a lot of function objects are created all the time it may not be feasible because (Ecmascript) function objects are unfortunately in a reference loop via their automatic .prototype object.

I'm not 100% sure yet, but I suspect our issue may be due at least in part to the sheer number of live objects we have at any one time. As you state, the more objects there are to mark, the more time it takes to run the algorithm. We can probably play tricks like hiding a manual GC during other expensive operations, but we're seeing GC hitches of as much as 200ms sometimes, which is really hard to hide in an application that needs to run at 30fps or higher.

We'll probably need to do more tracking to figure out how many function objects we are creating. Is there any internal profiling data within duktape we can use to monitor the number of objects currently in existence?

I really appreciate the amount of time you're taking to respond so thoroughly.

[svaarala]

The easiest way to see the number of objects and strings is to enable debug prints and look for mark-and-sweep summaries at the end of mark-and-sweep, similar to:

D0 duk_heap_markandsweep.c:739 (duk__sweep_heap): mark-and-sweep sweep objects (non-string): 0 freed, 376 kept, 0 rescued, 0 queued for finalization
D0 duk_heap_markandsweep.c:576 (duk__sweep_stringtable): mark-and-sweep sweep stringtable: 0 freed, 424 kept
D0 duk_heap_markandsweep.c:1197 (duk_heap_mark_and_sweep): garbage collect (mark-and-sweep) finished: 376 objects kept, 424 strings kept, trigger reset to 39424

There's no public API to inspect the heap in more detail, but the debugger protocol provides access to the heap via https://github.com/svaarala/duktape/blob/master/doc/debugger.rst#dumpheap-request-0x20; the DumpHeap command streams out all objects and property tables in the heap which allows one to reconstruct the object graph. The debugger web UI example converts this data into a JSON representation of the object list.

Finally, you can walk the heap manually by peeking into the internals. heap->heap_allocated is a list of all non-string objects in existence, and strings are in the string table (whose state is also in heap).

[svaarala]

@beevik @fatcerberus Revived some old testing of the on-demand constructor .prototype property here: #1873. It allows refcount collection of anonymous functions in many cases, but is far from a silver bullet, and I'll need to play with it a bit more to figure out if it's worth merging (i.e. complexity is worth the benefits).

((o) Duktape [linenoise] 2.2.99 (v2.2.0-261-gf88e04b6-dirty)
duk> var F = function () {};
= undefined
duk> Duktape.fin(F, function () { print('F finalized'); });
= undefined
duk> F = null;
F finalized
= null

Even if refcount collection is not possible, there's still a small benefit for memory usage in avoiding creating the prototype object for the 90+% of functions which are never actually used as constructors (despite being constructable).