 | Author: | “No Bugs” Hare Follow:   |
| Job Title: | Sarcastic Architect | |
| Hobbies: | Thinking Aloud, Arguing with Managers, Annoying HRs, Calling a Spade a Spade, Keeping Tongue in Cheek | |
If you’re not writing in C/C++, please ignore this post; matters discussed here are related to mitigation of certain decisions which were made 50+ years ago and which are pretty much carved in stone now by this 50-years-old tradition. In other words – this is one of those darker pages of C/C++ programming (and an attempt to make it less dark using some recent C++ developments).
Very recently, I was once again tasked with a yet another project of “enabling all the warnings and getting rid of them”. And as always, after enabling -Wall, by far the most annoying warning was “signed/unsigned mismatch” (known as C4018 in MSVC1, and -Wsign-compare in GCC/Clang); all the other warnings (well, if not enabling -pedantic) were very straightforward to deal with, but signed/unsigned mismatch was (as usual) severely non-trivial.
While dealing with all those pesky warnings – I recalled several experiences when
(and however strange it might sound, clients didn’t consider removed warnings in such an occasionally-failing program as a mitigating circumstance, demanding immediate rollback of the offending “fixes”).
The Root of The Problem
Who is to Blame?
TBH, the problem is rather nasty (and IIRC, specific to C/C++ ). It stems from a very generic rule (existing at least since K&R C) which (translating from standardese into my-broken-English) says that if both operands of some operator are of the same size, with one of them being unsigned, and another signed – are converted into unsigned one before the operator is really invoked. When applying this generic rule to comparisons, it means that if we’re comparing a negative signed integer x with an unsigned one y, then, first of all, the signed integer will be converted into unsigned one. At this point, as our signed integer x is negative, and at least when our system uses universal-in-practice “two’s complement” representation,2 it will become a very-large unsigned value (to be exact – 2^N+x, where N is number-of-bits-in-our-int-type). Then, our requested comparison operator will be invoked, comparing 2^N+x with y, which is most of the time not what we really meant when we wrote our code. For example (if you don’t believe me, see https://godbolt.org/g/npTtjY ):
1 | static_assert( -1 < 1U );//fails! |
“we're just narrowly avoiding a disaster without understanding how close we were.And it is not a quirk of a specific compiler: it is how ALL the existing compilers/platforms SHOULD behave, and perfectly according to the standard too. We’re just lucky that this doesn’t happen too often, so most of the time, we’re just narrowly avoiding a disaster without understanding how close we were.
To make things even worse, whenever sizeof(short) is less than sizeof(int), with short types it works differently-from-the-above and actually becomes intuitive on this occasion (because shorts – as well as all other “smaller-than-int” types – are implicitly “promoted” to signed ints before comparison):3
1 | static_assert( short(-1) < (unsigned short)(1) );//stands! |
And if we take operands of different sizes, the whole thing becomes very-strange-unless-you-know-how-conversions-are-written-in-the-standard:4
1 2 | static_assert( int64_t(-1) < 1U );//stands! - because converted to larger which is signedstatic_assert( -1 < uint64_t(1) );//fails! - because converted to larger which is unsigned |
Overall, the logic above (while formally defined in all C/C++ standards to date) – is very non-obvious and extremely-easy-to-forget-about even if you happen to know it by heart (I have to admit that I don’t, and have to think for some time until providing an answer to “what the result will be” in each particular case). Therefore – it makes perfect sense for the compiler to issue that signed/unsigned warning.
How To Fix It
What Is To Be Done?
While this signed/unsigned situation (which we’re informed about with a compiler warning) is indeed rather nasty,
While this warning does indicate potential problems with our code – explicit casts (whether it is C-style cast or static_cast<>) are usually even worse to our code than those-potential-signed-unsigned-problems above. In particular, IIRC, all the problems-I’ve-seen with a perfectly-working-program becoming an occasionally-non-working one as a result of “fixing” the warning, were due to improper use of explicit casts.
In other words,
TBH, changing some type (usually from signed to unsigned) – which is usually an ideal-solution-for-this-kind-of-issues at least from a performance point of view – is not that much safer than explicit casts in the short run (though it is indeed less fragile in the long run). Personally, I usually prefer to add an assert(x>=0) for each such type change (to ensure that the value-which-I-think-should-never-be-negative, is indeed never negative; as long as this stands, the conversion from signed to unsigned becomes perfectly safe). But even such an assertion (which we might or might not run into during our tests) doesn’t qualify as really safe.
An Idea
After thinking for a while about it – I came up with an idea, which IMO might help us to keep relevant code reasonably-readable – and without those pesky warnings (and more importantly, without results of such comparisons being counter-intuitive).
It is apparently possible to write a template function which performs all the comparisons between arbitrary integer types in a manner which is perfectly consistent with our intuitive expectations; moreover, with C++17 if constexpr, it is possible to write such a function in a manner which (saving for compiler optimization glitches) won’t cause any performance degradation beyond absolutely necessary. Saving for potential bugs, such a function is presented below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | namespace intuitive {template<class TA, class TB>inline constexpr bool lt(TA a, TB b) { using MAX_EFFICIENT_INT = intptr_t;//platform-dependent, but intptr_t is not a bad starting point static_assert(std::is_integral<TA>::value); static_assert(std::is_integral<TB>::value); constexpr bool aSigned = std::is_signed<TA>::value; constexpr bool bSigned = std::is_signed<TB>::value; if constexpr(aSigned == bSigned) return a < b;//both signed or both unsigned - no casts required, C promotions will do just fine else {//different is_signed, let's make TSIGNED always-signed, and TUNSIGNED - always-unsigned using TSIGNED = typename std::conditional<aSigned,TA,TB>::type; using TUNSIGNED = typename std::conditional<aSigned,TB,TA>::type; static_assert(sizeof(TSIGNED)+sizeof(TUNSIGNED)==sizeof(TA)+sizeof(TB));//self-check if constexpr(sizeof(TSIGNED)>sizeof(TUNSIGNED)) return a < b;//again, no casts required, C promotions will do just fine (promoting b to TA which is signed) if constexpr(sizeof(TUNSIGNED)<sizeof(int)) { return a < b;//again, no casts required, C promotion-to-int will do just fine (promoting both to int which is signed) } //at this point, we have sizeof(TUNSIGNED) >= sizeof(TSIGNED) => no-cast will be counterintuitive if constexpr(sizeof(TUNSIGNED)<sizeof(MAX_EFFICIENT_INT)) { //we can cast unsigned to MAX_EFFICIENT_INT if constexpr(aSigned) { assert(!bSigned); return a < MAX_EFFICIENT_INT(b); } else { assert(bSigned); return MAX_EFFICIENT_INT(a) < b; } } else { //last resort: expression assert(sizeof(TUNSIGNED)>=sizeof(TSIGNED)); if constexpr(aSigned) { //return a<0 ? true : TUNSIGNED(a) < b; return (a<0) | (TUNSIGNED(a) < b);//sic - single '|'; // equivalent to the above but seems to perform better under GCC (avoids branch) } else { assert(bSigned); //return b<0 ? false : a < TUNSIGNED(b); return (b>=0) & (a < TUNSIGNED(b));//sic - single '&'; // equivalent to the above but seems to perform better under GCC (avoids branch) } } }}}//namespace |
NB: very very formally, it is probably required to replace sizeof() comparisons with std::numeric_limits<> comparisons, but for any platform I can imagine, I expect sizeof() to produce exactly the same result (but if you know it is not the case – please give me a shout).
The idea is pretty simple: with a template function intuitive::lt having both its parameters as template parameters, we have both types in our hands, so we can perform some type math to determine an optimal way of performing intuitive conversion (and in quite a few cases, simplistic a<b can do the trick). Then, using results of this math, and if constexpr, we can force our compiler to choose only that variation which is really necessary for given TA and TB.
With this function, all the following static_asserts will stand (to test it, see https://godbolt.org/g/znwD8y ; the code works starting from clang 3.9 and GCC7; also works under MSVC 19.12, but 19.12 is not available on godbolt (yet?)):
1 2 3 4 | static_assert( intuitive::lt(-1,1U) );//standsstatic_assert( intuitive::lt(short(-1),(unsigned short)(1)) );//standsstatic_assert( intuitive::lt(int64_t(-1), 1U) );//standsstatic_assert( intuitive::lt(-1,uint64_t(1)) );//stands |
IMO, it is pretty intuitive that -1 is less than 1, regardless of the types we’re using to represent -1 and 1 (one point which might be less intuitive is that intuitive::eq(-1,unsigned(-1)) returns false, but it should be this way for consistency).
NB: when the post was ready, I run into [Walker], where implementation is different (on the first glnce, [Walker] seems to be slower, causing unnecessary branching at least under GCC), but the overall idea of achieving “safe” [Walker] or “intuitive” (this-post) comparison is very similar.
Generated Asm
TBH, I didn’t perform proper performance testing of intuitive::lt function (for such small pieces, it way too much depends on the context); instead, I used Compiler Explorer to see generated asm for intuitive::lt for different types under different compilers and to compare it to the code generated for usual C-style comparisons. Results (for x64, and as always, to be taken with a huge pile of salt):
| Operation | Clang 5 (asm ops/CPU cycles estimate) | GCC 7.3 (asm ops/CPU cycles estimate) | Comment |
|---|---|---|---|
| C-style int<int | 1/1 | 1/1 | |
| C-style int<unsigned | 1/1 | 1/1 | |
| C-style int<unsigned short | 2/2 | 2/2 | |
| C-style int<uint64_t | 2/2 | 2/2 | |
| C-style int64_t<unsigned | 2/2 | 2/2 | |
| intuitive::lt(int,int) | 1/1 | 1/1 | Same result, same code |
| intuitive::lt(int,unsigned) | 3/2.5 | 3/2.5 | Improved result, still very fast |
| intuitive::lt(int,unsigned short) | 2/2 | 2/2 | Same result, same code |
| intuitive::lt(int,uint64_t) | 5/4 | 5/45 | Improved result, the worst case for intuitive::lt performance-wise. Kudos to clang (and see footnote re. GCC) |
| intuitive::lt(int64_t,unsigned) | 2/2 | 2/2 | Same result, same code |
“there is a chance that intuitive::lt MIGHT be a good thing to make behaviour of our C++ code to correspond better to our-expectations-when-we're-reading-itAs we can observe:
- whenever intuitive version happens to provide the same result as C-style one – the cost is exactly the same. In other words, we’re NOT paying for whatever-we’re-NOT-using
- Costs in other cases are still very low; even in the worst-case, the costs are comparable to the cost of usual conversions. Moreover, for most of the app-level code, conversions (including casts) are perceived to be “free”, and even being 2x more than that shouldn’t be too bad.
Conclusion
With all the troubles which arise both from the extremely counter-intuitive signed/unsigned comparisons (and well-intended but poorly-implemented attempts to get rid of them) – there is a chance that intuitive::lt (which, with its counterparts gt, le, ge, eq, and ne is BTW available at https://github.com/ITHare/util) – MIGHT be a good thing to make behaviour of our C++ code to correspond better to our-expectations-when-we’re-reading-it. Whether it really happens to be a Good Thing(tm) in the long run – is yet to be seen.
Oh, and if somebody can rewrite the code above so it flies even with a C++11-based compiler (replacing if constexprs with template instantiations, for example, along the lines of [Walker]) – such contributions will be very welcome 6.
References
Acknowledgement
Cartoons by Sergey Gordeev
from Gordeev Animation Graphics, Prague.
Note that K&R used the unsigned preserving approach which is different than the value preserving approach used by both ANSI C and C++. So the following expression:
(unsigned char)1 > -1
would false for K&R and true for ANSI C and C++. I only know this wacky trivia because I once looked into how to tell you are using C or C++ and which version using the same code: https://github.com/shafik/determine_c_or_cpp
I guess in some ways this is worse because there must some ancient code out there that relies on this behavior but trying to port it to a modern compiler would break in weird ways.
I also quote some of the relevant sections from the C99 rationale document in my Stack Overflow answer here: https://stackoverflow.com/a/24372323/1708801
Thanks, I didn’t know it (TBH, it causes even more
Your select_type template already exists in the standard library; it’s called std::conditional (in ).
That was meant to read (in <type_traits>), I didn’t realise your comment box used HTML.
Re. std::conditional: I thought it should exist, but it was easier to write it than to search for it :-). Changed it in the text, on godbolt link, and in the library, thanks!
Why not we just use int instead of unsigned int on occasions when we know we need to compare our int and unsigned int variables ?
Also the picture cover picture shows the compiler returns 0, shouldn’t it return 1 thou ?
You mean casting unsigned to signed? It will help in some cases, but will ruin some other ones. The whole problem is about signed and unsigned of the same size having different ranges of values-they-can-represent, and whatever-conversion-within-the-same-size we use – we cannot possibly represent all the range from MIN_INT to MAX_UINT (which is simply more than 2^N). For example, for 8-bit integers: int8_t can represent values from -128 to 127, and uint8_t – from 0 to 255; to represent values from -128 to 255 (which would solve all the problems) – 8 bits is not enough, so we have to cast to some-larger-type – and if it is unavailable, we have to use expressions :-(.
EDIT:
> Also the picture cover picture shows the compiler returns 0, shouldn’t it return 1 thou ?
“Compiler returns 0” implies that static_assert() above stands…
Check https://www.reddit.com/r/cpp/comments/82hmsc/c_thoughts_on_dealing_with_signedunsigned_mismatch/dva91ho/
Checked, answered. Short summary: as it is known from maths, for elements of an empty set, every universal statement is true; for our case, it translates into “as the systems other than 2’s-complement don’t really exist at least in C++ world and are extremely unlikely to appear in the future – all the heated arguments about them are pretty much pointless”.
Do you have an example of “turned a perfectly-working-program-with-warnings, into a program-without-warnings-but-which-fails-once-a-day-or-so”?
It isn’t easy to give an example which isn’t obviously wrong, but in the real-world code, it happened in my projects several times (one guy has managed to mess another guy’s code so badly, that it was FUBAR, and we had to roll this bunch of changes back). IIRC, it was about dealing with the warning in some relatively-complicated expressions, and using integer-of-the-wrong-size when adding the explicit cast; for any 5-line example I can write – the error will be trivially recognizable, but when dealing with a 100-LoC function – it becomes easy to mess it up.
Overall, casts are evil (they tell compiler “shut up and do what I tell”) – and IMNSHO substantially more evil than quite a few compiler warnings. Especially so when casts are added as an afterthought, by somebody who has no idea what was the original intention at that point.
So, the weirdness of integer promotions became far less weird to me when I was reading about the history of C. It started out as a project to port the B language implementation they had, which targeted the PDP-7 that the initial versions of Unix were developed on, to their new PDP-11/20 which would give them room to really work on the OS.
B was Ken Thompson’s version of BCPL; both were typeless languages that operated only on machine word sized values. This fit well with the PDP-7 and earlier computers that were word-addressed; you could only ever load or store word-size elements and obviously the ALU would work on the same word size. But the PDP-11 had byte-addressed memory (with 8-bit bytes, which was not yet as solidified as it is now) and instructions for loading/storing full words and half-words (bytes).
As Dennis Ritchie was porting the B compiler to the PDP-11, he realized that having non-uniform data widths and different instructions for working with loading/storing them meant that the compiler would have to keep track of the storage size so it could generate the appropriate instructions and keep track of alignment when allocating. Since the PDP/11 promised to have a floating point add-on module as well, he decided that there was nothing to do but add a type system, which he borrowed largely from the work that had been done on Algol 68. After adding types and structures, Ken and Dennis decided that this new version of B was changed enough to have its own name, and thus C was born.
Anyway, loading a sub-word value from memory will naturally put it in a word-length register, which necessitates either a sign-extension or zero-extension. In a word-oriented language like B you would have to manually extract a sub-word value and perform the appropriate extension yourself before operating on the value. In a byte-addressed language like C, the machine does it for you depending on the type. But since there was no real notion of smaller-than-word data in B, and operations always acted on word-size data, the semantics of ALU operations remained the same in C rather than being type-constrained somehow.
This probably seemed like the most sensible and straightforward thing to do, and changed the meaning of things as little as possible–it wasn’t initially meant to be a new language, after all! It does seem a bit strange from our perspective today, where we are used to much richer types and more type enforcement though.
Interesting, thanks! I knew it was related to ALUs etc. (heck, all the CPUs I heard of, have just an untyped ‘register’, with signed-ness introduced only at the level of operations-over-those-untyped-registers), but didn’t know about PDP11 specifics.
Still, most important part is that we do have to deal with it now…
Seems like the main point has been missed. Developers need to pay attention to signed/unsigned from the start. Not rely upon refactoring to address the issue.
Anyone ignoring such a fundamental difference is not doing their job.
> Developers need to pay attention to signed/unsigned from the start. Not rely upon refactoring to address the issue.
I am certainly not arguing with this; however – the question which I tried to raise is that “HOW to address this issue whenever we know when it does exist?” (and IMO intuitive::lt might help for quite a few use cases).
“If you’re not writing in C/C++, please ignore this post;”
I read the whole thing, deal with it
This blog has very little information directly relevant to the Web Development world I live in. I simply find this world of compilers and system calls fascinating and your writing style makes these dry topics easier to understand and quite enjoyable. Although honestly, I’m only here for the bunnies.
> honestly, I’m only here for the bunnies.
Being a bit pedantic here, but only because I have some personal familiarity with this problem, there is a C++ compiler that does not use two’s-complement arithmetic. It’s UCPP on Unisys OS2200, which uses one’s-complement arithmetic because that’s what the underlying hardware uses (its architecture, while not binary compatible, can be traced all the way back to the original Univac machines of the 50’s, back before engineers had settled on two’s complement as the “right” way to do things).
I know they have C compiler, but that they have C++ is indeed new for me. I changed the wording.
Thank you very much for the post, just had to deal with this very problem several times in the following context:
size_t BUFFER_SIZE; /* strictly non-negative; declaring this int will cause problems in other places */
int user_supplied_length; /* negative value is not a parser error */
if (user_supplied_length = BUFFER_SIZE)
/* fail */;
Had to explicitly cast user_supplied_length to size_t in second comparison to avoid warning. Don’t you think compiler should be clever enough to see that user_supplied_length cannot be negative by the time it gets there so no warning (and explicit cast) is necessary?
Comments engine ate my code. It was:
—
size_t BUFFER_SIZE; /* strictly non-negative; declaring this int will cause problems in other places */
int user_supplied_length; /* negative value is not a parser error */
if (user_supplied_length < 0 || user_supplied_length >= BUFFER_SIZE)
/* fail */;
—
> Don’t you think compiler should be clever enough to see that user_supplied_length cannot be negative by the time it gets there so no warning (and explicit cast) is necessary?
In this particular case – it COULD, but there are cases where it COULDN’T; whether it SHOULD – is a different story (I would certainly like it to when there is enough information – including cases when we’re throwing exception just one line above, but IMO codifying this “SHOULD” into the standard most likely will be hopeless, so in practice we’ll be at the mercy of compiler writers
).
P.S.
> > Comments engine ate my code
Yes, it sucks I know; will try to fix it for the next version of the site…
Funny enough, according to trip reports, at Jacksonville the Committee expressed interested in breaking compatibility (8^O) and fix the built-in comparison operators in a way similar to your “intuitive” implementation. We’ll see where that goes…
Thanks for the update, it indeed sounds promising (and FWIW, I know for sure that quite a few WG21 members do read my blog
).
I thought you might like to see an instance of this problem, solved incorrectly, in the wild, that lead to a buffer overflow, possibly remotely executable: https://www.theregister.co.uk/2018/04/04/microsoft_windows_defender_rar_bug/
Yes, looks to be the same thing, thanks!
Since a lot of years ago I don’t have these problems because I only use signed vars.
The only few cases where I use unsigned vars is for bitwise operations and, inmediately, I cast the result to signed.
When a variable must not be negative, just use an assert, but do not use unsigned just to indicate that it must never be negative.
And my “Int” type is always the same size of the O.S. All my apps, libs, etc can be recompiled to 32, 64… bits (and in the future to 128) without any change in the code and with zero problems.
Your life will be much more easy if you do this…
Cheers!
PD: Here there is a nice video about signed/unsigned: https://www.youtube.com/watch?v=wvtFGa6XJDU
It would be indeed _really_ tempting if not for two things: (a) return types of many std:: functions are size_t, and (b) overflow on signed int is UB (in spite of ages of efforts to get rid of this abomination), which formally means that at the very moment when we know that we will overflow on a signed int (and it is next to impossible to guarantee that it _never ever_ happens), we can get user’s hard drive formatted, start_nuclear_war() function called (even if it is not used/referenced anywhere in code), etc.
> And my “Int” type is always the same size of the O.S.
Do you mean that you’re using your own Int type (with capital I) which is typedef-ed into something like int32_t (which BTW isn’t exactly possible for _all_ the platforms)? Or something else?
For a complete, definitive and comprehensive solution to this problem, please consider the boost safe numerics library. https://github.com/boostorg/safe_numerics . This was also the subject of an article in Overload: https://accu.org/index.php/journals/2344 .
C++20 has safe ways to compare un/signed integers and check that one type can fit within another, finally:
https://en.cppreference.com/w/cpp/utility/intcmp
https://en.cppreference.com/w/cpp/utility/in_range