Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

C\C++ specifications leave out a large number of behaviors open for compilers to implement in their own way. There are a number of questions that always keep getting asked here about the same and we have some excellent posts about it:

My question is not about what undefined behavior is, or is it really bad. I do know the perils and most of the relevant undefined behavior quotes from the standard, so please refrain from posting answers about how bad it is. This question is about the philosophy behind leaving out so many behaviors open for compiler implementation.

I read an excellent blog post that states that performance is the main reason. I was wondering if performance is the only criteria for allowing it, or are there any other factors which influence the decision to leaving things open for compiler implementation?

If you have any examples to cite about how a particular undefined behavior provides sufficient room for compiler to optimize, please list them. If you know of any other factors other than performance, please back your answer with sufficient detail.

If you do not understand the question or do not have sufficient evidences/sources to back your answer, please do not post broadly speculating answers.

share|improve this question

migrated from stackoverflow.com Aug 9 '11 at 15:27

This question came from our site for professional and enthusiast programmers.

3  
who ever heard of a deterministic computer anyway? –  sova Aug 9 '11 at 19:16

12 Answers 12

First, I'll note that although I only mention "C" here, the same really applies about equally to C++ as well.

The comment mentioning Godel was partly (but only partly) on point.

When you get down to it, undefined behavior in the C standards is largely just pointing out the boundary between what the standard attempts to define, and what it doesn't.

Godel's theorems (there are two) basically say that it's impossible to define a mathematical system that can be proven (by its own rules) to be both complete and consistent. You can make your rules so it can be complete (the case he dealt with was the "normal" rules for natural numbers), or else you can make it possible to prove its consistency, but you can't have both.

In the case of something like C, that doesn't apply directly -- for the most part, "provability" of the completeness or consistency of the system isn't a high priority for most language designers. At the same time, yes, they probably were influenced (to at least some degree) by knowing that it's provably impossible to define a "perfect" system -- one that's provably complete and consistent. Knowing that such a thing is impossible may have made it a bit easier to step back, breathe a little, and decide on the bounds of what they would try to define.

At the risk of (yet again) being accused of arrogance, I'd characterize the C standard as being governed (in part) by two basic ideas:

  1. The language should support as wide a variety of hardware as possible (ideally, all "sane" hardware down to some reasonable lower limit).
  2. The language should support writing as wide a variety of software as possible for the given environment.

The first means that if somebody defines a new CPU, it should be possible to provide a good, solid, usable implementation of C for that, as long as the design falls at least reasonably close to a few simple guidelines -- basically, if it follows something on the general order of the Von Neumann model, and provides at least some reasonable minimum amount of memory, that should be enough to allow a C implementation. For a "hosted" implementation (one that runs on an OS) you need to support some notion that corresponds reasonably closely to files, and have a character set with a certain minimum set of characters (91 are required).

The second means it should be possible to write code that manipulates the hardware directly, so you can write things like boot loaders, operating systems, embedded software that runs without any OS, etc. There are ultimately some limits in this respect, so nearly any practical operating system, boot loader, etc., is likely to contain at least a little bit of code written in assembly language. Likewise, even a small embedded system is likely to include at least some sort of pre-written library routines to give access to devices on the host system. Although a precise boundary is difficult to define, the intent is that the dependency on such code should be kept to a minimum.

The undefined behavior in the language is largely driven by the intent for the language to support these capabilities. For example, the language allows you to convert an arbitrary integer to a pointer, and access whatever happens to be at that address. The standard makes no attempt at saying what will happen when you do (e.g., even reading from some addresses can have externally visible affects). At the same time, it makes no attempt at preventing you from doing such things, because you need to for some kinds of software you're supposed to be able to write in C.

There is some undefined behavior driven by other design elements as well. For example, one other intent of C is to support separate compilation. This means (for example) that it's intended that you can "link" pieces together using a linker that follows roughly what most of us see as the usual model of a linker. In particular, it should be possible to combine separately compiled modules into a complete program without knowledge of the semantics of the language.

