5 ms·

Couple questions about how this works. 1. Is "acyclic" checked by the compiler in any way? or is the programmer basically saying "I'm responsible for making su

Couple questions about how this works. 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... [1] https://forum.nim-lang.org/t/5734 https://forum.nim-lang.org/t/5734

disruptek 6y ago
You can read about the reasoning behind subgraph ownership here: https://github.com/nim-lang/RFCs/issues/244 https://github.com/nim-lang/RFCs/issues/244
- scottlamb 6y ago
  Thanks. If I'm understanding correctly: with Isolated (which is still being built), any given object is reachable from only one thread. It can be used for message-passing but not shared memory. It looks like they've talked about shared memory as important for efficiency, eg https://nim-lang.org/araq/concurrency.html 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-different-tools.html 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?
  - elcritch 6y ago
    > 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? 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.
treeform 6y ago
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.
wisty 6y ago
If it's verifiable by the compiler, then it shouldn't need to have a pragma, just optimise it automatically. (OK, it might be useful as a hint). I'm guessing there's grey areas where this would be some kind of halting problem type issue though - you won't know until you run it. Constructing a graph that you know to be a tree would be a trivial example. Runtime checks would be possible but then you'd have to check every time you create an object.
- throwaway_pdp09 6y ago
  Pretty sure no efficent run-time algo for general cycle detection exists. It has (AFAIK) been a big area in garbage collection for a long while, so smart people have been all over it. Not sure if one exists for compile-time either.
  - bobthebuilders 6y ago
    How do GCs collect cycles then? I'm pretty sure most modern GCs handle cycles effortlessly.
    - Someone 6y ago
      It depends on what you call ‘effortlessly’. 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.
      - imtringued 6y ago
        Graph scans are trivial to implement though.
        throwaway_pdp09 6y ago
        Would you consider full graph scan efficient? Would you like a full graph scan after every allocation, millions of times a second? I don't understand why you said that.

disruptek 6y ago

You can read about the reasoning behind subgraph ownership here: https://github.com/nim-lang/RFCs/issues/244 https://github.com/nim-lang/RFCs/issues/244

scottlamb 6y ago
Thanks. If I'm understanding correctly: with Isolated (which is still being built), any given object is reachable from only one thread. It can be used for message-passing but not shared memory. It looks like they've talked about shared memory as important for efficiency, eg https://nim-lang.org/araq/concurrency.html 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-different-tools.html 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?
- elcritch 6y ago
  > 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? 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.

treeform 6y ago

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.

wisty 6y ago

If it's verifiable by the compiler, then it shouldn't need to have a pragma, just optimise it automatically. (OK, it might be useful as a hint). I'm guessing there's grey areas where this would be some kind of halting problem type issue though - you won't know until you run it. Constructing a graph that you know to be a tree would be a trivial example. Runtime checks would be possible but then you'd have to check every time you create an object.

throwaway_pdp09 6y ago
Pretty sure no efficent run-time algo for general cycle detection exists. It has (AFAIK) been a big area in garbage collection for a long while, so smart people have been all over it. Not sure if one exists for compile-time either.
- bobthebuilders 6y ago
  How do GCs collect cycles then? I'm pretty sure most modern GCs handle cycles effortlessly.
  - Someone 6y ago
    It depends on what you call ‘effortlessly’. 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.
    - imtringued 6y ago
      Graph scans are trivial to implement though.
      - throwaway_pdp09 6y ago
        Would you consider full graph scan efficient? Would you like a full graph scan after every allocation, millions of times a second? I don't understand why you said that.