Advantages of masking shift operators?

(Martin R) #1

I am trying to understand the possible advantages of the “masking shift operators” (&<< and &>>) over the “normal shift operators” (<< and >>). In SR-6749 it is said that

The goal of the operator, however, is never to have this wrapping behavior happen — it's what you use when you have static knowledge that your shift amount is <= the bitWidth. By masking, you and the compiler can agree that there's no branch needed, so you get slightly faster code without zero branching and zero risk of undefined behavior (which a negative or too large shift would be).

and I can see that they are used a lot in the Swift standard library, for example in UTF8.swift:

  let bits = source._biasedBits &- 0x01010101
  var value = (bits & 0b0_11_1111__0000_0000__0000_0000__0000_0000) &>> 24
  value    |= (bits & 0b0____________11_1111__0000_0000__0000_0000) &>> 10
  value    |= (bits & 0b0_______________________11_1111__0000_0000) &<< 4
  value    |= (bits & 0b0________________________________0000_0111) &<< 18

I have two questions:

  1. What is the “risk of undefined behavior” when using the normal shift operators?

    If I understand BinaryInteger.>>(_:_:) correctly, the behavior of a >> b is defined for all possible values of (signed or unsigned) operands, therefore I do not see where undefined behavior could occur.

  2. Why is it advantageous to use the masking shift operator if the shift amount is a literal constant (less than the bit width)?

    In the above example, the left operand is an UInt32 and the shift amounts are literal constants less than 32, so it is known at compile time that the shift amounts are less than the bit width. Why is it advantageous here to use the masking shift operators? Would the compiler (possibly) create branching code if, for example, &>>24 is replaced by >>24?

Thanks for any insight,
Martin

3 Likes
(Jordan Rose) #2

Neither kind of shift has undefined behavior; the two operators just take different approaches to handling out-of-range shift amounts:

  • << and >> treat shift amounts greater than the bit width as shifting out all the bits, i.e. producing 0 or -1. They also handle negative shift amounts. As you note, this is called out in the docs.

  • &<< and &>> "mask" their shift amount to be within the valid range for the argument; i.e. "64" on a 64-bit value is treated as a shift of 0, and "33" on a 16-bit value is treated as a shift of 1. Negative numbers also get this treatment, so "-1" on a 16-bit value becomes 15. The use of the term "mask" here is a bit of a misnomer since a bitmask operation only works for integer types whose bit-width is a power of two, but I think we decided it was better to have something slightly incorrect than invent a new notation family.

(The reference to undefined behavior comes from C, where shift amounts outside of 0..<BIT_WIDTH are considered undefined.)

The former, <<, is what we think someone would usually expect, but it means testing the value beforehand. So the latter, &<< is also available to do something slightly faster. With constant values, there "shouldn't" be any performance difference in which one you use, but in practice the compiler has an easier time reasoning about &>> than >>.

@scanon, confirm/refute?

9 Likes
(Steve Canon) #3

Everything Jordan says is correct.

  • All shifts in Swift are always fully defined.
  • The "masking" shifts shift by rhs mod lhs.bitWidth. That happens to correspond to mask for all power-of-two sized integer types, but if there were, say, an Int7 type, the "masking" shifts would mod the count into the range 0 ..< 7.
  • In practice, for in-range constants there should not be any difference.
  • I expect @Michael_Ilseman used &>> and &<< here out of an abundance of caution.
8 Likes
(Michael Ilseman) #4

That snippet is @dabrahams code. I also tend to put them on everything, even for constants, to reduce last-minute surprises and reduce cognitive load for the performance skeptic.

2 Likes