Unsigned integers

[certik]

All integers in Fortran are signed. It is a common request to include unsigned integers. At the very least to help with the interoperation with the C API that uses unsigned integers.

The best approach currently is to use signed integers of the same size, and then convert them to unsigned Fortran integers of a bigger size appropriately.

[zbeekman]

Yes, for certain algorithms (hash functions) the wrap around nature of unsigned ints is convenient and it would lead to less confusion with C interop. I do not believe the standard requires integers to be implemented as two's complement, but I do not know of a compiler that uses a different convention. This means that the underlying machinery for unsigned integers is already in place. (And that programmers can "roll their own" but this can be confusing or less clear/explicit in the source code.

[certik]

After talking about this with a few members on the committee, it seems most are in agreement that having this in the C interop might be a good idea, but allowing this in the Fortran language itself would do more harm than good (vendors don't like it; it's easy to have all kinds of subtle bugs with unsigned integers such as comparing subtracting etc.).

Python does not have unsigned integers, although NumPy does, and so does Julia.
It is true that it would be useful for hash functions. Numerical computational code does not seem to need them.

I can personally see very good arguments both for and against having this in the language itself.
I am leaning towards against, as it keeps the language smaller and excludes many kinds of possible bugs and warnings.

We can start with the C interop, where it should be easier to get agreement, to see if there is anything that would make sense to propose.

[gronki]

I wanted to chime in and say that one important use case of unsigned integers is handling images. To store a monochrome 8-bit image, one either has to use twice-as-large 16 bit integer or store it as 8 bit unsigned int and deal with wrapping modulo 128 which makes any arithmetic operation impossible. This is true for any binary data, not only images. So I think the issue is not stricly C-interop related.

[FortranFan]

I wanted to chime in and say that one important use case of unsigned integers is handling images. To store a monochrome 8-bit image, one either has to use twice-as-large 16 bit integer or store it as 8 bit unsigned int and deal with wrapping modulo 128 which makes any arithmetic operation impossible. This is true for any binary data, not only images. So I think the issue is not stricly C-interop related.

I agree with this: unsigned integers can be of great help in any systems programming context, handling of binary data of any form (images or otherwise) can be a use case within this space. Though some will argue unsigned integers are not an absolute must for systems programming, the fact is this facility can really make coders' lives easier. If Fortran intends to be taken truly seriously as a general-purpose language, it should consider including unsigned integers; its type system is general and it does not in any way appear to interfere with its introduction.

Interestingly, unsigned integers feature was 4th on the top 6 list of desired features by users in the WG5 survey for Fortran 202X. Ignoring this any longer feels like suppression of the voice of the customers!

[certik]

I just want to react to this particular point:

If Fortran intends to be taken truly seriously as a general-purpose language

Fortran is not a general-purpose language. Rather, it is a domain specific language for array oriented scientific computing.

As a larger point, it touches what we want Fortran to be, see #59.

[gronki]

Fortran is not a general-purpose language. Rather, it is a domain

specific language for array oriented scientific computing. I agree with this and with that direction, however reading/writing binary data is often a part of it, and this is the place where lack of byte/uint really bit me as very often data is stored as uint16 FITS/TIFF files. Dominik pon., 28 paź 2019 o 22:31 Ondřej Čertík <[email protected]> napisał(a):

…

I just want to react to this particular point: If Fortran intends to be taken truly seriously as a general-purpose language Fortran is not a general-purpose language. Rather, it is a domain specific language for array oriented scientific computing. As a larger point, it touches what we want Fortran to be, see #59 <#59>. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2?email_source=notifications&email_token=AC4NA3N4HGNT7GC7E7BKHMDQQ5K3XA5CNFSM4JBFTXZKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOECOOZEY#issuecomment-547155091>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AC4NA3LG6CZDOIS7GUO7UIDQQ5K3XANCNFSM4JBFTXZA> .

[certik]

@gronki I think you are right about the use case of reading binary data files. Let's collect such use cases. I think we want to be able to write readers and writers for binary files in Fortran.

[FortranFan]

I just want to react to this particular point:

If Fortran intends to be taken truly seriously as a general-purpose language

Fortran is not a general-purpose language. Rather, it is a domain specific language for array oriented scientific computing.
..

That may be the current reality with Fortran, but almost everyone who have worked on its language design and continue to do so will greatly dislike being reduced as such and would very much want Fortran to be seen as a general-purpose language. It's a different matter whether the words are backed up by actions!

[certik]

Let's continue the discussion what Fortran should become here: #59. I started in this comment: #59 (comment).

[klausler]

I'm not sure that Fortran needs an unsigned type so much as it actually needs some unsigned operations and relations. Be wary of simply copying-and-pasting C's unsigned types into Fortran, for they are full of pitfalls that shouldn't be perpetuated, mostly around their interactions with signed types and conversions.

[8bitmachine]

I too would like unsigned integers. Mainly because of bitmap, image data, and other binary coding or data.
I do not see that this should be a problem as it would be a new data type (not an operation, we do need a type) that existing programs would continue to default to signed integers.
My work around for simplicity (not elegance) is to use 16 bit integers and save the data as is in 8 bits when needed. I find that more convenient than having to check 8 bits all the time if only unsigned is needed.

[tkoenig1]

I would like to have unsigned integers as well, but there need to be clear definitions of how they interact with signed integers as well.

Assume

  integer :: i
  unsigned integer :: u

then the question of what type i+u should have is difficult, and needs to be resolved in a better way than C did. I would probably favor of banning arithmetic operations involving a signed and unsigned integer without explicit conversion.

Comparisons between signed and unsigned should take the sign into account, so that -2 is smaller than (unsigned) 1.
For constants it is also not quite clear how to differentiate an unsigned from a signed constant. The _ suffix
is already taken.

So, lots of decisions, and lots of traps and pitfalls. Avoiding everything that C got wrong does not mean that a proposal would get it right...

[FortranFan]

Imagine Fortran 202Y introduces a distinct new intrinsic type unsigned integers, say it is termed uinteger.

Now assume

1. it is only directly allowed in expressions, assignment, and comparisons with strict type compatibility requirements i.e., only with other uintegers,
2. A new intrinsic UINT intrinsic is introduced toward type conversion of integers to uintegers with well-defined requirements and semantics,
3. INT intrinsic is extended to support type conversion of uintegers to integers with well-defined requirements and semantics,

