[Pitch] Ban the top value in Int/UInt


(Guoye Zhang) #1

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?

- Guoye


(Kevin Nattinger) #2

Part of the beauty of how optionals are implemented in Swift is that the compiler doesn’t have to do any magic w.r.t. optionals besides a bit of syntactic sugar (`T?` -> `Optional<T>`, `if let x` -> `if let case .some(x)`, auto-boxing when necessary, etc.).
- I strongly dislike the idea of special-casing optionals just to save a Byte.
- Optionals were presented as explicitly removing the need for such a sentinel value in the first place.
- There are reasonable cases where such a bit pattern is reasonably necessary to the data (e.g. bit fields, RSSI, IP addresses, etc.) and removing that value would force ugly workarounds and/or moving to a larger int size because of an ill-advised implementation detail.
- If performance or memory is so critical to your specific use case, use a non-optional and your own sentinel value. It’s likely no less efficient than having the compiler do it that way.

(more below)

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,

I’d argue those imports are bugs and should be fixed to the correct signedness.

one value is not such big a drawback.

Unless you happen to need all $width bits.

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.

Trying to convert an invalid value like that crashes in most of Swift.

With optional integers improved, we could implement safe arithmetic efficiently, or even revisit lenient subscript proposals,

I don’t see how losing a particular value has any effect on either of those, but it’s possible there’s some theory or implementation detail I’m not aware of.

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?

We can, and do. C.f. structs, non-@objc classes, and enums not RawRepresentable with a C-compatible entity. If anything, this breaks compatibility with the rest of Swift.

···

On Oct 18, 2016, at 11:17 AM, Guoye Zhang via swift-evolution <swift-evolution@swift.org> wrote:

- Guoye
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Joe Groff) #3

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

···

On Oct 18, 2016, at 11:17 AM, Guoye Zhang via swift-evolution <swift-evolution@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?


(David Waite) #4

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.

There are two ways to do this (using Int8 for example)
1. 0xFF reserved to mean nil. As this normally means -1, all negative numbers now use complements rather than two’s complement form. This breaks a lot of binary math.

2. 0x80 reserved to mean nil. This is normally -128. Overflow would have to be modified in order to support this (otherwise, 127 + 1 == nil). bit padding no longer works (0x80 would expand to 0xFF80 for a Int16 with bit padding, not 0x8000)

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.

As the appropriate integer minimum value may already be in use in C or Objective C code, I believe you would need to define a new integer types to support this sort of constrained type.

Where I would see something like this be most appropriate would be for supporting a “BigNumber” type in the language, preferably as the default integer type. Ruby does this for example with Fixnum/Bignum - all values in Ruby are actually tagged pointers (where the lower bits are set to cause invalid alignment of a pointer in order to indicate it is a special case immediate value). So if the lowest bit is set, the value is a FixNum integer with a lower max/higher min than a traditional integer. On overflow, the value is promoted to be a BigNum, which is a reference to an arbitrary sized integer on the heap.

-DW

···

On Oct 18, 2016, at 12:17 PM, Guoye Zhang via swift-evolution <swift-evolution@swift.org> wrote:


(Benjamin Spratling) #5

Part of the beauty of how optionals are implemented in Swift is that the compiler doesn’t have to do any magic w.r.t. optionals
- I strongly dislike the idea of special-casing optionals just to save a Byte.

It is nice that enums are generic, but enums do know about extra bits laying around and compact themselves if possible.

As I understand it, It would actually save 7.875 bytes of storage. When the next stored value is Int-alignment, 7 extra bytes beyond the optional marking are used up. For code which uses several Int? in a row, it doubles the required memory - as I understand it.

If anything, this breaks compatibility with the rest of Swift.

Yep. So if it’s gonna be done, now's the time to do it.

An alternative is to introduce 63-bit and 31-bit integer types just to play nice with optionals. Or to play nice with more than 2 enum cases, why not introduce 56- and 24-bit Int/UInt? and leave space for many cases. Of course, there’s an added performance penalty when working with the mask, right? Maybe opting in to these odd byte sizes lets the developer know that.

