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

[Stephen Canon]

> 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