I didn't find any definitive documentation on this. According to https://nim-lang.github.io/Nim/mm.html, the reference counting used by ARC/ORC is not atomic, so I guess the answer is no for them? The documentation for refc says that it has thread-local heaps, so I guess you can't share refs using that either? Unfortunately, there doesn't seem to be any documentation on what exactly thread-local heaps imply. So is it somehow possible? What about using a GC with shared heap, like the Go GC? Is that even still supported?
My use case is that I want to try to implement some lock-free data structures and I don't want to have to deal with manual memory management. SharedPtr (from https://github.com/nim-lang/threading) might work in this case, but I'm still curious about the general case (where there might be reference cycles).
SharedPtr is indeed the way to go. Either that or UniquePtr, ConstPtr, or the new Isolate construct depending on your usecase. As you point out ARC by default doesn't use atomic ref counting, so sharing refs is quite tricky. The possibility of race conditions from destructors and such are simply too finicky to deal with. refc basically had to copy data or use raw pointers.
As an aside maybe SharedPtr should be resamed SharedRef?
With --mm:atomicArc, does every ref basically turn into a SmartPtr?
Yes, that is exactly what happens.
Aren't new ARC/ORC supposed to replace all other older GCs?
I had to withdraw that RFC so the old GCs are supported throughout the 2.x line. But that only affects the core compiler and standard library.
3rd party libraries can and should embrace the =hook mechanism which is tied to ARC/ORC.
For anybody interested in mm:atomicOrc consider these two papers:
https://pages.cs.wisc.edu/~cymen/misc/interests/Bacon01Concurrent.pdf but beware that there are at least 2 real bugs in the paper, one of which affects us.
For a theoretical better cycle collection algorithm have a look at https://ieeexplore.ieee.org/document/5381976 but it's really complex and it took me months to understand the used notation.
In theory you can combine both papers and implement a cycle collector that is better than anything else.
BTW I read most of the two papers and have been meaning to follow up.
https://pages.cs.wisc.edu/~cymen/misc/interests/Bacon01Concurrent.pdf but beware that there are at least 2 real bugs in the paper, one of which affects us.
This one seems to fully support concurrent operations. There's lots of papers and implementations of it too. I'm curious how much ORC is currently based on it?
For a theoretical better cycle collection algorithm have a look at https://ieeexplore.ieee.org/document/5381976 but it's really complex and it took me months to understand the used notation.
This algorithm has some very bad degenerate case when the number of cycles approaches the number of nodes. Looks like constructs like doubly linked lists perform worse than the standard Bacon style cycle collectors since you need to allocate space for extra metadata to keep track of the discovered cycles. The set operations on those cycles seem expensive for big sets too. Tree structures might also perform badly like doubly linked lists, ie like O(ln(N)) meta-data for trees with back refs?
Unfortunately it seems like some heavy pitfalls for a general purpose language runtime like Nim's. :/
In theory you can combine both papers and implement a cycle collector that is better than anything else.
I don't have a solid proof, but I'm fairly certain that the second algorithm also doesn't work for concurrent cases due to it's single pass nature.
The Bacon algorithms can detect race conditions or prevent them since they mark objects and then clear then clear the marks. The single pass algorithm from Hou et al can't. I ran through a number of their examples and it seems like there'd be no obvious way to prevent race conditions when detecting who owns a given cycles. Maybe there would be a way by modifying the meta-data but then you'd probably need extra locking and coordination, etc.
Also, the authors Hou et al published on this algorithm a couple of times and mention an upcoming concurrent version. However they never seemed to have published it which makes me think it's possible they ran into issues making it concurrent. That's just a hunch though.
I'm curious how much ORC is currently based on it?
It uses its trial deletion algorithm and adds its own heuristics.
cycle/leak detector and embrace ARC
Very interesting, would be nice to have a "cycle detector API".
Good point. But you cannot have race conditions on dead subgraphs (they are dead!), so if you reliably collect in one pass it should be possible.
The pain point was on shared parts of the graph, where one side was dead but the other side had a live root. If you had two algo's running concurrently on different threads then the live root could change. Then the state of the cycles would change in the middle of a pass.
Though that might be solvable, but the overhead of keeping track of the cycles was more concerning because it'd be non-obvious.
Also, wise people have suggested that rather than making the algorithm more complex, turn it into a cycle/leak detector and embrace (atomic)ARC as it simply is a better fit for modern Nim. And I agree.
There's definitely some benefits to that approach. Though wouldn't the cycle detector still need to be thread safe?
Though wouldn't the cycle detector still need to be thread safe?
Sure but then it doesn't have to be fast so that might simplify the solution. On the other hand, just implement the Bacon algorithm already.