ORC – Nim's new memory managment
nim-lang.org
nim-lang.org
1. Is "acyclic" checked by the compiler in any way? or is the programmer basically saying "I'm responsible for making sure this there are no cycles, and I accept that memory will leak if I'm wrong"? I imagine the latter because the compiler check sounds infeasible. (Similarly Rust's memory safety doesn't guarantee there are no leaks.)
2. How does it work with multiple threads? I see a Q/A here [1] which says
> C: We do not do atomic reference counting, we have a shared heap where you move subgraphs completely to a different thread. A graph is always owned by a single thread, there is no need to make the reference counting atomic. We have mechanisms in development to ensure this at runtime or at compile-time, inspired by the Pony programming language.
and would be curious to read the one-page rather than one-paragraph version of this...
It looks like they've talked about shared memory as important for efficiency, eg https://nim-lang.org/araq/concurrency.html (from back in 2013 apparently, and I don't know if it's a "canonical" project view or not) says:
> For real CPU efficiency on commodity hardware shared memory is unavoidable. Message passing doesn't cut it and ultimately doesn't address the same problems. (http://www.yosefk.com/blog/parallelism-and-concurrency-need-...) Also shared mutable memory is unavoidable in a systems programming context.
(I agree with that statement, fwiw.)
It sounds like they haven't built support for shared memory yet; correct? and as this Isolated construct is also in progress, I think there's basically no threading support in Nim yet?
Are they still intending to build shared memory as well as Isolated? Is it intended to be memory-safe (as in the Rust terminology) or not?
You can do shared memory already. There's concurrent hashes and lists, and full threading support. But currently it's on the programmer to not mess up the GC on shared data (eg ensure data graphs are isolated, but it's not too tricky). I use the ESP32's shared queue data structure in the esp-idf to move Nim's native JSON types between FreeRTOS tasks. It's non-copying and more efficient than normal message passing. I also use some shared globals. It all works pretty well.
2. It appears that Nim will use "move ownership of isolated object graph" from one thread to the other. The cycle detection code is very similar to freeing an object graph to moving of the ownership of an object graph to a different thread.
I would also like more clarification from the creators. The above is just how I understand it right now. More simple example code would be great.
First it’s good to note that ARC improves upon the standard reference counting as in Obj-C or Swift by using move and sink‘s which removes many redundant ref’s/decr’s. That is if Swift hasn’t added it. The compiler can infer when ownership is moved or not. Simple ideas but put together in a powerful fashion!
As I understand the isolation check, it is a compile time check that an object being moved to another thread is really isolated with no other external references. This can sometimes be done at compile time similar to acyclic structures though I don’t know the algorithm used. You can also use a runtime check which, appears related to cycle collection. Essentially you can count if the total internal references account for all the references in a given object graph — probably equivalent in cost to an ORC cycle check for that data sub-graph. Whether done at compile time or runtime the plan is to wrap the object in a special ‘Option’ like type ‘Isolated[T]’ that can be accepted by multithreaded constructs. So channels or concurrent queues, etc can declare that they only accept data that can safely be moved between threads using the standard move/sink annotations. This also lets users create their own.
It boils down to ‘Isolated[T]’ just being a data check, and you can move data between threads at your own risk. That’s what I’m doing currently since I’m doing multithreaded embedded programming and using some C Queue constructs. The move/sink and ARC handle the actual data movement. In theory you could use Isolated runtime checks during testing (if your data structures are too tricky for compile time checks), but disable it for release. Similar to cycle checking. There’s a setting to use ORC to print detected cycles, then in release you can turn off ORC.
You're right that if your language has an affine type system (that statically identifies some references as being unique), then you can use static type analysis to skip the runtime analysis at some call sites (those where the transferred subgraph contains only unique references).
I've worked on a system that used a collector based on that Bacon and Arjan paper linked in the article. It's a very interesting paper. It has something like seven colors as opposed to the classic three color collector.
One of the colors is for objects where static type analysis shows that cycles can't exist: ClassA has references to only objects of ClassB and ClassC, ClassC has references to only objects of ClassD, and classes B and D don't contain any references, so objects of any of these classes can't participate in cycles and are acyclic types. If ClassD had references to objects of type ClassA, then there would be a possibility of cycles. Note that tree structures are very common, and static type analysis (without linear/affine types) cannot rule out cycles in recursive data structures such as trees.
Edit: a quick search appears to show Nim has at least some limited support for affine types in its type system, so trees might be a bad example of where { acyclic } is helpful.
Presumably, the { acyclic } pragma is an escape hatch for these cases where the human knows some invariant that isn't visible from just type analysis. As you allude, the GC algorithm is still correct without this information, just less efficient.
I also agree that it looks like they run a variant of the GC algorithm when passing a reference between threads: run a variant of the algorithm that doesn't actually free unreachable objects and pretend to decrement the reference count on the passed object. If the GC algorithm shows that all objects reachable through the passed object would have been GC'd had you decremented its reference count, then it's safe to pass the reference between threads.
On a side note, my use case of a Bacon-Arjan type collector was in a codebase for a domain-specific language with a functional-reactive programming model. We actually used the GC for pruning dependency graphs, to remove nodes that didn't produce externally visible effects. Someone somewhere in a big C++ codebase for the DSL interpreter missed incrementing a reference count, resulting in live nodes being pruned from the graph under rare circumstances. We put a lot of effort into trying to find the missing refcount increment, but ended up ripping out the Bacon-Arjan collector and going with a dead simple mark-and-sweep. We only needed to run the GC in the rare occasions that the graph topology changed, so the performance difference wasn't very noticeable.
On a side note, my use case of a Bacon-Arjan type collector ...
The total CPU overhead of reference counting is proportional to the rate of reference creation and destruction. You can really bring this down if your compiler is told or can figure out which references can be borrowed.
The best case for reference counting is where the compiler is told (or can infer) which references are borrowed, and the code is written in a style that mostly borrows references, and rarely mutates data structures.
One interesting hybrid approach is "one bit reference counting". You have a 1-bit flag in the object header that gets set when a reference to the object gets copied. If a reference gets destroyed, and the object doesn't have the flag set, that means that the referenced object is garbage. Lots of objects never have more than one reference to them, and this little tweak allows for more immediate reclamation of many objects, which allows you to get away with doing tracing GC less often.
Runtime checks would be possible but then you'd have to check every time you create an object.
Not sure if one exists for compile-time either.
And, technically, GCs collect non-garbage, and throw away what remains. They don’t care whether what they throw away contains cycles or not, but have to take care that they don’t keep running in circles when they follow links between objects while collecting the non-garbage.
I don't understand why you said that.
See https://en.wikipedia.org/wiki/Tracing_garbage_collection#Na%...
And yes, you're correct that GCs handle cycles without issue (that's a large part of the reason to use tracing GC over other memory management strategies like ObjC's auto-reference counting).
[1]: https://en.wikipedia.org/wiki/Cycle_detection#Floyd.27s_Tort...
Still, fun algorithm.
Cycle detection at point of creation (when a pointer is set). You can do a full scan of data structure graph after every malloc but that's equivalent to your GC, and clearly horribly, unacceptably expensive.
Otherwise traditional GC use a copying mechanism, what doesn't end up copied is dead.
The old reference counting GC in Nim had that extra copying pass when a type could have cycles.
That said, it's very easy to tell if a type can have cycles or not at compile-time, you just need to check if it refers to itself i.e. does the Node type has a Node field (or a field that can recursively contain a Node field).
Certainly useful at times as I suppose it may be used to ensure you don't have cycles (I imagine that could be useful for resource management) but 'can have cycles' is definitely not 'does have cycles'. It's the latter that's important here.
In the future we might have formal verification helping as well: https://nim-lang.org/docs/drnim.html
In some languages, that’s relatively rare because modifying objects after they are created is rare; immutable objects can be part of cycles, but they can’t be the cause of cycles. That may be enough to make the overhead of cycle detection small.
I guess one could keep track of those ‘dirty’ links, and use them to avoid having to detect cycles in most cases.
It might be enough to add a single bit to each object-to-object pointer indicating “this reference was set after construction of the object” (could be an unused bit in a virtual address, or the least significant bit, so it wouldn’t introduce memory overhead).
With such bits, at first sight, one would only have to check for cycles when P references a _possibly_ younger Q, and destruction of some object (indirectly) decreases P’s ref count to 1. However, things probably would get hairy when objects may have many outgoing and/or incoming pointers (consider a set of 3 objects each referencing the other two).
I’ll go and read the referenced paper (https://researcher.watson.ibm.com/researcher/files/us-bacon/...) to see how it handles this.
In my experience, it's the worst of both worlds. You no longer have the full determinism of reference counting - you only retain it for non-cyclical structures, and in a large enough program, it can be easy to introduce those without noticing (with callbacks etc). But you still have the overhead of RC on every reference assignment.
The way I've gone about it in Nim so far, the refcounts are actually rare, especially copies (which is where increments occur). You can also look at the generated C and it's pretty clear where the overhead is happening, and I've found that in practice it happens rarely enough that this makes a lot of sense. It's pretty different from how things go in Python. In my project I also actually just use ARC and for sure don't have cycles, and the destructor calls are deterministic.
Here's a talk that's somewhat related (refcounts in the "Lobster" programming language, and how it also elides refcount calls using compile-time logic (which ends up being equivalent-ish to a framing in terms of move semantics)): https://www.youtube.com/watch?v=WUkYIdv9B8c