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

[David Sweeris]

Sent from my iPhone

> On Oct 20, 2016, at 10:25, Haravikk via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 
>> On 20 Oct 2016, at 15:51, Martin Waitz via swift-evolution <swift-evolution at swift.org> wrote:
>> 
>> Hello,
>> 
>>> 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.
>> 
>> When someone is really interested in fitting an optional integer into one machine word,
>> then the best way would be to use a smaller integer type (e.g. Int32 instead of Int64).
>> These also can be mapped well into Enums (a single reserved value does not help at all here).
>> 
>> There are some almost 64-bit integers (Builtin.Int60 .. Builtin.Int63).
>> Maybe something like this could also be provided for normal use?
> 
> I mentioned earlier, but it'd be nice to see the ability to specify arbitrary width integers up to the word size. I myself have a type where I could more efficiently use a 7-bit integer, to offset the extra bit for an optional, but currently have to just use a byte (or else use some kind of awkward trickery). Presumably all of the weird builtin sizes are implemented somehow to as 64-bit operations, it's just the size that differs.
> 
> I'm not very knowledgeable on the subject though, so I'm not sure if I'd be the best person to write up a proposal, though I could always keep it high level.

Conceptually, if we ever get around to allowing literals as generic parameters and default values for generic parameters, I don't think it would be too hard to write something like
    struct Int<Width: IntegerLiteral = 64> {...}
and have it generally perform as well as `Int` does now, just by sign-extending the bits to the next available CPU-native size when the value is loaded from memory. The exception is that if `Width` isn't a power of two (and >= 8) we'd have to do our own overflow checking, since CPUs only handle 8/16/32/64-bit ints. I *think* this only has to be done when the value is stored back into system memory... If the value stays overflown, it'd be caught when stored back to RAM, if it comes back down it'll have the correct answer despite temporarily needing a extra few bits (kinda like 80-bit floats), and if it overflows the native CPU type we haven't lost anything over the current approach. I haven't given it more thought than it took to write that out, though... I could easily be missing something (the location of the overflow exception, for example, could be relatively distant from where the "fauxverflow" happened... annoying for debuggers, but I don't think it matters once the code is working).

Personally, I'd be in favor of a note in the docs indicating that there's a slight speed hit from using non-"powers of two" widths, and letting develop decide if it's more important for them to prioritize memory use over absolute performance. Especially since one of the big hurdles of performance-critical is waiting on RAM anyway.

On a purely speculative note, the overflow-checking penalty would go away if CPUs get hardware support for oddly sized ints. Some of Intels newer CPUs (starting with Sky Lake's predecessor, IIRC) have instructions specifically to speed up BigNums, so I don't think it's so "out there" to think they might start including instructions for "LittleNums"

- Dave Sweeris