3 ms·

1. As I understand the {.acyclic.} pragma is way to telling the compiler that you take full responsibility. Otherwise without the {.acyclic.} pragma it will spe

1. As I understand the {.acyclic.} pragma is way to telling the compiler that you take full responsibility. Otherwise without the {.acyclic.} pragma it will spend the extra time scanning the objects for cycles. 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.

elcritch 6y ago
The isolation technique is an area I’ve been interested in and following. It’s not too well documented as that area is a work in progress and not really useable currently. Almost though! 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.
- KMag 6y ago
  > As I understand the isolation check, it is a compile time check 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).
KMag 6y ago
I think you're mostly correct about the { acyclic } pragma, except that the "Otherwise without" part needs a provisio "if static type analysis doesn't prove that objects of the type cannot participate in cycles". 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.
- elcritch 6y ago

elcritch 6y ago

The isolation technique is an area I’ve been interested in and following. It’s not too well documented as that area is a work in progress and not really useable currently. Almost though! 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.

KMag 6y ago
> As I understand the isolation check, it is a compile time check 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).

KMag 6y ago

I think you're mostly correct about the { acyclic } pragma, except that the "Otherwise without" part needs a provisio "if static type analysis doesn't prove that objects of the type cannot participate in cycles". 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.

elcritch 6y ago