I'm interested in this idea, so starting a dedicated thread for it.
Fleshing it out a bit more, I imagine the protocol would be something like:
protocol InlineOptionality {
static let none: Self
}
The premise seems clear and conceptually simple - allow types to opt into storing their presence internally, rather than requiring external storage. So that when Optional is used to wrap them, it can store just the wrapped type - no extra storage required.
As we saw in the [U]Int128 discussion thread, and with the existing Duration type, there are serious concerns with the storage efficiency of types with non-trivial alignment sizes.
As I understand it, there's already special-casing that does essentially this (inlining optionality) for pointers, by treating the literal value 0 as Optional.none?
A type conforming to this InlineOptionality protocol would of course have to ensure it never mutates between states ('nil' vs not), since that transition should only happen explicitly and externally to the type, via the Optional interface (e.g. by explicit assignment to nil, or re-assignment to a non-nil value).
e.g. if it's a numeric type and it uses a sentinel value to indicate nil, it needs to ensure that sentinel value cannot be modified once set [by Optional] (latching behaviour) and that it cannot be arrived upon accidentally (e.g. through regular arithmetic or any other such operations).
The question is, can this actually be implemented? Are there downsides?
It would be useful for types to be able to control whether they have invalid states that can be used for enum layout. It can't be as a normal protocol, though, because we have to know that the values we use absolutely are not valid normal values of the type, so it can't be a retroactively-added extension to the type. A requirement like static let none: Self would also not be workable because the net result would be that none is not a valid value of type Self. From an implementation standpoint, the thing that would most easily integrate with the implementation would be some way to specify the low-level bit patterns which are invalid for the type, like:
@extraInhabitants(0, 0xFFFF_FFFF) // we can use these values for no-payload enum tags
@spareBitMask(0xFF00_0000) // we can use these bits for multi-payload enum discriminators
struct Foo {
var value: Int32
}
That's not an implementation level that most developers are used to thinking at, of course. And by itself it wouldn't provide any assistance to the developer to ensure that the invalid representations aren't used as real values, making it undefined behavior if they allow it by accident. So it's worth considering how we can make it more user-friendly.
Good point - this is useful for more than just Optional. One post in and already I have to change the thread title.
For sure.
But, I'm pretty confident it doesn't have to be safer than that - these could always be named @unsafeExtraInhabitants and @unsafeSpareBitMask and left as "power-user" features. For immutable types the implementor only has to ensure their init(s) are safe, which is certainly practical, and a valuable subset of use cases even by themselves.
But of course it'd be fantastic if they weren't unsafe in this sense, and their validity were somehow enforced by the compiler. I must admit I'm pretty sceptical that this is possible, though, on first blush - I mean, if you have what's fundamentally an Int and you declare that some subset of its values are up for grabs for external use, how could the compiler plausibly enforce that every applicable initialiser, method, and operator don't carelessly produce those values?
Maybe the compiler could insert essentially a precondition at every actual memory assignment or modification, within the type's implementation, to ensure the underlying storage truly never gets into that state. But I suspect that'd become very expensive (in runtime)?
Perhaps the optimiser could deduce that some of those checks are impossible to fail and remove them, like it already does (I believe?) for integer overflow checks, but how reliable would that removal be? I imagine this is pretty complicated logic for the optimiser to have to evaluate. Especially for less trivial examples than mere Ints.
And it'd have to do that for all extensions as well, even outside the type's home module, which would at the least make adding these decorators binary-incompatible, right? 'course, this is true irrespective of the compiler's assistance. Not a deal-breaker, but a sharp edge at least.
To begin, I will temporarily change the question so it's about two independent invalid values. It could be expressed like this:
struct Foo {
@spareValue(1)
private var first: Int16
@spareValue(47)
private var second: Int16
}
This would have to be enforced at runtime by checking for an invalid value whenever you initialize or assign to first or second. Then the compiler can infer that any value where first == 1 or second == 47 is an invalid one.
We could make this fancier with multiple values and ranges, such as: @spareValue(1, 5, 33..<120).
And from this we can build something that answers the initial question. If only the combination of (first: 1, second: 47) is invalid, then can you express it like this:
Here, a value of Foo where content == (first: 1, second: 47) is invalid. Checking for nil could then be made using the above comparison. This comparison keeps the type system sound as there's no way to make a Foo that uses a spare value, and there's no need to create an invalid Foo since we're comparing fields of Foo, not Foo itself.
as the underlying type, it works in principle although there are these drawbacks:
in case of tuple alignment is 1 byte which might be undesired
with such a tuple there are lot's of values to sacrifices as invalid (any bit pattern that has 0xFF at one of the ends), which makes the total number of valid numbers not (2^64 - 1) (as with UnsafeRawPointer storage type) but (2^64 - 2^(64 - 8))
I'm interested in the case where there is exactly 1 or no invalid pattern. In such a case, checking for equality of an aggregate of (bitwise-copyable) values could be optimized to memcmp. It's very specific, but it could matter sometimes. (If there are two or more invalid patterns, all bets are off.)
struct S { var x: Int8; /*a giant padding here*/ var y: Int }
floats and types with custom EQ conformances.
Also Reference types:
class C: Equatable { ... }
struct S: Equatable { var c: C }
var a = S(c: C())
var b = S(c: C())
a == b // obviously
memcmp(&a, &b, MemoryLayout<S>.size) != 0 // i.e. not equal obviously
(although this case we could put in the "custom EQ conformance" bucket).
We could do 1-byte and 8-byte types with that property. I don't know how to do 2, 4 and other size types.
BTW, even if you have many unwanted bit patterns, you can choose a single bit pattern and use it consistently when needed for all operations that create new values of your type. In principle if you cover them all (and let put unsafeBitCast aside with which you could make arbitrary bit patterns), the extra unwanted bit patterns won't happen.
That's not enough to check for padding. Same example:
struct S {
var x: Int8
var y: Int
}
MemoryLayout<S>.size == MemoryLayout<S>.stride // true
A proper check would somehow enumerate all fields (how?) calculate their sum and compare to the struct size. Do so recursively to account for sub-structs. I don't know how to do this.
func equal<T>(_ a: T, _ b: T) -> Bool {
// somehow check there is no padding 🤔
if _isPOD(type(of: a)) && _isPOD(type(of: b)) {
var a = a, b = b
return memcmp(&a, &b, MemoryLayout.size(ofValue: a)) == 0
} else {
fatalError("HMM...")
}
}
func equal<T: Equatable>(_ a: T, _ b: T) -> Bool {
a == b
}
It would still fail the following test:
struct S {
static func == (lhs: Self, rhs: Self) -> Bool {
(lhs.value & ~1) == (rhs.value & ~1)
}
var value: Int16 = 0
}
var a = S(value: 0x100), b = S(value: 0x101)
precondition(a == b) // ✅
precondition(equal(a, b)) // ❌
Here S "forgot" to mark itself Equatable (and rightfully so: there is no law against it). Is there a way to check if type implements "==" ?
SwiftUI machinery is known to do memcmp comparisons for POD types for their diffing and it is very surprising to see that the type's EQ is not getting called. You add a field → the type is not POD anymore → your EQ starts being called.
Re: padding. Does Swift guarantee that padding bytes are always zeros?
func hasPadding<T>(_ value: T) -> Bool {
let size = MemoryLayout<T>.size
let fieldsSize = sizeOfAllFields(value)
print("size: \(size), fieldsSize: \(fieldsSize)")
precondition(fieldsSize <= size)
return size != fieldsSize
}
func sizeOfAllFields(_ value: Any) -> Int {
let m = Mirror(reflecting: value)
switch m.displayStyle {
case .none:
switch value {
case is Int8: return 1
case is Int16: return 2
case is Int32: return 4
case is Int64: return 8
case is Int: return MemoryLayout<Int>.size
case is UInt8: return 1
case is UInt16: return 2
case is UInt32: return 4
case is UInt64: return 8
case is UInt: return MemoryLayout<UInt>.size
case is Float: return MemoryLayout<Float>.size
case is Double: return MemoryLayout<Double>.size
default: fatalError("TODO")
}
case .struct:
return m.children.reduce(0) {
$0 + sizeOfAllFields($1.value)
}
case .class:
fatalError("TODO")
case .enum:
fatalError("TODO")
case .tuple:
return m.children.reduce(0) {
$0 + sizeOfAllFields($1.value)
}
case .optional:
// value is Any here
let v = value as! Optional<Any>
if let v {
return sizeOfAllFields(v) // WRONG
} else {
return MemoryLayout.size(ofValue: v) // WRONG!
}
case .collection:
fatalError("TODO")
case .dictionary:
fatalError("TODO")
case .set:
fatalError("TODO")
}
}
It works in primitive cases but even a mere Optional field:
struct S {
var x: Int?
}
brings it to halt. Here's the relevant fragment:
case .optional:
// value is Any here
let v = value as! Optional<Any>
if let v {
return sizeOfAllFields(v) // WRONG
} else {
return MemoryLayout.size(ofValue: v) // WRONG!
}
The first branch is wrong because whilst it calculate the wrapped value size properly it doesn't account for an extra byte (if any!) for the optional flag (and as we seen sometimes there is no extra optional flag byte in case of pointers and some enums). The second branch is wrong on two counts, as in addition to the unaccounted optional flag, it doesn't calculate the wrapped value size properly (always returning 32 which is the size of Any).
Let me dream: if we had _hasPadding() and _hasEQ() we would be able using memcmp to compare things without fear:
Yeah if we wanted to do optimised bitwise equality and comparison operations for complex structs, I think we would need the compiler to emit bitmasks so we only consider salient bits. Then we'd create an extended version of memcmp which uses that info, probably implemented directly in assembly (we could adapt some existing memcmp implementation).
It's too late for the Apple ABI, but one thing we wanted to add to the Swift ABI for types but ran out of time for was a "normalize" value witness, which could be applied before packing a value into an enum. The typical use for this would be to normalize padding bits, but it could also do things like normalize non-canonical NaN representations of floating-point types, allowing us to use those padding bits and non-canonical representations for enum layout optimization, so Double? could be 8 bytes and (Int8, Int32) + (Int8, Int32) could stuff its tag in the tuple padding. Now that you mention it, normalize would also be useful for enabling comparison by memcmp, since memcmp(normalize(x), normalize(y)) would reliably compare x and y even if there is padding. It could still be valuable to explore introducing this concept to the Swift implementation on non-ABI-stable platforms.
That's only ABI-incompatible if we wanted to make it a value witness though, isn't it?
Couldn't we introduce something like a protocol witness table for layout constraints, which could hold metadata relevant to, say, BitwiseCopyable, while remaining compatible with the Apple ABI?
It's also ABI-breaking on the enum's side to take advantage of it, so Optional wouldn't be able to, for instance. You're right that it could be introduced in a forward-compatible way as new metadata, but only newly-introduced enums could actually use the layout optimization. That could nonetheless be valuable for memcpy comparison and other optimizations.
