[swift-evolution] [Pitch] Ban the top value in Int/UInt

[Joe Groff]

> On Oct 18, 2016, at 11:17 AM, Guoye Zhang via swift-evolution <swift-evolution at swift.org> wrote:
> 
> Currently, Swift Int family and UInt family have compact representations that utilize all available values, which is inherited from C. However, it is horribly inefficient to implement optional integers. It takes double the space to store [Int?] than to store [Int] because of alignment.
> 
> I propose to ban the top value in Int/UInt which is 0xFFFF... in hex. Int family would lose its smallest value, and UInt family would lose its largest value. Top value is reserved for nil in optionals. An additional benefit is that negating an Int would never crash.
> 
> Interacting with C/Obj-C is a major concern, but since we are already importing some of the unsigned integers as Int which loses half the values, one value is not such big a drawback. Alternatively, we could leave current behavior as CInt/CUInt. Converting them to the new Int?/UInt? doesn't generate any instructions since the invalid value already represents nil.
> 
> With optional integers improved, we could implement safe arithmetic efficiently, or even revisit lenient subscript proposals, but they are not in the scope of this pitch. Float/Double optionals could also be improved with the similar idea. (Isn't signaling nan the same as nil) Nested optionals such as "Int??" are still bloated, but I don't think they are widely used.
> 
> So what do you think? Can we break C compatibility a bit for better Swift types?

I don't think we'd ever be able to do this for unsigned values, since their use as bitmasks is pervasive and requires all inhabitants. There's some appeal to taking the least negative value away from signed int types, since as you noted, it would define away the potential for negation and division to overflow. There would be several tradeoffs:

- It makes overflow checking more expensive. Most CPUs have hardware support for detecting two's complement signed overflow, but checking for INT_MIN would require additional code after every potentially-overflowing operation, greatly increasing the code size and performance hit we'd pay for safe arithmetic.
- It would make Swift integer values not "toll-free bridge" with C integers, complicating the interface between Swift and C APIs. We could import C APIs to use Int? or Int!, but that would inflict pain on the client-side code that has to check those optionals.

If someone was bringing up a CPU from the silicon up to run Swift code, to run a software environment with little or no C interop, reserving INT_MIN would definitely be an interesting design point to consider, but we decided that it wasn't practical for Swift's target platforms today. There are other things we can do to mitigate the size cost of Int? compared to Int. Although we don't take full advantage of it today, Swift understands the layout of types at the *bit* level, and we plan to optimize things so that structs containing many bit-sized components, such as Bools or the out-of-line tags for multiple Optionals, can be automatically packed into bitfields by default. Note that `Int??` already has the same size as `Int?`, since Swift knows it's already burned a tag bit to represent 'nil' and can just store different numeric values in the payload with the tag bit set to distinguish '.some(.none)' from '.none'. (It's true that the `Array` type is constrained by presenting its elements as contiguous in memory and well-aligned, so `[Int?]` will likely never be very efficiently represented, but you could fairly easily represent a collection of optional Ints more efficiently SoA-style by passing around a pair of [Int] and a bit vector, or else reserving an Int value you know to be unused in your own domain and passing around [Int].lazy.map { $0 == Int.min ? nil : $0 } or something similar.)

-Joe