Proposal: Explicit shift operations for C++

[Matthew Fioravante]

As suggested in the other thread about 2's complement, and also lifted from my previous proposal N3864. I've written a small proposal to add explicit shift operations to the standard library.

Should be pretty self explanatory.

https://github.com/fmatthew5876/stdcxx-bitops/blob/master/proposal/shift.md

Please let me know if you have any objections or feedback.

Thanks!

[John McFarlane]

Hi Matthew,

I am interested in a similar feature specifically related to arithmetic scaling (although I'm not completely certain of its necessity yet). However, it has a number of extra requirements. Notably, I'd like for users to be able to specialize scaling for their own, user-defined types. I'd also like to consider powers other than two.

The upshot of these two requirements would be classes in the style of std::hash with an additional parameter specifying the base. For example:

// standard

template<Integral T, int Base>

struct shar;

// user-defined

template<>

struct shar<MyIntegralType, 2> {
  constexpr MyIntegralType operator()(const MyIntegralType& x, int s);
}

How palatable does all this sound? I'm in two minds whether this should be something to consider in your proposal or merely something that would depend upon it for standard specializations involving built-in types.

Cheers,

John

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/95e94b53-d65a-4a81-8209-9ec5322d09d7%40isocpp.org.

[Matthew Fioravante]

On Tuesday, October 11, 2016 at 12:11:06 PM UTC-5, John McFarlane wrote:

Hi Matthew,

I am interested in a similar feature specifically related to arithmetic scaling (although I'm not completely certain of its necessity yet). However, it has a number of extra requirements. Notably, I'd like for users to be able to specialize scaling for their own, user-defined types. I'd also like to consider powers other than two.

The upshot of these two requirements would be classes in the style of std::hash with an additional parameter specifying the base. For example:

// standard

template<Integral T, int Base>

struct shar;

// user-defined

template<>

struct shar<MyIntegralType, 2> {
  constexpr MyIntegralType operator()(const MyIntegralType& x, int s);
}

How palatable does all this sound? I'm in two minds whether this should be something to consider in your proposal or merely something that would depend upon it for standard specializations involving built-in types.

Hi John,

The purpose of my proposal is just to give us portable access to basic shift operations provided by the processor. I think something like what you're proposing could be done separately as a later step and implementation of such could possibly be built using mine.

Adding more genericity adds complexity and you yourself have admitted that you aren't even sure of its necessity. What would likely end up happening is the combined proposal gets shot down because of all of these questionable extra features. I've made this mistake in the past with proposals trying to get too fancy by adding too many things and the half considered extras ended up killing the most important part which was the well reasoned about core feature.

As it stands now I believe what I've proposed is extremely simple and easy to reason about. The 80/20 principle applies and this will solve 80% of the problems related to shifts, with more specialized and generic use cases left to the users or later proposals.

[John McFarlane]

That makes a lot of sense. Although, I'm not sure it would be possible to build upon the functionality of your arithmetic variants without a base parameter.

For a little background, this is in relation to fixed-point proposal, P0037R2, which has gained some interest from the financial sector who have a desire for decimal fixed-point arithmetic. They may separately be interested in a decimal option with your functions.

--

You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.

To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/5b7d2c28-ffed-44f5-b19d-2d906f57a09a%40isocpp.org.

[Andrey Semashev]

I'm interested in this proposal and I have a few suggestions.

1. I think it would be better to reverse the letters that denote
left/right and logical/arithmetic shift. I.e. rename shlr -> shrl and
shar -> shra.

2. With the above naming change, add a new function shr(), which will be
equivalent to shra for signed types and shrl for unsigned. I think, this
is the "natural" shift that most developers expect and compilers
implement for operator>>. I would even say, this would be the most
useful shift function.

3. With the above naming change, it might be reasonable to also rename
shll -> shl since there is no arithmetic left shift anyway.

4. Use unsigned int for bit count. Yes, I know the committee members
announced the preference for signed types, but using a signed type and
immediately saying it must never have negative values is just nonsense, IMO.

[Matthew Fioravante]

Hi Andrey

On Tuesday, October 18, 2016 at 12:16:59 PM UTC-5, Andrey Semashev wrote:

On 10/11/16 07:50, Matthew Fioravante wrote:
> As suggested in the other thread about 2's complement, and also lifted
> from my previous proposal N3864. I've written a small proposal to add
> explicit shift operations to the standard library.
>
> Should be pretty self explanatory.
>
> https://github.com/fmatthew5876/stdcxx-bitops/blob/master/proposal/shift.md
>
> Please let me know if you have any objections or feedback.

I'm interested in this proposal and I have a few suggestions.

1. I think it would be better to reverse the letters that denote
left/right and logical/arithmetic shift. I.e. rename shlr -> shrl and
shar -> shra.

I like your names better. We usually say SHift Right Arithmetic instead of SHift Arithemetic Right. 

2. With the above naming change, add a new function shr(), which will be
equivalent to shra for signed types and shrl for unsigned. I think, this
is the "natural" shift that most developers expect and compilers
implement for operator>>. I would even say, this would be the most
useful shift function. 

I'm going to stay away from this one for now. We already have a function in the standard, its called operator>>(). See my other post about that. 

It comes down to a question of whether we fix operator>>() or leave it broken and adopt a replacement like shr(). I'm worried that by introducing such a function the proposal gets dragged down into that discussion and rejected entirely.

 

3. With the above naming change, it might be reasonable to also rename
shll -> shl since there is no arithmetic left shift anyway.

Seems reasonable to me. Although shl() is actually redundant so maybe I should remove it. We only really need the right shifts.

 

4. Use unsigned int for bit count. Yes, I know the committee members
announced the preference for signed types, but using a signed type and
immediately saying it must never have negative values is just nonsense, IMO.

Thats a philosophical question. Honestly I really don't care whether its signed or unsigned.  

[Andrey Semashev]

On 10/27/16 03:18, Matthew Fioravante wrote:
> Hi Andrey
>
> On Tuesday, October 18, 2016 at 12:16:59 PM UTC-5, Andrey Semashev wrote:
>
> 2. With the above naming change, add a new function shr(), which
> will be
> equivalent to shra for signed types and shrl for unsigned. I think,
> this
> is the "natural" shift that most developers expect and compilers
> implement for operator>>. I would even say, this would be the most
> useful shift function.
>
> I'm going to stay away from this one for now. We already have a function
> in the standard, its called operator>>(). See my other post about that.
>
> It comes down to a question of whether we fix operator>>() or leave it
> broken and adopt a replacement like shr(). I'm worried that by
> introducing such a function the proposal gets dragged down into that
> discussion and rejected entirely.

If we fix the operator>> so that it is portably defined for all inputs
then none of these functions are needed. If we don't, then shr() would
be useful, extremely so in generic code.

The problem I see in fixing operator>> is that I find a hard time seeing
it fixed without also requiring two's complement representation of
signed integers. Defining the operator only iff integers are two's
complement seems like a half solution to me. I mean, how should
programmers write their code portably if this change is made?

Defining operator>> in terms of bit patterns might be more viable, but
there's the question of trap representations. What if the shift
operation results in a trap representation?

Really, I think signed integers in C++ are doomed as there are currently
too many gotchas around them. C++ is a hostage of its own portability
here. I'm thinking about writing a signed facade around unsigned
integers that would just remove all "undefined" cases and never using
signed integers ever again. That facade would have two's complement
integer representation and the arithmetic right shift, as expected. I
find it embarrassing that a full-blown library solution is needed for
such a simple and intrinsic thing as integers.

> 3. With the above naming change, it might be reasonable to also rename
> shll -> shl since there is no arithmetic left shift anyway.
>
> Seems reasonable to me. Although shl() is actually redundant so maybe I
> should remove it. We only really need the right shifts.

I would prefer it there, for the completeness sake.

> 4. Use unsigned int for bit count. Yes, I know the committee members
> announced the preference for signed types, but using a signed type and
> immediately saying it must never have negative values is just
> nonsense, IMO.
>
> Thats a philosophical question. Honestly I really don't care whether its
> signed or unsigned.

For me, that is a question of interface clarity. If the function does
not handle negative values, don't provide a way to provide them.

[Thiago Macieira]

On quarta-feira, 26 de outubro de 2016 17:18:39 PDT Matthew Fioravante wrote:
> > 1. I think it would be better to reverse the letters that denote
> > left/right and logical/arithmetic shift. I.e. rename shlr -> shrl and
> > shar -> shra.
>
> I like your names better. We usually say SHift Right Arithmetic instead of
> SHift Arithemetic Right.

Another option is to move to the beginning: Logical Shift Right (LSHR or LSR),
Arithmetic Shift Left (ASL), etc. This is what ARM assembly does.

Any way you choose, you're going to find an assembly with different mnemonics.
It's a matter of how many people you're going displease. Just try to choose
something that doesn't cause confusion: it should be unambiguous whether the
shift is to the left or to the right.

> > 3. With the above naming change, it might be reasonable to also rename
> > shll -> shl since there is no arithmetic left shift anyway.
>
> Seems reasonable to me. Although shl() is actually redundant so maybe I
> should remove it. We only really need the right shifts.

Actually, no. Shifting left into the sign bit of a signed integer is undefined.
So this function may still be useful.

> > 4. Use unsigned int for bit count. Yes, I know the committee members
> > announced the preference for signed types, but using a signed type and
> > immediately saying it must never have negative values is just nonsense,
> > IMO.
>
> Thats a philosophical question. Honestly I really don't care whether its
> signed or unsigned.

It might be useful to shift in the other direction if the count is negative.
That would imply a difference in arithmetic and logical shifts left, since
they could go right too.

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center

[Matthew Fioravante]

On Thursday, October 27, 2016 at 4:31:30 PM UTC-5, Thiago Macieira wrote:

On quarta-feira, 26 de outubro de 2016 17:18:39 PDT Matthew Fioravante wrote:
> > 1. I think it would be better to reverse the letters that denote
> > left/right and logical/arithmetic shift. I.e. rename shlr -> shrl and
> > shar -> shra.
>
> I like your names better. We usually say SHift Right Arithmetic instead of
> SHift Arithemetic Right.

Another option is to move to the beginning: Logical Shift Right (LSHR or LSR),
Arithmetic Shift Left (ASL), etc. This is what ARM assembly does.

Any way you choose, you're going to find an assembly with different mnemonics.
It's a matter of how many people you're going displease. Just try to choose
something that doesn't cause confusion: it should be unambiguous whether the
shift is to the left or to the right.

> > 3. With the above naming change, it might be reasonable to also rename
> > shll -> shl since there is no arithmetic left shift anyway.
>
> Seems reasonable to me. Although shl() is actually redundant so maybe I
> should remove it. We only really need the right shifts.

Actually, no. Shifting left into the sign bit of a signed integer is undefined.
So this function may still be useful.

Interesting, I wasn't aware of this one. I'll add this to the paper.

 

> > 4. Use unsigned int for bit count. Yes, I know the committee members
> > announced the preference for signed types, but using a signed type and
> > immediately saying it must never have negative values is just nonsense,
> > IMO.
>
> Thats a philosophical question. Honestly I really don't care whether its
> signed or unsigned.

It might be useful to shift in the other direction if the count is negative.
That would imply a difference in arithmetic and logical shifts left, since
they could go right too.

This is a direction I don't want to go. These are supposed to be fast assembly mnemonics. If we add support for negative shifts and the user passes in a runtime value for the shift amount then now we have a branch.

Also It seems silly to have right shift and left shift functions when you're using a signed value to determine shift direction. Do away with directionality in the name and just have functions called arith_shift(), log_shift(), and rot_shift() which shift left for negative and right for positive.

[Thiago Macieira]

Em quinta-feira, 27 de outubro de 2016, às 14:41:03 PDT, Matthew Fioravante

> > Actually, no. Shifting left into the sign bit of a signed integer is
> > undefined.
> > So this function may still be useful.
>
> Interesting, I wasn't aware of this one. I'll add this to the paper.

Subtle wording of 5.9 [expr.shift]/2, that says:

"Otherwise, if E1 has a signed type and non-negative value, and E1 × 2^E2 is
representable in the corresponding unsigned type of the result type, then that
value, converted to the result type, is the resulting value; otherwise, the
behavior is undefined."

1 << 31 implies 1 * 2^31 = 2147483648, which is not representable in int,
therefore it's undefined to shift into the sign bit.

int(1U << 31) is implementation-defined.

> > It might be useful to shift in the other direction if the count is
> > negative.
> > That would imply a difference in arithmetic and logical shifts left, since
> > they could go right too.
>
> This is a direction I don't want to go. These are supposed to be fast
> assembly mnemonics. If we add support for negative shifts and the user
> passes in a runtime value for the shift amount then now we have a branch.

Fair enough, that's a good argument.

Sorry for missing the beginning of the discussion, but what is the plan for
when the shift count is larger than the type's size? That's UB in the standard
for the built-in operators.

[Chris Hallock]

Subtle wording of 5.9 [expr.shift]/2, that says:

"Otherwise, if E1 has a signed type and non-negative value, and E1 × 2^E2 is
representable in the corresponding unsigned type of the result type, then that
value, converted to the result type, is the resulting value; otherwise, the
behavior is undefined."

1 << 31 implies 1 * 2^31 = 2147483648, which is not representable in int,
therefore it's undefined to shift into the sign bit.

To nitpick, you can (since C++14) left-shift into the sign bit, but not past it. However, the resulting value is implementation-defined. Assuming 32-bit ints, 1 << 31 is equivalent to static_cast<int>(2147483648) because 1 * 2^31 "is representable in the corresponding unsigned type of the result type" (i.e. unsigned int).

[Matthew Fioravante]

On Thursday, October 27, 2016 at 7:53:29 PM UTC-5, Thiago Macieira wrote:

Sorry for missing the beginning of the discussion, but what is the plan for
when the shift count is larger than the type's size? That's UB in the standard
for the built-in operators.

Same undefined behavior for portable maximal efficiency. Think of this working exactly like operator>>() but with well defined semantics for the high bits of a right shift.

[Thiago Macieira]

Em quinta-feira, 27 de outubro de 2016, às 19:06:56 PDT, Chris Hallock
escreveu:

> > Subtle wording of 5.9 [expr.shift]/2, that says:
> >
> > "Otherwise, if E1 has a signed type and non-negative value, and E1 × 2^E2
> > is
> > representable in the corresponding unsigned type of the result type, then
> > that
> > value, converted to the result type, is the resulting value; otherwise,
> > the
> > behavior is undefined."
> >
> > 1 << 31 implies 1 * 2^31 = 2147483648, which is not representable in int,
> > therefore it's undefined to shift into the sign bit.
>
> To nitpick, you can (since C++14

> <http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#1457>)

> left-shift into the sign bit, but not past it. However, the resulting value
> is implementation-defined. Assuming 32-bit ints, 1 << 31 is equivalent to
> static_cast<int>(2147483648) because 1 * 2^31 "is representable in the
> corresponding unsigned type of the result type" (i.e. unsigned int).

Hmm... you're actually right. The resolution of CWG1457 is already in the text
I quoted.

So it isn't UB, it's implementation-defined behaviour.

[Matthew Fioravante]

On Thursday, October 27, 2016 at 9:47:23 PM UTC-5, Thiago Macieira wrote:

Em quinta-feira, 27 de outubro de 2016, às 19:06:56 PDT, Chris Hallock
escreveu:
> > Subtle wording of 5.9 [expr.shift]/2, that says:
> >
> > "Otherwise, if E1 has a signed type and non-negative value, and E1 × 2^E2
> > is
> > representable in the corresponding unsigned type of the result type, then
> > that
> > value, converted to the result type, is the resulting value; otherwise,
> > the
> > behavior is undefined."
> >
> > 1 << 31 implies 1 * 2^31 = 2147483648, which is not representable in int,
> > therefore it's undefined to shift into the sign bit.
>
> To nitpick, you can (since C++14
> <http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#1457>)
> left-shift into the sign bit, but not past it. However, the resulting value
> is implementation-defined. Assuming 32-bit ints, 1 << 31 is equivalent to
> static_cast<int>(2147483648) because 1 * 2^31 "is representable in the
> corresponding unsigned type of the result type" (i.e. unsigned int).

Hmm... you're actually right. The resolution of CWG1457 is already in the text
I quoted.

So it isn't UB, it's implementation-defined behaviour.

Does anyone else find it kind of sad that all of us who could be considered expert level C++ programmers still don't know little caveat rules like this?? How is there any hope for novices.. 

[Andrey Semashev]

On 10/28/16 05:06, Chris Hallock wrote:
> Subtle wording of 5.9 [expr.shift]/2, that says:
>
> "Otherwise, if E1 has a signed type and non-negative value, and E1 ×
> 2^E2 is
> representable in the corresponding unsigned type of the result type,
> then that
> value, converted to the result type, is the resulting value;
> otherwise, the
> behavior is undefined."
>
> 1 << 31 implies 1 * 2^31 = 2147483648, which is not representable in
> int,
> therefore it's undefined to shift into the sign bit.
>
>
> To nitpick, you can (since C++14

> <http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#1457>)

> left-shift into the sign bit, but not past it. However, the resulting
> value is implementation-defined. Assuming 32-bit ints, 1 << 31 is
> equivalent to static_cast<int>(2147483648) because 1 * 2^31 "is
> representable in the corresponding unsigned type of the result type"
> (i.e. unsigned int).

<nitpick> Except that static_cast<int>(2147483648) overflows, which is
UB. Assuming int is 32-bit two's complement, it should be -2147483648.
</nitpick>

[Chris Hallock]

Nitpick parry: it's implementation-defined, not UB. The static_cast finds an implicit conversion sequence ([expr.static.cast]/4) from the type of the literal, which is either long or long long ([lex.icon]/2), to int. The implicit conversion sequence consists of an integral conversion, which is implementation-defined if the input doesn't fit in a signed result type ([conv.integral]/3).

[Thiago Macieira]

Em quinta-feira, 27 de outubro de 2016, às 20:17:10 PDT, Matthew Fioravante
escreveu:

> > Hmm... you're actually right. The resolution of CWG1457 is already in the
> > text
> > I quoted.
> >
> > So it isn't UB, it's implementation-defined behaviour.
>
> Does anyone else find it kind of sad that all of us who could be considered
> expert level C++ programmers still don't know little caveat rules like
> this?? How is there any hope for novices..

Well, it used to be UB. I searched for the text that was making it so, copy &
pasted it. I just failed to re-read it and notice that it had changed, making
it IDB instead of UB.

[Bo Persson]

The difference is extremely small.

If it is UB, an implementation is still *allowed* to document some
reasonable behavior. Now it is *required* to document it, but the
behavior might still be blow-up (a hardware trap).

So for any code you want to be portable, you will still have to read the
documentation for every possible compiler. Just like it was before.


Bo Persson