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

Proposal to add 'owned' refs to Nim #144

Open
Araq opened this issue Mar 28, 2019 · 95 comments

Comments

@Araq
Copy link
Member

@Araq Araq commented Mar 28, 2019

Owned refs

This is a proposal to introduce a distinction between ref and owned ref in order to control aliasing and make all of Nim play nice with deterministic destruction.

The proposal is essentially identical to what has been explored in the Ownership You Can Count On paper.

Owned pointers cannot be duplicated, they can only be moved so they are very much like C++'s
unique_ptr. When an owned pointer disappears, the memory it refers to is deallocated. Unowned refs are reference counted. When the owned ref disappears it is checked that no dangling ref exists; the reference count must be zero. The reference counting can be enabled with a new runtime switch --checkRefs:on|off.

Nim's new returns an owned ref, you can pass an owned ref to either an owned ref or to an unowned ref. owned ref models the spanning tree of your graph structures and is a useful tool also helping Nim's readability. The creation of cycles is mostly prevented at compile-time.

Some examples:

  type
    Node = ref object
      data: int

  var x = Node(data: 3) # inferred to be an ``owned ref``
  let dangling: Node = x # unowned ref
  assert dangling.data == 3
  x = Node(data: 4) # destroys x! But x has dangling refs --> abort.

We need to fix this by setting dangling to nil:

  type
    Node = ref object
      data: int

  var x = Node(data: 3) # inferred to be an ``owned ref``
  let dangling: Node = x # unowned ref
  assert dangling.data == 3
  dangling = nil
  # reassignment causes the memory of what ``x`` points to to be freed:
  x = Node(data: 4)
  # accessing 'dangling' here is invalid as it is nil.
  # at scope exit the memory of what ``x`` points to is freed

The explicit assignment of dangling = nil is only required if unowned refs outlive the owned ref they point to. How often this comes up in practice remains to be seen.

Detecting the dangling refs at runtime is worse than detecting it at compile-time but it also gives different development pacings: We start with a very expressive, hopefully not overly annoying solution and then we can check a large subset of problems statically with a runtime fallback much like every programming language in existance deals with array index checking.

This is how a doubly linked list looks like under this new model:

  type
    Node*[T] = ref object
      prev*: Node[T]
      next*: owned Node[T]
      value*: T

    List*[T] = object
      tail*: Node[T]
      head*: owned Node[T]

  proc append[T](list: var List[T]; elem: owned Node[T]) =
    elem.next = nil
    elem.prev = list.tail
    if list.tail != nil:
      assert(list.tail.next == nil)
      list.tail.next = elem
    list.tail = elem
    if list.head == nil: list.head = elem

EDIT: Removed wrong proc delete.

Nim has closures which are basically (functionPointer, environmentRef) pairs. So owned also needs to apply to closures. This is how callbacks can be done:

  type
    Label* = ref object of Widget
    Button* = ref object of Widget
      onclick*: seq[owned proc()] # when the button is deleted so are
                                  # its onclick handlers.

  proc clicked*(b: Button) =
    for x in b.onclick: x()

  proc onclick*(b: Button; handler: owned proc()) =
    onclick.add handler

  proc main =
    var label = newLabel() # inferred to be 'owned'
    var b = newButton() # inferred to be 'owned'

    b.onclick proc() =
      label.text = "button was clicked!"

    createUI(label, b)

main is transformed into something like:

  proc main =
    type
      Env = ref object
        label: owned Label
        b: owned Button

    var env: owned Env
    env.label = newLabel()
    env.b = newButton()

    b.onclick proc(envParam: Env) =
      envParam.label.text = "button was clicked!"

    createUI(env.label, env.b)

This seems to work out without any problem if envParam is an unowned ref.

Pros and Cons

This model has significant advantages:

  • We can effectively use a shared memory heap, safely. Multi threading your code is much easier.
  • Deallocation is deterministic and works with custom destructors.
  • We can reason about aliasing, two owned refs cannot point to the same location and that's enforced at compile-time. We can even map owned ref to C's restrict'ed pointers.
  • The runtime costs are much lower than C++'s shared_ptr or Swift's reference counting.
  • The required runtime mechanisms map to weird, limited targets like webassembly or GPUs.
  • Porting Nim code to take advantage of this alternative runtime amounts to adding the owned keyword to strategic places. The compiler's error messages will guide you.
  • Since it doesn't use tracing the runtime is independent of the involved heap sizes. Heaps of terabytes or kilobytes in size make no difference.
  • Doubly linked lists, trees and most other graph structures are easily modeled and don't need a borrow checker or other parametrized type system extensions.
  • Valgrind and the Clang memory sanitizers work out of the box with Nim as it doesn't use conservative stack tracing anymore.

And of course, disadvantages:

  • Dangling unowned refs cause a program abort and are not detected statically.
  • You need to port your code and add owned annotations.
  • nil as a possible value for ref stays with us as it is required to disarm dangling pointers.

