IT Hare on Soft.ware

C++: Thoughts on Dealing with Signed/Unsigned Mismatch

posted by , translated by Sergey IgnatchenkoIRL

 
Author:  Follow: TwitterFacebook
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).

-1 > 0U

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

developers, while trying to get rid exactly of signed/unsigned warning, turned a perfectly-working-program-with-warnings, into a program-without-warnings-but-which-fails-once-a-day-or-so

(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”).

1 enabled starting with /W3 level, which is IIRC default for IDE projects

 

The Root of The Problem

Who is to Blame?

— Title of a novel by Alexander Herzen, Russia, 1845 —

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 ):

static_assert( -1 < 1U );//fails!

Hare with omg face:“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

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

static_assert( int64_t(-1) < 1U );//stands! - because converted to larger which is signed
static_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.

2 formally – it seems that other representations should behave “as if” they’re two’s complement during such conversions, though as no C++ compiler exists with other-than-two’s-complement representation (except for Unisys which you have about as many chances to code for as chances for a cold day in hell), it is pretty much a moot issue
3 As Shafik Yaghmour noted in comments below, comparison involving conversions-from-shorts will lead to different results under K&R C; under ANSI C and C++ the result below stands
4 assuming sizeof(int64_t) > sizeof(int)

 

How To Fix It

What Is To Be Done?

— Title of a novel by Nikolai Chernyshevsky, Russia, 1863 —

While this signed/unsigned situation (which we’re informed about with a compiler warning) is indeed rather nasty,

one thing which is even worse than having this admittedly-nasty warning – is trying to fix it with explicit casts

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,

Never ever use explicit casts merely to get rid of warnings (whether signed/unsigned or otherwise)

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.

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?)):

static_assert( intuitive::lt(-1,1U) );//stands
static_assert( intuitive::lt(short(-1),(unsigned short)(1)) );//stands
static_assert( intuitive::lt(int64_t(-1), 1U) );//stands
static_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
5 to avoid GCC generating branched code with potentional misprediction, it took rather weird (but hopefully still valid) code with bitwise operations on booleans

 

Femida hare:“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.

6 I know how to do it in general, but my level of attention to details is not sufficient to make sure if-constexpr-less version works

 

Don't like this post? Comment↯ below. You do?! Please share: ...on LinkedIn...on Reddit...on Twitter...on Facebook

Acknowledgement

Cartoons by Sergey GordeevIRL from Gordeev Animation Graphics, Prague.

Related posts

C++: On Using int*_t as Overload and Template Parameters On Programming Language Complexity, or Our Brain as a CPU with 7+-2 Registers C++ Performance: Common Wisdoms and Common “Wisdoms” Optimizing Big Number Arithmetic Without SSE Using Parallel <algorithm> Without a Clue: 90x Performance Loss Instead of 8x Gain
Join our mailing list:

Comments

  1. says

    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

    Reply

    • "No Bugs" Hare says

      Thanks, I didn’t know it (TBH, it causes even more as before)… I added a footnote to the post (referring to your comment) – give me a shout if you feel I got it wrong.

      Reply

  2. Ross Smith says

    Your select_type template already exists in the standard library; it’s called std::conditional (in ).

    Reply

    • "No Bugs" Hare says

      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!

      Reply

  4. says

    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 ?

    Reply

    • "No Bugs" Hare says

      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…

      Reply

    • "No Bugs" Hare says

      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”.

      Reply

  6. Lazy says

    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”?

    Reply

    • "No Bugs" Hare says

      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.

      Reply

  7. says

    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.

    Reply

    • "No Bugs" Hare says

      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…

      Reply

  8. Jack Smith says

    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.

    Reply

    • "No Bugs" Hare says

      > 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).

      Reply

  9. says

    “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.

    Reply

  10. DMLou says

    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).

    Reply

    • "No Bugs" Hare says

      I know they have C compiler, but that they have C++ is indeed new for me. I changed the wording.

      Reply

  11. qm2k says

    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?

    Reply

    • qm2k says

      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 */;
      —

      Reply

      • "No Bugs" Hare says

        > 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…

        Reply

  12. says

    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…

    Reply

    • "No Bugs" Hare says

      Thanks for the update, it indeed sounds promising (and FWIW, I know for sure that quite a few WG21 members do read my blog 😉 ).

      Reply

  14. Javi says

    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

    Reply

    • "No Bugs" Hare says

      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?

      Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Copyright © 2014-2016 ITHare.com