Then what are the pitfalls from other experiments (C-like languages) that can be envisioned with such a design in Fortran?

Note 1. above will mean

integer :: i, foo
uinteger :: u, bar
u = i !<-- Not allowed
i = u !<-- Not allowed
foo = i + u !<-- Not allowed
bar = i + u !<-- Not allowed
if ( i > u )  !<-- Not allowed
..
u = UINT( i )  !<-- Ok
foo = i + INT(u)  !<-- Ok
..

[certik]

Here is a small subset of possible pitfalls that I recommend to address:

• Subtracting two unsigned integers can wrap around (e.g. 3 - 5 = -2 -> -2+UINT_MAX+1).
• Consequently 3 - 5 < 3 is false, which can easily lead to many bugs in a code
• The last condition in unsigned int x = 1; int y = -2; (x + y > 0) evaluated to true, even though with signed integers x+y=(1)+(-2)=-1.
• Another variant: unsigned int a = 1000; signed int b = -1; (a > b) evaluates to false, even though with signed integers (1000 > -1 is true)
• Infinite loop: for (unsigned z = 5; z >= 0; z--) { do_something(z); }
• Complicated automatic casting in the frontend for things like comparisons of signed and unsigned integers
• Hard to figure out for users when to use each type. For example it's safer to use signed integers, except when a function returns an unsigned integer (say the .size() function in C++), then one gets compiler warnings in loops like for (int64_t i=0; i < x.size(); i++) of comparing signed and unsigned integer, so one is forced to rewrite to for (uint64_t i=0; i < x.size(); i++).
• Unsigned integers cannot be treated as a range-limited version of signed ones because their range of values is not a subset of the signed integers range. Neither signed, nor unsigned integers are subtypes of each other. For example -128 <= i8 <= 127 but 0 <= u8 <= 255, so x: i8 with the condition of x > 0 is not equal to x: u8, because for example x=200 is representable as a u8, but not i8.
• Many developers (but not all) believe that unsigned integers should be avoided, such as the Google C++ guidelines:

  • You should not use the unsigned integer types such as uint32_t, unless there is a valid reason such as representing a bit pattern rather than a number, or you need defined overflow modulo 2^N. In particular, do not use unsigned types to say a number will never be negative. Instead, use assertions for this.

  • Unsigned integers are good for representing bitfields and modular arithmetic. Because of historical accident, the C++ standard also uses unsigned integers to represent the size of containers - many members of the standards body believe this to be a mistake, but it is effectively impossible to fix at this point. The fact that unsigned arithmetic doesn't model the behavior of a simple integer, but is instead defined by the standard to model modular arithmetic (wrapping around on overflow/underflow), means that a significant class of bugs cannot be diagnosed by the compiler. In other cases, the defined behavior impedes optimization.

  • That said, mixing signedness of integer types is responsible for an equally large class of problems. The best advice we can provide: try to use iterators and containers rather than pointers and sizes, try not to mix signedness, and try to avoid unsigned types (except for representing bitfields or modular arithmetic). Do not use an unsigned type merely to assert that a variable is non-negative.

References:

• Bjarne Stroustrup: Subscripts and sizes should be signed
• https://blog.libtorrent.org/2016/05/unsigned-integers/
• Unsigned integers, and why to avoid them
• https://www.boost.org/doc/libs/develop/libs/safe_numerics/doc/html/index.html
• https://github.com/PeterSommerlad/PSsimplesafeint

[8bitmachine]

I'd prefer no wrap-around and an error if an unsigned integer overflowed /underflowed, but which could be checked and corrected with the same considerations as a carry bit so that increases/decreases could be handled. It would actually allow wrap-around with a correction function following by ignoring carry/borrow.
Unsigned integers are needed on occasions as others have mentioned. I've needed them for A-D conversion, bit checking and image handling.

[tkoenig1]

Here is a small subset of possible pitfalls that I recommend to address:

• Subtracting two unsigned integers can wrap around (e.g. 3 - 5 = -2 -> -2+UINT_MAX+1).

Yes, this is the nature of modulo arithmetic.

• Consequently 3 - 5 < 3 is false, which can easily lead to many bugs in a code

Again, this is the nature of modulo arithmetic. It would be the expectation that people who use it know what they are doing. Maybe this can be alleviated by chosing some more descriptive name which has the modulo in the name.

• The last condition in unsigned int x = 1; int y = -2; (x + y > 0) evaluated to true, even though with signed integers x+y=(1)+(-2)=-1.

It makes little sense to think of unsigned integers as "-1". Again, this is implied in modulo 2^n arithmetic.

• Another variant: unsigned int a = 1000; signed int b = -1; (a > b) evaluates to false, even though with signed integers (1000 > -1 is true)

Same thing.

• Infinite loop: for (unsigned z = 5; z >= 0; z--) { do_something(z); }

Jep. I would actually not permit unsigned types for DO loops.

• Complicated automatic casting in the frontend for things like comparisons of signed and unsigned integers

This, I would disallow - explicit type conversions only.

• Hard to figure out for users when to use each type. For example it's safer to use signed integers, except when a function returns an unsigned integer (say the .size() function in C++), then one gets compiler warnings in loops like for (int64_t i=0; i < x.size(); i++) of comparing signed and unsigned integer, so one is forced to rewrite to for (uint64_t i=0; i < x.size(); i++).

SIZE returns an integer, I would not change that. And no DO loops with unsigned variables, and explicit casts only.

• Unsigned integers cannot be treated as a range-limited version of signed ones because their range of values is not a subset of the signed integers range. Neither signed, nor unsigned integers are subtypes of each other. For example -128 <= i8 <= 127 but 0 <= u8 <= 255, so x: i8 with the condition of x > 0 is not equal to x: u8, because for example x=200 is representable as a u8, but not i8.

Make the conversion defined, and explicit only.

• Many developers (but not all) believe that unsigned integers should be avoided, such as the Google C++ guidelines:

  • You should not use the unsigned integer types such as uint32_t, unless there is a valid reason such as representing a bit pattern rather than a number, or you need defined overflow modulo 2^N. In particular, do not use unsigned types to say a number will never be negative. Instead, use assertions for this.

