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

[Joe Groff]

> On Oct 19, 2016, at 9:16 AM, Guoye Zhang via swift-evolution <swift-evolution at swift.org> wrote:
> 
>> 
>> 在 2016年10月19日，11:43，Kevin Nattinger <swift at nattinger.net> 写道：
>> 
>>> 
>>> On Oct 19, 2016, at 8:13 AM, Guoye Zhang via swift-evolution <swift-evolution at swift.org> wrote:
>>> 
>>> 
>>>> 在 2016年10月19日，07:10，Jeremy Pereira <jeremy.j.pereira at googlemail.com> 写道：
>>>> 
>>>> 
>>>>> On 18 Oct 2016, at 19:17, 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.
>>>> 
>>>> Is this a general problem with Swift? Are lots of people complaining that they are running out of space for their Optional<Int> arrays?
>>>> 
>>> It's just that a common data type wasting almost half the space seems inefficient. I guess this is also the reason why they didn't adopt optional integers widely in stdlib.
>> 
>> I’ve only needed an array of optionals once, maybe twice. I don’t think arrays of optionals are widely used to begin with, and the reason there are few optional integers in the stdlib is because the interface is from objc, which doesn’t have optionals. I doubt any thought at all was given in designing the standard library to the extra space for an optional.
>> 
> Swift stdlib is independent from objc. Currently, "Int?" storage has a tradeoff between less space (n + 1 bytes) and unaligned access, and more space (n * 2 bytes) and fast access. Neither of them is optimal.

Something worth considering at a higher level is whether Array ought to align storage at all. Modern Intel and Apple CPUs pay much less of a penalty for unaligned access than older microarchitectures, and the memory savings of packing arrays of Int? and similar types would be significant. (There are C compatibility issues here too, since C's semantic model requires pointers to be well-aligned for their type, and we want Swift.Arrays of C types to be cheaply interoperable with pointer-based C APIs. This could perhaps be dealt with by guaranteeing that C basic types and structs always have sizeof(T) % alignof(T) == 0, and well-aligning the beginning of arrays.)

-Joe

> 
>>>> 
>>>>> 
>>>>> 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.
>>>> 
>>>> Well the “top value” for signed ints would have to be 0x8000... not 0xffff... which is the representation of -1. The top value for unsigned ints cannot be banned because unsigned integers are often used as bit fields either directly or in OptionSets.
>>>> 
>>>> Furthermore, how would the semantics of &+ and &- be affected? What about the performance of those two operators?
>>>> 
>>> I was originally going for the symmetry between Int and UInt as in compatible bit patterns. Now that I think of it, UInt is commonly used for bitwise operations, and it doesn't make sense to optimize for "UInt?" which is uncommon. So I agree that 0x80... is better.
>>> 
>>> Int performance would surely suffer because of current instruction sets, but Int? would improve.
>> 
>> In my experience, ints are used orders of magnitude more often than optional int?s. Why optimize for the rare case?
>> 
> If we were to have safe arithmetic that produces optionals, or lenient subscript, it is important to have efficient optional integers. I do agree that Int slowing down is unacceptable.
> 
> - Guoye
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution