ch29.md 22 KB
Chapter 29. Lifetime-tracking hooks
The memory management for Nim’s standard string and seq types as well as other standard collections is performed via so-called "Lifetime-tracking hooks", which are particular type bound operators. There are different hooks for each (generic or concrete) object type T (T can also be a distinct type) that are called implicitly, in strategic places.
The word “hook” here does not imply any kind of dynamic
binding or runtime indirections, the implicit calls are statically
bound and potentially inlined.
29.1. =destroy hook
A =destroy hook frees the object’s associated memory and releases other
associated resources. Variables are destroyed via this hook when they go out
of scope or when the routine they were declared in is about to return.
The prototype of this hook for a type T needs to be:
proc =destroy(x: T)
The general pattern in =destroy looks like:
proc =destroy(x: T) =
# first check if 'x' was moved to somewhere else:
if x.field != nil:
freeResource(x.field)
199
29.2. =wasMoved hook
A =wasMoved hook sets the object to a state that signifies to the destructor
there is nothing to destroy.
The prototype of this hook for a type T needs to be:
proc =wasMoved(x: var T)
Usually some pointer field inside the object is set to nil:
proc =wasMoved(x: var T) =
x.field = nil
29.3. =sink hook
A =sink hook moves an object around, the resources are stolen from the
source and passed to the destination. It is ensured that the source’s
destructor does not free the resources afterward by setting the object to its
“was moved” value via the =wasMoved hook.
When not provided a combination of =destroy and copyMem is used instead.
This is efficient hence users rarely need to implement their own =sink
operator, it is enough to provide =destroy and =copy, the compiler takes care
of the rest.
The prototype of this hook for a type T needs to be:
proc =sink(dest: var T; source: T)
The general pattern in =sink looks like:
proc =sink(dest: var T; source: T) =
`=destroy`(dest)
`=wasMoved`(dest)
dest.field = source.field
=sink does not need to check for self-assignments. How self-
assignments are handled is explained later.
200
29.4. =copy hook
The ordinary assignment in Nim conceptually copies the values. The =copy
hook is called for assignments that couldn’t be transformed into =sink
operations.
The prototype of this hook for a type T needs to be:
proc =copy(dest: var T; source: T)
The general pattern in =copy looks like:
proc =copy(dest: var T; source: T) =
# protect against self-assignments:
if dest.field != source.field:
`=destroy`(dest)
`=wasMoved`(dest)
dest.field = duplicateResource(source.field)
The =copy proc can be marked with the {.error.} pragma. Then any
assignment that otherwise would lead to a copy is prevented at compile-time.
This looks like:
proc =copy(dest: var T; source: T) {.error.}
Notice that there is no = before the {.error.} pragma.
29.5. =dup hook
A =dup hook duplicates an object. =dup(x) can be regarded as an optimization
replacing a wasMoved(dest); =copy(dest, x) operation.
The prototype of this hook for a type T needs to be:
proc =dup(x: T): T
The general pattern in implementing =dup looks like:
201
type
Ref[T] = object
data: ptr T
rc: ptr int
proc =dupT: Ref[T] =
result = x
if x.rc != nil:
inc x.rc[]
29.6. =trace hook
A custom container type can support Nim’s cycle collector --mm:orc via the
=trace hook. If the container does not implement =trace, cyclic data
structures which are constructed with the help of the container might leak
memory or resources, but memory safety is not compromised.
The prototype of this hook for a type T needs to be:
proc =trace(dest: var T; env: pointer)
env is used by ORC to keep track of its internal state, it should be passed
around to calls of the built-in =trace operation.
The general pattern in using =destroy with =trace looks like:
type Test[T] = object
size: Natural
arr: ptr UncheckedArray[T] # raw pointer field
proc makeTestT: Test[T] =
Test[T](size: size,
arr: cast[ptr UncheckedArray[T]](alloc0(sizeof(T) * size)))
proc =destroyT =
if dest.arr != nil:
for i in 0 ..< dest.size: dest.arr[i].`=destroy`
dest.arr.dealloc
proc =traceT =
if dest.arr != nil: # trace the ``T``'s which may be cyclic
for i in 0 ..< dest.size: dest.arr[i].`=trace` env
# following may be other custom "hooks" as required...
202
The =trace hooks (which are only used by --mm:orc) are
currently more experimental and less refined than the other
hooks.
29.7. Move semantics A “move” can be regarded as an optimized copy operation. If the source of the copy operation is not used afterward, the copy can be replaced by a move. The notation lastReadOf(x) is used to describe that x is not used afterward. This property is computed by a static control flow analysis but can also be enforced by using system.move explicitly. One can query if the analysis is able to perform a move with system.ensureMove. move enforces a move operation and calls =wasMoved whereas ensureMove is an annotation that implies no runtime operation. An ensureMove annotation leads to a static error if the compiler cannot prove that a move would be safe. For example: proc main(normalParam: string; sinkParam: sink string) =
var x = "abc"
# valid:
let valid = ensureMove x
# invalid:
let invalid = ensureMove normalParam
# valid:
let alsoValid = ensureMove sinkParam
29.8. Swap The need to check for self-assignments and also the need to destroy previous objects inside =copy and =sink is a strong indicator to treat system.swap as a builtin primitive of its own that simply swaps every field in the involved objects via copyMem or a comparable mechanism. In other words, swap(a, b) is not implemented as let tmp = move(b); b = move(a); a = move(tmp). This has further consequences: • Objects that contain pointers that point to the same object are not
supported by Nim’s model. Otherwise swapped objects would end up in
203
an inconsistent state.
• Sequences can use realloc in the implementation. 29.9. Sink parameters To move a variable into a collection usually sink parameters are involved. A location that is passed to a sink parameter should not be used afterward. This is ensured by a static analysis over a control flow graph. If it cannot be proven to be the last usage of the location, a copy is done instead and this copy is then passed to the sink parameter. A sink parameter may be consumed once in the proc’s body but doesn’t have to be consumed at all. The reason for this is that signatures like proc put(t: var Table; k: sink Key, v: sink Value) should be possible without any further overloads and put might not take ownership of k if k already exists in the table. Sink parameters enable an affine type system, not a linear type system. The employed static analysis is limited and only concerned with local variables; however, object and tuple fields are treated as separate entities: proc consume(x: sink Obj) = discard "no implementation" proc main =
let tup = (Obj(), Obj())
consume tup[0]
# ok, only tup[0] was consumed, tup[1] is still alive:
echo tup[1]
Sometimes it is required to explicitly move a value into its final position: proc main =
var dest, src: array[10, string]
# ...
for i in 0..high(dest): dest[i] = move(src[i])
An implementation is allowed, but not required to implement even more move optimizations (and the current implementation does not). 204 29.10. Rewrite rules There are two different allowed implementation strategies:
- The produced finally section can be a single section that is wrapped around the complete routine body.
The produced finally section is wrapped around the enclosing scope. The current implementation follows strategy (2). This means that resources are destroyed at the scope exit. Table 10. Rewrite rules Pattern Rewritten as Rule name var x: T; stmts var x: T; try stmts
destroy-var finally: `=destroy`(x)g(f(...)) g(let tmp;
nested-function-call bitwiseCopy tmp, f(...); tmp) finally: `=destroy`(tmp)x = f(...)
=sink(x, f(...))function-sinkx = lastReadOf z
=sink(x, z)move-optimization `=wasMoved`(z)v = v discard "nop"
self-assignment-removalx = y
=copy(x, y)copyf_sink(g()) f_sink(g())
call-to-sinkf_sink(notLastReadOf (let tmp;
=dup(y);copy-to-sinky) f_sink(tmp)) f_sink(lastReadOf y) f_sink(y)
move-to-sink `=wasMoved`(y) 20529.11. Object and array construction Object and array construction is treated as a function call where the function has sink parameters. 29.12. Destructor removal =wasMoved(x) followed by a =destroy(x) operation cancel each other out. An implementation is encouraged to exploit this in order to improve efficiency and code sizes. The current implementation does perform this optimization. 29.13. Self assignments =sink in combination with =wasMoved can handle self-assignments but it’s subtle. The simple case of x = x cannot be turned into =sink(x, x); =wasMoved(x) because that would lose x's value. The solution is that simple self-assignments that consist of • Symbols: x = x • Field access: x.f = x.f • Array, sequence or string access with indices known at compile-time: x[0] = x[0] are transformed into an empty statement that does nothing. The compiler is free to optimize further cases. The complex case looks like a variant of x = f(x), we consider x = select(rand() < 0.5, x, y) here: 206 proc select(cond: bool; a, b: sink string): string = if cond: result = a # moves a into result else: result = b # moves b into result proc main = var x = "abc" var y = "xyz"
possible self-assignment:
x = select(true, x, y) Is transformed into: proc select(cond: bool; a, b: sink string): string = try: if cond:
`=sink`(result, a) `=wasMoved`(a)else:
`=sink`(result, b) `=wasMoved`(b)finally:
=destroy(b)=destroy(a) proc main = var x: string y: string try:=sink(x, "abc")=sink(y, "xyz")=sink(x, select(true,let blitTmp = x `=wasMoved`(x) blitTmp, let blitTmp = y `=wasMoved`(y) blitTmp))echo [x] finally:
=destroy(y)=destroy(x) As can be manually verified, this transformation is correct for self- assignments.20729.14. Lent type proc p(x: sink T) means that the proc p takes ownership of x. To eliminate even more creation/copy ←→ destruction pairs, a proc’s return type can be annotated as lent T. This is useful for “getter” accessors that seek to allow an immutable view into a container. The sink and lent annotations allow us to remove most (if not all) superfluous copies and destructions. lent T is like var T a hidden pointer. It is proven by the compiler that the pointer does not outlive its origin. No destructor call is injected for expressions of type lent T or of type var T. type Tree = object kids: seq[Tree] proc construct(kids: sink seq[Tree]): Tree = result = Tree(kids: kids)
converted into:
=sink(result.kids, kids);=wasMoved(kids)=destroy(kids) proc[]*(x: Tree; i: int): lent Tree = result = x.kids[i]borrows from 'x', this is transformed into:
result = addr x.kids[i]
This means 'lent' is like 'var T' a hidden pointer.
Unlike 'var' this hidden pointer cannot be used to mutate the object.
iterator children*(t: Tree): lent Tree = for x in t.kids: yield x proc main =
everything turned into moves:
let t = construct(@[construct(@[]), construct(@[])]) echo t[0] # accessor does not copy the element! 29.15. The .cursor annotation Nim’s ref type is implemented via the same runtime “hooks” and thus via reference counting. This means that cyclic structures cannot be freed immediately (but eventually they are freed as a cycle collector also exists). 208 With the .cursor annotation one can 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. Automatic reference counting also has the disadvantage that it introduces overhead when iterating over linked structures. The .cursor annotation can also be used to avoid this overhead: var it {.cursor.} = listRoot while it != nil: use(it) it = it.next 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, a compiler can try to prove .cursor annotations to be safe, but for ptr a compiler cannot report possible problems. 29.16. Cursor inference / copy elision The current implementation also performs .cursor inference. Cursor inference is a form of copy elision. To see how and when we can do that, think about this question: In dest = src when do we really have to materialize the full copy? - Only if dest or src are mutated afterward. If dest is a local variable that is simple to analyze. And if src is a location derived from a formal parameter, we also know it is not mutated! In other words, we do a compile-time copy-on-write analysis. This means that “borrowed” views can be written naturally and without explicit pointer indirections:
209proc main(tab: Table[string, string]) = let v = tab["key"] # inferred as .cursor because 'tab' is not mutated.
no copy into 'v', no destruction of 'v'.
use(v) useItAgain(v) 29.17. Hook lifting The hooks of a tuple type (A, B, ...) are generated by lifting the hooks of the involved types A, B, ... to the tuple type. In other words, a copy x = y is implemented as x[0] = y[0]; x[1] = y[1]; ..., likewise for =sink and =destroy. Other value-based compound types like object and array are handled correspondingly. For object however, the generated hooks can be overridden. This can also be important to use an alternative traversal of the involved data structure that is more efficient or in order to avoid deep recursions. 29.18. Hook generation The ability to override a hook leads to a phase ordering problem: type Foo[T] = object proc main = var f: Foo[int]
error: destructor for 'f' called here before
it was seen in this module.
proc
=destroyT = discard The solution is to define proc=destroy[T](f: var Foo[T])before it is used. The compiler generates implicit hooks for all types in strategic places so that an explicitly provided hook that comes too “late” can be detected reliably. These strategic places are derived from the following rewrite rules: • In the construct let/var x = ... (var/let binding) hooks are generated for typeof(x). 210 • In x = ... (assignment) hooks are generated for typeof(x). • In f(...) (function call) hooks are generated for typeof(f(...)). • For every sink parameter x: sink T the hooks are generated for typeof(x). 29.19. nodestroy pragma The experimental nodestroy pragma inhibits hook injections. This can be used to specialize the object traversal in order to avoid deep recursions: type Node = ref object x, y: int32 left, right: Node type Tree = object root: Node proc=destroy(t: var Tree) {.nodestroy.} =use an explicit stack so that we do not get stack overflows:
var s: seq[Node] = @[t.root] while s.len > 0: let x = s.pop if x.left != nil: s.add(x.left) if x.right != nil: s.add(x.right) # free the memory explicitly: dispose(x)
notice how even the destructor for 's' is not called implicitly
anymore thanks to .nodestroy, so we have to call it on our own:
=destroy(s) As can be seen from the example, this solution is hardly sufficient and should eventually be replaced by a better solution. 29.20. Copy on write String literals are implemented as "copy on write". When assigning a string literal to a variable, a copy of the literal won’t be created. Instead the variable simply points to the literal. The literal is shared between different variables which are pointing to it. The copy operation is deferred until the first write. The abstraction fails for addr x because whether the address is211 going to be used for mutations is unknown.prepareMutation should be called before the address operation: var x = "abc" var y = x prepareMutation(y) moveMem(addr y[0], addr x[0], 3) assert y == "abc" 29.21. Practice In practice the hooks for memory and resource management should be used rarely; Nim usually does the right thing and overriding the default behavior can be both error-prone and result in non-intuitive behavior. However, the hooks are very useful for interoperability with C and C++. Here is a prototypical example of a C library that we want to wrap: #include typedef struct { double x; char* s; } Obj; Obj* createObj(const char* s) { Obj* result = (Obj) malloc(sizeof(Obj)); result->x = 40.0; result->s = malloc(100); strcpy(result->s, s); return result; } void destroyObj(Obj obj) { free(obj->s); free(obj); } void useObj(Obj* obj) {} double getX(Obj* obj) { return obj->x; } The wrapper should automate the memory management so that destroyObj does not have to be called explicitly: 212 type Obj = object 1 proc createObj(s: cstring): ptr Obj {.importc.} 2 proc destroyObj(obj: ptr Obj) {.importc.} proc useObj(obj: ptr Obj) {.importc.} proc getX(obj: ptr Obj): float {.importc.} type Wrapper = object 3 obj: ptr Obj proc
=destroy(dest: var Wrapper) = if dest.obj != nil: destroyObj(dest.obj) 4 proc=copy(dest: var Wrapper; source: Wrapper) {.error.} 5 proc create(s: string): Wrapper = Wrapper(obj: createObj(cstring(s))) 6 proc use(w: Wrapper) = useObj(w.obj) proc getX(w: Wrapper): float = getX(w.obj) 7 proc useWrapper = 8 let w = @[create("abc"), create("def")] 9 use w[0] echo w[1].getX 10 useWrapper() 1 The C struct is mapped directly to a Nim object. 2 The procs createObj, destroyObj, useObj, and getX are imported from C. 3 The Wrapper object encapsulates a C ptr Obj. 4 The wrapper has a custom destructor that calls destroyObj. The destructor is called automatically if the lifetime of an object of type Wrapper ends. 5 Because the C library offers no way to copy an Obj the wrapper does not offer it either. Any attempt to copy a wrapper will be rejected by the compiler. 6 create is used to wrap createObj. Its input parameter was changed from cstring to string in order to improve memory safety. 7 Obj also offers useObj and getX operations. These are wrapped in order to work on Wrapper. Alternatively a converter from Wrapper to ptr Obj could be provided.2138 useWrapper shows how the wrapper can be used. 9 Sequences of Wrapper can be created easily and the memory management is automatic. 10 When useWrapper returns w's destructor is called which calls the destructor of Wrapper. The destructor of Wrapper then calls destroyObj ensuring that there are no memory leaks.
At the time of this writing, the example needs to use the --mm:orc or --mm:arc compiler switches. Otherwise the destruction of the sequence of Wrapper does not call Wrappers
destructor. Later versions of the compiler will make --mm:orc the default.Instead of prohibiting the =copy operation via {.error.} the wrapper could also offer reference counting: type Wrapper = object obj: ptr Obj rc: ptr int 1 proc
=destroy(dest: var Wrapper) = if dest.obj != nil: if dest.rc[] == 0: 2dealloc(dest.rc) 3 destroyObj(dest.obj)else:
dec dest.rc[]proc
=copy(dest: var Wrapper; source: Wrapper) = 4 inc source.rc[] 5=destroy(dest) 6 dest.obj = source.obj 7 dest.rc = source.rc proc create(s: string): Wrapper = Wrapper(obj: createObj(cstring(s)),rc: cast[ptr int](alloc0(sizeof(int)))) 81 Wrapper now has a reference count (rc). This must be a ptr or a ref and allocated on the heap so that its value is shared between different instances. 2 Use the reference count to see if destroyObj needs to be called. 214 3 The reference count itself also needs to be deallocated because it is stored on the heap. 4 The copy operation. 5 Increment the source's reference count first in order to protect against self assignments. 6 Destroy what was in dest as we are about to overwrite its contents. 7 Copy the data over. 8 alloc0 allocates memory of a given size and sets the memory cells to zero. It is used here to initialize the reference count.