Garbage collection

[LiarPrincess]

CPython

In CPython they use manual reference counting:

• each object has a reference count and an address of the previous and the next allocated object (doubly linked list)
• Py_INCREF is used to retain (reference count += 1)
• Py_DECREF to release (reference count -= 1) an object

If the reference count reaches 0 then it is deallocated and the linked list entries are updated (having a reference to both previous and next object makes this trivial). Linked list itself is used by garbage collection algorithm to break cycles (at some point they need to iterate over all of the currently alive objects).

This is how the object header looks like:

#define _PyObject_HEAD_EXTRA            \
    struct _object *_ob_next;           \
    struct _object *_ob_prev;

typedef struct _object {
    _PyObject_HEAD_EXTRA
    Py_ssize_t ob_refcnt;
    struct _typeobject *ob_type;
} PyObject;

Violet

In Swift we have automatic reference counting for class instances (and a few others). The big catch here is that the user (programmer) is expected to take care of the strong reference cycles (to simplify things a bit: imagine 2 objects that hold a reference to each other, both have reference count 1, so neither of them will be deallocated).

Our options are:

• manual retain/release - in this approach the programmer is responsible for inserting the retain/release calls. For example: when adding an object to a list we retain it, when removing it (or deleting the whole list) we release it.

  The main drawback is of course the manual labor of adding the retain/release calls. It is also extremely difficult to get right and even a single mistake may have consequences:

  • unbalanced retain - object lives forever (along with all of the objects it references)
  • unbalanced release - “use after free” error -> crash

  This approach is really good if you can make it right. CPython uses it, because they can afford it: they have the time and manpower to find and fix any possible errors. I don't think we could do the same.

• manually implemented smart pointer - I don't think it is possible in Swift to write our own version of smart pointer. Even in languages which give you more control (like C++) it is an extremely hard thing to do.

• full garbage collection without ARC - there are tons of materials about this on the internet.

• (THIS ONE IS NOT POSSIBLE ACCORDING TO NEW OBJECT MODEL) using Swift native ARC - I'm not really sure if you can just allocate a bunch of memory with native Swift ARC, but as a last resort we can use ManagedBufferPointer without elements.

  This is nice because (in theory) Swift takes case of everything. In practice however… there are some problems. First of all, you still need a some form of garbage collection to break the cycles. This will be simpler than full-on garbage collection and the requirements will be not as demanding since it will run less often, but still, it is something to keep in mind.

  The other things is that most of the garbage collection algoritms work by somehow marking all of the reachable objects and then in a 2nd phase removing all of the not-marked ones. Unfortunately to do this you need a reference to all of the reachable objects (most commonly by some sort of a linked list). The question is: what kind of reference would it be?

  • strong - always present +1 reference count, which invalidates the whole point of reference counting
  • unowned - this will allow objects to be deallocated, but we would somehow need to know which references are alive and which not
  • weak - this is an obvious choice

  Unfortunately there is a possible performance problem since having just a single the weak reference in Swift, moves the whole reference count to side-table. Unfortunately this side-table is off-line (it is an separate allocation outside of the object). This is a potential memory/cache waste, not to mention that the retain now has to fetch the object and then fetch the side-table (it is called slowRC for a reason).

  Code to test the presence of the side table

    import Foundation
  
    // Sources:
    // SWIFT_REPO/stdlib/public/SwiftShims/RefCount.h
    // SWIFT_REPO/stdlib/public/SwiftShims/HeapObject.h
  
    let strongExtraRefCountShift: UInt64 = 33
    let strongExtraRefCountBitCount: UInt64 = 30
    let strongExtraRefCountMask: UInt64 = ((1 << strongExtraRefCountBitCount) - 1) << strongExtraRefCountShift
  
    let useSlowRCShift: UInt64 = 63
    let useSlowRCBitCount: UInt64 = 1
    let useSlowRCMask: UInt64 = ((1 << useSlowRCBitCount) - 1) << useSlowRCShift
  
    func printARC(name: String, ptr: UnsafeMutableRawPointer) {
      let namePad = name.padding(toLength: 18, withPad: " ", startingAt: 0)
      // let typePtr = ptr.load(as: UInt64.self)
      let refCountBits = ptr.load(fromByteOffset: 8, as: UInt64.self)
  
      let hasSideTable = (refCountBits & useSlowRCMask) >> useSlowRCShift
      if hasSideTable == 1 {
        print("\(namePad)| sideTable")
      } else {
        let strongExtraRefCount = (refCountBits & strongExtraRefCountMask) >> strongExtraRefCountShift
        print("\(namePad)| strongExtraRefCount: \(strongExtraRefCount)")
      }
    }
  
    class Alice {
      var ptr: UnsafeMutableRawPointer {
        return Unmanaged.passUnretained(self).toOpaque()
      }
    }
  
    let alice = Alice()
    printARC(name: "1 strong", ptr: alice.ptr) // strongExtraRefCount: 0
  
    let aliceInWonderland = alice
    printARC(name: "2 strong", ptr: alice.ptr) // strongExtraRefCount: 1
  
    weak var aliceBackInLondon = alice
    printARC(name: "2 strong + 1 weak", ptr: alice.ptr) // sideTable

