Nim's new cycle collector

[Adnan]

https://forum.nim-lang.org/t/5734#38665

Text:

Progress update:

     The new exception handling implementation is the default with 
--gc:arc (and --gc:orc). [Shipping in 1.2]
     The compiler infers the sink parameter annotation for you, 
there is little need to use it explicitly. [Shipping in 1.2]
     The cycle collector --gc:orc is now much faster. [Not yet in 
an official release.] The implementation does exploit the revived 
acyclic annotation.

That means the existing async designs (stdlib, chronos) work 
without modifications with --gc:orc. (In theory; in practice more 
testing is required.)

If you use ref object like C++'s unique_ptr the performance is on 
par (or - because of Nim's superior parameter passing semantics - 
better than) C++'s unique_ptr: all RC operations are elided and 
the cycle collector isn't involved either.

So how does --gc:orc work?

It's a myth that reference counting doesn't work with cyclic 
structures, but it is true that it reintroduces the "tracing" 
aspects and heuristics when to run the tracing and over which 
subgraphs in order to make this fast enough. The current 
implementation is based on so called "trial deletion" with 
Bacon's improvements, read 
https://researcher.watson.ibm.com/researcher/files/us-bacon/Bacon01Concurrent.pdf for more information.

Highlights

     Only traces the subgraphs that were modified since the last 
GC run, somewhat comparable to a generational GC (but in theory 
actually better than a generational GC). What you don't touch in 
memory the GC doesn't touch either, it's independent of the 
involved heap sizes (but not independent of the involved 
subgraphs (SCCs) ...).
     Our implementation uses a novel "type tag free" optimization 
so that most heap objects do not have to store a type tag in the 
heap, saving 8 bytes of memory which we use to make cyclic root 
removal an O(1) operation. This implies that at runtime we 
exploit even more acyclic cases than previous designs.