Immutability

This RFC is not about immutability, but once we have a clear notion of ownership in Nim, it can be added rather easily. We can add an opt-in rule like "only the owner should be allowed to mutate the object".

Possible migration period

Your code can either use a switch like --newruntime and needs to use owned annotations or else
you keep using Nim like before. The standard library needs to be patched to work in both modes. owned is ignored if --newruntime is not active. We can also offer an --owned switch that enables the owned checks but does use the old runtime.

@jido

This comment has been minimized.

Copy link

@jido jido commented Mar 28, 2019

You could define a standard macro that does node = nil, to hide this unsightly sight.

@andreaferretti

This comment has been minimized.

Copy link

@andreaferretti andreaferretti commented Mar 28, 2019

Not being familiar with C++, I am confused by the direction Nim is taking. I am confused about the whole new runtime thing, and I am a little worried seeing how much effort goes into inventing new semantics and patching the standard library to work in both modes, instead of making Nim ready for a 1.0 release, with garbage collection, thread-local heaps and a shared unsafe heap as it was advertised before.

Do not misunderstand me: I think the semantics of Nim about mutability is not great now, and fixing that will probably require some form of ownership concept. But it seems to me that the new runtime is an experiment of which the semantic is not formally proved to work and something that can open a myriad of new bugs.

Recently, we have seen new work about

  • changing the semantics of exceptions
  • using destructors in place of GC
  • moving to a shared heap model

These are not small changes: they are quite fundamental distinguishing features of a language. I may even agree that these are useful directions to explore. But it leaves me worried about what will happen for Nim as I know it now. A language that uses garbage collection, freeing me from reasoning pervasively about ownership, which I can compile to C (not C++), which has a limited but simple threading model which I can easily reason about

@nc-x

This comment has been minimized.

Copy link

@nc-x nc-x commented Mar 28, 2019

I am a little worried seeing how much effort goes into inventing new semantics and patching the standard library to work in both modes, instead of making Nim ready for a 1.0 release

IMO, it makes sense to do these changes before 1.0 release because -

they are quite fundamental distinguishing features of a language.

But it leaves me worried about what will happen for Nim as I know it now.

As far as I understand, destructors and owned refs are optional features that you may or may not choose to use. And they provide better safety as well as optimization opportunities wherever required.


But incremental compilation should be postponed after v1. Instead (after destructors and owned refs are implemented) one release cycle should focus on bugfixes only.

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Mar 28, 2019

@andreaferretti I share your fears and this is indeed all stuff for version 2. Having said that, if we release v1 as it is with breaking changes in the future for v2 then why did we even take so long for v1. v1 took so long we might as well put in the extra effort and get the language into a shape we're confident it'll stand the test of time.

Also, most regressions are not even due to feature changes. Most regressions are the result of bugfixes. That's terrible but apart from testing ever more things I'm out of ideas how to deal with this problem.

Having said that, when was the last time we made Nim worse? I don't see it, nil for strings and seqs is gone (yay), func started to become a thing (people like it), toOpenArray was added, exceptions started to work with async, tons of bugs have been fixed, the spec became more refined, the documentation improved and we put a lot of effort into our testing infrastructure.

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Mar 28, 2019

But incremental compilation should be postponed after v1. Instead (after destructors and owned refs are implemented) one release cycle should focus on bugfixes only.

Completely agree, if we improve the DLL/static lib generation stability that also offers a way out of the increasing compile-times.

@andreaferretti

This comment has been minimized.

Copy link

@andreaferretti andreaferretti commented Mar 28, 2019

Having said that, when was the last time we made Nim worse?

Uh, sorry for the misunderstanding, I never claimed that! In fact, I have seen many improvements :-)

It's just that new features are piling and I am not sure that the language that will be standardized as v1 will resemble much the original vision of Nim (let's say Nim as we know now)

@mratsim

This comment has been minimized.

Copy link

@mratsim mratsim commented Mar 28, 2019

As far as I understood, the GC is still there in V1, how would the transition work?

AFAIK destructors are replacing the old =destroy that didn't really work so we are not changing usual Nim semantics with destructors but refining them.

However owned refs are quite different indeed.

The macro to hide = nil can be called dispose ;)

@andreaferretti

This comment has been minimized.

Copy link

@andreaferretti andreaferretti commented Mar 28, 2019

Of course the GC is there in v1, to make a transition possible. But a transition to what? To a language without GC? This is unfortunately still not clear to me.

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Mar 28, 2019

To a language without GC? This is unfortunately still not clear to me.

Yes but it's easy to misinterpret when you put it this way. Memory management is still mostly declarative and automatic. And it's not like the existing GC frees you of memory managment problems, you can easily have a cache that keeps growing in size and becoming a logical memory leak. (I have seen this happening in production a lot of times). In addition to that the GC doesn't close your sockets etc reliably, the new runtime would.

@mratsim

This comment has been minimized.

Copy link

@mratsim mratsim commented Mar 28, 2019