When working with Int / UInt the developer is not usually specifying “Int64”, but instead saying "big integer, oh, 64-bits, that should handle it.” When they say “it might be 32-bits, uh oh”, then they explicitly specify Int64. So maybe "typealias Int = Int56" solves this problem.

There was talk of adding a variable-byte-sized Integers to the built-ins in the future. Maybe these changes could work together with that?

-Ben

···

On Oct 18, 2016, at 1:54 PM, Kevin Nattinger via swift-evolution <swift-evolution@swift.org> wrote:


#6

If we went that route, could arithmetic operations still be implemented
efficiently?

Nevin

···

On Tuesday, October 18, 2016, Guoye Zhang via swift-evolution < swift-evolution@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?

- Guoye
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <javascript:;>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Guoye Zhang) #7

在 2016年10月18日,14:54,Kevin Nattinger <swift@nattinger.net> 写道:

Part of the beauty of how optionals are implemented in Swift is that the compiler doesn’t have to do any magic w.r.t. optionals besides a bit of syntactic sugar (`T?` -> `Optional<T>`, `if let x` -> `if let case .some(x)`, auto-boxing when necessary, etc.).

Swift compiler is already using magic for optional pointers. Invalid address are used for optional pointers. `MemoryLayout<ManagedBuffer<Int, String>???>.size` is still 8.

- I strongly dislike the idea of special-casing optionals just to save a Byte.

Not just a byte, it saves half the space in arrays. [Int?] is double the size of [Int].

- Optionals were presented as explicitly removing the need for such a sentinel value in the first place.
- There are reasonable cases where such a bit pattern is reasonably necessary to the data (e.g. bit fields, RSSI, IP addresses, etc.) and removing that value would force ugly workarounds and/or moving to a larger int size because of an ill-advised implementation detail.

I agree. Perhaps we just special case Int, and keep UInt intact for bitwise operations?

- If performance or memory is so critical to your specific use case, use a non-optional and your own sentinel value. It’s likely no less efficient than having the compiler do it that way.

(more below)

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,

I’d argue those imports are bugs and should be fixed to the correct signedness.

It is for indexing Swift array easier.

one value is not such big a drawback.

Unless you happen to need all $width bits.

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.

Trying to convert an invalid value like that crashes in most of Swift.

CInt to Optional<Int> would not crash because invalid value becomes nil.

With optional integers improved, we could implement safe arithmetic efficiently, or even revisit lenient subscript proposals,

I don’t see how losing a particular value has any effect on either of those, but it’s possible there’s some theory or implementation detail I’m not aware of.

Unaligned memory access would be a huge performance hit.

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?

We can, and do. C.f. structs, non-@objc classes, and enums not RawRepresentable with a C-compatible entity. If anything, this breaks compatibility with the rest of Swift.

I don't want that, either.

···

On Oct 18, 2016, at 11:17 AM, Guoye Zhang via swift-evolution <swift-evolution@swift.org> wrote:

- Guoye
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Guoye Zhang) #8

在 2016年10月18日,15:15,Joe Groff <jgroff@apple.com> 写道:

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

Thanks for your response. I'm glad to know that it is discussed.

- Guoye

···

On Oct 18, 2016, at 11:17 AM, Guoye Zhang via swift-evolution <swift-evolution@swift.org> wrote:


(Guoye Zhang) #9

在 2016年10月18日,15:30,David Waite <david@alkaline-solutions.com> 写道:

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.

There are two ways to do this (using Int8 for example)
1. 0xFF reserved to mean nil. As this normally means -1, all negative numbers now use complements rather than two’s complement form. This breaks a lot of binary math.

2. 0x80 reserved to mean nil. This is normally -128. Overflow would have to be modified in order to support this (otherwise, 127 + 1 == nil). bit padding no longer works (0x80 would expand to 0xFF80 for a Int16 with bit padding, not 0x8000)

Yes, 0x80 is better for arithmetic, checking for nil might be slower.

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.

As the appropriate integer minimum value may already be in use in C or Objective C code, I believe you would need to define a new integer types to support this sort of constrained type.