There is another type of undefined behavior (that's much more common in C++ than C), which is present simply because of the limits on compiler technology -- things that we basically know are errors, and would probably like the compiler to diagnose as errors, but given the current limits on compiler technology, it's doubtful that they could be diagnosed under all circumstances. Many of these are driven by the other requirements, such as for separate compilation, so it's largely a matter of balancing conflicting requirements, in which case the committee has generally opted to support greater capabilities, even if that means lack of diagnosing some possible problems, rather than limiting the capabilities to ensure that all possible problems are diagnosed.

These differences in intent drive most of the differences between C and something like Java or a Microsoft's CLI-based systems. The latter are fairly explicitly limited to working with a much more limited set of hardware, or requiring software to emulate the more specific hardware they target. They also specifically intend to prevent any direct manipulation of hardware, instead requiring that you use something like JNI or P/Invoke (and code written in something like C) to even make such an attempt.

Going back to Godel's theorems for a moment, we can draw something of a parallel: Java and CLI have opted for the "internally consistent" alternative, while C has opted for the "complete" alternative. Of course, this is a very rough analogy -- I doubt anybody's attempting a formal proof of either internal consistency or completeness in either case. Nonetheless, the general notion does fit fairly closely with the choices they've taken.

share|improve this answer
9  
I think Godel's Theorems are a red herring. They deal with proving a system from its own axioms, which is not the case here: C does not need to be specified in C. It is quite possible to have an completely specified language (consider a Turing machine). –  poolie Aug 10 '11 at 2:48
2  
Sorry, but I fear you've completely misunderstood Godel's Theorems. They deal with the impossibility of proving all true statements in a consistent system of logic; in terms of computing, the incompleteness theorem is analogous to saying that there are problems that cannot be solved by any program - problems are analogous to true statements, programs to proofs and the model of computation to the logic system. It has no connection at all to undefined behaviour. See for an explanation of the analogy here: scottaaronson.com/blog/?p=710. –  Alex ten Brink Aug 10 '11 at 9:57
1  
I should note that a Von Neumann machine is not required for a C implementation. It's perfectly possible (and not even very difficult) to develop a C implementation for a Harvard architecture (and I wouldn't be surprised to see a lot of such implementations on embedded systems) –  bdonlan Aug 30 '11 at 3:53

The C rationale explains

The terms unspecified behavior, undefined behavior, and implementation-defined behavior are used to categorize the result of writing programs whose properties the Standard does not, or cannot, completely describe. The goal of adopting this categorization is to allow a certain variety among implementations which permits quality of implementation to be an active force in the marketplace as well as to allow certain popular extensions, without removing the cachet of conformance to the Standard. Appendix F to the Standard catalogs those behaviors which fall into one of these three categories.

Unspecified behavior gives the implementor some latitude in translating programs. This latitude does not extend as far as failing to translate the program.

Undefined behavior gives the implementor license not to catch certain program errors that are difficult to diagnose. It also identifies areas of possible conforming language extension: the implementor may augment the language by providing a definition of the officially undefined behavior.

Implementation-defined behavior gives an implementor the freedom to choose the appropriate approach, but requires that this choice be explained to the user. Behaviors designated as implementation-defined are generally those in which a user could make meaningful coding decisions based on the implementation definition. Implementors should bear in mind this criterion when deciding how extensive an implementation definition ought to be. As with unspecified behavior, simply failing to translate the source containing the implementation-defined behavior is not an adequate response.

Important is also the benefit for programs, not only the benefit for implementations. A program that depends on undefined behavior can still be conforming, if it is accepted by a conforming implementation. The existence of undefined behavior allows a program to use non-portable features explicitly marked as such ("undefined behavior"), without becoming non-conforming. The rationale notes:

C code can be non-portable. Although it strove to give programmers the opportunity to write truly portable programs, the Committee did not want to force programmers into writing portably, to preclude the use of C as a ``high-level assembler'': the ability to write machine-specific code is one of the strengths of C. It is this principle which largely motivates drawing the distinction between strictly conforming program and conforming program (§1.7).

And at 1.7 it notes

The three-fold definition of compliance is used to broaden the population of conforming programs and distinguish between conforming programs using a single implementation and portable conforming programs.

A strictly conforming program is another term for a maximally portable program. The goal is to give the programmer a fighting chance to make powerful C programs that are also highly portable, without demeaning perfectly useful C programs that happen not to be portable. Thus the adverb strictly.

Thus, this little dirty program that works perfectly fine on GCC is still conforming!

share|improve this answer

The speed thing is especially a problem when compared to C. If C++ did some things that might be sensible, like initializing large arrays of primitive types, it would lose a ton of benchmarks to C code. So C++ initializes its own data types, but leaves the C types the way they were.

Other undefined behavior just reflects reality. One example is bit-shifting with a count larger than the type. That actually differs between hardware generations of the same family. If you have a 16-bit app, the exact same binary will give different results on an 80286 and an 80386. So the language standard says that we don't know!

Some things are just kept the way they were, like the order of evaluation of subexpressions being unspecified. Originally this was believed to help compiler writers optimize better. Nowadays the compilers are good enough to figure it out anyway, but the cost of finding all places in existing compilers that take advantage of the freedom is just too high.

share|improve this answer
    
+1 for the second paragraph, which shows something that would be awkward to have specified as implementation-defined behavior. –  David Thornley Aug 9 '11 at 15:59
2  
The bit shift just an example of accepting undefined compiler behaviour and using the hardware capabilites. It would be trivial to specify a C result for a bit shift when the count is larger than type, but expensive to implement on some hardware. –  mattnz Aug 9 '11 at 21:24

As one example, pointer accesses almost have to be undefined and not necessarily just for performance reasons. For example, on some systems, loading specific registers with a pointer will generate a hardware exception. On SPARC accesssing an improperly aligned memory object will cause a bus error, but on x86 it would "just" be slow. It's tricky to actually specify behavior in those cases since the underlying hardware dictates what will happen, and C++ is portable to so many types of hardware.

Of course it also gives the compiler freedom to use architecture specific knowledge. For an unspecified behavior example, right shift of signed values may be logical or arithmetic depending on the underlying hardware, to allow for using whichever shift operation is available and not forcing software emulation of it.

I believe also it makes the compiler-writer's job rather easier but I can't recall the example just now. I'll add it if I recall the situation.

share|improve this answer
2  
The C language could have been specified such that it always had to use byte-by-byte reads on systems with alignment restrictions, and such that it had to provide exception traps with well-defined behavior for invalid address accesses. But of course this all would have been incredibly costly (in code size, complexity, and performance) and would have offered no benefits whatsoever to sane, correct code. –  R.. Aug 9 '11 at 17:49

Simple: Speed, and portability. If C++ guaranteed that you got an exception when you de-reference an invalid pointer, then it wouldn't be portable to embedded hardware. If C++ guaranteed some other things like always initialized primitives, then it would be slower, and in the time of origin of C++, slower was a really, really bad thing.

share|improve this answer
1  
Huh? What do exceptions have to do with embedded hardware? –  Mason Wheeler Aug 9 '11 at 16:09
2  
Exceptions may lock up the system in ways that are very bad for Embedded Systems that need to respond quickly. There are situations where a false reading is much less damaging that a slowed system. –  World Engineer Aug 9 '11 at 16:13
1  
@Mason: Because the hardware has to catch the invalid access. It's easy for Windows to throw an access violation, and harder for embedded hardware with no operating system to do anything except die. –  DeadMG Aug 9 '11 at 16:14
3  
Also remember that not every CPU has an MMU to guard against invalid accesses in hardware to begin with. If you start requiring your language to check all pointer accesses, then you have to emulate an MMU on CPUs without one - and thus EVERY memory access becomes extremely expensive. –  fluffy Aug 10 '11 at 0:19

C was invented on a machine with 9bit bytes and no floating point unit - suppose it had mandated that bytes be 9bits, words 18bits and that floats should be implemented using pre IEEE754 aritmatic?

share|improve this answer
4  
I suspect you're thinking of Unix -- C was originally used on the PDP-11, which was actually pretty conventional current standards. I think the basic idea stands nonetheless. –  Jerry Coffin Aug 9 '11 at 18:44
    
@Jerry - yes, you're right - I'm getting old ! –  Martin Beckett Aug 9 '11 at 19:01
    
Yup -- happens to the best of us, I'm afraid. –  Jerry Coffin Aug 9 '11 at 19:08

One of the early classic cases was signed integer addition. On some of the processors in use, that would cause a fault, and on others it would just continue on with a value (likely the appropriate modular value). Specifying either case would mean that programs for machines with the unfavored arithmetic style would have to have extra code, including a conditional branch, for something as similar as integer addition.

share|improve this answer

I don't think the first rationale for UB was to let room to the compiler to optimize, but just the possibility to use the obvious implementation for the targets at a time when architectures had more variety than now (remember if C was designed on a PDP-11 which has a somewhat familiar architecture, the first port was to Honeywell 635 which is far less familiar -- word addressable, using 36 bit words, 6 or 9 bits bytes, 18 bits addresses... well at least it used 2's complement). But if heavy optimization wasn't a target, obvious implementation doesn't include adding run-time checks for overflow, the shift count over the register size, that aliases in expressions modifying multiple values.

Another thing taken into account was ease of implementation. A C compiler at the time was multiple passes using multiple process because having one process handle everything would not have been possible (the program would have been too large). Asking heavy coherence check was out of the way -- especially when it involved several CU. (Another program than the C compilers, lint, was used for that).

share|improve this answer

I'd say it was less about philosophy than it was about reality -- C has always been a cross platform language, and the standard has to reflect that and the fact that at the time any standard is released, there are going to be a large number of implementations on a lot of different hardware. A standard that forbid necessary behavior would either be disregarded or produce a competing standards body.

share|improve this answer

Some behaviors cannot be defined by any reasonable means. I mean accessing a deleted pointer. The only way to detect it would be banning pointer value after deletion (memorizing its value somewhere and not allowing any allocation function return it anymore). Not only such a memorization would be overkill, but for a long running program would cause running out of allowed pointers values.

share|improve this answer
    
or you could allocate all pointers as weak_ptr and nullify all references to a pointer that gets deleted... oh wait, we're approaching garbage collection :/ –  Matthieu M. Aug 9 '11 at 17:29
    
boost::weak_ptr's implementation is a pretty good template to start with for this usage pattern. Rather than tracking and nullifying weak_ptrs externally, a weak_ptr just contributes to the shared_ptr's weak count, and the weak count is basically a refcount to the pointer itself. Thus, you can nullify the shared_ptr without having to delete it immediately. It's not perfect (you can still have lots of expired weak_ptrs maintaining the underlying shared_count for no good reason) but at least it's fast and efficient. –  fluffy Aug 22 '11 at 21:31

I'll give you an example where there's pretty much no sensible choice other than undefined behavior. In principle, any pointer could point to the memory containing any variable, with the small exception of local variables that the compiler can know have never had their address taken. However, to get acceptable performance on a modern CPU, a compiler must copy variable values into registers. Operating entirely out of memory is a non-starter.

This basically gives you two choices:

1) Flush everything out of registers before any access through a pointer, just in case the pointer points to that particular variable's memory. Then load everything needed back into register, just in case the values were changed through the pointer.

2) Have a set of rules for when a pointer is allowed to alias a variable and when the compiler is permitted to assume that a pointer does not alias a variable.

C opts for option 2, because 1 would be terrible for performance. But then, what happens if a pointer aliases a variable in a way the C rules prohibit? Since the effect depends on whether the compiler did in fact store the variable in a register, there's no way for the C standard to definitively guarantee specific results.

share|improve this answer

Efficiency is the usual excuse, but whatever the excuse, undefined behavior is a terrible idea for portability. In effect undefined behaviors become unverified, unstated assumptions.

share|improve this answer
4  
The OP specified this: "My question is not about what undefined behavior is, or is it really bad. I do know the perils and most of the relevant undefined behavior quotes from the standard, so please refrain from posting answers about how bad it is." Looks like you didn't read the question. –  Etienne de Martel Aug 9 '11 at 18:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.