That, I would agree with.

• Unsigned integers are good for representing bitfields and modular arithmetic. Because of historical accident, the C++ standard also uses unsigned integers to represent the size of containers - many members of the standards body believe this to be a mistake, but it is effectively impossible to fix at this point. The fact that unsigned arithmetic doesn't model the behavior of a simple integer, but is instead defined by the standard to model modular arithmetic (wrapping around on overflow/underflow), means that a significant class of bugs cannot be diagnosed by the compiler. In other cases, the defined behavior impedes optimization.

Fortran has had SIZE returning a signed integer for ages. We should definitely avoid returning unsigneds there.

• That said, mixing signedness of integer types is responsible for an equally large class of problems. The best advice we can provide: try to use iterators and containers rather than pointers and sizes, try not to mix signedness, and try to avoid unsigned types (except for representing bitfields or modular arithmetic). Do not use an unsigned type merely to assert that a variable is non-negative.

Again, agreed. If type conversion has to be explicit, then people will hopefully not use it just for the (non)-fun of it.

[8bitmachine]

subtracting two unsigned numbers can also overflow, though.
To ensure correct programming some means of flagging up the carry/borrow is needed, in case of (perhaps) unexpected conditions.
That seems to me to be the problem. 3-5 <3 would be interpreted correctly if a carry/borrow flag is used in the evaluation, if both are unsigned. That would also work in a do loop.
Checking the size of files, etc could benefit from unsigned values, though the usual solution of using a larger max integer is adequate as files are not likely to need 31bit sizes.
I would still request unsigned, but with the restrictions of not mixing them and explicit conversion if needed.

[gronki]

I agree with tkoenig in every point. Coming from the field of computer vision and image processing, where Fortran could fight for its large share, not having unsigned type causes a lot of pain. I would not be concerned about overflows as unsigned arithmetic is modulo arithmetics by design. I agree that no implicit conversion of any kind should occur, nor should size or other intrinsic return types be changed to unsigned. Unsigned int should be only restricted to be useful where it is needed (signal processing and data storage). Currently, using oversized data type causes half of the memory to be effectively wasted, and leads to computational overhead. Dominik pt., 13 sty 2023, 16:48 użytkownik 8bitmachine ***@***.***> napisał:

…

subtracting two unsigned numbers can also overflow, though. To ensure correct programming some means of flagging up the carry/borrow is needed, in case of (perhaps) unexpected conditions. That seems to me to be the problem. 3-5 <3 would be interpreted correctly if a carry/borrow flag is used in the evaluation, if both are unsigned. That would also work in a do loop. Checking the size of files, etc could benefit from unsigned values, though the usual solution of using a larger max integer is adequate as files are not likely to need 31bit sizes. I would still request unsigned, but with the restrictions of not mixing them and explicit conversion if needed. — Reply to this email directly, view it on GitHub <#2 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AC4NA3OZEVI4I6KUZ3R6YEDWSF2OTANCNFSM4JBFTXZA> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[tkoenig1]

@certik : I share your concerns about people making stupid mistakes because it is too easy to confuse signed and unsigned ints. To alleviate this, maybe this:

Unsigned constants should also be distinguished from normal integers. Anybody who wants -1 as an unsigned number should either write something like u_int(-1) or u_int(-1,KIND_NUMBER). If that is too cumbersome, maybe another suffix could be added, maybe something like #.

So, u = -1# would be fine, u = -1 not (if u is an unsigned number). That should alert both readers and writers of programs that something unsigned is going on there.

Comparisons between signed and unsigned could actually be permitted, but the values would be compared, so -1 < u would always be true. This would correct one of C's worst abominations.

[klausler]

Unsigned integers don't have to be a full-fledged type in Fortran; it just needs a few more unsigned integer operations. Just as IAND can be well-defined on integers, so could IUADD and IULT, &c.

[gronki]

I think idea by Peter Klausler is also worthwhile and much more simple to introduce, since adding intrinsic is much less work intensive. I would add that conversion from uint to float is a very common operation. So simple arithmetic and conversion would cover most of the needs as far as the computer vision goes. Dominik pt., 13 sty 2023, 18:12 użytkownik Peter Klausler ***@***.***> napisał:

…

Unsigned integers don't have to be a full-fledged *type* in Fortran; it just needs a few more unsigned integer *operations*. Just as IAND can be well-defined on integers, so could IUADD and IULT, &c. — Reply to this email directly, view it on GitHub <#2 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AC4NA3J2WFJPG7CHISYU3OTWSGEGXANCNFSM4JBFTXZA> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[tkoenig1]

Unsigned integers don't have to be a full-fledged type in Fortran; it just needs a few more unsigned integer operations. Just as IAND can be well-defined on integers, so could IUADD and IULT, &c.

Possible, of course, but it would not be very much like "Formula Translation" any more, it would look more like LISP :-)

Another possibility would be an intrinsic module which exports an otherwise opaque type which just happens to have certain operations, and others not. But this would not work seamlessly with I/O, so better not.

[klausler]

Formatted I/O already has BOZ editing, so add U editing for unsigned decimal. (List-directed and NAMELIST I/O would require a new type, yes.)

I think that people are underestimating the compiler engineering effort needed to extend Fortran's type system with a new intrinsic type, and overestimating the benefit to be gained from the effort. But adding just some unsigned integer operations would be cheap.

[kargl]

I just sent a PR with the new unsigned proposal that I think we can all agree upon: #341,

The "can all agree upon" seems a bit presumptive. Here's a portion of Marsaglia's 64-bit KISS prng implemented and tested with gfortran

function kiss()
   unsigned(uk) kiss
   unsigned(uk) t
   t = ishft(sd(1), 58) + sd(4)
   if (s(sd(1)) == s(t)) then
      sd(4) = ishft(sd(1), -6) + s(sd(1))
   else
      sd(4) = ishft(sd(1), -6) + 1u_uk - s(sd(1) + t)
   end if
   sd(1) = t + sd(1)
   sd(2) = m(m(m(sd(2), 13), -17), 43)
   sd(3) = 6906969069u_uk * sd(3) + 1234567u_uk
   kiss = sd(1) + sd(2) + sd(3)
end function kiss