Where I would see something like this be most appropriate would be for supporting a “BigNumber” type in the language, preferably as the default integer type. Ruby does this for example with Fixnum/Bignum - all values in Ruby are actually tagged pointers (where the lower bits are set to cause invalid alignment of a pointer in order to indicate it is a special case immediate value). So if the lowest bit is set, the value is a FixNum integer with a lower max/higher min than a traditional integer. On overflow, the value is promoted to be a BigNum, which is a reference to an arbitrary sized integer on the heap.

-DW

I would also like to see big number some day.

- Guoye

···

On Oct 18, 2016, at 12:17 PM, Guoye Zhang via swift-evolution <swift-evolution@swift.org> wrote:


(Charlie Monroe) #10

Talking about bridging - my guess is that it would mess with NSNotFound which still has legit use cases even in Swift (when dealing with ObjC APIs) and is defined as NSIntegerMax at this moment, though its usage is slowly on the decline...

But there are still many many APIs (mostly C-based) that define some "magic" constants as (unsigned)(-1), which I believe this would mess with.

Given this, it would IMHO have huge consequences for backward compatiblity.

···

On Oct 18, 2016, at 8:54 PM, Kevin Nattinger via swift-evolution <swift-evolution@swift.org> wrote:

Part of the beauty of how optionals are implemented in Swift is that the compiler doesn’t have to do any magic w.r.t. optionals besides a bit of syntactic sugar (`T?` -> `Optional<T>`, `if let x` -> `if let case .some(x)`, auto-boxing when necessary, etc.).
- I strongly dislike the idea of special-casing optionals just to save a Byte.
- Optionals were presented as explicitly removing the need for such a sentinel value in the first place.
- There are reasonable cases where such a bit pattern is reasonably necessary to the data (e.g. bit fields, RSSI, IP addresses, etc.) and removing that value would force ugly workarounds and/or moving to a larger int size because of an ill-advised implementation detail.
- If performance or memory is so critical to your specific use case, use a non-optional and your own sentinel value. It’s likely no less efficient than having the compiler do it that way.

(more below)

On Oct 18, 2016, at 11:17 AM, Guoye Zhang via swift-evolution <swift-evolution@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,

I’d argue those imports are bugs and should be fixed to the correct signedness.

one value is not such big a drawback.

Unless you happen to need all $width bits.

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.

Trying to convert an invalid value like that crashes in most of Swift.

With optional integers improved, we could implement safe arithmetic efficiently, or even revisit lenient subscript proposals,

I don’t see how losing a particular value has any effect on either of those, but it’s possible there’s some theory or implementation detail I’m not aware of.

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?

We can, and do. C.f. structs, non-@objc classes, and enums not RawRepresentable with a C-compatible entity. If anything, this breaks compatibility with the rest of Swift.

- Guoye
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Jeremy Pereira) #11

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?

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?

So what do you think? Can we break C compatibility a bit for better Swift types?

Well it’s not just C compatibility, it’s underlying processor compatibility. And actually, yes, I think C compatibility is vastly more important than being able to make your [Int?] arrays smaller considering that full 2’s complement numbers is what the OS calls and libc calls are expecting.

···

On 18 Oct 2016, at 19:17, Guoye Zhang via swift-evolution <swift-evolution@swift.org> wrote:

- Guoye
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Guoye Zhang) #12

Perhaps not considering the current instruction set. Safe arithmetics that produce optionals would be simpler though.

- Guoye

···

在 2016年10月18日,14:43,Nevin Brackett-Rozinsky <nevin.brackettrozinsky@gmail.com> 写道:

If we went that route, could arithmetic operations still be implemented efficiently?

Nevin

On Tuesday, October 18, 2016, Guoye Zhang via swift-evolution <swift-evolution@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?

- Guoye
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Guoye Zhang) #13

In that case, NSNotFound can be seamlessly converted to nil. Those magic might also be better represented in optionals. It is indeed bad for compatibility otherwise.

- Guoye

···

在 2016年10月18日,15:09,Charlie Monroe <charlie@charliemonroe.net> 写道:

Talking about bridging - my guess is that it would mess with NSNotFound which still has legit use cases even in Swift (when dealing with ObjC APIs) and is defined as NSIntegerMax at this moment, though its usage is slowly on the decline...

But there are still many many APIs (mostly C-based) that define some "magic" constants as (unsigned)(-1), which I believe this would mess with.