Btw. we had a similar problem when writing our implementation of BigInt: after the heap-allocated storage is not needed -> how do we release it? And how do we even know that it is no longer needed? We went with ManagedBufferPointer to get Swift ARC, but technically you can implement an BigInt with a garbage collector (although I am not sure that this would be a good idea).

I think that the main difference between the BigInt and the Python object representation is that the Python objects can contain references to other objects, possibly creating a cycle. Anyway, under the hood we were dealing with an unowned pointers, so we can either find the owners (this would be on case-by-case basis, so a lot of room for mistakes) or automate things (either via ARC or garbage collector).

[LiarPrincess]

Anyway, we will probably end up with garbage collector without any of the retain/release/ref count.

As for the exact choices:

• serial vs parallel - in serial collection, only one thing happens at a time. When parallel collection is used the garbage collection is split into parts executed simultaneously, on different CPUs.
• stop-the-world vs concurrent - stop-the-world garbage collection suspends the execution of the application, so that no new allocations can occur. Alternatively, one or more garbage collection tasks can be executed concurrently, that is, simultaneously, with the application.
• generational vs non-generational - when generational collection is used, the memory is divided into generations: separate pools holding objects of different ages. This is based on following assumptions:
  • most allocated objects die young
  • there are few references from older to younger objects
• non-compacting vs compacting vs copying - after the compacting collector has determined which objects in memory are live and which are garbage, it moves all of the alive objects together reclaiming the remaining memory. This enables the bump-the-pointer allocator for new object in the reclaimed space. Copying collector copies (or evacuates) live objects to a different memory area.

I think that the simplest choice is a serial, stop-the-word, non-compacting and generational garbage collector.

As for the generations:

• immortal immutable - scanned once and never again, for example: interned int/str, builtin types, builtinFunction
• immortal mutable - we have to re-scan them again on each collection, but the object itself will never be deallocated, for example: user created types (the result of the class statement)
• mutable young - just allocated, will probably die in just a moment
• mutable old - object from mutable young that survived for a bit

Btw. this whole thing depends on me having time and will to write it.

[LiarPrincess]

After some thoughts, there is a way to implement a nice garbage collection in Swift. The catch is that it requires move-only types.

Semantics

• assign (=) is move

• copy is explicit

• deint is always called on lifetime end

• methods allow specifying whether the argument is:

  Argument	Semantics	Syntax
  Moved	Transfers ownership (calls move).	elsa: consume Princess or elsa: Princess (better)
  Borrowed	Does not call move/copy, does not affect lifetime.	elsa: borrow Princess or elsa: Princess&
  Copied	Calls some predefined method like copy(other: Self) or init(copy: Self). This one is optional, you can just copy before call and move into arg.	elsa: copy Princess

Then we would define a type with following semantics:

• move = nop
• copy = retain
• deinit = release, then if refCount == 0: deallocate

Collections/aggregates would be pain to deal with, but oh… well… (also, we can define our own collections with get = copy and delete = take ownership).

Obviously, we would still need a garbage collector to resolve reference cycles…

Implementation

// Helper protocol to which all of the types conform to (already exists).
protocol PyObjectMixin: MoveOnly {
  var ptr: RawPtr { get }
  init(ptr: RawPtr)
}

extension PyObjectMixin {
  /// Create a new reference to this object.
  func copyRef() -> Self {
    let result = Self(ptr: self.ptr)
    result.referenceCount += 1 // Stored on the heap at 'self.ptr + someOffset'
    return result
  }
}

struct PyInt: PyObjectMixin, MoveOnly {
  let ptr: RawPtr { get }

  init(ptr: RawPtr) {
    self.ptr = ptr
  }

  // 'MoveOnly' enables 'deinit' on 'struct'
  deinit {
    self.referenceCount -= 1
    if self.referenceCount == 0 {
      // Let it go, let it go
      // Can't hold it back anymore
      // Let it go, let it go
      // Turn away and slam the door
    }
  }
}

// === Usage ===

func foo() {
  let int: PyInt = …
  let intCopy = int.copyRef() // ref count += 1
  bar(intCopy) // consumes 'intCopy', calls 'ref count -= 1'

  print("foo: \(int)") // ok
  print("foo: \(intCopy)") // compiler error, 'intCopy' was consumed by 'bar'
}

func bar(int: consume PyInt) {
  print("bar: \(int)")
  // end of lifetime: ref count -= 1
}

Downcasting

Downcasting would be weird, because it would always retain. We can't express: "valid cast -> move", "failed cast -> nop" semantics:

let object: PyObject = …
if let int = py.cast.asInt(object) {
  // 'object' was moved into 'int'
} else {
  // 'object' is still valid
}

The only way to do this would be to return CastResult = succeeded(PyInt) | failed(PyObject) type (which always moves).

Making some types copyable

It would be tempting to opt out of the reference counting for some types (for example None - it is immortal). The problem is that they store move-only (reference counted) members, and as soon as you store at least 1 move-only member then you also become move-only.

Can we convince the compiler that we know what we are doing?