The proper term is resource management, resource being something that cannot be trivially copied/aliased:

  • memory
  • file handles and streams
  • database handles
  • sockets

Though putting file.close() in a finalizer kind of works at the moment.

@akavel

This comment has been minimized.

Copy link

@akavel akavel commented Mar 28, 2019

If I understand correctly, the reference counting would default to being disabled (in release builds?). If yes, do I understand correctly, that it is essentially a similar level of danger as disabled bounds checking? (Which is also disabled by default in release builds, right?)

If yes, could there be some "middle" level of compilation, with optimizations as in release build, but with bounds checks + owned refcounting enabled? Say, "memory-safe release", or "bounds-checked release", or something? (Name totally open to being bikeshedded.) Or at least some flag for the release build, that would enable both checks at once? I mean, if I had bounds checks enabled in release builds as of now (is it even possible?), I wouldn't know I need to add another flag to "be safe" without reading this RFC. Generally, I would very much like an idea of a well advertised "safe" mode of compilation, for people who want some benefits of a "release" build, but "safety" is paramount to them, who are willing to trade some performance if this means keeping as much safety as possible (in hope of avoiding heartbleed-style bugs, etc.).

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Mar 28, 2019

@akavel Yes, completely agree and I consider it part of this proposal. You can use --checks:on with --opt:speed --lineTrace:off for servers / critical software. You always could. We need to communicate it better.

Also you can disable the checking only for the performance critical parts with {.push checks:off.}...{.pop.}.

Furthermore https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/Undangle.pdf
suggests it is a good tradeoff to disable the ref counting for stack slots:

e. It also shows that dangling pointers stored in the stack and registers are specially short-lived; at use time all but one dangling pointers are stored in the heap

@nc-x

This comment has been minimized.

Copy link

@nc-x nc-x commented Mar 28, 2019

@akavel
You can enable bounds checking or any other checking in release build.
Check nim --fullhelp ->

nim --fullhelp | grep bound
  --boundChecks:on|off      turn bound checks on|off

Also see config/nim.cfg in the Nim install dir, and search for release in it, you can enable the checks there, or create a release-safe and send a PR to nim ;D

@akavel

This comment has been minimized.

Copy link

@akavel akavel commented Mar 28, 2019

@Araq Thanks! I'm only not yet clear what exactly are you referring to by "it"; in particular, as part of the proposal, are you intending to add something like the release-safe mentioned by @nc-x, or maybe would you be OK with me/someone sending a PR with an attempt to do it? Or you don't want to add something like this?

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Mar 28, 2019

I wanted to add -d:safe for a long time but it's very orthogonal to this RFC because in this RFC I propose --refChecks:on/off which is included by --checks:on/off just like all the other runtime checks we perform.

@nepeckman

This comment has been minimized.

Copy link

@nepeckman nepeckman commented Mar 28, 2019

Out of curiosity, how hard would it be to write a prototype of this runtime? I'm a little cautious about this feature for a lot of the same reasons as @andreaferretti mentioned, but I can see the potential benefits as well. Playing with a prototype would be really helpful in understanding how Nim would change.

As a small aside, I like this proposed syntax for unowned refs better: https://forum.nim-lang.org/t/4743#29636

@Varriount

This comment has been minimized.

Copy link

@Varriount Varriount commented Mar 29, 2019

I posted this on IRC, but I thought it would be good to post it here as well:

How is this different from the unique_ptr and raw pointers that C++ offers? It seems that an owned reference is equivalent to a unique_ptr, and an unowned reference equivalent to a raw pointer. The only difference is lack of shared_ptr, and optional runtime debug checks (which are largely equivalent to using valgrind, purify, or the various memory sanitizers available).

Let say I have a piece of important, complex, multithreaded server software that I'm using in a commercial product. It's important that it not crash unexpectedly or corrupt memory, otherwise I'll have angry customers (and an angry manager) to deal with.

  • If I compile it with --checkRefs:on, and some weird threading race condition occurs that causes an unowned ref to live beyond the lifetime of its object, then the server program aborts.
  • If I compile it with --checkRefs:off, and the same situation occurs, the program might or might not continue on beyond the race condition. At best, nothing bad will occur. At worst, I'll have some form of hard-to-trace memory corruption that causes a segmentation fault somewhere random.

Both these outcomes are rather unappealing - I'm facing a higher risk* of programming oversights that lead to random program aborts and memory corruption.

This change would appear to actually put Nim in a situation that's worse than C++ with regards to memory management - at least C++ has the shared_ptr type! For this new runtime, one would have to construct a shared_ptr type on top of plain reference types. I don't know how difficult that would be to implement, but I would be willing to bet that there will be some hard-to-handle corner cases.

Look at all the commonly used programming languages - Python, Java, Ruby, Javascript, C#, C++, C, PHP, Go. Out of all of those, only 2 have memory management schemes that involve manual or semi-manual memory management mechanisms of the sort being proposed. Even Rust has something that, while not exactly as automatic as a garbage collector, is at least as surefire as one.

