# reliably checking for overflow before addition?

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 06-21-2008
cyberfish
reliably checking for overflow before addition?
Is there a reliable way to check for overflow before addition, without casting to a bigger type, or go into assembly to check the carry flag?

If I understand it correctly, the classic way -
Code:

```u32 a; if ((a+10) < 10) //overflow```
is not reliable since overflow is not defined, and the compiler can and do optimize the check away.
• 06-21-2008
CornedBee
The overflow of unsigned numbers is defined. They use modulo arithmetic.

For signed numbers, there is no portable way.
• 06-21-2008
dwks
Why not something like this?
Code:

```#include <climits> int addition_will_overflow(int x, int y) {     if(INT_MAX - x >= y) return 0;     // the addition will overflow     return 1; }```
That only works for positive numbers, but I'm sure you could figure something out for negative ones too . . . .
• 06-21-2008
grumpy
Close dwks. There are two circumstances when computing x+y (both ints) will overflow:

1) When both are positive, and INT_MAX - x < y; OR

2) When both are negative, and INT_MIN - x < y

I'll leave it as an exercise to work out if adding a positive to a negative value overflows, if adding zero overflows, what happens when computing INT_MAX - x (x positive), or what happens when computing INT_MIN - x (for x negative).

Incidentally, INT_MAX and INT_MIN are represented as std::numeric_limits<int>::max() and std::numeric_limits<int>::min() respectively in C++.
• 06-21-2008
cyberfish
Quote:

The overflow of unsigned numbers is defined. They use modulo arithmetic.

For signed numbers, there is no portable way.
Thanks. Nice to know.

Quote:

I'll leave it as an exercise to work out if adding a positive to a negative value overflows, if adding zero overflows, what happens when computing INT_MAX - x (x positive), or what happens when computing INT_MIN - x (for x negative).
The answer is they all don't overflow?

From dwks's code and grumpy's hint -
Code:

```bool addition_will_overflow(int a, int b) {         if (a > 0 && b > 0) {                 return (INT_MAX - a) < b;         } else if (a < 0 && b < 0) {                 return (INT_MIN - a) > b;         }         return false; }```
Is that it?
• 06-21-2008
Elysia
Quote:

Originally Posted by grumpy
Incidentally, INT_MAX and INT_MIN are represented as std::numeric_limits<int>::max() and std::numeric_limits<int>::min() respectively in C++.

And I still don't understand why they made them runtime functions.
You could alternatively use boost::integer_traits<int>::const_max or boost::integer_traits<int>::const_min.
They're constant, so that's far better than std's implementation.
• 06-21-2008
grumpy
Quote:

Originally Posted by Elysia
And I still don't understand why they made them runtime functions.

There is no requirement they be runtine functions.

std::numeric_limits<int>::min() and max() return implementation defined values, with nothing preventing them being inlined at compile time. In practice, it is not difficult for compilers to inline such functions (they are simply a getter) and the return value is usually substituted directly in place of the "function call" at compile time.

In other words, there is nothing in the standard that requires these functions to be evaluated at runtime and, in practice, they usually are not.
Quote:

Originally Posted by Elysia
You could alternatively use boost::integer_traits<int>::const_max or boost::integer_traits<int>::const_min.
They're constant, so that's far better than std's implementation.

Just a different way of achieving the same thing.
• 06-21-2008
Elysia
Quote:

Originally Posted by grumpy
There is no requirement they be runtine functions.

std::numeric_limits<int>::min() and max() return implementation defined values, with nothing preventing them being inlined at compile time. In practice, it is not difficult for compilers to inline such functions (they are simply a getter) and the return value is usually substituted directly in place of the "function call" at compile time.

In other words, there is nothing in the standard that requires these functions to be evaluated at runtime and, in practice, they usually are not.

Perhaps. But then again, perhaps not.
Do they return constant values?
If not, that's a major oversight on their part, because it severely hinders what can be done at compile time, especially with meta-programming.

Quote:

Just a different way of achieving the same thing.
• 06-21-2008
grumpy
Quote:

Originally Posted by Elysia
Perhaps. But then again, perhaps not.
Do they return constant values?

std::numeric_limits<T>::min() and max() return the minimum and maximum finite value of the type respectively - and those values are implementation defined constants (ie in the case of int they are INT_MIN and INT_MAX respectively).
Quote:

Originally Posted by Elysia
If not, that's a major oversight on their part, because it severely hinders what can be done at compile time, especially with meta-programming.

That is not true: C++ templates are specified as a compile-time, Turing-complete, meta-language ie the process of template expansion can be implemented completely and optimised at compile time. There is a pile of information freely available on such things; look up the topic of "Compile-time code optimization" - interestingly inlining of functions is one of the simplest metaprogramming techniques.
Quote:

