What Every C Programmer Should Know About Undefined Behavior #2/3

http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_14.html

by ryannielsen • 15 years ago

172 43 15 years ago

blog.llvm.org

fragsworth2• 15 years ago

Kind of off topic, but I am curious: is this one of the advantages of functional programming - the notion that you can prove or disprove certain things about the code and therefore optimize the compiler, based on such proofs, to your heart's content?

bhickey• 15 years ago

Can you elaborate on your question?

I don't think what you're saying is intrinsic to FP. There are static analysis tools for non-functional languages. At the end of the day, everything is getting turned into an abstract syntax tree, so style should be irrelevant.

Do you mean pure (side-effect free) functional languages?

fragsworth2• 15 years ago

Yes, I was thinking of something like Haskell.

Rusky• 15 years ago

It's more an advantage of very-specifically designed languages like Haskell, some of which happen to be functional because part of the reason they can be specified in so much detail is because of the lack of side effects.

jowiar• 15 years ago

The relevant element of FP is statelessness. That said, statelessness could easily be considered a leaky abstraction because, at some point, the machine you are working on has state. Your machine has CPU registers and memory and such, so the entire "statelessness" of FP is subject to the underlying system-level implementation.

Peaker7• 15 years ago

> The relevant element of FP is statelessness. That said, statelessness could easily be considered a leaky abstraction because, at some point, the machine you are working on has state. Your machine has CPU registers and memory and such, so the entire "statelessness" of FP is subject to the underlying system-level implementation.

It is only leaky if you are exposed to the statefulness of the underlying machine.

Haskell's pure code does enjoy the abstraction of purity without exposing the non-pure primitives from which it is exposed. Haskell's non-pure code is marked as such, and not supposed to be abstracted away from the nature of the underlying machine. I'm not sure what abstraction leak you're referring to. Can you give an example?

jrockway2• 15 years ago

Your machine has CPU registers and memory and such, so the entire "statelessness" of FP is subject to the underlying system-level implementation.

In the end, it's all a few billion transistors that need to be switched on and off at just the right time. C is as far away from that as Haskell is.

perlgeek• 15 years ago

To a big part the ability to optimize stems form a static and very detailed type system.

In Haskell you happen to know about statelessness from the types, which is an additional bonus. But other statically type languages like Eiffel are also pretty well optimizable.

Peaker7• 15 years ago

The more advanced of a type system you have, the more you can optimize indeed. A nice example of this is the zip function.

In Haskell:

    zip :: [a] -> [b] -> [(a, b)]
    zip [] _ = []
    zip _ [] = []
    zip (x:xs) (y:ys) = (x,y) : zip xs ys

Note how each iteration needs to check both lists for emptiness.

In a more advanced type system (or using more advanced type hackery in Haskell) you can have length-indexed lists. That is: lists that have 2 type parameters or "indexes" instead of 1. The 1 is usually the type of element inside the list, the extra 1 is a natural number indicating the length of the list.

So the function zip becomes something like:

    zip :: List N a -> List N b -> List N (a, b)
    zip [] [] = []
    zip (x:xs) (y:ys) = (x,y) : zip xs ys

The compiler checks the code and verifies, at compile-time, that both the input lists and the resulting list are all of the same length. This also means that you only need one runtime emptiness check instead of 2. If the N is concretely known at compile-time, you may need 0 (though that case might be caught by inlining/loop unrolling optimizations anyway).

cwzwarich2• 15 years ago

In an unsafe language like C or C++, you would just assert that the two containers are the same length and use parallel iterators. The type system here lets you optimize away some of the overhead of using a safe language, but it doesn't let you write code that is more optimized than the obvious unsafe code, at least in this example.

Also, in this example you're using a singly linked list, which is usually a performance loss compared to a more appropriate data structure. CPUs are designed to favor contiguous arrays.

guygurari2• 15 years ago

This is interesting, but the two versions of zip you present are not equivalent. The standard version can handle lists of different lengths; it effectively truncates the longer list to the shorter one's length. Can you get this behavior in the second version and still have just one emptiness check?

CamperBob• 15 years ago

What would possess someone to write

  if (i < 0 || buffer+i-128 >= buffer)

... instead of

  if ((i < 0) || (i >= sizeof(buffer))

?

defen• 15 years ago

Working within the "contrived example" framework, it would have made a little more sense if buffer were a pointer rather an array, in which case you wouldn't be able to use "sizeof".

leif• 15 years ago

If it were not an array, the "undefined behavior" wouldn't come into effect. If it were a pointer, it would not have been eliminate (I'm pretty sure).

nonzero• 15 years ago

