128 bit integers

[Niall Douglas]

I just posted the following to the WG14 reflector, copying it here for some std-proposals extra feedback.

Niall

--- cut ---

Dear WG14,

As you may know, C++ is busy adding variable bit number support to itself (`int<128>`, `uint<256>` etc), but what I find myself yearning for is a simple, ordinary, builtin 128-bit signed and unsigned integer type which acts exactly like a normal integer, just bigger.

1. Would WG14 approve of adding builtin 128-bit signed and unsigned integer types to C22? If so, I can write the paper.

2. If so, what would be the preferred choice of naming? Some choices:

  a) Leaving the type unspecified, and instead say that `uint128_t` and `int128_t` will typedef to whatever it is.

  b) `unsigned long long long` and `long long long`.

  c) `_UInt128` and `_Int128`.

In terms of prior art, GCC and clang already implement 128-bit integers (https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html) and have done so for many years now. There is definitely an established user base, surprise ought to be very limited.

Niall

[Thiago Macieira]

On Tuesday, 2 October 2018 01:09:27 PDT Niall Douglas wrote:
> In terms of prior art, GCC and clang already implement 128-bit integers
> (https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html) and have done so
> for many years now. There is definitely an established user base, surprise
> ought to be very limited.

Note that 128-bit integers in GCC and Clang are only supported on 64-bit
architectures. That's probably because it's practically the same code that
they need for 32-bit platforms to support 64-bit integers, just on a platform
with a wider register.

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

[Alberto Barbati]

Hi Niall,

Since you are asking specifically for 128 bit integers, I believe the right choice would be to just add int128_t and uint128_t alias (to unspecified types) into <cstdint>. Since the presence of most of the aliases in that header is already conditionally provided, it should not be a burden to implementations. The only problem in this area is that we should consider deprecating intmax_t and uintmax_t. Other discussions have pointed that it was a bad idea to introduce them, since an implementation can’t change its definition without potentially breaking binary compatibility.

Just my two eurocent,

Alberto

[Brian Bi]

Why does it matter whether it's built-in? What would uint128_t do that uint<128> wouldn't?

Also can someone link me to the proposal that defines uint<128> and friends? Thanks

--
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-proposal...@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/4111d349-b11d-45a4-aa06-d871d8efb20e%40isocpp.org.

--

Brian Bi

[Myriachan]

One issue with the current C++ Standard is that it does not allow cstdint to define anything other than 8/16/32/64/max, whereas the C Standard does.  So an implementation cannot currently define a std::uint128_t but could define a uint128_t.

The C Standard mentions the possibility of non-power-of-2 sizes, calling out uint24_t as an example.  (Trivia: uint24_t would actually be a sensible type on an eZ80.)

The C++ Standard ought to do the same as the C Standard.  We also should get a proposal for std::uint_t<N> and such.

A separate problem with something like uint128_t is that it breaks the definition of uintmax_t.  We can't change uintmax_t on an existing platform, because that's a breaking change.  And if uint128_t exists and is larger than uintmax_t, what does that mean?

Melissa

[inkwizyt...@gmail.com]

On Wednesday, October 3, 2018 at 9:31:32 PM UTC+2, Myriachan wrote:

One issue with the current C++ Standard is that it does not allow cstdint to define anything other than 8/16/32/64/max, whereas the C Standard does.  So an implementation cannot currently define a std::uint128_t but could define a uint128_t.

The C Standard mentions the possibility of non-power-of-2 sizes, calling out uint24_t as an example.  (Trivia: uint24_t would actually be a sensible type on an eZ80.)

The C++ Standard ought to do the same as the C Standard.  We also should get a proposal for std::uint_t<N> and such.

A separate problem with something like uint128_t is that it breaks the definition of uintmax_t.  We can't change uintmax_t on an existing platform, because that's a breaking change.  And if uint128_t exists and is larger than uintmax_t, what does that mean?