Other than convenience of syntax, I'd be curious to know what you consider those to be. (I exclude syntax, because the notion of "best" or "advantageous" is highly subjective when it comes to elements of syntax -- we could debate different ideas about syntax for months, and both be completely correct at the same time by some measure).
• 06-21-2008
Elysia
Well, maybe I am underestimating what the compiler can do, but I would still like to prefer boost's syntax, at least.
• 06-21-2008
CornedBee
OK, let's see. The return values of numeric_limits::min() and max() are not compile-time constants from the language point of view, for the simple reason that function return values never are. This is not a performance problem, since these functions will most definitely be inlined by any even halfway decent compiler, but it matters because compile-time constants are required in some circumstances. In particular, you can't use min() and max() as array bounds or as non-type template parameters.

There are some very good reasons to make them functions. Peculiarly enough, one of those reasons is performance. Consider:
Code:

```// This is <limits> template <> struct numeric_limits<float> {   static float min() { return <minimal floating point value>; } };```
This is what a specialization of numeric_limits looks like in the standard. The compiler, seeing a call of min(), would simply inline the function and find out that it's dealing with a simple literal, opening up a lot of new optimization opportunities.

Let's examine the possibilities if it's a static constant variable.
Code:

```// This is <limits> template <> struct numeric_limits<float> {   static const float min = <minimal floating point value>; };```
Nope, that's an error. Inline initialization is only allowed for integral static constants.

Code:

```// This is <limits> template <> struct numeric_limits<float> {   static const float min; }; template <> const float numeric_limits<float>::min = <minimal floating point value>;```
Nope, that's another error. Specifically, you'll get linker errors from this symbol.

Code:

```// This is <limits> template <> struct numeric_limits<float> {   static const float min; }; // This is limits.cpp, a file linked into the compiler's precompiled standard library. template <> const float numeric_limits<float>::min = <minimal floating point value>;```
Ah yes, that works. Only, now the constant value is no longer accessible to the compiler for further optimization. Oops.

OK, so a compiler that does cross-module optimization might be able to optimize this. If, that is, you're linking against a static version of the runtime. Definitely not if you're linking against a dynamic version.

So by converting the function to a static constant, in the belief that perhaps this is faster, you've actually made it slower.

Here's the good news: C++0x introduces the constexpr keyword, which forces the compiler to evaluate simple functions at compile time if possible. Thus, the result becomes a proper compiler-time constant expression, and you get the best of both worlds.
• 06-21-2008
iMalc
Quote:

Originally Posted by grumpy
C++ templates are specified as a compile-time, Turing-complete, meta-language ie the process of template expansion can be implemented completely and optimised at compile time. There is a pile of information freely available on such things; look up the topic of "Compile-time code optimization" - interestingly inlining of functions is one of the simplest metaprogramming techniques.

As CornedBee says, return results are not constants. You can't use the return result as the size to declare an array, or as a value assigned to an enum etc. As such, I'd say Elysia was correct in that they really aren't useful in Template meta-programming. It's not an oversight though, as demonstrated, there just isn't a better way.

It's not about what it could optimise, it's about what is or isn't legal C++. "Inlining of functions" in template meta-programming isn't about inlining a normal function, it's about writing a template meta-program to replace what would otherwise be a function call, to the point that there is no function call at all, both in the syntax of the entire meta-program itself and where it's used.
E.g:
Code:

```template <unsigned n, unsigned b> struct ceilLogb {         enum { ret = ceilLogb<(n+b-1)/b, b>::ret + 1 }; }; template <unsigned b> struct ceilLogb<1, b> {   enum { ret = 0 }; }; int digits[ceilLogb<MYMAXVAL, 10>::ret];```
instead of the following, which of course cannot compile:
Code:

`int digits[ceil(log10(MYMAXVAL))];`
constexpr sounds really cool, as it seems that it will finally enable actual function calling in template meta-programming, and presumably allow things like that second piece of code to compile!
• 06-22-2008
CornedBee
To a point. The restrictions on constexpr functions are pretty heavy. They must consist of a single return statement. They may not call themselves recursively.
The latter really is trouble.

However, constexpr has other uses too. For example, if you make a constructor constexpr, you can have a compile-time constant instance of the class. If you further make the getters of this class constexpr, the result will stilll be compile-time constant.
• 06-22-2008
Elysia
The first I can understand (maybe), but the second...? Why the heavy restrictions? To make it easier for compilers?
So long as the function contains code that can be determined at compile time, it shouldn't be a problem, even if calls it recursively or return multiple things.
• 06-22-2008
CornedBee
I think it was because they wanted a useful subset of full functionality that can be specified with sane language. If you have the feature of limited evaluation at compile time, then you have to specify in the standard how much "limited" is. If you don't, the feature is useless, because compilers will have different support, meaning that it's very hard to write portable code.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last