Note, m() and s() are pure internal functions with an UNSIGNED type. Here's the same code using the intrinsic routines suggested here.

 function kiss()
   unsigned(uk) kiss
   unsigned(uk) t
   t = add_wrapping(ishft(sd(1), 58), sd(4))
   if (s(sd(1)) == s(t)) then
      sd(4) = add_wrapping(ishft(sd(1), -6), s(sd(1)))
   else
      sd(4) = sub_wrapping(add_wrapping(ishft(sd(1), -6), 1u_uk), &
      &  s(add_wrapping(sd(1), t)))
   end if
   sd(1) = add_wrapping(t, sd(1))
   sd(2) = m(m(m(sd(2), 13), -17), 43)
   sd(3) = add_wrapping(mul_wrapping(6906969069u_uk, sd(3)), 1234567u_uk)
   kiss = add_wrapping(add_wrapping(sd(1), sd(2)), sd(3))
end function kiss

It would be even more difficult to parse if, e.g., add_wrapping(ishft(sd(1), -6), s(sd(1))) were replaced by, say, unsigned_add(ishft(sd(1), -6), s(sd(1)), mode='modular').

Hopefully, there is some agreement that one of these kiss() routines is easier to read and parse.

[certik]

@kargl awesome, thanks for the code. Can I include that in the proposal? Yes, indeed the add_wrapping version is more verbose / less readable. The reason is that in this case it would be helpful to have a modular arithmetic behavior (type). My proposal does leave the door open to add such a type, and you can recover the "simple" version of your code. The alternative proposal makes "unsigned" the modular arithmetic type, but that means you get the unwanted wraparound in all other cases that you don't want.

[kargl]

Anything I post in a public forum without an explicit copyright notice is fair game for others to use as they see fit. Even the KISS example isn't too complicated, but shows the verbose use of functions.

As a side note, I agree with @klausler and @tkoenig1 that introducing new processor-dependent behavior into the Fortran standard is undesirable.

[PierUgit]

Hopefully, there is some agreement that one of these kiss() routines is easier to read and parse.

That's right, and we have to explore how to make it simpler, which is possible IMO.

As a side note, I agree with @klausler and @tkoenig1 that introducing new processor-dependent behavior into the Fortran standard is undesirable.

It seems to me that the standard constantly introduces some undefined behaviors, which is not necessarily a bad thing in itself, as UB's leave more room for some optimizations by the compilers.

[tkoenig1]

Hopefully, there is some agreement that one of these kiss() routines is easier to read and parse.

That's right, and we have to explore how to make it simpler, which is possible IMO.

As a side note, I agree with @klausler and @tkoenig1 that introducing new processor-dependent behavior into the Fortran standard is undesirable.

It seems to me that the standard constantly introduces some undefined behaviors, which is not necessarily a bad thing in itself, as UB's leave more room for some optimizations by the compilers.

@PierUgit

Fortran has prohibitions in the code, as in "shall not", and requirements, as in "shall". If somebody does a calculation involving integer overflow, then that is illegal, The processor can do optimizations based on the assumption that this does not happen, and if the user makes that mistake then it can ignore the error, trap, or start World War III.

Intentionally introducing undefined behavior into the language would be a) a bad idea, as C has learned and b) will be equivalent to a prohibition. Framing this as anything else is just wrong, and shows either a basic flaw in understanding of language design, or something else.

[septcolor]

(PierUgit wrote:) And another possibility in my opinion is "no default at all" (i.e. the "+ - * /" operators cannot be used by default).

Naively, I thought that having no default arithmetic operations and requesting the user to import a desired set of operators (+, *, etc, (*1)) from some intrinsic module (e.g., at the top of a user module) seems useful to keep the readability of the code. Is such an operator-based approach already out of option for some reason (e.g., because operators can take only up to 2 arguments so less flexible (*2)), and so intrinsic function-based approaches currently considered instead?

(*1) Here, I imagine a set of operators are provided in an intrinsic module for each mode (e.g. modular) and the user can select which mode to use via the use statement.
(*2) Another concern might be computational efficiency and what happens if operators of different modes are imported in a mixed way.

Personally, I expect the "modular" behavior (255 + 2 -> 1) will be okay as the default because (i) Fortran users use signed integers up to now, and only "power users" will use unsigned integer for their special purposes (so I expect they know what they are doing), and (ii) other languages seem to use the modular mode, so porting the code seems easier.

[PierUgit]

Intentionally introducing undefined behavior into the language would be a) a bad idea, as C has learned and b) will be equivalent to a prohibition.

Agree, but I don't think this is the intent of @certik , as he wrote in his proposal: "Just like the current (signed) integers, arithmetic overflow is undefined. This allows processors to optionally check for overflow." . So he is explicitely saying that the unsigned overflow should be handled the same way as the signed overflow. Nonetheless some words should be changed in the proposal (undefined -> prohibited).

Framing this as anything else is just wrong, and shows either a basic flaw in understanding of language design, or something else.

Maybe I'm dumb, maybe something else...

[PierUgit]

Naively, I thought that having no default arithmetic operations and requesting the user to import a desired set of operators (+, *, etc, (*1)) from some intrinsic module (e.g., at the top of a user module) seems useful to keep the readability of the code.

(*1) Here, I imagine a set of operators are provided in an intrinsic module for each mode (e.g. modular) and the user can select which mode to use via the use statement.

Indeed I previously suggested something similar in this discussion:

subroutine foo1()
   unsigned, parameter :: a = huge(0u)
   print*, 1u + 1u   ! compilation error, "+" is not defined
   print*,  a + 1u   ! compilation error, "+" is not defined
end subroutine

subroutine foo2()
   unsigned overflow no
   unsigned, parameter :: a = huge(0u)
   print*, 1u + 1u   ! prints "2"
   print*,  a + 1u   ! prohibited overflow, the compiler can catch it
                                           (but is not required to)
end subroutine

subroutine foo3()
   unsigned overflow wrap
   unsigned, parameter :: a = huge(0u)
   print*, 1u + 1u   ! prints "2"
   print*,  a + 1u   ! prints "0"
end subroutine

subroutine foo3()
   unsigned overflow saturate
   unsigned, parameter :: a = huge(0u)
   print*, 1u + 1u   ! prints "2"
   print*,  a + 1u   ! prints the value of huge(0u)
end subroutine