Given this, it would IMHO have huge consequences for backward compatiblity.

On Oct 18, 2016, at 8:54 PM, Kevin Nattinger via swift-evolution <swift-evolution@swift.org> wrote:

Part of the beauty of how optionals are implemented in Swift is that the compiler doesn’t have to do any magic w.r.t. optionals besides a bit of syntactic sugar (`T?` -> `Optional<T>`, `if let x` -> `if let case .some(x)`, auto-boxing when necessary, etc.).
- I strongly dislike the idea of special-casing optionals just to save a Byte.
- Optionals were presented as explicitly removing the need for such a sentinel value in the first place.
- There are reasonable cases where such a bit pattern is reasonably necessary to the data (e.g. bit fields, RSSI, IP addresses, etc.) and removing that value would force ugly workarounds and/or moving to a larger int size because of an ill-advised implementation detail.
- If performance or memory is so critical to your specific use case, use a non-optional and your own sentinel value. It’s likely no less efficient than having the compiler do it that way.

(more below)

On Oct 18, 2016, at 11:17 AM, Guoye Zhang via swift-evolution <swift-evolution@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,

I’d argue those imports are bugs and should be fixed to the correct signedness.

one value is not such big a drawback.

Unless you happen to need all $width bits.

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.

Trying to convert an invalid value like that crashes in most of Swift.

With optional integers improved, we could implement safe arithmetic efficiently, or even revisit lenient subscript proposals,

I don’t see how losing a particular value has any effect on either of those, but it’s possible there’s some theory or implementation detail I’m not aware of.

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?

We can, and do. C.f. structs, non-@objc classes, and enums not RawRepresentable with a C-compatible entity. If anything, this breaks compatibility with the rest of Swift.

- Guoye
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Charlie Monroe) #14

Which would required all developers to update all APIs to annotate, where some magic value may be used - because otherwise all non-Swift APIs would return optional Ints or run into risk of crashing during runtime (since once entering Swift code, the value would become nil)...

I agree that it would be the ideal case, but reastically, given how many APIs out there are still with no nullability annotations (and it's been what - 3-4 years now?), I don't see this practical...

···

On Oct 18, 2016, at 9:16 PM, Guoye Zhang <cc941201@me.com> wrote:

In that case, NSNotFound can be seamlessly converted to nil. Those magic might also be better represented in optionals. It is indeed bad for compatibility otherwise.

- Guoye

在 2016年10月18日,15:09,Charlie Monroe <charlie@charliemonroe.net> 写道:

Talking about bridging - my guess is that it would mess with NSNotFound which still has legit use cases even in Swift (when dealing with ObjC APIs) and is defined as NSIntegerMax at this moment, though its usage is slowly on the decline...

But there are still many many APIs (mostly C-based) that define some "magic" constants as (unsigned)(-1), which I believe this would mess with.

Given this, it would IMHO have huge consequences for backward compatiblity.

On Oct 18, 2016, at 8:54 PM, Kevin Nattinger via swift-evolution <swift-evolution@swift.org> wrote:

Part of the beauty of how optionals are implemented in Swift is that the compiler doesn’t have to do any magic w.r.t. optionals besides a bit of syntactic sugar (`T?` -> `Optional<T>`, `if let x` -> `if let case .some(x)`, auto-boxing when necessary, etc.).
- I strongly dislike the idea of special-casing optionals just to save a Byte.
- Optionals were presented as explicitly removing the need for such a sentinel value in the first place.
- There are reasonable cases where such a bit pattern is reasonably necessary to the data (e.g. bit fields, RSSI, IP addresses, etc.) and removing that value would force ugly workarounds and/or moving to a larger int size because of an ill-advised implementation detail.
- If performance or memory is so critical to your specific use case, use a non-optional and your own sentinel value. It’s likely no less efficient than having the compiler do it that way.

(more below)

On Oct 18, 2016, at 11:17 AM, Guoye Zhang via swift-evolution <swift-evolution@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,

I’d argue those imports are bugs and should be fixed to the correct signedness.

one value is not such big a drawback.

Unless you happen to need all $width bits.

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.

Trying to convert an invalid value like that crashes in most of Swift.

With optional integers improved, we could implement safe arithmetic efficiently, or even revisit lenient subscript proposals,

I don’t see how losing a particular value has any effect on either of those, but it’s possible there’s some theory or implementation detail I’m not aware of.

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?

We can, and do. C.f. structs, non-@objc classes, and enums not RawRepresentable with a C-compatible entity. If anything, this breaks compatibility with the rest of Swift.

- Guoye
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Jean-Daniel) #15

