In summary, you want to move GC/reference counting to be debug only feature, with compiler putting in the proper disposes based on when owned ref gets out of scope?
I would love to be with the new hotness: prove everything at compile time (debug runtime?) - no GC languages. But it does come at a writing complexity. I want to solve the problem at hand not baby the compiler to put in the proper frees where they supposed to be. I don’t want to solve owned puzzles with cryptic errors. I just want to get stuff done. I like that you can write nim like python without thinking about crap, then come back and make things faster.
If the error messages can guide you to a better faster GC-less language I am all for it. I think the hard part is in the error messages for this feature not the feature itself.
I personally have no major issue with current GC. Having the ability to do most of the stuff on the stack is a huge win over other heap-only languages.
I personally have no major issue with current GC. Having the ability to do most of the stuff on the stack is a huge win over other heap-only languages.
I think the current GC is the reason for why most Nim code runs single threaded. ;-) I don't think "you cannot easily pass Table[string, string] to a different thread and locks won't help you" is good enough for Nim in the long run. It's high time we address this problem.
1. I don't think thread local heaps work well for parallelism,
O.k. Good, this makes things simpler. The distinction between "iso" and "trn" isn't necessary longer. "iso" does the job, and "iso" is shorter to write than "owned" isn't it. Pony strives to transfer references between threads and to maintain write-ability at the same time. It might not be a clever idea - however, Pony integrated "capabilities" in the type system. This allows some inference. Anything that can be inferred takes a burden from the programmer, makes programs shorter and reduces errors.
Usually accessing dangling.data would be a "use after free" bug but since dispose returns the memory to a type-safe memory pool we know that x = Node(data: 4) will allocate memory from the same pool; either by re-using the object that previously had the value 3 (then we know that dangling.data == 4) or by creating a fresh object (then we know dangling.data == 3).
This is exactly the pony-way with their "destructive read".
I've got some questions as I'm trying to grok this. First, to make sure I understand: unowned refs would need to be set to nil so the type based allocater can free them, and owned refs will be automatically freed when they leave the scope. Is that summary correct?
Not entirely, usually unowned refs are also discarded. The setting to nil only applies when the unowned ref outlives the owned ref. Maybe see https://researcher.watson.ibm.com/researcher/files/us-bacon/Dingle07Ownership.pdf for more details.
If I create a owned ref and pass it to a proc that takes an owned ref, does that mean that the context that created the ref no longer owns it?
Yes.
And lastly, how would multi threading code change with this new feature? Would the convention be to create owned refs and pass them from thread to thread.
Yes.
@Sixte
Anything that can be inferred takes a burden from the programmer, makes programs shorter and reduces errors.
IME the complexity quickly comes up, especially for newcomers: the inferred rules show up in error messages and they usually break when you have an indirect function call. The more complexity you can avoid in a type system, the better.
Look, I don't want to add owned to Nim's type system. But I consider it our best option, all things considered, having studied these problems for years.
You don't even have to do anything, you can compile your Nim code like before but the stdlib grew some pointless owned annotations that are ignored when you use the older runtime with its GC.
nil as a possible value for ref stays with us as it is required to unarm dangling pointers.
Can nil be somehow made illegal for owned refs only?
Since immutable would be annotated to the ref type, it seems misplaced and/or like a misnomer to me: We don't want the ref to be immutable but the object it refers to, and the immutability is conditional. How about one of these:
type
Node {.protected.} = ref object # or maybe "restricted"
...
Node = ref protected object # breaks backwards compatibility and needs parser extension
...
@Araq:
As per my consideration in my last posts:
unless every object was owned by default...
Although that could work, it likely isn't a good idea as it would put the overhead of owned/dangling "hooks" on every data type and it's unnecessary.
Rather, it must be used according to the "simple rule" I mentioned: "Every data type that either refers to the heap or contains something referring to the heap must be created within an "owned" wrapper so that it can be either "owned" or cast to the distinct "dangling" wrapper according to the rules of its copy/move semantics.
So the next question is: Given such a simple rule, it seems that the compiler will be able to check whether "owned" needs to be applied or not and can guide the programmer, then could the compiler insert the "owned" wrapper itself when necessary on creation?
If it could, then would the "owned/dangling" keywords not be necessary and "it would just work" including the implicit casting to "dangling" according to the copy/move rules, although when one could see when things have been wrapped by looking at the "repr" of a binding where the "owned/dangling" wrappers would show up? One could still override what the compiler would automatically do by applying the deepCopy/shallowCopy procs, which for these wrappers are complements of each other where deepCopy takes an "owned" or a "dangling" and makes a new independent "owned" and shallowCopy takes a "owned" or a "dangling" and always casts to output a "dangling".
I see that making this automatic avoids some complication the compiler might have in eliding nested "owned" wrappers: Consider a Window that creates an "owned" wrapper that contains not only a Button that is "owned but also many nested items all of which are owned, perhaps to many levels deep; for efficiency it would be good if the compiler elides all those nested "owned" wrappers away except for the outer one.
If the compiler needs to elide away all the declared "owned" wrappers, wouldn't it be better (simple) that the compiler just injects the outer "owned" wrapper by itself as necessary according to the "simple rule"?
Rather, it must be used according to the "simple rule" I mentioned: "Every data type that either refers to the heap or contains something referring to the heap must be created within an "owned" wrapper so that it can be either "owned" or cast to the distinct "dangling" wrapper according to the rules of its copy/move semantics.
This "owned wrapper" becomes a memory region with all its known up- and downsides: Faster, uses more memory, freeing a "subobject" inside the region is either impossible or really problematic for memory safety.
So the next question is: Given such a simple rule, it seems that the compiler will be able to check whether "owned" needs to be applied or not and can guide the programmer, then could the compiler insert the "owned" wrapper itself when necessary on creation?
Owned vs non-owned looked intractable to compute to me. Sure, you can "infer" it in lots of places but then the restrictions remain and error messages referring to concepts that are invisible/inferred in/from the source code are usually a bad user experience. I'd rather put more effort into detecting dangling refs at compile-time. :-)
I don't think that is a good argument, (regarding tuples work in C++)
I meant that I don't care what works or partly works in C++; I care about what is easy to remember how to use in Nim: In Nim, to the casual programmer, tuples are just like objects but with a short cut declaration, construction, and dereferencing. In considering them this way, it might seem strange that one can't apply custom "hooks" to them although there are ways around that using what does work or will work when you fix the bug. "I'm just sayin'..." ;-)
This "owned wrapper" becomes a memory region with all its known up- and downsides...
I may be too simple to understand how a "owned" wrapper turns into a memory region; perhaps the following example will help and you can tell me its problems or give me a reference so I can learn; a proposed impementation of a Owned/Dangling wrapper pair as follows:
const hasThreadSupport = compileOption("threads") and defined(threadsafe)
# can only create Owned; can not create Dangling...
# defined in this order because we can't {.borrow `.`.} generic types yet...
type
Dangling[T] = object
cntnts: T
refcnt: int
Owned[T] = distinct Dangling[T]
proc `=destroy`[T](x: var Owned[T]) {.inline.} =
if x != nil:
let cst = cast[Dangling[T]](x) # so we can access non Dangling fields
assert cst.refcnt == 0, "destroying owned type with dangling references!"
cast[ptr T](cst.cntnts.unsafeAddr)[].deepDestroy; x.reset
proc `=`[T](dst: var Owned[T]; src: Owned[T]) {.error: "owned types can only be moved".}
proc `=sink`[T](dst: var Owned[T]; src: Owned[T]) {.inline.} =
let cstdst = cast[Dangling[T]](dst); let cstsrc = cast[Dangling[T]](src)
if cstdst.cntnts != cstsrc.cntnts:
dst.`=destroy`; cast[ptr T](cstdst.cntnts.unsafeAddr)[] = cstsrc.cntnts
# when `=move` is used instead of `=sink`
proc `=move`[T](dst, src: var OwnedRefRC[T]) {.inline.} =
let cstdst = cast[Dangling[T]](dst); let cstsrc = cast[Dangling[T]](src)
if cstdst.cntnts != cstsrc.cntnts:
dst.`=destroy`; cast[ptr T](cstdst.cntnts.unsafeAddr)[] = cstsrc.cntnts; src.reset
proc `$`[T](x: Owned[T]): string =
result = "owned: "; result &= $cast[Dangling[T]](x).cntnts
proc `=destroy`[T](x: var Dangling[T]) {.inline.} =
when hasThreadSupport: x.refcnt.atomicDec else: x.refcnt.dec
proc `=`[T](dst: var Dangling[T]; src: Dangiing[T]) {.inline.} =
when hasThreadSupport: dst.refcnt.atomicInc else: dst.refcnt.inc
when hasThreadSupport: src.refcnt.atomicInc else: src.refcnt.inc
copyMem(dst.unsafeAddr, src.unsafeAddr, src.sizeof) # just copy the pointer is a byte copy
proc `=sink`[T](dst: var Dangling[T]; src: Dangling[T]) {.inline.} =
# moves are the same as assignments
`=`(dst, src)
proc `=move`[T](dst, src: var Dangling[T]) {.inline.} =
# moves are the same as assignments
`=`(dst, src)
proc `$`[T](x: RefRC[T]): string =
result = "unowned: "; result &= $x.cntnts
Owned vs non-owned looked intractable to compute to me...
You're "the man" regarding what you think can be done with the compiler ;-) I'm just envisioning a simple syntax where one doesn't have to go back and change every declaration of a data type that is a heap reference or contains a heap reference to add the "owned" designation. There is also the question of handling nested "owned"'s but perhaps there is no need if my understanding of "owned" just being a wrapper is incorrect.
The only complication on automatic application of the "simple rule" is what to do with the raw pointers pointer and ptr T which might reference the heap but can reference any memory location anywhere including the code as for literals or the stack as for local bindings...
I've done more thinking about this, and I think the right answer is to deallocate these raw pointers just as we do ref's at the end of the scope of their "owned". There is no overhead complications necessary, or shouldn't be if there currently are, as when the Allocator is asked to deallocate a pointer to some memory address, it will try to look up that memory address in some way to find the memory control block, which it won't find for literals or for stack bindings as they were never allocated. In that case, it should just no-op and make no changes if that isn't what it does now.
By deallocating all forms of pointer when they are inside an "owned", we can have no forms of memory leak when the memory pointers are inside a "owned" data type structure. The only way to get memory leaks is to allocate manually and not manually deallocate for a pointer that is not part of a data structure and thus not automatically "deepDestroy"'ed, and even that would not be possible if we also made normally allocated pointers "owned".
Then the final consideration is what to do with pointers that come about as a result of addr and unsafeAddr: we need these in order to bypass copy/move semantics so these need to remain as truly "raw", but as the documentation says, these are "unsafe" and "really really unsafe", so only to be used internally and by people who know what they are doing for reasons of performance.
In what sense is owned "a wrapper"? And why does that cause problems with "nesting"?
You are now in crazy-talk-land... "deepDestroy"? destroying 'ptr' automatically? What's wrong with B/D anyway? Please read their paper again, their design does not mention any of this crazy stuff. They wrote a full compiler with their design without much trouble. Now compare that to using RC for a compiler: Once you're done, the compiler will be slow and it will be hard to maintain the "no cycles allowed" invariant manually.
In what sense is owned "a wrapper"?
I think of "owned" as a "wrapper" because it contains a "T" type and adds some behavior to it, namely the B/D "hooks" along with the other "dangling" behavior for its alternate distinct type.
And why does that cause problems with "nesting"?
I may be wrong in my reasoning, but I am envisioning a complex "owned" structure that contains nested objects with (owned or dangling) heap reference pointers, some of which nested structures (including possibly both tuples and objects) may in turn be "owned" because they in turn contain heap reference pointers and so on. I am asking the question of what happens when it comes time to destroy from the outside in as when the outer "owned" goes out of scope. My concern is due to that only objects can have "hooks" yet some of the nested items will be objects (or tuples) and others may be pointers of any of the three kinds (pointer/ptr T/ref T). Objects (and eventually tuples when the bug is fixed) will be automatically destroyed when they go out of scope because the outer "container" goes out of scope, but pointers and AFAIK ref's don't currently have "hooks". When the "owned" was applied only to ref, that wasn't a problem because the "owned" applied the hooks directly to the ref and caused destruction of what it referenced but now? This is why I envisioned a "deepDestroy" which would take care of all of that as it's the only way I could think of to make it work while still under the current version; but...
Perhaps you have now modified the compiler so it applies B/D destroy/copy/move semantics to ref's directly as well? This would then automatically "drill down" through a nested structure.
destroying 'ptr' automatically...
Once we have the B/D "hooks" applied to what ref's point to either by "deepDestroy" or by some other method such as making "hooks" apply directly to "owned" ref's, my idea was that since B/D works so well, it could take care of the problem of such a nested structure also containing pointer's or 'ptr T's and apply B/D hooks to them as well, thus having complete protection from memory leaks for anything inside an "owned".
An example of something that might need this would be closures where the second pointer in the tuple is untyped and the type is known only to the compiler and the first pointer which is a nimcall proc that uses it as a hidden parameter. There needs to be some custom hooks to cause that pointer to be deallocated.
Now compare that to using RC for a compiler...
I've backed entirely off of using RC except as a check as per spec 2 and as I understand B/D (optionally) uses it;
You are now in crazy-talk-land... "deepDestroy"?
I'll re-read B/D as per your suggestion to see what I'm missing. I understood that your implementation is "beyond B/D" in overcoming some of it's limitations, so am trying to think "outside the box" to discover if there are limitations.
Part of the reason I was thinking about "deepDestroy" is to try to make most of the work be done by default versions of the B/D hooks so that the programmer wouldn't have to write so many custom hooks. Thus, deepDestroy isn't something the compiler generates but rather part of the runtime that the B/D default "hooks" can call as an easy means to destroy as deep as necessary according to the B/D rules.
Yes, B/D wrote a complete compiler design adequate to prove the points they were making, but AFAIK it was never used for a production application and may have limitations beyond what was tested.
Another limitation I can think of that I'll re-read to see how it would be overcome is the case where one needs to "deepCopy" (because B/D assignments are essentially shallow by definition) such as a case where one might need to pass the same data to multiple threads that would own it and either pass it back to an owned or pass it on, etc.; Although pure B/D does work with cyclic data, and can destroy cyclic data if the defaults take some care (resetting pointers to nil before destroying from a temporary copy), "deepCopy" is harder because it has to follow the links and some multiple number of them may be recursive. Again, it can be overcome, but it would be better to be a proc in the runtime and not something the compiler has to generate itself.
All of this is motivated by the desire to have the system as safe as possible while a performant as possible, yet have most of that safety come about by default without the programmer having to write much custom boilerplate code and preferably need to make only minimal changes if any to existing libraries.
You are now in crazy-talk-land... "deepDestroy"?
I'll re-read B/D as per your suggestion to see what I'm missing. I understood that your implementation is "beyond B/D" in overcoming some of it's limitations...
I have re-read B/D thoroughly and see we are well beyond their original concept although true to the basic concepts. I think what we are developing is even better. They had the same problems with destroying potentially cyclic data and their proposed extended solution was as follows:
To overcome these limitations, we propose adding destructors
to Gel, and propose a multi-phase object destruction mechanism.
Gel could destroy an object graph rooted at a pointer P in the
following phases.
1. Recursively descend all objects in the ownership tree
below P, running each object's destructor.
2. Recursively descend again; for each non-owning pointer
in every object, decrement the reference count of the
object pointed to.
3. Recursively descend again; for each object, check that
its reference count is zero and free the object.
My "deepDestroy" implements this as they suggest but adapted to the outer controling "owned" being an object rather than a pointer. They seem to have missed the precaution of setting the pointers (all of owned, dangling, and primitive) to nil before we destroy what they reference from a temporary copy so if they are attempted to be destroyed recursively by a path that leads back to the root owned object itself, we don't enter a data race as the recursive path will be nil. When applied to any dangling pointers, they will only be decremented once even if reference count checking is on, but we do need to do a scan "destroying" (possibly decrementing reference counts) for dangling pointers first as proposed in case any of these pointers are the same as some of the owned pointers. That means that every pointer must be "wrapped" in a owned/dangling object so we know which are which, and that means that these interior owned/dangling "wrappers" can't be elided.
So the concept of "deepDestroy" isn't so crazy and is in line with what B/D proposed.
With ownership becoming part of the type system we can easily envision a rule like "only the owner should be allowed to mutate the object"....
Now this won't work generally as explored further in that blog post as there are many cases where the "dangling" reference must be able to mutate the object. However, there could be controlled mutability as in languages like Rust and Pony, etc. which allow reference mutation when there is only one mutator reference, with the following changes:
I may have missed some rules or simplification of rules, but I'm sure they can be filled in, as this is basically the scheme used by Rust/Pony/languages that control mutation type safety.
If this were done, I believe we would have the type safety regarding mutability of Rust or Pony but perhaps without the complications and covering the cases as mentioned in the blog where a particular wrapper cannot be owned but needs mutation. The above rules would seem to be reasonably easy to be enforced by the compiler as the compiler already seems to have accommodated verifying lifetimes are long enough as for lent and var return values . As before, the ref counts can be "virtual" ref counts where they don't even exist if ref count checking is turned off and therefor of zero execution and memory cost for the "release" or "danger" cases.
It is well beyond B/D (but then we are moving that way anyway) but the increased type safety might be worth it?