I know there are alternatives out there. What about doing pure reference counting, and trying to detect possible reference cycles at compile time using the type graph? or special-casing reference cycles so that users have to mark a break point?


At the end of the day, I think the decision on whether to implement this proposal comes down to who and what Nim is targeting. If Nim is supposed to be used as a general programming language, in the same areas as Go, C#, Java, and Python, then it needs to have reliability, in addition to performance. However, if Nim is supposed to be used primarily in embedded or HPC systems, where assembly, C, and C++ are the only suitable candidates, then perhaps performance needs to be the only concern.

Personally, not having to worry about memory corruption or resource leaks** is one of the features that drew me to Nim. Having a language that had the speed of C, with the reliability and ease-of-use of Python, was what I was looking for.

* Relative to Nim's current semantics
** Beyond bad cache logic and such

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Mar 29, 2019

which are largely equivalent to using valgrind, purify, or the various memory sanitizers available

No, they are not. The difference is that the scheme detects dangling pointers when they exist, not when they are deref'ed. That's something that valgrind, purify etc cannot detect because it would violate C's semantics. Whether that is in practice a big difference or not remains to be seen.

Let say I have a piece of important, complex, multithreaded server software that I'm using in a commercial product. It's important that it not crash unexpectedly or corrupt memory, otherwise I'll have angry customers (and an angry manager) to deal with.

We don't have many of these highly reliable multithreaded servers in Nim. In practice the existing GC plus the various complex interactions with the OS's APIs mean that we have more unreliability than with a simpler more deterministic solution. Proof: Look at Nim's issue tracker.

This change would appear to actually put Nim in a situation that's worse than C++ with regards to memory management - at least C++ has the shared_ptr type!

No, the shared_ptr type is worse than a safer unique_ptr as you need to watch out you don't create cycles.

Personally, not having to worry about memory corruption or resource leaks is one of the features that drew me to Nim.

You can have plenty of resource leaks, the GC only collects memory.

@jido

This comment has been minimized.

Copy link

@jido jido commented Mar 29, 2019

If I compile it with --checkRefs:on, and some weird threading race condition occurs that causes an unowned ref to live beyond the lifetime of its object, then the server program aborts.

The point is that you get a chance to detect and correct the weird threading race condition in that mode.

I do support adding a shared_ptr equivalent but I am sure it is not needed right now.

@cooldome

This comment has been minimized.

Copy link
Member

@cooldome cooldome commented Mar 30, 2019

@Varriount
IMO, this PR paves the way for safe and overhead free memory management. Reference counting adds noticeable overhead especially if you consider atomic inc/dec instructions that have 18-25 cycles delay (https://www.agner.org/optimize/instruction_tables.pdf).

If you do have use case where you have multiple references and there is no way you can say which one is the owner, all references have 100% dynamic life time (improbable but possible use case) then shared_ptr and its overhead become justifiable. shared_ptr in Nim is possible even now, if you need it. See PR: nim-lang/Nim#10485. Though, I don't think everyone needs to pay reference counting overhead.

@Varriount

This comment has been minimized.

Copy link

@Varriount Varriount commented Mar 30, 2019

@cooldome How does this pave the way for anything safer than what Nim currently has?

As the language currently stands, use-after-free and memory corruption bugs are practically non-existent - one has to be using ptr types, interfacing with C code or using some other explicitly unsafe mechanism to cause them.

This proposal would change that. Any program using references could exhibit those bugs.

Rebuttals to this fact seem to be the following:

  1. Just write more/better tests
  2. Implement checks in the compiler

With regards to the first point, unfortunately we do not live in a perfect world. Code gets written all the time that isn't properly tested, whether out of laziness, or because an individual simply doesn't have time to. In many situations, it is also incredibly difficult to write comprehensive tests (such as when code relies heavily on external data, such as a REST API); there is only so much mocking and separation one can do.

With regards to the second point, without drastically changing the language, no amount of static analysis could ever hope to find all the situations in which use-after-free situations could arise. To do so, one would need to solve the halting problem. Even finding some of those situations will be hard, especially when one considers how multithreading can affect when parts of a program's logic (and therefore memory allocation, deallocation, and accesses) may run.

I would much prefer just biting the bullet and using atomic reference counting and cycle detection. If a program is too slow, I throw more computing power behind it. If I can't do that, then I can resort to using raw pointers and the risks they bring (and let's not kid ourselves here, that's what this proposal is all about, turning the majority of references into a kind of raw pointer type).

Technical implementation aside, what doesn't seem to be considered here is how this behavior will be perceived by those evaluating Nim. Most commonly used programming languages don't have the possibility of use-after-free or memory corruption bugs. The worst thing most languages have that's even remotely similar is null pointer/reference errors.
How will it look to those coming from C#, Javascript, etc. that they now have to put more thought into how long an object will live? "Why switch from Javascript to Nim, and face errors I've never seen before, when I could switch instead to something like Go?"

I'm not saying that Nim should just become a clone of another language, but there is a limit to what people are willing to consider.

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Mar 30, 2019

With regards to the second point, without drastically changing the language, no amount of static analysis could ever hope to find all the situations in which use-after-free situations could arise. To do so, one would need to solve the halting problem.

That's wrong. Almost always whenever somebody brings up the halting problem it's wrong. What generally happens is that the analysis is pessimistic, but safe. For example

var s = "string"
if haltingProblem:
   s = 34 

The Nim compiler does not allow s = 34 and it doesn't have to solve the halting problem which is encoded in the condition.

I would much prefer just biting the bullet and using atomic reference counting and cycle detection. If a program is too slow, I throw more computing power behind it. If I can't do that, then I can resort to using raw pointers and the risks they bring (and let's not kid ourselves here, that's what this proposal is all about, turning the majority of references into a kind of raw pointer type).

Atomic reference counting with cycle detection is one of the slowest GC algorithms you could come up with! And if you don't mind its overhead nobody is stopping you to leave on refchecks all the time for everything.

and let's not kid ourselves here, that's what this proposal is all about, turning the majority of references into a kind of raw pointer type

Pure FUD.

"Why switch from Javascript to Nim, and face errors I've never seen before, when I could switch instead to something like Go?"

How is that different from today where thousands of programmers already picked Go and not Nim? And since when is performance not important to have and a feature of its own? Most existing users of Nim picked it - among other things - for its performance.

@zah

This comment has been minimized.

Copy link
Member

@zah zah commented Mar 31, 2019

One of the best qualities of Nim is that most of the time it is a strict superset of the capabilities of any other language - that is, any code that you can imagine in Ruby, JavaScript, C++ or Malbolge can have an equivalent representation in Nim, composed of roughly the same abstractions, expressed with similar elegance.

Completely eliminating the GC would lose us this quality because certain APIs rely on the existence of a GC. With that said, I don't see this proposal as a definitive plan to eliminate the GC from Nim, but rather as a way to greatly increase the number of programs that can be written without one. In particular, the standard library of Nim will be written with more care regarding resource management and the result will be that many user programs will become smaller and more efficient. Where the nature of the problem still requires more ad-hoc sharing, I think Nim can still provide a shared ref pointer type in the future that will trigger the inclusion of the current GC in your program. We don't have to lose what we already have.

@cdunn2001

This comment has been minimized.

Copy link

@cdunn2001 cdunn2001 commented Mar 31, 2019

@Araq, Is there a branch where you're working on this? Or when would you expect a somewhat working (or at least building) prototype? That might make the discussion more concrete.

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Mar 31, 2019

The prototype implementation hides behind the --newruntime switch. But please don't report bugs with it yet, it's too early. We hope to have a prototype within the next weeks but no promises.

@dom96

This comment has been minimized.

Copy link
Member

@dom96 dom96 commented Mar 31, 2019

So if I understand correctly what you're proposing are optional annotations that allow the GC to be turned off, is that correct?

What follows is that libraries need to be explicitly written to support these annotations, right? So we will have two different ways to do things in Nim and end up in situations where libraries are written without a care in the world that they use a GC, and that will mean my GC-free app that uses owned won't be able to use those libraries. Is my assumption correct?

@gemath

This comment has been minimized.

Copy link

@gemath gemath commented Mar 31, 2019

That's wrong. Almost always whenever somebody brings up the halting problem it's wrong. What generally happens is that the analysis is pessimistic, but safe. For example

var s = "string"
if haltingProblem:
   s = 34

The Nim compiler does not allow s = 34 and it doesn't have to solve the halting problem which is encoded in the condition.

Yes, because of type checking, which can be done at compile time. Ref count checking to catch use-after-free cannot, so this is not an analogue.

As to test coverage for a ref counting debug build: it's good that we don't have to test all the control flow paths which deref the owned ref. But since the abort could be triggered by any invalidation of the memory behind the owned ref, we do have to test all flow paths which do that, is that correct? If it is, these would be cases where the owned ref

  • goes out of scope (this one is probably not a big problem)
  • is assigned a new value (and the old one is not re-used?)
  • is explicitly destroyed (will that even be allowed with destructors?)

Do we have any metrics for the effort this would take? It "feels" easier than covering derefs, though.

@gemath

This comment has been minimized.

Copy link

@gemath gemath commented Mar 31, 2019

... libraries are written without a care in the world that they use a GC, and that will mean my GC-free app that uses owned won't be able to use those libraries. Is my assumption correct?

AFAIU, your owned-ref-aware app code could be compiled in use-GC-mode together with the non-owned-ref-aware lib code. The owned (and maybe dispose) keywords in the app code could just be ignored then.

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Mar 31, 2019

But since the abort could be triggered by any invalidation of the memory behind the owned ref, we do have to test all flow paths which do that, is that correct?

Probably but we have the technology in the compiler to iterate over all control flow paths for a proc body. What would be required is some "abstract RC effect summary" for every proc so that the analysis doesn't have to inline every proc. Solving this for the general case seems intractable indeed but the tool could tell you if the program couldn't be proven and you should keep the runtime checks. It's too early to put too much thought into it.

If you care that much about correctness why do you even use ref to begin with. Ada Spark doesn't support dynamic heap management for good reasons and it works, it produces robust proven software since decades. Once you're into correctness-over-everything you also start to care about out-of-memory situations...

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Mar 31, 2019

So if I understand correctly what you're proposing are optional annotations that allow the GC to be turned off, is that correct?

Correct, but It's too early to say if they stay optional in the long run or not.

What follows is that libraries need to be explicitly written to support these annotations, right? So we will have two different ways to do things in Nim and end up in situations where libraries are written without a care in the world that they use a GC, and that will mean my GC-free app that uses owned won't be able to use those libraries. Is my assumption correct?

Correct and I propose to not support the GC mode forever for this reason to avoid a permament split. But it's much too early for this decision.

@SixteNim

This comment has been minimized.

Copy link

@SixteNim SixteNim commented Apr 3, 2019

We should discuss potential traps and flaws of the Bacon/Dingle model regarding Nim.

The point is that Bacon/Dingle do not model a stack, they model a heap. And it's not split into regions like a generational GC would do it, if you want to compare it to a GC, it's closer to reference counting than anything else.

Your GC is heap-based . The stack is a pointer-pool only , an array of u64 , potential refs to the heap isn't it. The Checkpoints for deallocation are zero-refs on the heap resulting in potentially further deallocation. The GC allows for sharing of refs arbitrarily. If Nim would take the Bacon/Dingle model as published, it would abandon the GC. It's not a "simply better GC".

The point is that Bacon/Dingle do not model a stack, they model a heap. And it's not split into regions like a generational GC would do it, if you want to compare it to a GC, it's closer to reference counting than anything else.

It is basically a malloc/free with unique_ptr. Every object on the heap can be reached by a chain of unique_ptr , Presumed, that the program is correct, nothing else is needed. If an owned gets out of scope, deallocation takes place after checking the ptr for nil. The same happens if a ownedgets nilified deliberately. Nice, but let's find out now where the pitfalls are.

@andreaferretti

This comment has been minimized.

Copy link

@andreaferretti andreaferretti commented Apr 3, 2019

I had promised to avoid more commenting but there is one point I think is important from this comment of @SixteNim

It is self-explanatory if you delete something, you can't use it anymore

This is not self-explanatory at all. I am deleting an item from a list, not wiping it out of existence, at least not intentionally. This is something I can do with a GC

list.delete(node)
# use node for something else, unrelated to its presence inside `list`

Maybe I am just moving it from a container to another

list1.delete(node)
list2.add(node)

The only solution really seems to return an owned reference to the caller, like

let node1 = list1.delete(node)
list2.add(node1)
@SixteNim

This comment has been minimized.

Copy link

@SixteNim SixteNim commented Apr 3, 2019

@andreaferretti

list1.delete(node)
list2.add(node)

The ´´delete´´ is an unlink. It should be: let enode = list1.unlink(node)
let enode being owned Node (inferred)
and then: list2.add(enode)

unlink gets a unowned and returns an owned Node. The unowned should be passed as kill Node. The caller gets the node back however!
list2.add(enode) expects an owned as shown.

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Apr 3, 2019

Nice, but let's find out now where the pitfalls are.

What do you think we have been doing in this thread? ;-)

