This issue tries to design a new way of representing a single Python object in memory.

This may seem like a massive amount of work (we already have implemented almost all of the 100+ Python types and now we want to change this), but fortunately almost every aspect of the current model is exposed to code generation scripts (“Generated” directory inside the “Objects” module). This includes Swift type (with parent type), Swift fields, Swift methods and initializers, Python type, Python properties and Python methods.

We also try to not rely on the current model too much, for example we do not use Swift initializers, but instead we use our own PyMemory type (which will eventually call init). We also have our own way of casting object from one type to another type via PyCast that checks the runtime Python type.

Current - Swift class instances

Currently we are using Swift objects to represent Python instances. For example Swift PyInt object represents a Python int instance (Sourcery annotations are explained in Violet documentation):

// sourcery: pytype = int, isDefault, isBaseType, isLongSubclass
public class PyInt: PyObject {

  // sourcery: pymethod = __add__
  public func add(_ other: PyObject) -> PyResult<PyObject> {
    // …
  }
}

This is nice because:

• Is very easy to add new types/methods - which is important since we have more than 120 types and 780 methods to implement.
• Free type compatibility - which means that we can cast object reference (represented as PyObject instance) from VM stack to a specific Python type, for example int (represented as PyInt instance).

Not-so-nice things include:

• Wasted cache/memory on Swift metadata - each Swift object holds a reference to its Swift type. We do not need this since we store a reference to Python type which serves a similar function.

• Forced Swift memory management - ARC is “not the best” solution when working with circular references (which we have, for example: object type has type type and type type is a subclass of object, not to mention that type type has type as its type).

• We have to perfectly reproduce Python type hierarchy inside Swift which can cause some problems if the 2 languages have different view on a certain behavior, for example:

  class PyInt {
    func and() { print("int.and") }
  }
  
  // `bool` is a subclass of `int` in Python.
  class PyBool: PyInt {
    override func and() { print("bool.and") }
  }
  
  let f = PyInt.and // This is stored inside `int.__dict__`
  f(intInstance)(rhs) // 'int.and', as expected
  f(boolInstance)(rhs) // 'bool.and'! 'int.and' was expected, since we took 'f' from 'PyInt'
  

Pointer to struct + type punning

The other approach would be to use struct and type punning to create object hierarchy by hand (this is more-or-less what CPython does).

struct Ref<Pointee> {
  let ptr: UnsafePointer<Pointee>
}

struct PyObjectHeader {
  var type: Ref<PyType>
  var flags: UInt32
  private let padding = UInt32.max
}

struct PyObject {
  var header: PyObjectHeader
}

struct PyInt {
  var header: PyObjectHeader
  var value: Int
}

func newInt(value: Int) -> Ref<PyInt> {
  // Basically malloc(sizeof(PyInt)) + filling properties
}

// 'int' is a Python object representing number '2'
let int = newInt(value: 2)

// Cast it to 'PyObject' — this is really important since
// we will need to do this to store object on VM stack.
// (spoiler: this is not legal!)
let object = Ref<PyObject>(ptr: int.ptr)

As we can see both PyObject and PyInt start with PyObjectHeader, so one could assume that they can easily convert from Ref<PyInt> to Ref<PyObject>.

Well… Swift does not guarantee that the memory layout will be the same as declaration order (even with SE-0210: Add an offset(of:) method to MemoryLayout). Yes, this is what happens right now, but it may change in the future. There are some exceptions, for example:

• struct with single member will have the same layout as this member
• enum with single case with payload will have the payload layout
• homogenous tuples will look “as expected”
• @frozen thingies with library-evolution enabled

But, none of them applies in our case.

This approach also blocks us from using flexible array member, unless we do some additional things (allocate more space, and then offset the struct pointer to get aligned address of array members).

Related resources:

• WWDC 2020: Safely manage pointers in Swift
• Swift forum: “Guarantee (in-memory) tuple layout…or don’t” thread by Jordan Rose
• Swift docs: TypeSafeMemory.rst
• Swift evolution: UnsafeRawPointer API

Manual alignment

We can just allocate a block of memory and manually assign where do each field starts and ends.

struct PyInt {

  internal let ptr: UnsafePointer

  // `PyObjectHeader` holds `type/flags` (and maybe `__dict__`).
  internal var header: PyObjectHeader {
    return PyObjectHeader(ptr: self.ptr)
  }

  // Without using [flexible array member](https://en.wikipedia.org/wiki/Flexible_array_member).
  // This may also invoke needless COW when we modify the value, but there are
  // ways to prevent this.
  internal var value: Int {
    // We also need to align this 'ptr', but we will skip this in the example, 
    // since the code for this would depend on the property type.
    // Or we could craft 'PyObjectHeader', so that its 'size' is always word aligned.
    let ptr = self.ptr + PyObjectHeader.size
    return ptr.pointee
  }
}

extension PyMemory {

  internal func newInt(type: PyType, value: Int) {
    // Skipping alignment (again…)
    let memorySize = PyObjectHeader.size + Int.size
    let ptr = self.allocate(size: memorySize)
    let int = PyInt(ptr: ptr)

    int.header.type = type
    int.header.flags = // Something…
    int.value = value

    // register for garbage collection/arc
    self.startTracking(object: int.header)
  }
}

This is really promising since the whole concept is quite simple. The execution (as in: writing the code) is a little bit more complicated since it lacks the compiler support for proper alignment.

Using C

If we declare our objects in C we will get the C-layout. Then we can import them into Swift. This is nice because C layout is predictable and well described (see: cppreference.com: type).

Unfortunately this has its own problems, most notably that some of the properties on our Swift types are not trivially representable in C.

As far as I know this is the “official” (recommended by Swift team) way of dealing with this situation.

Memory management

When discussing object representation we have to bear in mind the memory management - a way of releasing unused instances.

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) and 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;

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).

Anyway, now it's our turn to discuss this:

• 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
  

• 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 while list) we release it. Everything else is the same as in the “using Swift native ARC” point.

  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.

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).

Currently we use GenericLayout to calculate offsets of PyObject members (like this).

Instead we could do the usual offset/size dance:

extension PyObject {
  public static let member2Offset = calculateOffset(
    previousMemberOffset: Self.member1Offset,
    previousMemberSize: MemoryLayout<Member1Type>.size,
    alignment: MemoryLayout<Member2Type>.alignment
  )
}

func calculateOffset(previousMemberOffset: Int, previousMemberSize: Int, alignment: Int) -> Int {
  var offset = previousMemberOffset + previousMemberSize
  return round(offset, to: alignment)
}

Though, I have not checked what Swift compiler emits for the current version, so maybe it is not needed.

From developer.apple.com/ManagedBufferPointer/Capacity:

This value may be nontrivial to compute; it is usually a good idea to store this information in the “header” area when an instance is created.

Under the hood

From ManagedBuffer.swift:

extension ManagedBufferPointer {
  @inlinable
  @available(OpenBSD, unavailable, message: "malloc_size is unavailable.")
  public var capacity: Int {
    return (
      _capacityInBytes &- ManagedBufferPointer._elementOffset
    ) / MemoryLayout<Element>.stride
  }
}

Where _capacityInBytes is defined as malloc_size:

static inline __swift_size_t _swift_stdlib_malloc_size(const void *ptr) {
  extern __swift_size_t malloc_size(const void *);
  return malloc_size(ptr);
}

Solutions

• Store additional member capacity: Int in Header. Header size: 2 words.
• Pack capacity inside existing header. Header size: 1 word. Layout [1bit - isNegative][31 bits - count][32 bits - capacity]

Currently we store tuple elements inside Swift array (elements: [PyObject]). The better idea would be to allocate more space after the tuple and store elements there (this is called flexible array member in C). This saves a pointer indirection and is better for cache, since we can fit a few first elements in the same line as type, __dict__ etc. We can also do this for other immutable container types:

• str - currently native Swift String. This would force us to implement our own String type - not hard, but takes a lot of time.
• int - currently our own BigInt implementation (which does store values in Int32 range inside the pointer).

Calculating layout

This is not a problem since GenericLayout.Field already supports repeatCount:

internal struct GenericLayout {

  internal struct Field {
    internal let size: Int
    internal let alignment: Int
    internal let repeatCount: Int

    /// `repeatCount` is the number of times `type` is repeated:
    /// ```c
    /// struct DisnepPrincess {
    ///     char name[20];
    /// };
    /// sizeof (struct DisnepPrincess) // 20
    /// ```
    internal init<T>(_ type: T.Type, repeatCount: Int = 1) {
      assert(repeatCount >= 0)
      self.size = MemoryLayout<T>.size
      self.alignment = MemoryLayout<T>.alignment
      self.repeatCount = repeatCount
    }
  }

  internal init(initialOffset: Int, initialAlignment: Int, fields: [Field]) { things… }
}

So, for tuple with count 5 we would have following layout:

• PyObject things
• PyTuple things - for example count and cached hash (though we have to remember that while tuple is immutable, the elements inside are not)
• GenericLayout.filed(PyObject.self, repeatCount: 5) <- this is the new thing

Homo/hetero

• Homomorphic - all allocated elements are layout compatible, both inline (for example RawPtr for storing multiple PyObjects) and on the heap (all PyObjects have the same header). This is true for tuple.
• Heteromorphic - tail allocated elements can be different. Example for PyFrame.FastLocalsCellFreeBlockStackStorage:
  • fastLocals - PyObject?
  • cell/free - PyCell
  • blocks - PyFrame. Block - totally incompatible with PyObject? and PyCell

With the new object model (see: #1) it should be possible to run unit tests with --parallel enabled (because py is no longer a global variable). Maybe. Probably…

• UnicodeDataDoesNotCrashTests. test_iterateAll should be split by plane giving us 17 tests
• make test (in Makefile) should be updated

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).