[Pitch] Remove bit shift traps


(Patrick Pijnappel) #1

Currently, bit shifting with an amount greater than or equal to the size of
the type traps:

func foo(x: Int32) {
  let y = x << 32 // Runtime trap (for any << or >> with amount >= 32)
}

I propose to make this not trap, and just end up with 0 (or ~0 in case of
right-shifting a negative number):

   - Unlike the traps for integer arithmetic and casts, it is obvious what
   a bitshift past the end does as fundamentally the behavior stays the same.
   - If the intention is to make it analogous with multiplication/division
   by 2**n, the checks don't really change anything. Right shift are still
   identical to divisions by 2**n. Left shifts are like multiplication by 2**n
   but with different overflow behavior, which is already the case with the
   current rules (e.g. Int.max << 1 doesn't trap)
   - It could lead to bugs where users expect this to work, e.g. the
   following crashes when the entire buffer is consumed: buffer = buffer <<
   bitsConsumed
   - Bitshift are often used in performance-sensitive code, and with the
   current behavior any non-constant bit shift introduces a branch.


(Greg Parker) #2

Defining large shifts to 0 or ~0 does not improve performance on some architectures. The result of the i386 and x86_64 shift instruction is undefined for shift equal to or larger than the data size. The arm64 shift instruction shifts by (shift_value % data_size). If you want large shifts to return zero on architectures like these then you still need a branch.

···

On Mar 17, 2016, at 10:34 PM, Patrick Pijnappel via swift-evolution <swift-evolution@swift.org> wrote:

Currently, bit shifting with an amount greater than or equal to the size of the type traps:

func foo(x: Int32) {
  let y = x << 32 // Runtime trap (for any << or >> with amount >= 32)
}

I propose to make this not trap, and just end up with 0 (or ~0 in case of right-shifting a negative number):
Unlike the traps for integer arithmetic and casts, it is obvious what a bitshift past the end does as fundamentally the behavior stays the same.
If the intention is to make it analogous with multiplication/division by 2**n, the checks don't really change anything. Right shift are still identical to divisions by 2**n. Left shifts are like multiplication by 2**n but with different overflow behavior, which is already the case with the current rules (e.g. Int.max << 1 doesn't trap)
It could lead to bugs where users expect this to work, e.g. the following crashes when the entire buffer is consumed: buffer = buffer << bitsConsumed
Bitshift are often used in performance-sensitive code, and with the current behavior any non-constant bit shift introduces a branch.

--
Greg Parker gparker@apple.com <mailto:gparker@apple.com> Runtime Wrangler


#3

Since the trap represents a possible mistake, I think it’s better to keep it. However, we could have &<< and &>> operators that return the suggested defaults? This would also be more explicit that there is extra behaviour on the operation (so it may be a tiny bit slower than << and >>).

Behaviour-wise, this &operator would be quite different that the other ones, as it doesn't handle overflow of the result, but an invalid rhs. If the meaning of &operator is that flexible, I think it may be better to use &<< and &>> for the missing rotate operator. I cannot say that I have ever had a use for rotate in high level language, but it have been quite useful in assembly.

Dany

···

Le 18 mars 2016 à 07:03, Haravikk via swift-evolution <swift-evolution@swift.org> a écrit :

On 18 Mar 2016, at 05:34, Patrick Pijnappel via swift-evolution <swift-evolution@swift.org> wrote:

Currently, bit shifting with an amount greater than or equal to the size of the type traps:

func foo(x: Int32) {
  let y = x << 32 // Runtime trap (for any << or >> with amount >= 32)
}

I propose to make this not trap, and just end up with 0 (or ~0 in case of right-shifting a negative number):
Unlike the traps for integer arithmetic and casts, it is obvious what a bitshift past the end does as fundamentally the behavior stays the same.
If the intention is to make it analogous with multiplication/division by 2**n, the checks don't really change anything. Right shift are still identical to divisions by 2**n. Left shifts are like multiplication by 2**n but with different overflow behavior, which is already the case with the current rules (e.g. Int.max << 1 doesn't trap)
It could lead to bugs where users expect this to work, e.g. the following crashes when the entire buffer is consumed: buffer = buffer << bitsConsumed
Bitshift are often used in performance-sensitive code, and with the current behavior any non-constant bit shift introduces a branch.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Haravikk) #4

Since the trap represents a possible mistake, I think it’s better to keep it. However, we could have &<< and &>> operators that return the suggested defaults? This would also be more explicit that there is extra behaviour on the operation (so it may be a tiny bit slower than << and >>).

···

On 18 Mar 2016, at 05:34, Patrick Pijnappel via swift-evolution <swift-evolution@swift.org> wrote:

Currently, bit shifting with an amount greater than or equal to the size of the type traps:

func foo(x: Int32) {
  let y = x << 32 // Runtime trap (for any << or >> with amount >= 32)
}