Talking about bridging - my guess is that it would mess with NSNotFound which still has legit use cases even in Swift (when dealing with ObjC APIs) and is defined as NSIntegerMax at this moment, though its usage is slowly on the decline…

Bridge the API that may return NSNotFound to return optional. It would work perfectly well as the nil optional and NSNotFound would have the same binary representation.

···

Le 18 oct. 2016 à 21:09, Charlie Monroe via swift-evolution <swift-evolution@swift.org> a écrit :

But there are still many many APIs (mostly C-based) that define some "magic" constants as (unsigned)(-1), which I believe this would mess with.

Given this, it would IMHO have huge consequences for backward compatiblity.

On Oct 18, 2016, at 8:54 PM, Kevin Nattinger via swift-evolution <swift-evolution@swift.org> wrote:

Part of the beauty of how optionals are implemented in Swift is that the compiler doesn’t have to do any magic w.r.t. optionals besides a bit of syntactic sugar (`T?` -> `Optional<T>`, `if let x` -> `if let case .some(x)`, auto-boxing when necessary, etc.).
- I strongly dislike the idea of special-casing optionals just to save a Byte.
- Optionals were presented as explicitly removing the need for such a sentinel value in the first place.
- There are reasonable cases where such a bit pattern is reasonably necessary to the data (e.g. bit fields, RSSI, IP addresses, etc.) and removing that value would force ugly workarounds and/or moving to a larger int size because of an ill-advised implementation detail.
- If performance or memory is so critical to your specific use case, use a non-optional and your own sentinel value. It’s likely no less efficient than having the compiler do it that way.

(more below)

On Oct 18, 2016, at 11:17 AM, Guoye Zhang via swift-evolution <swift-evolution@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,

I’d argue those imports are bugs and should be fixed to the correct signedness.

one value is not such big a drawback.

Unless you happen to need all $width bits.

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.

Trying to convert an invalid value like that crashes in most of Swift.

With optional integers improved, we could implement safe arithmetic efficiently, or even revisit lenient subscript proposals,

I don’t see how losing a particular value has any effect on either of those, but it’s possible there’s some theory or implementation detail I’m not aware of.

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?

We can, and do. C.f. structs, non-@objc classes, and enums not RawRepresentable with a C-compatible entity. If anything, this breaks compatibility with the rest of Swift.

- Guoye
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Kevin Nattinger) #16

在 2016年10月19日,07:10,Jeremy Pereira <jeremy.j.pereira@googlemail.com> 写道:

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.

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?

···

On Oct 19, 2016, at 8:13 AM, Guoye Zhang via swift-evolution <swift-evolution@swift.org> wrote:

On 18 Oct 2016, at 19:17, Guoye Zhang via swift-evolution <swift-evolution@swift.org> wrote:

So what do you think? Can we break C compatibility a bit for better Swift types?

Well it’s not just C compatibility, it’s underlying processor compatibility. And actually, yes, I think C compatibility is vastly more important than being able to make your [Int?] arrays smaller considering that full 2’s complement numbers is what the OS calls and libc calls are expecting.

Yes, that is also the result Joe said of their previous internal discussion. Anyway, I know this is improbable, and I'm just glad that this possibility is considered.

- Guoye
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dave Abrahams) #17

在 2016年10月19日,07:10,Jeremy Pereira <jeremy.j.pereira@googlemail.com> 写道:

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.

For the record, we made no explicit choice to avoid optional integers.
We'd use them wherever it was appropriate.

···

on Wed Oct 19 2016, Guoye Zhang <swift-evolution@swift.org> wrote:

On 18 Oct 2016, at 19:17, Guoye Zhang via swift-evolution <swift-evolution@swift.org> wrote:

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.

