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

[Haravikk]

Personally I prefer the way Optionals currently work (add one bit), but I think a better compromise would be the ability to specify arbitrary width integers.

For example, I have a type that stores an optional (so 1-bit overhead) and I want to store less than a byte of extra data; if I could specify a 7-bit integer then I could limit overhead to a single byte, but currently cannot (at least, not without using single Bools which I don't want to do.


For collections there may be other options; for example, storing the optionality of values in a separate bitmap, which would reduce memory overhead, perhaps types could be added that can do this? For storing lots of optionals this would be more efficient on memory, with a slight overhead for double optionality checking. Here's a quick example of what I mean:

struct OptionalArray<T> : Collection {
    var values:[T] = [], bitmap:[Bool] = [], defaultValue:T

    init(defaultValue:T) { self.defaultValue = defaultValue }
    init<S:Sequence>(_ theElements:S, defaultValue:T) where S.Iterator.Element == T? {
        self.defaultValue = defaultValue

        self.values.reserveCapacity(theElements.underestimatedCount)
        self.bitmap.reserveCapacity(theElements.underestimatedCount)

        for eachElement in theElements {
            self.values.append(eachElement ?? defaultValue)
            self.bitmap.append(eachElement != nil)
        }
    }

    var count:Int { return self.values.count }

    var startIndex:Int { return self.values.startIndex }
    var endIndex:Int { return self.values.endIndex }

    func formIndex(after i:inout Int) { self.values.formIndex(after: &i) }
    func index(after i:Int) -> Int { return self.values.index(after: i) }

    subscript(index:Int) -> T? {
        get { return self.bitmap[index] ? self.values[index] : nil }
        set { self.values[index] = newValue ?? self.defaultValue }
    }
}

You could easily adapt this to store optionality using a default value that's unlikely to occur, like so:

struct OptionalArrayAlt<T:Equatable> : Collection {
    var values:[T] = [], defaultValue:T

    init(defaultValue:T) { self.defaultValue = defaultValue }
    init<S:Sequence>(_ theElements:S, defaultValue:T) where S.Iterator.Element == T? {
        self.defaultValue = defaultValue
        values.reserveCapacity(theElements.underestimatedCount)
        self.values = theElements.map { return $0 ?? defaultValue }
    }

    var count:Int { return self.values.count }

    var startIndex:Int { return self.values.startIndex }
    var endIndex:Int { return self.values.endIndex }

    func formIndex(after i:inout Int) { self.values.formIndex(after: &i) }
    func index(after i:Int) -> Int { return self.values.index(after: i) }

    subscript(index:Int) -> T? {
        get { let value = self.values[index]; return value == self.defaultValue ? value : nil }
        set { self.values[index] = newValue ?? self.defaultValue }
    }
}

With the caveat that you either can't store values equal to defaultValue (they become nil) or add an assertion/error if that value is stored.

But yeah, I don't think that rolling out the idea to all optionals is a good idea; the biggest gains will be had in collections, so any efforts should be focused there IMO, and on making custom types align better if possible.
> On 18 Oct 2016, at 21:32, Jean-Daniel via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 
>> Le 18 oct. 2016 à 21:09, Charlie Monroe via swift-evolution <swift-evolution at swift.org> a écrit :
>> 
>> 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.
> 
> 
>> 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 at 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 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,
>>> 
>>> 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- at 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 at swift.org
>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>> 
>>> _______________________________________________
>>> swift-evolution mailing list
>>> swift-evolution at swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>> 
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20161018/b5e0e5a7/attachment.html>