I propose to make this not trap, and just end up with 0 (or ~0 in case of right-shifting a negative number):
Unlike the traps for integer arithmetic and casts, it is obvious what a bitshift past the end does as fundamentally the behavior stays the same.
If the intention is to make it analogous with multiplication/division by 2**n, the checks don't really change anything. Right shift are still identical to divisions by 2**n. Left shifts are like multiplication by 2**n but with different overflow behavior, which is already the case with the current rules (e.g. Int.max << 1 doesn't trap)
It could lead to bugs where users expect this to work, e.g. the following crashes when the entire buffer is consumed: buffer = buffer << bitsConsumed
Bitshift are often used in performance-sensitive code, and with the current behavior any non-constant bit shift introduces a branch.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Haravikk) #5

Hmm, perhaps, though in some respects overflowing is what the 0 or ~0 represent, as you have shifted a value so far that all of the bits have shifted off the end, just an addition overflows because bits are lost from the end, the difference is that an addition may leave other bit positions filled resulting in the potentially invalid result. Of course you could also argue that every shift is causing overflowing in that sense, so yeah, maybe it isn’t clear enough.

Anyway, it’s an alternative, some other operator could do the same, either way I think that the current trap should remain due to the possibility of catching mistakes; code that can intentionally shift by too many places should have to do-so explicitly by some means IMO, rather than the operators doing this for everything, as it may not be what a programmer wanted to happen as a result of zero could create subtle bugs.

···

On 18 Mar 2016, at 12:10, Dany St-Amant via swift-evolution <swift-evolution@swift.org> wrote:

Le 18 mars 2016 à 07:03, Haravikk via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> a écrit :

Since the trap represents a possible mistake, I think it’s better to keep it. However, we could have &<< and &>> operators that return the suggested defaults? This would also be more explicit that there is extra behaviour on the operation (so it may be a tiny bit slower than << and >>).

Behaviour-wise, this &operator would be quite different that the other ones, as it doesn't handle overflow of the result, but an invalid rhs. If the meaning of &operator is that flexible, I think it may be better to use &<< and &>> for the missing rotate operator. I cannot say that I have ever had a use for rotate in high level language, but it have been quite useful in assembly.


(Patrick Pijnappel) #6

Defining large shifts to 0 or ~0 does not improve performance on some
architectures. The result of the i386 and x86_64 shift instruction is
undefined for shift equal to or larger than the data size. The arm64 shift
instruction shifts by (shift_value % data_size). If you want large shifts
to return zero on architectures like these then you still need a branch.

That's unfortunate. Well at least we not *increasing* the amount of
branches by implementing the behavior. Because I'd argue that from the
user's perspective not trapping would be more sensible.

···

On Fri, Mar 18, 2016 at 5:05 PM, Greg Parker <gparker@apple.com> wrote:

On Mar 17, 2016, at 10:34 PM, Patrick Pijnappel via swift-evolution < > swift-evolution@swift.org> wrote:

Currently, bit shifting with an amount greater than or equal to the size
of the type traps:

func foo(x: Int32) {
  let y = x << 32 // Runtime trap (for any << or >> with amount >= 32)
}

I propose to make this not trap, and just end up with 0 (or ~0 in case of
right-shifting a negative number):

   - Unlike the traps for integer arithmetic and casts, it is obvious
   what a bitshift past the end does as fundamentally the behavior stays the
   same.
   - If the intention is to make it analogous with
   multiplication/division by 2**n, the checks don't really change anything.
   Right shift are still identical to divisions by 2**n. Left shifts are like
   multiplication by 2**n but with different overflow behavior, which is
   already the case with the current rules (e.g. Int.max << 1 doesn't
   trap)
   - It could lead to bugs where users expect this to work, e.g. the
   following crashes when the entire buffer is consumed: buffer = buffer
   << bitsConsumed
   - Bitshift are often used in performance-sensitive code, and with the
   current behavior any non-constant bit shift introduces a branch.

Defining large shifts to 0 or ~0 does not improve performance on some
architectures. The result of the i386 and x86_64 shift instruction is
undefined for shift equal to or larger than the data size. The arm64 shift
instruction shifts by (shift_value % data_size). If you want large shifts
to return zero on architectures like these then you still need a branch.

--
Greg Parker gparker@apple.com Runtime Wrangler


(Dave Abrahams) #7

This is addressed in
https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb
which we intend to propose very soon.

(negative shift amounts work too).

https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L1628

For users who want to be sure they're not paying for any checks, there
is a masking bitshift (&<<, &>>, &<<=, &>>=).

···

on Thu Mar 17 2016, Patrick Pijnappel <swift-evolution@swift.org> wrote:

Currently, bit shifting with an amount greater than or equal to the size of
the type traps:

func foo(x: Int32) {
  let y = x << 32 // Runtime trap (for any << or >> with amount >= 32)
}

I propose to make this not trap, and just end up with 0 (or ~0 in case of
right-shifting a negative number):

   - Unlike the traps for integer arithmetic and casts, it is obvious what
   a bitshift past the end does as fundamentally the behavior stays the same.
   - If the intention is to make it analogous with multiplication/division
   by 2**n, the checks don't really change anything. Right shift are still
   identical to divisions by 2**n. Left shifts are like multiplication by 2**n
   but with different overflow behavior, which is already the case with the
   current rules (e.g. Int.max << 1 doesn't trap)
   - It could lead to bugs where users expect this to work, e.g. the
   following crashes when the entire buffer is consumed: buffer = buffer <<
   bitsConsumed
   - Bitshift are often used in performance-sensitive code, and with the
   current behavior any non-constant bit shift introduces a branch.

--
-Dave


(Patrick Pijnappel) #8

Actually this would increase code size, as you'd need to deal with the
negative case separately :/.

···

On Fri, Mar 18, 2016 at 5:58 PM, Patrick Pijnappel < patrickpijnappel@gmail.com> wrote:

Defining large shifts to 0 or ~0 does not improve performance on some

architectures. The result of the i386 and x86_64 shift instruction is
undefined for shift equal to or larger than the data size. The arm64 shift
instruction shifts by (shift_value % data_size). If you want large shifts
to return zero on architectures like these then you still need a branch.

That's unfortunate. Well at least we not *increasing* the amount of
branches by implementing the behavior. Because I'd argue that from the
user's perspective not trapping would be more sensible.

On Fri, Mar 18, 2016 at 5:05 PM, Greg Parker <gparker@apple.com> wrote:

On Mar 17, 2016, at 10:34 PM, Patrick Pijnappel via swift-evolution < >> swift-evolution@swift.org> wrote:

Currently, bit shifting with an amount greater than or equal to the size
of the type traps:

func foo(x: Int32) {
  let y = x << 32 // Runtime trap (for any << or >> with amount >= 32)
}

I propose to make this not trap, and just end up with 0 (or ~0 in case of
right-shifting a negative number):

   - Unlike the traps for integer arithmetic and casts, it is obvious
   what a bitshift past the end does as fundamentally the behavior stays the
   same.
   - If the intention is to make it analogous with
   multiplication/division by 2**n, the checks don't really change anything.
   Right shift are still identical to divisions by 2**n. Left shifts are like
   multiplication by 2**n but with different overflow behavior, which is
   already the case with the current rules (e.g. Int.max << 1 doesn't
   trap)
   - It could lead to bugs where users expect this to work, e.g. the
   following crashes when the entire buffer is consumed: buffer = buffer
   << bitsConsumed
   - Bitshift are often used in performance-sensitive code, and with the
   current behavior any non-constant bit shift introduces a branch.

Defining large shifts to 0 or ~0 does not improve performance on some
architectures. The result of the i386 and x86_64 shift instruction is
undefined for shift equal to or larger than the data size. The arm64 shift
instruction shifts by (shift_value % data_size). If you want large shifts
to return zero on architectures like these then you still need a branch.

--
Greg Parker gparker@apple.com Runtime Wrangler


(Patrick Pijnappel) #9

Great! Totally forgot to check those, even though I already skimmed them
before ;). Looks like a lot of great improvements in one go!

···

On Tue, Mar 22, 2016 at 9:52 AM, Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:

on Thu Mar 17 2016, Patrick Pijnappel <swift-evolution@swift.org> wrote:

> Currently, bit shifting with an amount greater than or equal to the size
of
> the type traps:
>
> func foo(x: Int32) {
> let y = x << 32 // Runtime trap (for any << or >> with amount >= 32)
> }
>
> I propose to make this not trap, and just end up with 0 (or ~0 in case of
> right-shifting a negative number):
>
> - Unlike the traps for integer arithmetic and casts, it is obvious
what
> a bitshift past the end does as fundamentally the behavior stays the
same.
> - If the intention is to make it analogous with
multiplication/division
> by 2**n, the checks don't really change anything. Right shift are
still
> identical to divisions by 2**n. Left shifts are like multiplication
by 2**n
> but with different overflow behavior, which is already the case with
the
> current rules (e.g. Int.max << 1 doesn't trap)
> - It could lead to bugs where users expect this to work, e.g. the
> following crashes when the entire buffer is consumed: buffer = buffer
<<
> bitsConsumed
> - Bitshift are often used in performance-sensitive code, and with the
> current behavior any non-constant bit shift introduces a branch.

This is addressed in

https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb
which we intend to propose very soon.

(negative shift amounts work too).

https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L1628

For users who want to be sure they're not paying for any checks, there
is a masking bitshift (&<<, &>>, &<<=, &>>=).

--
-Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution