10 ms·

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

172 points by ryannielsen 15y ago

fragsworth 15y 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?
- perlgeek 15y 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.
- bhickey 15y 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?
  - fragsworth 15y ago
    Yes, I was thinking of something like Haskell.
- Rusky 15y 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 15y 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.
  - Peaker 15y 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?
    - comex 15y ago
      Debug.Trace, for instance. More generally, the fact that execution time and memory usage (tail recursion!) sometimes depend on how well the compiler can turn your stateless algorithm into a stateful one, in ways that don't make sense from the perspective of the abstract machine.
      - Peaker 15y ago
        Debug.Trace explicitly breaks referential transparency and its entire purpose is to penetrate the evaluation order out of the abstraction. It's a tool to penetrate the abstraction, much like a debugger. But the existence of such debugging tools does not mean the abstractions themselves are leaky, because these tools do not leak the abstraction as a side-effect, it is their only purpose. Performance analysis of pure algorithms is not a leak of the abstraction, if you consider the abstraction relates to the semantics, the result of the algorithm, and not how much resources it takes to execute. If you wish to know the resource use of your pure code, then none of the nice abstractions hold anymore, but most of the time, you don't need to.
- Peaker 15y 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).
  - cwzwarich 15y 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.
    - Peaker 15y 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. Well, you can choose any two of: 1. Fast (less run-time), 2. Safe (cannot crash), 3. Simple types (None of the advanced type hackery). Many choose 1+3 or 2+3, but advanced types let you choose 1+2 which in many cases is remarkable and somewhat surprising that it is even possible. Also note that runtime checks, in many cases, do not give you safety. For example, normally, you have an array indexing operation like: readArray :: Array a -> Int -> IO a Ignore the "IO" if you are unfamiliar with Haskell's IO type. This is unsafe whether or not you have index bounds checking. A runtime check will only convert one kind of error (corruption/segfault) to another (runtime exception). In these (common cases), your only option of getting safety is advanced type hackery. Something like: index :: (size:N) -> Array size a -> Fin size -> a where Fin N is the type of integer ranged between 0 and (N-1). > 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 Nothing about this type hackery is specific to singly linked lists, and advanced type hackary is applicable for pretty much any data structure. Also note that the singly linked lists used in zip may not actually be represented by pointer-chasing singly-linked lists. They may be "fused" together into efficient loops that process the input directly.
CamperBob 15y ago
What would possess someone to write if (i < 0 || buffer+i-128 >= buffer) ... instead of if ((i < 0) || (i >= sizeof(buffer)) ?
- defen 15y 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 15y 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).
    - iam 15y ago
      Precisely. This optimization is possible because according to ANSI C, a variable is allowed to point to an address anywhere within an object, or at most one (sizeof) past an object. Anything else is undefined behavior (what they refer to as as "illegal pointer" in the post). Therefore, buffer through buffer+1 would be valid pointers, but unless they can prove that i-128 is <=1 they can safely assume that the final pointer can be more than 1 past the buffer. If it was just a pointer (not an array) they could do the same analysis if the pointer was mallocced right then in the same function with a constant size. More likely though, the pointer would be a function argument and then they would not know where the object boundaries were without doing interprocedural analysis (which I assume is outside of the scope of this post) and some other additional propagation (so technically within the C99 spec, but I doubt you would see an optimization that actually would do that).
- nonzero 15y 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.
peterbotond 15y 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 15y ago
  Do you fuzz your inputs? Run with the clang undefined integer overflow checker? Run your program on hardware with 16-bit int?
  - peterbotond 15y 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.
gabi38 15y 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 15y 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.
  - gabi38 15y 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..
    - jrockway 15y ago
      "Bad"? You use C because you want speed above all else. If you don't know the language and need hand-holding, don't use C. Compilers are going to optimize C -- that's why it usually runs so fast.
      - gabi38 15y ago
        This is bad because the optimizer ignores the imperfect reality about the big crowd of non standard programs. It actually punishes non standard programs (and probably the majority of programs out there are not 100% standard). So it is a bad and patronizing optimization
rwmj 15y 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/ http://www.astree.ens.fr/
- vog 15y 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.