My thoughts exactly. I figured maybe there was some other crap in the ... that necessitated the convoluted 2nd part of the || statement, but I couldn't think of anything that would.

kjksf• 15 years ago

That's not the right way of looking at this.

Instead, consider it from the point of view of probability.

Even if probability of any single programmer writing an exceedingly stupid piece of code is vanishingly small, the number of programmers writing new code daily is so big, that mistakes of vanishingly small probability end up being quite common indeed.

To given a real example: consider that Apple undoubtably employs only the finest programmers for their OS group and yet every iOS release is jailbroken quite quickly due to a piece of code which had a security bug.

Even within a much smaller scope of a single application, all web browser from Microsoft, Apple, Mozilla (and sometimes Google) are regularly compromised via security bugs despite huge investments from all those companies into security.

Toss in the fact that many programmers actually like doing things in unnecessarily clever or novel ways and inevitably the clever code is more likely to be buggy than boring code.

Bugs and crappy code is a statistical certainty, especially in languages like C and C++ that give you so many ways to shoot yourself in the foot.

jws• 15 years ago

Many of the strange things that happen in C language edge cases come about from macro expansion or code generation.

Unrelated to the issue, but the superfluous parenthesis added in the second example are interesting. I think every C coder has a level of comfort with the 15 sets in the operator precedence rules, and beyond that they throw parenthesis at it. I'm fine with the rules until I use a <<, >>, &, ^, or |[1]. Then I drag out the parenthesis.

[1] I swear the positions of the ones I named are placed alphabetically rather than in relation to their mathematical function.

gsg2• 15 years ago

& and | have the wrong precedence because in primordial C they were both either short-circuiting boolean or bitwise depending on context.

sonoffett• 15 years ago

The OP has since changed the article but IIRC `buffer` was an array of `int`s, in which case the `sizeof` operator would return 512. Generally you'd want `(i >= sizeof(buffer)/sizeof(buffer[0]))`.

Someone• 15 years ago

I would guess there are two answers:

- macro expansions

- the author took an example from a larger function and simplified it into a minimal test case. For example, there might be a

    #define BUFSIZE 128;
    ...
    j = buffer+i;
    ...
    if( (i < 0) || (i-BUFSIZE >= buffer))

Still weird (i - BUFSIZE could underflow), but more believable.

peterbotond2• 15 years ago

the way to write good solid code is to use more than 2 compiler, and optimisation etc. i mostly write code that runs on at least 3 different os, and 2 different hardware. ... and it just works. no prog-lang can be faulted for bad programming using one. learn the lang, and use it. :-)

gcc still gets the pointer dereference and assignment to what a pointer points to, due to deferring assignments. these edges, idioms of any lang needs to be looked at with academic eyes. :-)

astrange• 15 years ago

Do you fuzz your inputs? Run with the clang undefined integer overflow checker? Run your program on hardware with 16-bit int?

peterbotond2• 15 years ago

yes, random bits flipped on good input. yes, i run anything that can help me and covers the problem. nowadays, 32 and 64 bit are what i write code for. oh, the days of 16bit ints on win3.11 for workgroups are gone. :-)

llvm is an excellent tool, hats off, and thanks.

gabi383• 15 years ago

Is it just me or the LLVMs idea that "If arithmetic on an 'int' type (for example) overflows, the result is undefined.. For example, knowing that INT_MAX+1 is undefined allows optimizing "X+1 > X" to "true"." is incredibly stupid? Who said that undefined number is bigger than a defined one ??

perokreco• 15 years ago

It is not that the result of operation is undefined, the operation of INT_MAX+1 itself is undefined(actually the entire program becomes undefined when you do it), so the compiler can do whatever it pleases. According to the C standard, INT_MAX+1 might as well lead to formatting of your hard drive. So, it is safe to assume that x!=INT_MAX and that x+1>x for all x, because if x=INT_MAX your program is undefined, so compiler can do whatever it wants, including setting it to true or outputting an error or formatting the hard drive.

gabi383• 15 years ago

This kind of logic is the exact cause to the optimization problem described. We all know that in practice MAX_INT+1 is negative, and that many "non-standard" programs depends on it, but still, the optimizer is sticking to the C standard that no one follows just because it gives it a nice optimization chance. Bad..

rwmj• 15 years ago

Interesting they say there is no way to detect undefined behaviour in C code. This is precisely what the following project is all about:

http://www.astree.ens.fr/

vog• 15 years ago

The cited project is about proving that a C program has no undefined behaviour. If such proof can't be found, the code may still be okay.

So the existence of that tool doesn't contradict the statement of the article.

What Every C Programmer Should Know About Undefined Behavior #2/3

Related Stories