Printable View
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 -
is not reliable since overflow is not defined, and the compiler can and do optimize the check away.Code:u32 a;
if ((a+10) < 10) //overflow
The overflow of unsigned numbers is defined. They use modulo arithmetic.
For signed numbers, there is no portable way.
Why not something like this?
That only works for positive numbers, but I'm sure you could figure something out for negative ones too . . . .Code:#include <climits>
int addition_will_overflow(int x, int y) {
if(INT_MAX - x >= y) return 0;
// the addition will overflow
return 1;
}
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++.
Thanks. Nice to know.Quote:
The overflow of unsigned numbers is defined. They use modulo arithmetic.
For signed numbers, there is no portable way.
The answer is they all don't overflow?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).
From dwks's code and grumpy's hint -
Is that it?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;
}
And I still don't understand why they made them runtime functions.Quote:
Originally Posted by grumpy
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.
There is no requirement they be runtine functions.Quote:
Originally Posted by Elysia
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.
Just a different way of achieving the same thing.Quote:
Originally Posted by Elysia
Perhaps. But then again, perhaps not.Quote:
Originally Posted by grumpy
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.
But it has its advantages.Quote:
Just a different way of achieving the same thing.
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
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:
Originally Posted by Elysia
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).Quote:
But it has its advantages.
Well, maybe I am underestimating what the compiler can do, but I would still like to prefer boost's syntax, at least.
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:
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.Code:// This is <limits>
template <>
struct numeric_limits<float>
{
static float min() { return <minimal floating point value>; }
};
Let's examine the possibilities if it's a static constant variable.
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 = <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;
};
template <>
const float numeric_limits<float>::min = <minimal floating point value>;
How about this then?
Ah yes, that works. Only, now the constant value is no longer accessible to the compiler for further optimization. Oops.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>;
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.
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.Quote:
Originally Posted by grumpy
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:instead of the following, which of course cannot compile: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];
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!Code:int digits[ceil(log10(MYMAXVAL))];
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.
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.
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.
Then hopefully we'll be able to get limited evaluation at compile time some time in the future, as they define what limited is. Hopefully.
Making it easier for compiler (or compiler vendors) is one reason. The other common reason is that less restrictions usually mean a lot more possible meanings to be properly specified in the standard (which is a lot of work, as interactions with other language features have to be properly analysed and/or specified). Easier in the first instance (particularly with a large language like C++) to specify something in a restricted manner, and only relax restrictions if there is a real world need to do so.Quote:
Originally Posted by Elysia
Yes, this is very significant also. Remember, you can never back something out of a standard, only add to it, if you want to keep backward compatibility.Quote:
Easier in the first instance (particularly with a large language like C++) to specify something in a restricted manner, and only relax restrictions if there is a real world need to do so.
The only exception I know of is the auto keyword, whose old meaning will be removed completely. That's safe because absolutely nobody used that keyword, and even if someone did, it's completely redundant anyway.
You're right, but it's worth noting there is a defined mechanism for backing things out of the standard: deprecation is essentially flagging a feature for removal from a future version of the standard. Of course, actually removing a previously deprecated feature will break backward compatibility, so it will be interesting to see if any deprecated features in the language ever do disappear in a future version of a standard for C or C++ and - if they do - how many vendors will remove them.Quote:
Originally Posted by CornedBee