172 points by ryannielsen 15y 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?

perlgeek 15y 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.
bhickey 15y 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?
- fragsworth 15y ago
  Yes, I was thinking of something like Haskell.
Rusky 15y 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 15y 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.
- Peaker 15y 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?
  - comex 15y ago
    Debug.Trace, for instance. More generally, the fact that execution time and memory usage (tail recursion!) sometimes depend on how well the compiler can turn your stateless algorithm into a stateful one, in ways that don't make sense from the perspective of the abstract machine.
    - Peaker 15y ago
      Debug.Trace explicitly breaks referential transparency and its entire purpose is to penetrate the evaluation order out of the abstraction. It's a tool to penetrate the abstraction, much like a debugger. But the existence of such debugging tools does not mean the abstractions themselves are leaky, because these tools do not leak the abstraction as a side-effect, it is their only purpose. Performance analysis of pure algorithms is not a leak of the abstraction, if you consider the abstraction relates to the semantics, the result of the algorithm, and not how much resources it takes to execute. If you wish to know the resource use of your pure code, then none of the nice abstractions hold anymore, but most of the time, you don't need to.
Peaker 15y 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).
- cwzwarich 15y 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.
  - Peaker 15y 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. Well, you can choose any two of: 1. Fast (less run-time), 2. Safe (cannot crash), 3. Simple types (None of the advanced type hackery). Many choose 1+3 or 2+3, but advanced types let you choose 1+2 which in many cases is remarkable and somewhat surprising that it is even possible. Also note that runtime checks, in many cases, do not give you safety. For example, normally, you have an array indexing operation like: readArray :: Array a -> Int -> IO a Ignore the "IO" if you are unfamiliar with Haskell's IO type. This is unsafe whether or not you have index bounds checking. A runtime check will only convert one kind of error (corruption/segfault) to another (runtime exception). In these (common cases), your only option of getting safety is advanced type hackery. Something like: index :: (size:N) -> Array size a -> Fin size -> a where Fin N is the type of integer ranged between 0 and (N-1). > 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 Nothing about this type hackery is specific to singly linked lists, and advanced type hackary is applicable for pretty much any data structure. Also note that the singly linked lists used in zip may not actually be represented by pointer-chasing singly-linked lists. They may be "fused" together into efficient loops that process the input directly.

CamperBob 15y ago

What would possess someone to write if (i < 0 || buffer+i-128 >= buffer) ... instead of if ((i < 0) || (i >= sizeof(buffer)) ?

defen 15y 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 15y 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).
  - iam 15y ago
    Precisely. This optimization is possible because according to ANSI C, a variable is allowed to point to an address anywhere within an object, or at most one (sizeof) past an object. Anything else is undefined behavior (what they refer to as as "illegal pointer" in the post). Therefore, buffer through buffer+1 would be valid pointers, but unless they can prove that i-128 is <=1 they can safely assume that the final pointer can be more than 1 past the buffer. If it was just a pointer (not an array) they could do the same analysis if the pointer was mallocced right then in the same function with a constant size. More likely though, the pointer would be a function argument and then they would not know where the object boundaries were without doing interprocedural analysis (which I assume is outside of the scope of this post) and some other additional propagation (so technically within the C99 spec, but I doubt you would see an optimization that actually would do that).
nonzero 15y 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.

peterbotond 15y 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 15y ago
Do you fuzz your inputs? Run with the clang undefined integer overflow checker? Run your program on hardware with 16-bit int?
- peterbotond 15y 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.

gabi38 15y 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 15y 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.
- gabi38 15y 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..
  - jrockway 15y ago
    "Bad"? You use C because you want speed above all else. If you don't know the language and need hand-holding, don't use C. Compilers are going to optimize C -- that's why it usually runs so fast.
    - gabi38 15y ago
      This is bad because the optimizer ignores the imperfect reality about the big crowd of non standard programs. It actually punishes non standard programs (and probably the majority of programs out there are not 100% standard). So it is a bad and patronizing optimization

rwmj 15y 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/ http://www.astree.ens.fr/

vog 15y 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.