Terrible struct layout with Never? and [Never], why?

Never? and [Never] ought to be equivalent to Void, so both of these should have a stride of 8:

struct S1<Element>
{
    let elements:[Element]
    let x:Int 
}
struct S2<Element>
{
    let elements:Element?
    let x:Int 
}

print("S1<Int>", MemoryLayout<S1<Int>>.stride)
print("S1<Never>", MemoryLayout<S1<Never>>.stride)

print("S2<Int>", MemoryLayout<S2<Int>>.stride)
print("S2<Never>", MemoryLayout<S2<Never>>.stride)
S1<Int> 16
S1<Never> 16
S2<Int> 24
S2<Never> 16

S1<Never> and S2<Never> take up twice the memory they should…

S1 is expected to be 16 bytes in size and stride because an array is always 8 bytes in size/stride no matter what the element is. S2 is problematic because your layout may lead to lots of padding. S2 can be rewritten as:

struct S2<Element> {
  let x: Int
  let elements: Element?
}

and now MemoryLayout<S2<Never>>.size is 9, but stride will still be 16 for alignment reasons. An optional will always be at least 1 byte large in order to remember whether it is .some/.none.

1 Like

size is not really relevant to me most of the time, because when you are optimizing for memory consumption more often than not it is because you are storing something like S2<Never> in an array, where only stride matters.

a Never? can never be some, so why does it need the tag byte?

The runtime code to calculate the number of tag bytes needed for a single-payload enum does look at the extra inhabitants of its payload, but it doesn’t look at whether that payload is uninhabited, because that information isn’t exposed in the common type layout. This might have been worth burning a flag on, but now it would be ABI-breaking to change, because layouts have to match in both static (Optional<Never>) and dynamic (Optional<T> where T == Never) contexts.

7 Likes

gotcha.

i will add the problem i am trying to solve here is i have a generic struct with 2 specializations:

Organizer.Item<[Generic.Constraint]>>
Organizer.Item<Void>>

where an instance of the type parameter is stored inline, so the Void specialization never allocates storage for the wrapped instance.

but i cannot write extensions on Item that are constrained by the generic parameter, because Void cannot conform to protocols, and Array can only conform to a protocol once. so instead i tried to do

Organizer.Item<Generic.Constraint>>
Organizer.Item<Never>>

where Item stores an array of T instead of T itself. and Never can conform to a protocol, and Generic.Constraint can conform to a protocol without conflicting with other element types.

any advice?

What’s in the Item struct, that you have both [T] and T? fields? Because most of the time I’d consider this premature optimization, but presumably you have a need.

Item stores a [T] and a String URI:

struct Item<T>
{
    let constraints:[T]
    let uri:String
}

without the constraints, i would expect it to have a stride of 16. the strings are referenced elsewhere and they share storage, so the string contents are less important than the memory footprint of the list of item descriptors themselves.

Hm, then you’re kind of stuck at this abstraction level. Array just doesn’t depend on its element type for layout at all, because it’s “just” a reference-counted pointer. So if you really need to shrink these, you’ll have to put that into a protocol, as you were already reaching for:

struct OptimizedArray<T: OptimizedArrayAware> {
  private var storage: T.Storage
  var value: [T] {
    T.arrayFromStorage(storage)
  }
}

protocol OptimizedArrayAware {
  associatedtype Storage = [Self]
  static func arrayFromStorage(_ storage: Storage) -> [Self]
}

extension OptimizedArrayAware where Storage == [Self] {
  static func arrayFromStorage(_ storage: Storage) -> [Self] { storage }
}

extension OptimizedArrayAware where Storage == () {
  static func arrayFromStorage(_ storage: Storage) -> [Self] { [] }
}

extension Never: OptimizedArrayAware {
  typealias Storage = ()
}

(you could probably make OptimizedArray a property wrapper, even, but that would make the example even longer, and I already left out a bunch)

The downside is that you’re introducing more generic code that might not get optimized away, so this could easily become a run-time/space trade-off instead of just complexity/space.

1 Like

i ended up just creating an empty struct to replace Void, and a wrapper struct around the [Generic.Constraint] array, which allowed me to conform the two cases to a protocol that i could parameterize Item over

1 Like