@disruptek

This comment has been minimized.

Copy link

@disruptek disruptek commented Apr 3, 2019

I may be all wet on this, but shouldn't the goal be to clarify dialog with the user? I agree with @mratsim that we need language constructs to codify our dispose intent, especially since this is a particularly significant notation (and perhaps because dangling = nil is so insignificant).

Explicit language isn't just easier for us to read and reason about; it's easier for the compiler to analyze and optimize, too. The rewards are more accurate static analysis, more precise debugging information, and superior optimization. These aren't Rusty hoops we have to jump through; these are the means by which we may sidestep those hoops, and (not least) they help the compiler better serve our actual intent.

If the specificity with which we can notate semantics improves, then I don't see how it will matter which backend the user selects -- the compiler will be able to do the Right Thing given the circumstances, both with libraries that assume a GC and with a scope-based MM technique and with whatever new-fangled automanual gizmo arrives in 2.0.

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Apr 3, 2019

@disruptek It shall be called disarm.

@Wh1teDuke

This comment has been minimized.

Copy link

@Wh1teDuke Wh1teDuke commented Apr 3, 2019

I chose nim for the reason of being a fast and elegant language that was easier to read and understand than c/c++ (while being almost as fast), but faster and less verbose than c#/java without sacrificing safety.
I'm happy with the ptr/ref dichotomy, and though is not perfect I can work around it, since for the majority of my projects and code ref is enough. It removes the weight off my shoulders.

