[swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu]

On Fri, Jan 13, 2017 at 7:51 PM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:

> Thanks, that's very helpful. Yes, my question was more directed to those
> situations that can't be optimized away. It's good to know that the maximum
> total cost is an and and a shift, which is what it sounded like but wasn't
> made explicit.


Oy, I misread your reply; the maximum total cost for a _masking_ shift is
two very cheap instructions; the maximum total cost for a _smart_ shift is
potentially higher. I know it's unrealistic, but what will we be looking at
when it comes to this:

```
func foo() -> UInt32 {
    return arc4random() >> arc4random()
}
```


On Fri, Jan 13, 2017 at 17:25 Stephen Canon <scanon at apple.com> wrote:
>
>> > On Jan 13, 2017, at 5:14 PM, Xiaodi Wu via swift-evolution <
>> swift-evolution at swift.org> wrote:
>> >
>> > [Resending to list with original message removed for length.]
>> >
>> > This is fantastic. Glad to see it take shape. Very neat and insightful
>> to have trailingZeros on BinaryInteger but leadingZeros on
>> FixedWidthInteger. A couple of questions on smart shifts: What is the
>> performance penalty as compared to the existing operators? Beyond
>> performance, what are the implications for migrating existing bit twiddling
>> algorithms written in Swift 3?
>>
>> Hi Xiaodi —
>>
>> I don’t want to speak for Max and Dave, but I think I can provide some
>> insight for your questions about shifts.
>>
>> First, the overwhelming majority of shifts have a compile-time-constant
>> RHS. For these cases, there’s no performance change (except that the smart
>> shifts may be able to optimize away the entire expression if the shift is
>> overlarge).
>>
>> For smart shifts with non-constant right-hand sides, the compiler will
>> frequently still be able to prove that the shift count is always positive
>> or negative and less than word size (this handles a lot of the most common
>> cases like normalizing an integer, reading from a bitstream, or shifting
>> words of a bignum); again there’s no performance penalty.
>>
>> In the remaining cases where the compiler cannot bound the right-hand
>> side, there will be some branches present; there may be a few regressions
>> from these cases, but I expect most to be small (and the code
>> simplifications are well worth it).  Users can always use the masking
>> shifts, which lower to single instructions for 32b and 64b integers types
>> on Intel and arm64, and which are at worst an and and a shift (two very
>> cheap instructions) on other architectures.
>>
>> Basically, I expect there to be no perf impact for almost all code, and
>> that the perf impact is relatively easily mitigated when it does occur.
>> This is an easy tradeoff for fully-defined and sensible operator behavior.
>>
>> – Steve
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170114/865d19a4/attachment.html>