Toughest bug/war stories

This is a discussion on Toughest bug/war stories within the Tech Board forums, part of the Community Boards category; Yup. Brewbuck got it. It's a particularly pernicious case of undefined behavior because not many of us think to check ...

  1. #16
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,467
    Yup. Brewbuck got it. It's a particularly pernicious case of undefined behavior because not many of us think to check the order of evaluation on assignment operations, taking it for granted (and falling flat on our faces) that the right hand side is evaluated first.

    Edit: It's the postfix operator that doesn't offer you that guarantee, abachler. Not the assignment operator.

    Here:

    ISO-IEC 14882-2003(E) - 5 Expressions, 4.
    Except where noted, the order of evaluation of operands of individual operators and subexpressions of individual
    expressions, and the order in which side effects take place, is unspecified.53) Between the previous
    and next sequence point a scalar object shall have its stored value modified at most once by the evaluation
    of an expression. Furthermore, the prior value shall be accessed only to determine the value to be stored.
    The requirements of this paragraph shall be met for each allowable ordering of the subexpressions of a full
    expression; otherwise the behavior is undefined.
    [Example:
    i = v[i++]; // the behavior is unspecified
    i = 7, i++, i++; // i becomes 9
    i = ++i + 1; // the behavior is unspecified
    i = i + 1; // the value of i is incremented
    Last edited by Mario F.; 12-28-2009 at 02:36 PM.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  2. #17
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,467
    Quote Originally Posted by brewbuck View Post
    The use of a variable multiple times in an expression, where one of the uses involves an increment/decrement operator, is explicitly undefined and one of the classic examples of undefined behavior.
    Not really. Not that easy.
    Check the 2nd example above. But generally? Yes. The 2nd example is also ugly code.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  3. #18
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by abachler View Post
    No, that part is not undefined. the value of the index must be calculated before the assignment, as the assignment depends on the data at the memory location, hence the pointer must be resolved prior to assignment....
    Blah blah blah. What you say makes sense, but not that much. Why does the value of the index have to be decided first? There is nothing to demand that the left side must be evaluated before the right.

    That is a single expression. We've seen a few of these here, and they always end with someone demonstrating their compiler did it in an unpredicted way. Even if it seems silly, it's still undefined.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #19
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by MK27 View Post
    Blah blah blah. What you say makes sense, but not that much. Why does the value of the index have to be decided first? There is nothing to demand that the left side must be evaluated before the right.
    It's a dependency issue. the value of foo[x] cannot be evaluated prior to knowing the value of x. if x is an expression it must therefore be evaluated BEFORE you can find the value of foo[x] (duh!!!!) as you cannot index into an array without knowing the value of the index. Since assignment cannot take place until you have the value to assign, evaluation of x must occur before assignment. Because the standard specifically states that i++ evaluates to the value of i prior to incrementing, foo[i++] therefore evaluates to foo[i]. foo[i++] + i is undefined because the the standard does not require foo[i++] to be evaluated in any particular priority over i, so long as proper order of operations is maintained.

    foo[i] = foo[i++] will always evaluate to foo[i] = foo[i]. The left side is always calculated first in any standard compliant compiler specifically because expressions on the right side may alter the index value in this way.
    Last edited by abachler; 12-28-2009 at 04:42 PM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  5. #20
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,743
    Quote Originally Posted by abachler
    No, that part is not undefined. the value of the index must be calculated before the assignment, as the assignment depends on the data at the memory location, hence the pointer must be resolved prior to assignment. The index into the array must be calculated before the pointer can be resolved, and i++ specifically uses the value prior to incrementation as the evaluated value, hence by the standard it must resolve to foo[i]. If it produces variant behavior then the implementation is non-compliant.
    The C standard states that:
    Quote Originally Posted by C99 Section 6.5 Paragraph 2
    Between the previous and next sequence point an object shall have its stored value modified at most once by the evaluation of an expression. Furthermore, the prior value shall be read only to determine the value to be stored.
    As an example of undefined behaviour, the C99 text provides:
    Code:
    a[i++] = i;
    The C++ standard states that:
    Quote Originally Posted by C++03 Section 5 Paragraph 4 (part)
    Between the previous and next sequence point a scalar object shall have its stored value modified at most once by the evaluation of an expression. Furthermore, the prior value shall be accessed only to determine the value to be stored.
    The C++03 text provides an example:
    Code:
    i = v[i++]; // the behavior is unspecified
    Now, the problem with this is that it violates the rule that "the prior value shall be read/accessed only to determine the value to be stored":
    Code:
    foo[i] = foo[i++];
    I think that the problem with your reasoning is that you assume that the effects of the increment must take place after foo[i] and foo[i++] are evaluated since "the assignment depends on the data at the memory location", but actually it can take place at any point between the previous and next sequence points, e.g., foo[i++] could be evaluated, and immediately thereafter the effects of the increment take effect, upon which foo[i] on the left hand side is evaluated, but now with i having the incremented value.

    EDIT:
    Quote Originally Posted by Mario F.
    Not really. Not that easy.
    Check the 2nd example above. But generally? Yes. The 2nd example is also ugly code.
    The reason is that the comma operator introduces a sequence point.

    Quote Originally Posted by abachler
    The left side is always calculated first in any standard compliant compiler specifically because expressions on the right side may alter the index value in this way.
    That is false (other than as an observation of what happens in existing standard compliant compilers). The copy assignment operator does not introduce a sequence point, and except for special cases the order of evaluation is otherwise unspecified.
    Last edited by laserlight; 12-29-2009 at 03:28 AM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #21
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Quote Originally Posted by abachler View Post
    No, that part is not undefined. the value of the index must be calculated before the assignment, as the assignment depends on the data at the memory location, hence the pointer must be resolved prior to assignment. The index into the array must be calculated before the pointer can be resolved, and i++ specifically uses the value prior to incrementation as the evaluated value, hence by the standard it must resolve to foo[i]. If it produces variant behavior then the implementation is non-compliant.

    What would be undefined however is foo[i] = foo[i++] + i, as there is no guarantee in which order the variables foo[i++] and i are evaluated, and hence it may add either i or i+1.
    Are we sure about that?
    Don't know exactly the rules, but can't the compiler resolve foo[i] = foo[i++] like
    Code:
    temp = foo[i];
    i = i+1;
    foo[i] = temp;
    //or
    temp = foo+i;
    *temp = foo[i];
    i = i+1;
    lets say i=0. The sure thing is that the right value is foo[0] and i=1 in the end. But when is the left value evaluated (the location the right value is written at). If the compiler reads first the right value then it might do option #1. If it reads the left value first it might do option #2. It might always leave the increment for the end of the whole line, but is that for sure?

  7. #22
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,467
    Quote Originally Posted by C_ntua View Post
    Don't know exactly the rules, but can't the compiler resolve [..]
    The compiler can and will resolve it. Undefined behavior does not mean a compiler can't do something. Undefined behavior is a feature of the programming language rules, not of the compiler. Compilers are profoundly deterministic and do not display undefined behavior. This does not mean however you will know how exactly the compiler will implement it, unless you read the resulting assembly.

    In short, any rule that has undefined behavior means the compilers are free to implement it as they see fit. And this can even mean the same compiler may (and I believe they usually do) implement the same rule differently, on different contexts depending on its optimization concerns.
    Last edited by Mario F.; 12-29-2009 at 09:57 AM.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  8. #23
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Mario F. View Post
    In short, any rule that has undefined behavior means the compilers are free to implement it as they see fit. And this can even mean the same compiler may (and I believe they usually do) implement the same rule differently, on different contexts depending on its optimization concerns.
    So you are saying it would be almost foolish to do something that you know depends on an undefined behavior being resolved in a clearly defined way?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  9. #24
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,743
    Quote Originally Posted by MK27
    So you are saying it would be almost foolish to do something that you know depends on an undefined behavior being resolved in a clearly defined way?
    What do you mean?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #25
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    I don't understand why abachler is arguing about it. The construction in question is, and has been, the cause of numerous bugs throughout time. You are disputing reality itself.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  11. #26
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by Mario F. View Post
    The compiler can and will resolve it. Undefined behavior does not mean a compiler can't do something. Undefined behavior is a feature of the programming language rules, not of the compiler. Compilers are profoundly deterministic and do not display undefined behavior. This does not mean however you will know how exactly the compiler will implement it, unless you read the resulting assembly.
    Strictly, the behavior is unspecified, not undefined. Unspecified means "Something predictable will happen, but there are multiple possibilities and we do not specify which, and it is dependent on the compiler." Undefined means "Anything and everything could happen, including pink elephants emerging from your ass."

    For instance, the representation of signed integers is unspecified, but not undefined. If it was undefined then signed integers could not exist. It's just up to the implementation.

    Or, if you look at it from the perspective of the person writing the compiler, when you see "unspecified" it means "up to you," whereas "undefined" means "don't even worry about this case."
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  12. #27
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,467
    If I understand the question correctly:

    >> an undefined behavior being resolved in a clearly defined way

    Undefined behavior is always clearly defined by the implementation (the combination of compiler and CPU). The same code will always compile to the exact same machine code. There's nothing undefinable about compilers.

    >> almost foolish

    No. Entirely foolish. Because there's only one guarantee the code will behave as we expect: Never change the code, always compile it using the same compiler, with the same version, to run on the same CPU, and with the same compiler flags. Since real-life code very rarely can agree with these limitations, it would be a mistake to inspect the resulting assembly to determine how undefined behavior is being treated by the compiler and decide or not how to write the code from that. A new compiler version, the need to add/change code or any other alteration could mean different behavior on how the compiler would treat that undefined behavior.

    >> So you are saying

    No. I wasn't saying anything like that.

    Instead, you can expect a compiler to behave predictably. That's what they do best. What this does not mean however is that one can (or has the ability for that matter) to predict how the compiler will behave.

    Quote Originally Posted by brewbuck View Post
    Strictly, the behavior is unspecified, not undefined.
    I stand corrected.
    Last edited by Mario F.; 12-29-2009 at 12:01 PM.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  13. #28
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,246
    Quote Originally Posted by Mario F.
    Undefined behavior is always clearly defined by the implementation (the combination of compiler and CPU). The same code will always compile to the exact same machine code. There's nothing undefinable about compilers.
    I don't think that is true. You can update the compiler to a different version, or change the optimization flags and get completely different behavior. The issue here is not "undefined assembly code", it's "undefined behavior".
    bit∙hub [bit-huhb] n. A source and destination for information.

  14. #29
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,467
    New compiler version = different compiler.
    New compiler version != same compiler.

    Besides I addressed it on my post. You are reading too fast
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  15. #30
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    except that foo[i] is not a single sequence point, but 2 as is foo[i++].
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Name Stories
    By sean in forum A Brief History of Cprogramming.com
    Replies: 55
    Last Post: 11-22-2004, 03:02 AM
  2. toughest math course
    By axon in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 10-28-2003, 09:06 PM
  3. Drug stories
    By Zewu in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 07-30-2003, 08:12 AM
  4. Drinking stories
    By Govtcheez in forum A Brief History of Cprogramming.com
    Replies: 24
    Last Post: 07-30-2003, 07:24 AM
  5. I love ghost stories
    By Nutshell in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 07-04-2003, 01:57 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21