Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Unify Nim's GC/memory management options #177

Open
Araq opened this issue Nov 6, 2019 · 2 comments
Milestone

Comments

@Araq
Copy link
Member

@Araq Araq commented Nov 6, 2019

This is an alternative to #144. #144 is not dead but scheduled for Nim version 2 which is a couple of years away. The reason for this is that owned is quite a breaking change and we're better served with stability now that version 1 is out and with us for the years to come.

GC: destructors

The plan is to leverage the technology developed for destructors to give us a new GC mode, --gc:destructors that maps ref to atomic refcounting. Atomic RC operations are optimized away when you use the sink and lent annotations as they are outlined in https://nim-lang.org/docs/destructors.html. How cycles are dealt with is an open question, the first implementation will ignore the problem, but there are a couple of solutions:

  1. Detect potential or definite cycles at compile-time.
  2. Detect cycles at run-time in some debug mode.
  3. Introduce a collectCycles(someRef) API for manually freeing cyclic data structures in a subgraph of the heap.
  4. Use the .cursor annotation on object fields that are "parent" / unowning pointers. More on this later.

The GC modes

The plan is to deprecate and remove the GC options until we are left with only --gc:destructors and --gc:boehm. Both options can handle shared heaps and work well with multi-threading, --gc:destructors is optimized for latency and works for all heap sizes, small or really big, --gc:boehm is better for throughput on medium sized heaps (medium here means about 500MB). --gc:destructors also works out of the box on weird targets such as webassembly and has better interop with C/C++/Python/etc.

The .cursor annotation

Besides cycles this proposal has a shortcoming in that so called "cursor" variables imply RC ops. These are very hard to optimize away in a multi-threaded setting and yet also can add considerable runtime overhead:

var it = listRoot # it is a 'cursor' variable
while it != nil:
  use(it)
  it = it.next

The solution is to annotate it with .cursor to tell the compiler it doesn't need to emit RC ops. In fact, .cursor more generally prevents object construction/destruction pairs and so can also be useful in other contexts. The alternative solution would be to use raw pointers (ptr) instead which is more cumbersome and also more dangerous for Nim's evolution: Later on the compiler can try to prove .cursor annotations to be safe, but for ptr the compiler has to remain silent about possible problems.

It is natural to extend the .cursor pragma to object fields in order to break up cycles declaratively:

type
  Node = ref object
    left: Node # owning ref
    right {.cursor.}: Node # non-owning ref

But please notice that this is not C++'s weak_ptr, it means the right field is not involved in the reference counting, it is a raw pointer without runtime checks.

@mratsim

This comment has been minimized.

Copy link

@mratsim mratsim commented Nov 6, 2019

That sounds good, I've notive lots of overhead with a tree data structure with a backpointer to the parent.
However if the {.cursor.} is a raw pointer, does that mean that ref cannot be moved in memory by any of the GC now? This would require removing mark-and-sweep from the get go.

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Nov 6, 2019

That's a good point, since we don't lose the type information (it's still a ref after all) a moving GC is very possible. In other words, a moving GC would ignore the .cursor annotation.

@Araq Araq added this to the Nim2020 milestone Nov 8, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
2 participants
You can’t perform that action at this time.