Its not native size? We could redefine it as biggest that can be handle by CPU. For current implementation it will stay same but in new it could be less than uint64.

[Niall Douglas]

Since you are asking specifically for 128 bit integers, I believe the right choice would be to just add int128_t and uint128_t alias (to unspecified types) into <cstdint>. Since the presence of most of the aliases in that header is already conditionally provided, it should not be a burden to implementations. The only problem in this area is that we should consider deprecating intmax_t and uintmax_t. Other discussions have pointed that it was a bad idea to introduce them, since an implementation can’t change its definition without potentially breaking binary compatibility.

Thanks everybody for your feedback.

The discussion on WG14 has been considerably more detailed, but as a reasonable summary:

1. There is widespread consensus that intmax_t et al should reflect the largest basic integer type. And therefore it wouldn't change.
   
2. I'm going to propose that C implements http://wg21.link/P0539 A Proposal to add wide_int Template Class directly into the C language.
3. Probably a dramatically simplified subset of the proposed syntax in http://wg21.link/P0989 Standardizing Extended Integers would be proposed.

And we shall see what happens!

Niall

[Barry Revzin]

On Thursday, October 4, 2018 at 3:06:15 AM UTC-5, Niall Douglas wrote:

1. There is widespread consensus that intmax_t et al should reflect the largest basic integer type. And therefore it wouldn't change.
   
2. I'm going to propose that C implements http://wg21.link/P0539 A Proposal to add wide_int Template Class directly into the C language.
3. Probably a dramatically simplified subset of the proposed syntax in http://wg21.link/P0989 Standardizing Extended Integers would be proposed.

I just want to point out that P0989 is an April Fool's joke. 

Cue Tony strenuously denying this in 3... 2... 

[Niall Douglas]

I had noticed the first of April date, and most of the proposal is obviously terrible. However there are some good ideas in there, and I'm going to propose them for standardisation. Niall

[Tony V E]

April fool's?! 

Pure coincidence I say!

Don't forget to consider the rebuttal, http://wg21.link/p0990

Sent from my BlackBerry portable Babbage Device

From: Barry Revzin Sent: Thursday, October 4, 2018 8:34 AM To: ISO C++ Standard - Future Proposals Reply To: std-pr...@isocpp.org Subject: [std-proposals] Re: 128 bit integers

--

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-proposal...@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/618c6701-abd5-4caa-8917-c1a15a5840d5%40isocpp.org.

[John McFarlane]

If you're collecting related papers, you might want to mention P0539 which is a 100% serious paper.

On Thu, Oct 4, 2018, 13:38 Niall Douglas <nialldo...@gmail.com> wrote:

I had noticed the first of April date, and most of the proposal is obviously terrible. However there are some good ideas in there, and I'm going to propose them for standardisation. Niall

--
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-proposal...@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/869310a4-67f1-4594-8157-e33ae7d7e0f3%40isocpp.org.

[Niall Douglas]

On Friday, October 5, 2018 at 2:18:30 PM UTC+1, John McFarlane wrote:

If you're collecting related papers, you might want to mention P0539 which is a 100% serious paper.

My C proposal paper is actually a direct response to P0539, and it discusses what I think are showstopper problems with that paper, and why we need a language solution instead. As I wrote:

