A Quiz About Integers in C
blog.regehr.org
blog.regehr.org
I often hear developers talking about how C is a simple language, but it may or may not be, depending on how you define "simple". For example, a written alphabet with only two letters -- A and B -- is "simple" to grasp (there's only two letters to learn!), but it would be very difficult, in the real world, to read and write such a language.
I think C is similar: "simple" in a sense, but very, very complex in another sense. C could use some massive clean-up, in my opinion. Much of its design was so that it could be ported to CPUs which haven't really existed in the wild in a long time in great enough numbers to warrant all the undefined and implementation dependent behavior.
The language could be hugely simplified, in the usage sense, if much of the cruft were jettisoned.
Also, language users often rebel when language designers make breaking changes. Python 3 tried to remove cruft, and look how slowly it's been adopted. Instead of adopting 3.x, people backported the features they wanted to 2.x.
I would love it if C had less cruft, but when I say that I mean, "I want C with less cruft, but with the same huge ecosystem of documentation and libraries and tools and debuggers and profilers that crufty-C has."
As a result, these features are largely orthogonal, and the rules are simple to state and learn -- even if they at first seem a bit odd (you have to cast all numeric types to each-other before they can interact).
In contrast to Scala, another modern language I investigated recently, which seemed like quite a thicket of features.. some of which seemed just to be there to mediate the interaction of other features.
And Scheme's syntax for numbers was invented by Cthulhu himself.
(Python 3 was supposed to be adopted this slowly, last time I checked.)
A lot of the implementation dependent behavior is now expected. Not too long ago, I was taking part here in a brief debate in the comments for a Go language related post, and the programmer was up in arms that the Go compiler didn't transparently cast things for him. I pointed out that this would result in implementation dependent behavior, and maybe the design goal in Go was to eliminate that.
His reply: That's what people should expect. >Of course< you should expect all these arcane things to happen when you port from one platform to another.
I was that programmer, and I've now changed my mind.
The whole 'less design is better' is always more palatable when it doesn't touch the things one is used to taking for granted (in my case, having a nice numeric tower).
But the union of all the common such features gives you something like Scala, which is to me obviously over-designed. Go is more like the intersection.
I decided a long time ago that it makes no sense to trust myself and everyone who might have to maintain my code to always remember all these rules. It's a lot simpler and safer to remember a much smaller set of rules like don't mix signed and unsigned and just enable all the warnings.
One thing I do that may be controversial is to prefer fixed size types most of the time. In my opinion, the decision to use a 16, 32 or 64 bit int type is not primarily a portability or performance issue. It's a decision driven by application requirements, and I want to express these requirements as explicitly as possible in my code.
I think C is complicated with all the 191 undefined behaviors and 52 unspecified behaviors (source for these number is the paper that the author of the quiz wrote for specifying CSmith). One must master C before having absolutely knowledge that the code that he wrote doesn't fall into one of the two black-holes (undefined and unspecified behaviors). For instance, almost everyone that I ask, they tell me that dereferencing a NULL pointer yields 'Segmentation fault' but it's just not true. It's in fact undefined behavior.
The other thing is the rules for strict aliasing... It's pretty much impossible to convert one pointer to another without breaking some of the C rules. The experts say type punning is the way to go but type punning relies in another not defined behavior. Reading an element from an union that wasn't the last element written is undefined behavior.
EDIT: Ok, Ada has this done right.
Errors in the quiz:
3. (unsigned short)1 > -1: This will evaluate to 0 on systems where sizeof(short)<sizeof(int), and 1 on systems where sizeof(short)==sizeof(int). Yes, such systems exist. Old Cray supercomputers and various DSP processors don't have byte-addressable memory, only word-addressable, so they make all primitive types a word long.
5. SCHAR_MAX == CHAR_MAX: The person who wrote the quiz even ACKNOWLEDGES that the quiz is incorrect here and apologizes. This is implementation-dependent, it is 1 when char is signed and 0 when char is unsigned. Both types of systems exist. You can use -funsigned-char on GCC, for example.
11: int x; x << 31: This is only defined for some values on platforms where int has at least 32 bits. There exist systems where int has 16 bits, in which case this is undefined for all values. Old DOS PCs often used 16-bit ints, and I believe that ints were 16 bits when C was invented.
12: int x; x << 32: This is only undefined on systems where int has no more than 32 bits. There exist systems where int has more bits. Do a search for ILP64 if you wish to hear about such systems.
14: unsigned x; x << 31: Again, this is only defined on systems where int has at least 32 bits. See #11.
15: unsigned short; x << 31: This one is tricky. There are four different cases, depending on the size of int and whether sizeof(short)==sizeof(int).
15a: sizeof(short) == sizeof(int): defined for all x, since x gets promoted to unsigned.
15b: sizeof(short) < sizeof(int), int has less than 32 bits: defined for no x. I don't think any such systems exist.
15c: sizeof(short) < sizeof(int), int has at least 32 bits but less than 32 more than a short: defined for some x. This is the most common, with 16-bit short and 32-bit int.
15d: sizeof(short) < sizeof(int), int has at least 32 more bits than a short: defined for all x. This is the uncommon ILP64 system.
18: int x; (short)x + 1: This is outright incorrect. Casting int to short results in undefined behavior if the value cannot be represented as a short. Truncation is only guaranteed to occur for unsigned types.
In other words, please answer each question in the context of a C compiler whose implementation-defined characteristics include two's complement signed integers, 8-bit chars, 16-bit shorts, and 32-bit ints. The long type is 32 bits on x86, but 64 bits on x86-64 (this is LP64, for those who care about such things).
1. Always do bit operations on unsigned types.
2. Never overflow signed types.
3. Always shift less than the type width. I can name architectures which implement large shifts in three distinct ways.
4. Know that most integers get promoted to int or unsigned, so you need an explicit cast to get 64 bits on most platforms. So 1ULL << 48 is okay, 1U << 48 is bad.
5. Treat unsigned int / unsigned long as contagious, just like float and double.
Regehr clarifies this in the comments section: "Regarding signed overflow being defined or not, compiler developers generally draw a sharp distinction between undefined behavior and implementation-defined behavior. 32-bit ints, 2's complement, etc. are examples of the latter and signed overflow is an example of the former. A lot of developers do not draw such a sharp distinction, which is why I made a point of asking questions about this issue."
The funny part is that it's often better to use int exactly because of the undefined behavior on overflow. By signaling to the compiler that you don't intend to overflow a particular variable, it can optimize appropriately.
If int is 32 bits and short is 16 bits, then converting unsigned short to int will always give a value in the range [0, 0xffff]. No exceptions.
Longs are 32 bits on Windows(both 32 and 64), but are 32 for Linux 32-bit and 64 for Linux 64-bit. So the answer could be B or C there.
Basically, IMO, C's implicit conversions are a flaw in the spec. A more sensible language would require every conversion (aside from those involving un-dimensioned constant data) to be spelled out explicitly. Since you can't make C sensible, the next best thing is to scrupulously isolate the stupid parts.
I believe that the reason people need to know these things is not because they should be playing Russian roulette with them, but because they need to know what's going on when things go accidentally wrong.
Edit: As pointed out by the responses, I am wrong
Unfortunately this does not educate people to that kind of issues, which is very unfortunate.
"When any scalar value is converted to _Bool, the result is 0 if the value compares equal to 0; otherwise, the result is 1"
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf page 43
Why do people who haven't checked the C standard make such claims? My C lecturer made exactly the same mistake.
INT_MAX + 1 is never 0 for unsigned int. (unsigned)INT_MAX + 1 is equal to INT_MAX + 1. You're thinking of UINT_MAX + 1, which is always 0.
1. To give compilers some leeway when optimizing stuff (for examples, see http://blog.llvm.org/2011/05/what-every-c-programmer-should-...)
2. To make C usable for those worried about erroneous overflows in their code.
3. To make it easier to write C compilers for CPUs that trap on integer overflow.
4. To allow for performant C compilers on CPUs that use one's complement arithmetic.
I'm curious about this. See below.
> 2. To make C usable for those worried about erroneous overflows in their code.
I think you're saying that the rule allows compilers to implement -fwrapv if they choose, which sounds reasonable.
> 3. To make it easier to write C compilers for CPUs that trap on integer overflow. > 4. To allow for performant C compilers on CPUs that use one's complement arithmetic.
I wonder how much these matter nowadays.
For optimization, the blog post you cite describes the following examples:
- "X+1 > X" to true
- "X*2/2" to "X"
- "<= loops" and "int" induction variables
Code using "int" induction variables to step through arrays on 64-bit targets is often sloppy. Such code won't handle very large arrays properly, due to the limited range of "int", which is a bug that may not be quickly noticed.
And for the "<= loop" itself:
for (i = 0; i <= N; ++i) { ... }
Instead of having compiler writers sit around and think up clever ways to repurpose anachronistic language rules, I might prefer to have them focus instead on ways they can help me write better code instead :-).
The other vision for C is a portable systems programming language. When trying to write portable code, undefined or implementation-defined behavior is a big problem. I'm glad that compiler writers employ a take-no-prisoners approach here. People shouldn't be relying on undefined behavior when trying to write portable code, so compiler writers shouldn't be bound to implement consistent behavior in those cases. That's especially the case if code ever needs to be compiled with a different compiler, which might decide to implement different consistent behavior.
It's also worth noting that in some cases, the exploitation of undefined behavior doesn't always happen in a single place in a compiler. Instead, it can be a combination of applying a few different rules in different optimization passes that produces surprising results.
With that being said, it sure would be nice if the compiler writers figured out how to give more warnings when undefined behavior is detected. If x + 1 > x is optimized to false, tell me! If a dereference of a pointer that could be null leads to potentially dead code being eliminated, tell me about that too! It's the silently surprising behavior that causes the most problems.
The problem with undefined behavior is not people ignoring portability. It's that it's actually really easy to accidentally misuse it. For example, Regehr's group has found quite a few such bugs in widely ported code written by smart people [0].
It's fairly non-trivial to tell a user "if you switch these 5 loop nests, we may be able to do something cool!"
Would it really kill you to decide on the questionnaire rules before writing the questions? :-)
A few of the questions seemed odd, or mixing implementation specifics with standardize.
Edit: s/width/range/
The point being made is that the default signedness of char can be different from platform to platform, and the default can be confusing to people who associate the char type with binary data. Better to use int8_t and uint8_t when you want a portable signed or unsigned 8-bit number. int8_t is always signed, and uint8_t is always unsigned.
> Also assume that x86 or x86-64 is the target. In other words, please answer each question in the context of a C compiler whose implementation-defined characteristics include two's complement signed integers, 8-bit chars, 16-bit shorts, and 32-bit ints. The long type is 32 bits on x86, but 64 bits on x86-64 (this is LP64, for those who care about such things).
On Question 12 ("Assume x has type int. Is the expression x<<32..."), why is this considered an error? Why do we want a compiler to prefer this over "x<<n means shift x by (n % sizeof(int))"?
Another possible reason: CPUs have instructions for implementing << as it now stands.
7 bits is problematic because some code may assume that x << -y is an optimization for x << (32-y). I thought there was some architecture where this assumption didn't work on 32bit either, which led to my post above.
[1] http://pic.dhe.ibm.com/infocenter/aix/v7r1/topic/com.ibm.aix...