So what do you think? Can we break C compatibility a bit for better Swift types?

Well it’s not just C compatibility, it’s underlying processor
compatibility. And actually, yes, I think C compatibility is vastly
more important than being able to make your [Int?] arrays smaller
considering that full 2’s complement numbers is what the OS calls
and libc calls are expecting.

Yes, that is also the result Joe said of their previous internal
discussion. Anyway, I know this is improbable, and I'm just glad that
this possibility is considered.

- Guoye
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
-Dave


(Dave Abrahams) #18

在 2016年10月19日,07:10,Jeremy Pereira <jeremy.j.pereira@googlemail.com> 写道:

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,

For the record, the interface of the stdlib is not 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.

That's not true; we made several implementation changes based on that
extra space. We never felt there was a good reason to consider it in
making API choices, though.

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?

Yes, that's the core of the issue.

···

on Wed Oct 19 2016, Kevin Nattinger <swift-evolution@swift.org> wrote:

On Oct 19, 2016, at 8:13 AM, Guoye Zhang via swift-evolution <swift-evolution@swift.org> wrote:

On 18 Oct 2016, at 19:17, Guoye Zhang via swift-evolution <swift-evolution@swift.org> wrote:

So what do you think? Can we break C compatibility a bit for better Swift types?

Well it’s not just C compatibility, it’s underlying processor
compatibility. And actually, yes, I think C compatibility is vastly
more important than being able to make your [Int?] arrays smaller
considering that full 2’s complement numbers is what the OS calls
and libc calls are expecting.

Yes, that is also the result Joe said of their previous internal
discussion. Anyway, I know this is improbable, and I'm just glad
that this possibility is considered.

- Guoye
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
-Dave


(Alex Blewitt) #19

I've just finished the implementation of Decimal in Foundation on Linux, which provides for a greater (though not unlimited) space of numbers.

https://github.com/apple/swift-corelibs-foundation/pull/687

Alex

···

On 18 Oct 2016, at 20:46, Guoye Zhang via swift-evolution <swift-evolution@swift.org> wrote:

在 2016年10月18日,15:30,David Waite <david@alkaline-solutions.com <mailto:david@alkaline-solutions.com>> 写道:

On Oct 18, 2016, at 12:17 PM, Guoye Zhang via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
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.

There are two ways to do this (using Int8 for example)
1. 0xFF reserved to mean nil. As this normally means -1, all negative numbers now use complements rather than two’s complement form. This breaks a lot of binary math.

2. 0x80 reserved to mean nil. This is normally -128. Overflow would have to be modified in order to support this (otherwise, 127 + 1 == nil). bit padding no longer works (0x80 would expand to 0xFF80 for a Int16 with bit padding, not 0x8000)

Yes, 0x80 is better for arithmetic, checking for nil might be slower.

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.

As the appropriate integer minimum value may already be in use in C or Objective C code, I believe you would need to define a new integer types to support this sort of constrained type.

Where I would see something like this be most appropriate would be for supporting a “BigNumber” type in the language, preferably as the default integer type. Ruby does this for example with Fixnum/Bignum - all values in Ruby are actually tagged pointers (where the lower bits are set to cause invalid alignment of a pointer in order to indicate it is a special case immediate value). So if the lowest bit is set, the value is a FixNum integer with a lower max/higher min than a traditional integer. On overflow, the value is promoted to be a BigNum, which is a reference to an arbitrary sized integer on the heap.

-DW

I would also like to see big number some day.


(Guoye Zhang) #20

在 2016年10月19日,07:10,Jeremy Pereira <jeremy.j.pereira@googlemail.com> 写道:

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 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.

So what do you think? Can we break C compatibility a bit for better Swift types?

Well it’s not just C compatibility, it’s underlying processor compatibility. And actually, yes, I think C compatibility is vastly more important than being able to make your [Int?] arrays smaller considering that full 2’s complement numbers is what the OS calls and libc calls are expecting.

Yes, that is also the result Joe said of their previous internal discussion. Anyway, I know this is improbable, and I'm just glad that this possibility is considered.

- Guoye

···

On 18 Oct 2016, at 19:17, Guoye Zhang via swift-evolution <swift-evolution@swift.org> wrote: