Tuples with tail allocation

[LiarPrincess]

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