But yes, it could also be done with intrinsic modules (use unsigned_overflow_[no|wrap|saturate])

[septcolor]

Hi @PierUgit,
One of the limitations of the operator approach (or the above import-type approach) may be that it is not straightforward to specify the mode to be used in a function like dot_product() or sum(), because the passed arguments themselves do not have the information about the mode in the current scope... In principle, it may be possible to pass the information somehow via additional arguments, or call specific routines like sum_wrap(), though. (I guess the same thing applies to the function-based approach also?) This kind of issue is not present if distinct types (or kinds) are defined for different modes (because sum() can call specific routines using the type or kinds of arguments).

[certik]

@tkoenig1 wrote:

Intentionally introducing undefined behavior into the language would be a) a bad idea, as C has learned and b) will be equivalent to a prohibition. Framing this as anything else is just wrong, and shows either a basic flaw in understanding of language design, or something else.

This was already addressed by @PierUgit at #2 (comment). A simple video call would clarify such basic points easily. @tkoenig1 all you need to do is reply to the email I sent you. :) The proposal in #341 does not prohibit to later do your full proposal. You can relax a prohibition and no user code will break (unless they were using something that is prohibited).

[ashe2]

Intentionally introducing undefined behavior into the language would be a) a bad idea, as C has learned and b) will be equivalent to a prohibition.

Agree, but I don't think this is the intent of @certik , as he wrote in his proposal: "Just like the current (signed) integers, arithmetic overflow is undefined. This allows processors to optionally check for overflow." . So he is explicitely saying that the unsigned overflow should be handled the same way as the signed overflow. Nonetheless some words should be changed in the proposal (undefined -> prohibited).

I don't understand this reply. @certik is proposing that the result of unsigned arithmetic is not defined in some cases. How is that not introducing new undefined behavior?

[PierUgit]

I don't understand this reply. @certik is proposing that the result of unsigned arithmetic is not defined in some cases. How is that not introducing new undefined behavior?

Saying that the behavior is "undefined" is actually consistent with the current text of the standard for the existing numeric types, which says:

Actually, I can't find in the standard anything that says that the integer type overflow is prohibited, it is just not defined by the standard and the behavior is left to the compilers. So, it could be the same for the unsigned type.

[tkoenig1]

For people who want saturating or checked or ... arithmetic, here is an implementation - changing a parameter in user code changes the behavior. A user who desires different behavior could easily change that parameter; this
would even be more finely grained than a general compiler switch.

This contains a subroutine chk_add which is modeled on the C23 feature, which in turn is modeled on gcc's integer overflow builtins

module checked_unsigned
  implicit none
  private
  public :: uc, operator(+), assignment(=)
  type uc
     unsigned :: u
  end type uc
  enum, bind(c)
     enumerator :: uc_no_check = 0, uc_check=1, uc_saturating = 2
  end enum
  integer, parameter :: this_check = uc_saturating

  interface operator(+)
     procedure checked_add_uc
     procedure checked_add_cu
     procedure checked_add_cc
  end interface operator(+)
  interface assignment(=)
     procedure set_uc
     procedure set_cu
  end interface assignment(=)
contains
  recursive elemental function checked_add_uc(a,b) result(c)
    unsigned, intent(in) :: a
    type(uc), intent(in) :: b
    type(uc) :: c
    logical :: overflow
    select case (this_check)
    case (uc_no_check)
       c%u = a + b%u
    case (uc_check)
       call chk_add (c%u, a, b%u, overflow)
       if (overflow) error stop
    case (uc_saturating)
       call chk_add (c%u, a, b%u, overflow)
       if (overflow) c%u = huge(c%u)
    end select
  end function checked_add_uc

  recursive elemental function checked_add_cu(a,b) result(c)
    type(uc), intent(in) :: a
    unsigned, intent(in) :: b
    type(uc) :: c
    logical :: overflow
    select case (this_check)
    case (uc_no_check)
       c%u = a%u + b
    case (uc_check)
       call chk_add (c%u, a%u, b, overflow)
       if (overflow) error stop
    case (uc_saturating)
       call chk_add (c%u, a%u, b, overflow)
       if (overflow) c%u = huge(c%u)
    end select
  end function checked_add_cu

  recursive elemental function checked_add_cc(a,b) result(c)
    type(uc), intent(in) :: a, b
    type(uc) :: c
    logical :: overflow
    select case (this_check)
    case (uc_no_check)
       c%u = a%u + b%u
    case (uc_check)
       call chk_add (c%u, a%u, b%u, overflow)
       if (overflow) error stop
    case (uc_saturating)
       call chk_add (c%u, a%u, b%u, overflow)
       if (overflow) c%u = huge(c%u)
    end select
  end function checked_add_cc

  recursive elemental subroutine set_uc(a,b)
    type(uc), intent(in) :: b
    unsigned, intent(out) :: a
    a = b%u
  end subroutine set_uc
  recursive elemental subroutine set_cu(a,b)
    unsigned, intent(in) :: b
    type(uc), intent(out) :: a
    a%u = b
  end subroutine set_cu

  ! Ideally, this should be provided as an intrinsic, not necessarily
  ! in the form as shown here.  An alternative would be a logical
  ! function which does not return the result.

  recursive elemental subroutine chk_add (c, a, b, overflow)
    unsigned, intent(out) :: c
    unsigned, intent(in) :: a, b
    logical, intent(out) :: overflow
    c = a + b
    overflow = c < a
  end subroutine chk_add

end module checked_unsigned

program main
  use checked_unsigned
  implicit none
  type(uc) :: a
  a = huge(a%u)
  print '(Z8.8)',a + 5u
end program main

Based on this, it makes more sense to extend J3/24-116 with user-accessible overflow-checking intrinsics, especially since the overflow for multiplication is easier if one has access to widening multiplication that is widely implemented in hardware, like the compiler does. (Footnote: Only needed for the largest KIND of unsigned that the processor supports).

To anybody who thinks this is too verbose: If this finds acceptance, I volunteer to write a module which encompasses all variants from UINT8 to UINT64. I will cheat by using a Perl script to write this, though.

@certik : Could equivalent functionality also be implemented using templates?

[PierUgit]

For people who want saturating or checked or ... arithmetic, here is an implementation - changing a parameter in user code changes the behavior. A user who desires different behavior could easily change that parameter; this
would even be more finely grained than a general compiler switch.

