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

[Dave Abrahams]

on Sat Jan 14 2017, Xiaodi Wu <swift-evolution at swift.org> wrote:

> 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()
> }
> ```

This is a shift by an unsigned quantity, so we know it's positive.  It
should optimize down to something like this:

     let _lhs = arc4random(), _rhs = arc4random()
     return _rhs > 31 ? 0 : Builtin.shiftRight(_lhs, _rhs)

> 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
>>
>>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

-- 
-Dave