I'd be happy to know that v1.0 will be released under the initial assumptions on resource management, or else to know that the change will not happen overnight. And, if possible, to prioritize fixing the most important bugs first before any library adaptations.

@runvnc

This comment has been minimized.

Copy link

@runvnc runvnc commented Apr 5, 2019

I'm really happy to hear about this as it seems to be a major improvement to the language. I actually always assumed that Araq would find some nice ergonomic way to add more safety and efficiency.

However, I may need to scroll through again but from the discussion I am not 100% certain exactly where this leaves the 1.0 release and whether it actually is going into 2.0. Can I assume that there will be a 1.0 with libraries set up for GC that is available for use while we learn the new system and it gets refined?

I wonder if there is a way to distinguish between these major runtime discrepancies when it comes to packages and dependency management.

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Apr 5, 2019

The current plan is:

  • Have owned and disarm annotations in Nim v1 but they are ignored unless --newruntime is used which is experimental / vaporware / unusable.
  • Nim v1 will ship with the existing GCs, what else.
  • Libraries can be written to support both Nim v1 and v2 without conditional defines because even v1 recognizes system.owned and system.disarm.
  • Libraries can also be written to only support Nim v1, the annotations can be added later and remain compatible with v1. The important point is that Nim v1 knows about these 2 new builtins (and ignores them).

Worst case: it turns out that everything fails and owned is not worth its costs. Then you're left with pointless annotations about ownership that are neither checked nor enforced until we remove them again.

@cooldome

This comment has been minimized.

Copy link
Member

@cooldome cooldome commented Apr 7, 2019

Just as untested idea: is it possible to use existing system.reset instead of introducing new system.disarm?

@SixteNim

This comment has been minimized.

Copy link

@SixteNim SixteNim commented Apr 7, 2019

Nim v1 will ship with the existing GCs, what else.

Seems reasonable. Is there still some hope for a vtable implementation ? Like Rusts "fat pointer" ?

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Apr 7, 2019

Just as untested idea: is it possible to use existing system.reset instead of introducing new system.disarm?

Seems too risky, firstly it's not clear what reset is for. Secondly, disarm would only exist for unowned refs.

Seams reasonable. Is there still some hope for a vtable implementation ? Like Rusts "fat pointer" ?

There are Nimble packages that provide these things and v1 needs to be about stabilizing what we have.

@danieloff

This comment has been minimized.

Copy link

@danieloff danieloff commented Apr 11, 2019

I'm very interested in trying this feature if/when it is functional enough. There always seem to be some comments/fear about C# and managed languages, not having gc... etc. I'll not speculate here, but I did want to just mention my personal perspective as a potential nim user. I've got 3 years professional c# usage on 3d house design/engineering software. And 7 years as a pro c++ developer for mining optimization software. The only way I'm going to be able to touch these "less popular" languages is in my free time. Or if I can sell it to my boss :), of course. I love learning about them. Read the rust book. Read the nim book. Ported a good portion of the corange engine to rust as a hobby experiment to see what made the language tick. I would like to get into nim more. As far as I'm concerned there is little difference with coding a gc language, or a non gc from my user perspective: if the container object is thin & is on the stack, heap allocations are hidden behind some abstraction and there is some deterministic hands off destruction. All written by whoever is providing the structure. I know there are a lot of details left out there, but for "getting stuff done", it serves me. Pythonic just seems to be the syntax my mind likes best and nim has the macro system going for it, regardless of the semantics of object destruction. And it is compiled. I just wanted to chime in that this particular proposal was something that really struck me as intriguing for how I personally like to code.

@StefanSalewski

This comment has been minimized.

Copy link

@StefanSalewski StefanSalewski commented Apr 22, 2019

The owned refs conceps seems to be similar to Pointer Ownership Model of David Svoboda

https://resources.sei.cmu.edu/asset_files/WhitePaper/2013_019_001_55008.pdf

https://resources.sei.cmu.edu/library/asset-view.cfm?assetid=55000

@jwollen

This comment has been minimized.

Copy link

@jwollen jwollen commented May 15, 2019

@Araq your blog post mentions backing refs with type-specific memory allocators. Right now in --newruntime they still uses alloc0.

Would refs eventually use Allocators, just like seq? If so would that abstraction change? E.g. similar to c++ std::allocator<T> and std::memory_resource?

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented May 15, 2019

There is also -d:useMalloc for --newruntime and then it uses malloc with its ways to "override" it at linking time.

@jwollen

This comment has been minimized.

Copy link

@jwollen jwollen commented May 16, 2019

That's slightly ugly, since both the default allocator and new use malloc, so having malloc call into an allocator isn't ideal. Also I wouldn't want to get rid of the default allocation strategy, but mix it with others.

I would instead suggest for new to use the current local allocator, like seq. refs already behave much like intrusive pointers, so i would go all the way and have them carry around their allocator. Would you be ok with such a PR?

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented May 20, 2019