WG21 is currently proceeding down a library-based path for implementing
extended precision integers (https://wg21.link/P0539), but my issue with
it is that it is very hard to get the compiler to predictably generate
optimal code with a library only solution. In particular, compilers fail
to spot when they can use carry-adds or carry-multiplies from hints
provided by generic C or C++ code. This is why I have become convinced
we need a language based implementation so compilers know exactly what
they are supposed to do. Hence me coming here to WG14.

Current proposal being discussed on the WG14 reflector looks as follows:

1. For any integer type excluding _Bool (char, short, int, long, long long), one may extend it into an extended arithmetic type by annotating it with "_Wide(N)":

    - _Wide(4) int

    - long long _Wide(2)

This simply tells the compiler to emit the add-with-carry or multiply-with-carries instructions necessary to increase the precision of the specified arithmetic type. And before anyone asks, yes it is legal to widen small types:

    - _Wide(2) short (NOT an int)

    - _Wide(4) char (NOT an int)

2. These wide integer types are not integral types, and thus do not affect intmax_t etc. ABI remains unchanged.

3. As the compiler knows the size of these at compile time, and that they will always be some twos power multiple of an integral type, implementation cost for compiler vendors is straightforward. *Optimising* them is hard, but then so is optimisation in any case.

4. These extended types would have the same ABI as a struct of however many of their integral type e.g. _Wide(4) long int has the same ABI as struct { long int[4] }. So they'll get passed mostly by reference, whatever the current calling convention says. Nothing changes for the calling convention.

5. My current feeling is that these wide arithmetic types should have the alignment of their integral type but doubled as necessary. This enables them to "stand in" for types hardware available on bigger CPUs. It also enables SIMD vectorisation by optimisers - AVX-512 CPUs can do 8x 128-bit integer adds four times faster than with the scalar instructions for example.

6. I'm still deciding on whether to support _Complex or not.

7. I'm minded that wide multiplication does not emit doubled precision outputs, but that instead we gain a new multiplication operator whose result type is double the precision of that of its input types. My suggestion would be **. That new operator would apply to the integral types too. In particular, Intel CPUs have had a special opcode for 64 bit x 64 bit = 128 bit multiply for a while now, but making use of it without intrinsics has been hard.

Niall

[Thiago Macieira]

On Friday, 5 October 2018 08:42:21 PDT Niall Douglas wrote:
> 7. I'm minded that wide multiplication does not emit doubled precision
> outputs, but that instead we gain a new multiplication operator whose
> result type is double the precision of that of its input types. My
> suggestion would be **. That new operator would apply to the integral types
> too. In particular, Intel CPUs have had a special opcode for 64 bit x 64
> bit = 128 bit multiply for a while now, but making use of it without
> intrinsics has been hard.

That's one of the things what int128_t was useful for. Just cast one of the
operands to it before doing the multiplication and you get a 128-bit result.
So I feel we don't need a new operator if we can programmatically find the
integer of the next size

That's how Qt implements the mul_overflow() operation if the compiler does not
support __builtin_mul_overflow() but does support 128-bit integers. We use
QIntegerForSize<sizeof(T) * 2>::Signed or Unsigned. See:
https://code.woboq.org/qt5/qtbase/src/corelib/global/qnumeric_p.h.html#314

For MSVC, we have to do as you said: use the _mul128 and _umul128 intrinsic,
as seen a few lines below in the same file.

[Alisdair Meredith]

Does your proposal address _Atomic in C, and atomic<integral> in C++?  I want to be sure that no-one is laboring under conflicting assumptions here, even when it means stating the (apparently) obvious.

Sent from my iPhone

--
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-proposal...@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/b5d854b4-c24e-4a3f-8fcc-3c793527b791%40isocpp.org.

[Niall Douglas]

On Friday, October 5, 2018 at 6:10:37 PM UTC+1, Alisdair Meredith wrote:

Does your proposal address _Atomic in C, and atomic<integral> in C++?  I want to be sure that no-one is laboring under conflicting assumptions here, even when it means stating the (apparently) obvious.

Do bear in mind that my proposal is a generalised wide integer proposal for C. So, P0539, but at the C language level.

 

It does not address Atomic. I have asked WG14 if it ought to address Atomic, and we shall see what they prefer.

Niall 

[ol...@join.cc]

Op vrijdag 5 oktober 2018 17:42:22 UTC+2 schreef Niall Douglas:

On Friday, October 5, 2018 at 2:18:30 PM UTC+1, John McFarlane wrote:

If you're collecting related papers, you might want to mention P0539 which is a 100% serious paper.

My C proposal paper is actually a direct response to P0539, and it discusses what I think are showstopper problems with that paper, and why we need a language solution instead. As I wrote:

WG21 is currently proceeding down a library-based path for implementing
extended precision integers (https://wg21.link/P0539), but my issue with
it is that it is very hard to get the compiler to predictably generate
optimal code with a library only solution. In particular, compilers fail
to spot when they can use carry-adds or carry-multiplies from hints
provided by generic C or C++ code. This is why I have become convinced
we need a language based implementation so compilers know exactly what
they are supposed to do. Hence me coming here to WG14.

What about having 'intrinsics' for carry-adds, carry-multiplies and other operations (saturating and wrapping ops for example)?

[Alberto Barbati]

Il giorno domenica 7 ottobre 2018 23:11:31 UTC+2, Niall Douglas ha scritto:

On Friday, October 5, 2018 at 6:10:37 PM UTC+1, Alisdair Meredith wrote:

Does your proposal address _Atomic in C, and atomic<integral> in C++?  I want to be sure that no-one is laboring under conflicting assumptions here, even when it means stating the (apparently) obvious.

Do bear in mind that my proposal is a generalised wide integer proposal for C. So, P0539, but at the C language level.

 

I was wondering why the C standard allows implementations to optionally add intN_t and uintN_t for any N (including 128 and non-powers-of-two like 24), but C++ only mentions 8, 16, 32 and 64. Is there a strong rationale for that? Would it hurt to explicitly allow those "exotic" integer types to be conditionally-supported in C++ also?

Alberto

[Niall Douglas]

What about having 'intrinsics' for carry-adds, carry-multiplies and other operations (saturating and wrapping ops for example)?

Firstly, I am unaware of any precedent for that sort of intrinsic in either C or C++. It seems too specific for standardisation to me, but maybe I'm wrong.

Secondly, such a thing would be rather hardware dependent. For example RISC V has no carry flag, and thus no carry based arithmetic. So kinda hard to standardise such support.

Niall

[Niall Douglas]

I was wondering why the C standard allows implementations to optionally add intN_t and uintN_t for any N (including 128 and non-powers-of-two like 24), but C++ only mentions 8, 16, 32 and 64. Is there a strong rationale for that? Would it hurt to explicitly allow those "exotic" integer types to be conditionally-supported in C++ also?

C and C++ are required to define "least" and "fast" forms of various bit sized integers, and only if the architecture permits exactly 8, 16, 32 and 64 bits does it define typedefs for those.

My proposal would leave integral arithmetic alone. What the hardware supports, it supports. Extended precision integers are by definition at least four fold slower than the hardware supported integers, and often much slower than that again. So they ought to exist in a different "space" to integral integers if that makes sense. Then it's clear they're not like normal integers, they are obviously different.

Niall

[Niall Douglas]

On Friday, October 5, 2018 at 6:10:37 PM UTC+1, Alisdair Meredith wrote:

Does your proposal address _Atomic in C, and atomic<integral> in C++?  I want to be sure that no-one is laboring under conflicting assumptions here, even when it means stating the (apparently) obvious.

So, WG14 seem to feel it ought to address _Atomic with support for arbitrary fixed length extended precision integers. I shall try my best to write something coherent on that.

Niall 

[Alberto Barbati]

Il giorno lunedì 8 ottobre 2018 21:50:51 UTC+2, Niall Douglas ha scritto:

I was wondering why the C standard allows implementations to optionally add intN_t and uintN_t for any N (including 128 and non-powers-of-two like 24), but C++ only mentions 8, 16, 32 and 64. Is there a strong rationale for that? Would it hurt to explicitly allow those "exotic" integer types to be conditionally-supported in C++ also?

C and C++ are required to define "least" and "fast" forms of various bit sized integers, and only if the architecture permits exactly 8, 16, 32 and 64 bits does it define typedefs for those.

According to my interpretation of the C and C++ standards, if the implementation has a integer types of exactly N bits, it is allowed to provide intN_t and uintN_t aliases in C11 for any N, but it can do so in C++11/14/17 only if N = 8, 16, 32, 64. For example, paragraph 7.20.1.1/2 in C11 explicitly mentions the possibility to have a uint24_t type. Under this interpretation, an implementation may provide int128_t and uint128_t types in C but not in C++. I find this strange. Am I missing something?

[Bo Persson]

The C++ synopsis only describes the types that are required (if present
on the hardware). It doesn't say that this is all that is allowed, but
rather refers the rest to the C standard.

16.4/2:

"The header defines all types and macros the same as the C standard
library header <stdint.h>.

See also: ISO C 7.20"

[Alberto Barbati]

English is not my mother language, but I have always interpreted that statement with the meaning “The header defines all types and macros *described in the previous paragraphs* the same as the C standard library header <stdint.h>”. Since types and macros were introduced without a definition, this interpretation makes sense to me. It would make less sense to define something that hasn’t been previously described. Moreover, if we were actually to define *all types and macros of <stdint.h> in the same way as C does*, we would have to put them in the global namespace. If the intent of that statement is to import optional C11 types not described by the C++ standard in namespace std, I believe the statement ought to be more explicit.

Just my opinion,

[John McFarlane]

On Fri, 5 Oct 2018 at 16:42 Niall Douglas <nialldo...@gmail.com> wrote:

On Friday, October 5, 2018 at 2:18:30 PM UTC+1, John McFarlane wrote:

If you're collecting related papers, you might want to mention P0539 which is a 100% serious paper.

My C proposal paper is actually a direct response to P0539, and it discusses what I think are showstopper problems with that paper, and why we need a language solution instead. As I wrote:

WG21 is currently proceeding down a library-based path for implementing
extended precision integers (https://wg21.link/P0539), but my issue with
it is that it is very hard to get the compiler to predictably generate
optimal code with a library only solution. In particular, compilers fail
to spot when they can use carry-adds or carry-multiplies from hints
provided by generic C or C++ code. This is why I have become convinced
we need a language based implementation so compilers know exactly what
they are supposed to do. Hence me coming here to WG14.

This makes it a lot clearer that you're talking about P0539. I would not use shorthand `int<128>` to describe that library type.

I'm not sure why you think that implementers are restricted to supplying pure-library solutions or why using something like the free functions in P0103 would not solve this. Do you go into any more detail about the reasons you don't think a library solution is practical for C++?

Current proposal being discussed on the WG14 reflector looks as follows:

1. For any integer type excluding _Bool (char, short, int, long, long long), one may extend it into an extended arithmetic type by annotating it with "_Wide(N)":

    - _Wide(4) int

    - long long _Wide(2)

This simply tells the compiler to emit the add-with-carry or multiply-with-carries instructions necessary to increase the precision of the specified arithmetic type. And before anyone asks, yes it is legal to widen small types:

    - _Wide(2) short (NOT an int)

    - _Wide(4) char (NOT an int)

2. These wide integer types are not integral types, and thus do not affect intmax_t etc. ABI remains unchanged.

3. As the compiler knows the size of these at compile time, and that they will always be some twos power multiple of an integral type, implementation cost for compiler vendors is straightforward. *Optimising* them is hard, but then so is optimisation in any case.

4. These extended types would have the same ABI as a struct of however many of their integral type e.g. _Wide(4) long int has the same ABI as struct { long int[4] }. So they'll get passed mostly by reference, whatever the current calling convention says. Nothing changes for the calling convention.

That would seem to imply they have 4 sign bits but presumably they don't, right?

5. My current feeling is that these wide arithmetic types should have the alignment of their integral type but doubled as necessary. This enables them to "stand in" for types hardware available on bigger CPUs. It also enables SIMD vectorisation by optimisers - AVX-512 CPUs can do 8x 128-bit integer adds four times faster than with the scalar instructions for example.

Are you only aiming for powers of two? That's another way in which this would differ from P0539.

John

[Niall Douglas]

I'm not sure why you think that implementers are restricted to supplying pure-library solutions or why using something like the free functions in P0103 would not solve this. Do you go into any more detail about the reasons you don't think a library solution is practical for C++?

I do go into more detail, but the crux of it is that to get efficient codegen, you're going to either have to (a) hint to the compiler using intrinsics what you're doing or (b) have the compiler special case how it interprets wide_integer<>. I would argue in that case, just bite the bullet and add it to the core C language.

 

That would seem to imply they have 4 sign bits but presumably they don't, right?

They do not.

 

5. My current feeling is that these wide arithmetic types should have the alignment of their integral type but doubled as necessary. This enables them to "stand in" for types hardware available on bigger CPUs. It also enables SIMD vectorisation by optimisers - AVX-512 CPUs can do 8x 128-bit integer adds four times faster than with the scalar instructions for example.

Are you only aiming for powers of two? That's another way in which this would differ from P0539.

There are many more C compiler implementations than C++ compilers. WG14 feels it is important that a C compiler can be easily implemented by a single person in a reasonable period of time. Using powers of two covers the majority use case at minimum implementation expense, indeed such implementation for arbitrary fixed length extended precision integers could be done within a day or two.

Niall

[Daniel Krügler]

Am Mo., 8. Okt. 2018 um 22:38 Uhr schrieb Alberto Barbati
<alberto...@gmail.com>:

Please take a look at

http://cplusplus.github.io/LWG/lwg-active.html#2820

which should solve the current deviation between C and C++ (at least
that seems to be the intention).

Thanks,

- Daniel

[olafv...@gmail.com]

Op maandag 8 oktober 2018 21:47:24 UTC+2 schreef Niall Douglas:

What about having 'intrinsics' for carry-adds, carry-multiplies and other operations (saturating and wrapping ops for example)?

Firstly, I am unaware of any precedent for that sort of intrinsic in either C or C++. It seems too specific for standardisation to me, but maybe I'm wrong.

Maybe, maybe not. I've wondered about intrinsics like "read (aligned) big-endian / little-endian 8/16/32/64-bit value from *p" before. They seem kinda simple to define for appropriate definitions of simple. ;)

Same for this one.

 

Secondly, such a thing would be rather hardware dependent. For example RISC V has no carry flag, and thus no carry based arithmetic. So kinda hard to standardise such support.

Would emulation of the intrinsic be worse than doing it without the intrinsic? In that case a way to detect the intrinsic being available would make sense.

Not having the intrinsic at all just makes it much harder for everybody that still needs the functionality.

[Alisdair Meredith]

Thanks - my main concern is that the topic is either explicitly addresses, or

explicitly not addressed, so readers off the proposal do not have differing

understandings!

AlisdairM

--
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-proposal...@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/bf21d232-2924-45bc-b114-365a53ecf256%40isocpp.org.

[Alberto Barbati]

Il giorno martedì 9 ottobre 2018 13:36:40 UTC+2, Daniel Krügler ha scritto:

>
> According to my interpretation of the C and C++ standards, if the implementation has a integer types of exactly N bits, it is allowed to provide intN_t and uintN_t aliases in C11 for any N, but it can do so in C++11/14/17 only if N = 8, 16, 32, 64. For example, paragraph 7.20.1.1/2 in C11 explicitly mentions the possibility to have a uint24_t type. Under this interpretation, an implementation may provide int128_t and uint128_t types in C but not in C++. I find this strange. Am I missing something?
>

Please take a look at

http://cplusplus.github.io/LWG/lwg-active.html#2820

which should solve the current deviation between C and C++ (at least
that seems to be the intention).

Daniel, thank you very much for the pointer. The proposed resolution of this issue completely addresses my concerns. I hope it will get integrated in C++2a.

Alberto