So there would be something like

call checked_unsigned_behavior(uc_check|uc_nocheck|uc_saturate)

Right?

If yes, tell me how this is fundamentally different from what I proposed earlier with a kind of directive unsigned arithmetic uncheck|modular|saturate (if the directive is absent, the arithmetic operations are not allowed at all), for which you said "not my cup of tea"? And there's no need of a derived type for this.

Moreover: any arithmetic operation on such a derived type would go through several function calls, some tests, etc... Doesn't sound good for performances...

And what if one wants unchecked behavior for maximum performances (call checked_unsigned_behavior(uc_nocheck), but want to temporaly enable checks to debug? Usually, with a type having an undefined overflow behavior, one just use a compiler option e.g. -fcheck=..., without touching the source code. But if the intrisic type on which your module is based has a defined overflow behavior (wrapping) then the compiler will have no error to report. Instead, the user has to temporarily convert all the call checked_unsigned_behavior(uc_nocheck) to call checked_unsigned_behavior(uc_check).

[tkoenig1]

For people who want saturating or checked or ... arithmetic, here is an implementation - changing a parameter in user code changes the behavior. A user who desires different behavior could easily change that parameter; this
would even be more finely grained than a general compiler switch.

So there would be something like

call checked_unsigned_behavior(uc_check|uc_nocheck|uc_saturate)

Right?

If the user wants, and implements, that, yes, but I would not expect this to be in frequent use. Otherwise no; I would envision having a parameter in a module being the most common case, and people would then change that parameter
and recompile.

If yes, tell me how this is fundamentally different from what I proposed earlier with a kind of directive unsigned arithmetic uncheck|modular|saturate

Very much different - user code vs. some sort of pragma, which Fortran currently does not have. A user could also have finer control by using different types.

(if the directive is absent, the arithmetic operations are not allowed at all), for which you said "not my cup of tea"? And there's no need of a derived type for this.

A user-defined derived type can be tailored exactly towards what the user wants.

Moreover: any arithmetic operation on such a derived type would go through several function calls, some tests, etc... Doesn't sound good for performances...

Modern compilers are quite good at inlining, and LTO exists for a reason.

And what if one wants unchecked behavior for maximum performances (call checked_unsigned_behavior(uc_nocheck), but want to temporaly enable checks to debug? Usually, with a type having an undefined overflow behavior, one just use a compiler option e.g. -fcheck=..., without touching the source code. But if the intrisic type on which your module is based has a defined overflow behavior (wrapping) then the compiler will have no error to report. Instead, the user has to temporarily convert all the call checked_unsigned_behavior(uc_nocheck) to call checked_unsigned_behavior(uc_check).

This is based on the assumption of checking being changed on runtime, which I assume will not be a frequent occurence.

It will be interesting if Fortran's templates are powerful enough to offer a different solution, though; this might be preferred.

[PierUgit]

I will answer the rest of your post later on, but just about this:

Moreover: any arithmetic operation on such a derived type would go through several function calls, some tests, etc... Doesn't sound good for performances...

Modern compilers are quite good at inlining, and LTO exists for a reason.

Not only this puts all the burden on the compilers, but I'm not sure thay are as good as you say for that. At least this can hardly be a general statement.

I took your module and just changed unsigned to integer to be able to test the performances with a production compiler (gfortran 13). I set the "uc_no_check" mode, which is the minimal overhead. And I am summing 100 times two integer arrays of size 10**7. Summing the intrinsic integers is about 8 times faster than summing the integers that are encapsulated in a derived type:

$ gfortran -O3 -march=native -fopenmp unsigned_m.f90 unsigned.f90 && ./a.out
 Addition of intrinsic integers:       0.34460100065916777      seconds
 Addition of encapsulated integers:    2.5247349999845028      seconds
         100
         100

This an old CPU (2011), but I would be surprised if the ratio was completely different with a more recent one.

program foo
use omp_lib
use checked_unsigned
implicit none

integer, allocatable :: a(:), b(:)
type(uc), allocatable :: ua(:), ub(:)
integer :: i, j
integer, parameter :: N=10**7, M=100
double precision :: tic, toc

allocate( a(N), b(N), ua(N), ub(N) )

a(:) = 1
b(:) = 0
ua(:) = a
ub(:) = b

tic = omp_get_wtime()
do j = 1, M
   b = b + a
end do
toc = omp_get_wtime()

print*, "Addition of intrinsic integers:     ",toc-tic, "seconds"

tic = omp_get_wtime()
do j = 1, M
   ub = ub + ua
end do
toc = omp_get_wtime()

print*, "Addition of encapsulated integers: ",toc-tic, "seconds"

print*, b(1)
b = ub
print*, b(1)

end 

[kargl]

I took your module and just changed unsigned to integer to be able to test the performances with a production compiler (gfortran 13). I set the "uc_no_check" mode, which is the minimal overhead. And I am summing 100 times two integer arrays of size 10**7. Summing the intrinsic integers is about 8 times faster than summing the integers that are encapsulated in a derived type:

What you have demonstrated is that benchmarking is difficult and one often finds what one is looking for.

A simply modification of your program (see below) removes the loop overhead and gives

 % gfcx -c -O3 -march=native -mtune=native p1.f90 
 % gfcx -o z -O3 -march=native -mtune=native p2.f90 p1.o -funsigned -fopenmp 
 % ./z
 Addition of intrinsic integers:        1.3563246487174183      seconds
 Addition of encapsulated integers:    2.8749521519057453      seconds
     100
     100

 % gfcx -c -O3 -march=native -mtune=native -flto p1.f90
 % gfcx -o z -O3 -march=native -mtune=native p2.f90 p1.o -funsigned -fopenmp -flto
 % ./z
  Addition of intrinsic integers:        1.3533457750454545      seconds
  Addition of encapsulated integers:    1.4680523253045976      seconds
     100
     100

p1.f90 is presumably the same as your modified module. p2.f90 is my modification to your code (see below).
This is on an ancient AMD Phenom(tm) II X2 560 Processor.

program foo
use omp_lib
use checked_integer
implicit none

integer, allocatable :: a(:), b(:)
type(uc), allocatable :: ua(:), ub(:)
integer :: i, j
integer, parameter :: N=10**7, M=100
double precision :: tic, toc, tot

allocate( a(N), b(N), ua(N), ub(N) )

a(:) = 1
b(:) = 0
ua(:) = a
ub(:) = b

tot = 0
do j = 1, M
   tic = omp_get_wtime()
   b = b + a
   toc = omp_get_wtime()
   tot = tot + (toc - tic)
end do

print*, "Addition of intrinsic integers:     ",tot, "seconds"

tot = 0
do j = 1, M
   tic = omp_get_wtime()
   ub = ub + ua
   toc = omp_get_wtime()
   tot = tot + (toc - tic)
end do

print*, "Addition of encapsulated integers: ",tot, "seconds"

print*, b(1)
b = ub
print*, b(1)

end 

[tkoenig1]

Let's see what a modern compiler can actually do:

$ cat cu.f90 
module cu
  implicit none
  private
  public :: uc, operator(+), assignment(=)
  type uc
     unsigned :: u
  end type uc
  enum, bind(c)
     enumerator :: uc_no_check = 0, uc_check=1, uc_saturating = 2
  end enum
  integer, parameter :: this_check = uc_no_check

  interface operator(+)
     procedure checked_add_uc
     procedure checked_add_cu
     procedure checked_add_cc
  end interface operator(+)
  interface assignment(=)
     procedure set_uc
     procedure set_cu
  end interface assignment(=)
contains
  recursive elemental function checked_add_uc(a,b) result(c)
    unsigned, intent(in), value :: a
    type(uc), intent(in), value :: b
    type(uc) :: c
    logical :: overflow
    select case (this_check)
    case (uc_no_check)
       c%u = a + b%u
    case (uc_check)
       call chk_add (c%u, a, b%u, overflow)
       if (overflow) error stop
    case (uc_saturating)
       call chk_add (c%u, a, b%u, overflow)
       if (overflow) c%u = huge(c%u)
    end select
  end function checked_add_uc

  recursive elemental function checked_add_cu(a,b) result(c)
    type(uc), value :: a
    unsigned, value :: b
    type(uc) :: c
    logical :: overflow
    select case (this_check)
    case (uc_no_check)
       c%u = a%u + b
    case (uc_check)
       call chk_add (c%u, a%u, b, overflow)
       if (overflow) error stop
    case (uc_saturating)
       call chk_add (c%u, a%u, b, overflow)
       if (overflow) c%u = huge(c%u)
    end select
  end function checked_add_cu

  recursive elemental function checked_add_cc(a,b) result(c)
    type(uc), intent(in), value :: a, b
    type(uc) :: c
    logical :: overflow
    select case (this_check)
    case (uc_no_check)
       c%u = a%u + b%u
    case (uc_check)
       call chk_add (c%u, a%u, b%u, overflow)
       if (overflow) error stop
    case (uc_saturating)
       call chk_add (c%u, a%u, b%u, overflow)
       if (overflow) c%u = huge(c%u)
    end select
  end function checked_add_cc

  recursive elemental subroutine set_uc(a,b)
    type(uc), value :: b
    unsigned, intent(out) :: a
    a = b%u
  end subroutine set_uc
  recursive elemental subroutine set_cu(a,b)
    unsigned, intent(in), value :: b
    type(uc), intent(out) :: a
    a%u = b
  end subroutine set_cu

  ! Ideally, this should be provided as an intrinsic, not necessarily
  ! in the form as shown here.  An alternative would be a logical
  ! function which does not return the result.

  recursive elemental subroutine chk_add (c, a, b, overflow)
    unsigned, intent(out) :: c
    unsigned, value :: a, b
    logical, intent(out) :: overflow
    c = a + b
    overflow = c < a
  end subroutine chk_add

end module cu
$ cat foo.f90 
program foo
  use cu
  implicit none

  unsigned, allocatable :: a(:), b(:)
  type(uc), allocatable :: ua(:), ub(:)
  integer :: i, j
  integer, parameter :: N=10**7, M=100
  double precision :: tic, toc

  allocate( a(N), b(N), ua(N), ub(N) )

  a(:) = 1u
  b(:) = 0u
  ua(:) = a
  ub(:) = b

  call cpu_time(tic)
  do j = 1, M
     b = b + a
  end do
  call cpu_time(toc)

  print*, "Addition of intrinsic integers:     ",toc-tic, "seconds"

  call cpu_time(tic)
  do j = 1, M
     ub = ub + ua
  end do
  call cpu_time(toc)

  print*, "Addition of encapsulated integers: ",toc-tic, "seconds"

  print*, b(1)
  b = ub
  print*, b(1)
end program foo
$ gfortran -flto  -O3  -march=native -funsigned cu.f90 foo.f90 
$ ./a.out
 Addition of intrinsic integers:       0.17165799999999998      seconds
 Addition of encapsulated integers:   0.15055099999999999      seconds
         100
         100

Note that this is without checking (see the parameter). If you want checking, or if you want to be able to change it at runtime, you will pay a price in performance. Duh.

I think the performance argument has been laid to rest.

[PierUgit]

What you have demonstrated is that benchmarking is difficult and one often finds what one is looking for.

A simply modification of your program (see below) removes the loop overhead and gives

OK that benchmarking is difficult. That said, making the same changes as in your code (i.e. moving the calls to omp_get_wtime() inside the loops) doesn't reduce the total times in my case:

$ gfortran -O3 -march=native -fopenmp unsigned_m.f90 unsigned.f90 && ./a.out
 Addition of intrinsic integers:       0.72970699891448021      seconds         100
 Addition of encapsulated integers:    2.7904760027304292      seconds         100

On the contrary both timings have an additional ~+0.35 sec.. I tend to give more credit to the timings that are made outside of the loop, and I am (naively ?) expecting the loop overhead with 100 iterations to be quite low compared to the total 10**9 additions (and moreover I am expecting the overhead to be the same for the two cases).

That said, what I am also timing here are the RAM<->CPU transfers (but again, the extra cost is the same for the two cases).

[kargl]

@PierUgit, what overhead does -fopenmp add?

You seem to miss that both @tkoenig1 and I used the -flto option in execution of our benchmarks. This shows that it is a wash. Here's Thomas's result again.

 $ gfortran -flto  -O3  -march=native -funsigned cu.f90 foo.f90 
 $ ./a.out
 Addition of intrinsic integers:       0.17165799999999998      seconds
 Addition of encapsulated integers:   0.15055099999999999      seconds
     100
     100

BTW, I modified my version of your benchmark to RDTSC. Without the -flto option, ub = ub + ua took twice as many ticks than b = b + a. With -flto, the unsigned addition was marginally faster.

More importantly, the module does not even need to physically exist. A compiler can generate the module on the fly. One of uc_no_check = 0, uc_check=1, uc_saturating = 2 will be present in the source code, and the compiler can just do the right thing. This then would eliminate the complications of a recursive elemental reference.

[PierUgit]

You seem to miss that both @tkoenig1 and I used the -flto option in execution of our benchmarks.

I noticed the -flto in @tkoenig1 's post, but indeed missed it in your post, as your comment was apparently focused on moving the timings inside the loop because of some "loop overheads"

[PierUgit]

I think the performance argument has been laid to rest.

I guess that with -flto the compiler can take full advantage of the elemental nature of the procedure? What more surprises me is that even by forcing scalar computations only, and modifying your module to have a runtime selection of the mode (this_check being a public variable instead of a private constant) the timings are similar between the intrisic integers and the encapsulated integer. I would expect an extra cost due to the select case on each call of the checked_add_* function.

Anyway, as I wrote earlier I wanted to comment the rest of your post:

So there would be something like

call checked_unsigned_behavior(uc_check|uc_nocheck|uc_saturate)

Right?

If the user wants, and implements, that, yes, but I would not expect this to be in frequent use. Otherwise no; I would envision having a parameter in a module being the most common case, and people would then change that parameter and recompile.

So it would be a module that everyone would copy, possible modify, adapt to their own need, etc... IMO this would soon be a mess, with similar but incompatible versions. Assuming that an approach with a module was eventually retained, it should definitly be a standard module (iso_unsigned_checked) or at the very least a module in stdlib (aiming at being standard at some point).

The consequence is that the mode chek/nocheck/saturate should be selectable at runtime.

If yes, tell me how this is fundamentally different from what I proposed earlier with a kind of directive unsigned arithmetic uncheck|modular|saturate

Very much different - user code vs. some sort of pragma, which Fortran currently does not have.

The mechanism is different, the effect is the same.

I don't think anyway that "Fortran hasn't the feature xxx" is a strong argument: if the feature is useful, then it can be considered. And isn't implicit already some sort of pragma?

(if the directive is absent, the arithmetic operations are not allowed at all), for which you said "not my cup of tea"? And there's no need of a derived type for this.

A user-defined derived type can be tailored exactly towards what the user wants.

My point of view is that if we have to consider a user-defined derived type from the start of the design of a new intrisic type, it's maybe a sign that the design is not the best one and that a workaround is needed. Derived types are not as convenient as a first class intrisic types, they have various limitations... It doesn't seem to me that the iso_varying_string module has been very successful for instance.

[klausler]

The consequence is that the mode chek/nocheck/saturate should be selectable at runtime.

No. That's not how the hardware works, so you're asking for compiler-generated code to branch based on an environment variable value or some other dynamic selection. That would perform badly.

And isn't implicit already some sort of pragma?

No. Any program that is correct with IMPLICIT statements remains correct and behaves identically with those IMPLICIT statements deleted.

Correction: I mean IMPLICIT NONE statements.

[tkoenig1]

My point of view is that if we have to consider a user-defined derived type from the start of the design of a new intrisic type, it's maybe a sign that the design is not the best one and that a workaround is needed.

That is not a good argument to make in language design - if I can use A as a building block for B, it does not mean that B should also be included of necessity. This way lies the feature stampede of C++.

[PierUgit]

The consequence is that the mode chek/nocheck/saturate should be selectable at runtime.

No. That's not how the hardware works, so you're asking for compiler-generated code to branch based on an environment variable value or some other dynamic selection. That would perform badly.

What hardware? I was talking about the module proposed by @tkoenig1 : it contains a parameter to select the desired behavior at compile time. Just making it a variable enables selecting the behavior at runtime.

And isn't implicit already some sort of pragma?

No. Any program that is correct with IMPLICIT statements remains correct and behaves identically with those IMPLICIT statements deleted.

Mmmhhh...

implicit integer(a-z)
x = 2.5
print*, x
end

Doesn't behave the same if the implicit statement is removed.

[PierUgit]

My point of view is that if we have to consider a user-defined derived type from the start of the design of a new intrisic type, it's maybe a sign that the design is not the best one and that a workaround is needed.

That is not a good argument to make in language design - if I can use A as a building block for B, it does not mean that B should also be included of necessity. This way lies the feature stampede of C++.

It's not "of necessity", and that's why I also used the word "maybe". But at the very least there should be discussions about that point, up to the committee level. And I am completely fine if at the end the conclusions are "better not including B in the language"... As long as it has been discussed.

[certik]

I agree with @PierUgit, things must be discussed. The committee sometimes has good internal discussions but not always, so it's not a guarantee either. My plan is to prepare the proposal in the coming weeks, and summarize the discussion so far, and we can discuss more, I also want to do a prototype.

@klausler, @tkoenig1 what is the best way for a Fortran compiler to do bounds checking for signed integers? For example using LLVM, do you recommend using the llvm.sadd.with.overflow.* style intrinsics? It looks like on x86 it uses the jo instruction and on arm it uses the adds / bvs instructions.

[gronki]

it contains a parameter to select the desired behavior at compile time

Which, again, I think was and will always be an awful idea. The scoping of this would have to be very narrow, and there would be issues if you need to use both types of operation (overflowing and trapping) in one function or even worse -- one expression.

As shown by your example with implicit, this is exactly why it is considered obsolete (besides none which is its last mission in Fortran ever): the same snippet of code will behave differently depending on the context. Any kind of design which has some "state" or "scoped switch" is bad from the start and Fortran has been moving away from that for the past 30 years.

I still do not think there is any way other than using + for trapping and intrinsic functions for wrapping behavior (or vice versa). Maybe it is verbose, but at least it will not cause everyone to clench their fist in anger in 10 years, like implicit save does today.

[klausler]

I've merged -funsigned into f18.