Bah, it's ok I guess, but we should have allocators that are page-aligned (or more than that) so that we can do bitmasking of pointers to access the underlying allocator, no need to carry the allocator around as a separate internal pointer everywhere.

@johnperry-math

This comment has been minimized.

Copy link

@johnperry-math johnperry-math commented May 31, 2019

Question: Why is it necessary to have a runtime error for dangling unowned refs? Could the runtime not simply set them to nil? This would require the use of unowned refs to be guarded by nil, which I think can be checked statically -- for instance, Kotlin and Eiffel do it, if I understand correctly.

Apologies if this is a dumb question, but it came to mind.

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Jun 1, 2019

Setting weak pointers to nil automatically is much more expensive, you would need to keep a data structure around just to be able to do this. This is particularly problematic for unowned refs on the stack, it would require a register/unregister pair for every stack slot that has an unowned ref.

@johnperry-math

This comment has been minimized.

Copy link

@johnperry-math johnperry-math commented Jun 1, 2019

@Araq Had I but paused a moment to think of that, it would have been obvious. Thank you.

@duneroadrunner

This comment has been minimized.

Copy link

@duneroadrunner duneroadrunner commented Jun 10, 2019

you would need to keep a data structure around just to be able to do this

But not necessarily a separate data structure. This is implemented by, for example, SaferCPlusPlus' "registered pointers" by making each pointer object double as a node in a linked list that tracks all the references currently targeting the given object.

The registering and unregistering does add some expense. SaferCPlusPlus provides both "auto-self-nulling" registered pointers and non-owning alias counting "norad" pointers like the references Nim seems to be adopting, and simple micro-benchmarks for them. The micro-benchmarks indicate that the copy and assignment operations of "auto-self-nulling" pointers are, as expected, more expensive than those of "alias counting" pointers, but not by as much as I might have thought. (Shared-owning (non-atomic) reference counting pointers appear to be in the same performance ballpark as well.) In practice, my experience is that there's rarely a noticeable performance difference in the application overall.

With this proposal, it seems to me that the primary use case for these non-owning references would be dynamic data structures with cyclic references. I suspect that in most of those cases either the differences in overhead of any pointer operations would be small relative to the cost of the accompanying memory allocation operations, or, for cache-coherency reasons, the organizational structure of the nodes (if not the nodes themselves) would be stored in a contiguous vector, in which case indexes could/would take the place of the non-owning pointers. No?

That said, I don't disagree with the choice of using "alias counting" as the safety mechanism. But I don't think it's an either-or situation. There are (maybe rare but) legitimate use cases for weak pointers that can handle the "untimely" destruction of their target. I think that ultimately you're going to want to provide both.

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Jun 10, 2019

Most forms of weak pointers, including "auto niling" pointers solve a different problem, a "modelling" problem. For instance in a game your entities can "die" and then all the subsystems are "notified" about this. I don't think it's a good general purpose model -- when I write a BTree implementation etc I don't want to be notified about my now-dangling pointers, I want to fix my implementation so that it doesn't dangle.

Of course, with Nim's destructors and assignments you can implement all these things, you can also implement traditional reference counting, but the proposal is about what Nim's default, builtin ref should do.

@duneroadrunner

This comment has been minimized.

Copy link

@duneroadrunner duneroadrunner commented Jun 11, 2019

I don't want to be notified about my now-dangling pointers, I want to fix my implementation

Is this part of a general "Don't attempt to recover from program logic errors." principle? Is there an inconsistency with out-of-bounds array index errors throwing an exception rather than terminating the program?
I wouldn't disagree that "bailing immediately" is probably the most appropriate course of action in most cases when encountering a logic error. But I don't know, I could imagine there being situations where attempting to handle it more gracefully would be, while not ideal, still preferable.

with Nim's destructors and assignments you can implement all these things

Yeah, that's a good point. If there is sufficient demand for these alternatives they'll likely end up being implemented anyway. Without adding clutter to the base language.

@Araq

This comment has been minimized.

Copy link
Member Author

@Araq Araq commented Jun 12, 2019

Is this part of a general "Don't attempt to recover from program logic errors." principle?

Yes.

Is there an inconsistency with out-of-bounds array index errors throwing an exception rather than terminating the program?

No, it is not, from https://nim-lang.org/docs/manual.html#definitions

"Whether a checked runtime error results in an exception or in a fatal error is implementation specific. Thus the following program is invalid; even though the code purports to catch the IndexError from an out-of-bounds array access, the compiler may instead choose to allow the program to die with a fatal error."

In fact, we restructured the exception handling to make this more explicit.

@andreaferretti

This comment has been minimized.

Copy link

@andreaferretti andreaferretti commented Jun 12, 2019

Whether a checked runtime error results in an exception or in a fatal error is implementation specific

Wow, that's strong. Is there a performance reason for doing so?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
You can’t perform that action at this time.