3? or 4?

Discussion in 'Mac Programming' started by notjustjay, Feb 15, 2006.

  1. macrumors 603

    notjustjay

    Joined:
    Sep 19, 2003
    Location:
    Canada, eh?
    #1
    Consider this snippet:

    int main(void)
    {
    int n = 0;
    n=(++n) + (++n);
    cout << n << endl;
    }

    To me, the result of this is clearly going to be 3. Indeed, when I try it, that is the answer I get.

    However, my friend claims he consistently gets 4, and is therefore quite confused (as am I). I trust my friend, so I want to put it out to see what others get.

    (Edit: My friend showed me, and indeed, the very same code on his machine does produce 4. He's using g++ 3.3.4 while I had 3.3.)

    Does anyone else get any circumstance in which this does not return 3? And if so, any ideas why it would do so?
     
  2. macrumors 6502

    Joined:
    Apr 16, 2003
    Location:
    Boston, MA
    #2
    You'll get 4 here.

    You're basically saying

    x = 0;
    x = x+1; (x = 1);
    x = x + 1; (x = 2);
    x = x + x; (x = 4)
     
  3. jsw
    Moderator emeritus

    jsw

    Joined:
    Mar 16, 2004
    Location:
    Andover, MA
    #3
    I think it's a compiler bug. The first ++n should have been stored as a result before the second ++n was evaluated.
     
  4. thread starter macrumors 603

    notjustjay

    Joined:
    Sep 19, 2003
    Location:
    Canada, eh?
    #4
    Yeah, I can see the reasons why it could be one or the other. If the pre-increment expressions are both operated on before the final addition, sure you get 4. If the expressions are evaluated as-you-go, left-to-right, then you get 3.

    I guess the question is, is this a bug, or a matter of preference (by the compiler)? Seems like it could have pretty serious implications if it's so easy to invoke.

    My compiler here at work also says 3, as does Java.
     
  5. macrumors 6502

    Joined:
    Apr 16, 2003
    Location:
    Boston, MA
    #5
    I got 4 when I used my Powerbook here, as well as my linux machine (which doesn't really suprise me, as they're most likely using the same GCC.

    MP
     
  6. jsw
    Moderator emeritus

    jsw

    Joined:
    Mar 16, 2004
    Location:
    Andover, MA
    #6
    Shared bug then, I think, because what the code should be saying is:

    x = 0;
    x' = x+1; (x' = 1)
    x" = x' + 1; (x" = 2)
    x = x' + x"; (x = 3)

    The fact that it's considering the two "(++n)"'s as a single variable and evaluating them serially (n=1, then n=2), then adding them as though they're the same (n=2), means it's a bug.
     
  7. macrumors 68000

    Josh

    Joined:
    Mar 4, 2004
    Location:
    State College, PA
    #7
    Using Visual C++ 2005 here at work, I get 4 as well.
     
  8. Moderator emeritus

    grapes911

    Joined:
    Jul 28, 2003
    Location:
    Citizens Bank Park
    #8
    Sun's complier gave me 4. This is either huge bug in the root of C compilers, or we missing some concept of how compilers works. I'm not sure.
     
  9. macrumors 601

    zimv20

    Joined:
    Jul 18, 2002
    Location:
    chicago
    #9
    afaik, this is an undefined expression in the c++ language because the order of the evaulation of expressions is undefined.

    therefore, neither compiler result is right or wrong, because the result is simply a product of its implemenation of that undefined expression.

    i hope that, IRL, no one's coding like that.
     
  10. macrumors 68030

    superbovine

    Joined:
    Nov 7, 2003
    #10
    snicker...

    Code:
    #include <iostream>
    
    using namespace std;
    
    int main(void)
    {
    int n = 0;
    int y1, y2, y0;
    
    y1 = y2 = y0 = 0;
    
    n=(++n) + (++n);
    cout << "n:  " << n << endl;
    
    
    y1=(++y1);
    cout << "y1:  " << y1 << endl;
    y2=(++y1);
    cout << "y2:  " << y2 << "  y1:  " << y1 << endl; 
    y0 = y1 + y2;
    cout << "y0:  " << y0 << endl;
    }
    
    output
    Code:
    n:  4
    y1:  1
    y2:  2  y1:  2
    y0:  4
    
    this might clear this up...It isn't a bug.

    Think about writing the code in assembly, if you try to write it out your'll get 4.
     
  11. macrumors 6502

    Joined:
    Apr 16, 2003
    Location:
    Boston, MA
    #11
    That's true, that's really ugly code. How did this come up?
     
  12. macrumors 68030

    superbovine

    Joined:
    Nov 7, 2003
    #12
  13. thread starter macrumors 603

    notjustjay

    Joined:
    Sep 19, 2003
    Location:
    Canada, eh?
    #13
    My friend said he and his friend were playing around, so it was probably a contrived example to begin with. He found it interesting that the two of them were getting different answers.

    When I read the code in my head I see 3 (i.e. the x= x' + x'' logic that jsw wrote out above), and that is indeed what my compilers give me, so it confused me as well.

    I suppose the true proof is to see the assembly code generated and verify that it is indeed translating the compound statement into

    ++n;
    ++n;
    n = n + n;
     
  14. macrumors member

    irrªtiºnal

    Joined:
    Dec 15, 2005
    Location:
    Toronto
    #14
    ok, let;s be serious

    What's the value of i++ + i++?

    by Bjarne Stroustrup himslef...

    it also addresses the issues of

    v = i++;

    and

    f(v,i++);

    :D
     
  15. jsw
    Moderator emeritus

    jsw

    Joined:
    Mar 16, 2004
    Location:
    Andover, MA
    #15
    To quote:


    The important part is the "don't do that"....
     
  16. macrumors 65816

    MacDonaldsd

    Joined:
    Sep 8, 2005
    Location:
    London , UK
    #16
    Its more than likely because you put ++n rather n++ , that maybe why your getting a different value
    and It is 3
     
  17. macrumors G4

    Joined:
    Jan 5, 2006
    Location:
    Redondo Beach, California
    #17
    a clear example in nonclearity

    I think 3 is correct. But seeing as this is clearly not clear it serves as an example of very poor code. Code should always be clearly writen. pre-iincrements are never easy to understand and all they save is a few characters of typing. Years ago they hinted to the compiler to use some special increment instruction but optimizes are better now.
     
  18. macrumors 601

    zimv20

    Joined:
    Jul 18, 2002
    Location:
    chicago
    #18
    yes, as i said, it's undefined.
     
  19. macrumors 6502

    Joined:
    Apr 16, 2003
    Location:
    Boston, MA
    #19
  20. macrumors 68030

    Catfish_Man

    Joined:
    Sep 13, 2001
    Location:
    Portland, OR
    #20
    http://thedailywtf.com/

    Unfortunately, code much worse than the OP shows up in real life :(
     
  21. macrumors 6502

    Joined:
    Apr 16, 2003
    Location:
    Boston, MA
    #21
    Fantastic site -- Not that I'm the best programmer, as I'm usually just patching something together to run through data for myself. Even then, my code doesn't look like that.
     
  22. macrumors 65816

    MarkCollette

    Joined:
    Mar 6, 2003
    Location:
    Calgary, Canada
    #22
    Yes, this is the correct answer. In C/C++, you cannot refer to an autoincremented variabled in the same statement, as that's undefined.

    Basically, if we break down what i = ++i means, in assembler, we get:

    INCREMENT MemLocation i
    STORE MemLocation i -> MemLocation i

    Sounds straightforward, right? Well, most RISC platforms cannot operate on values in memory, but can only do so in registers. So, we have:

    LOAD MemLocation i -> Register Rx
    INCREMENT Rx
    STORE Register Rx -> MemLocation i // Keep Rx, i in sync
    STORE Register Rx -> MemLocation i // Do i = ...

    In both cases there's a redundant STORE , but maybe an optimising compiler could take away the second STORE.

    Now, let's look at i = ++i + ++i. Preincrement takes precedence over addition. Also, in this specific case, right to left, or left to right, would not make a difference, but would with a different expression.

    So a parse tree would be built like this:

    Code:
               =
              /  \
             i    +
                 / \
             pre++  pre++
               |      |
               i      i
    
    We could write that parse tree as (let me build it in steps) the following. Assume arguments are evaluated left to right:

    assignTo( "++i + ++i", i )
    assignTo( add("++i", "++i"), i )
    assignTo( add( preInc(i), preInc(i) ), i )

    Because the C/C++ language(s) do not define this any further, it all comes down to compiler implementation. So, we're left with a bunch of questions:

    1. Does each call to preInc(i) load i from memory? Or is it preloaded once, and used repeatedly, in a register, or is it lazily loaded on demand?

    2. If preInc loads i into a register, does it save that register back into the memory location i right away?

    So, a simplistic execution of the tree would yield, using lazy evaluation of i:

    // 1st preInc
    LOAD MemLocation i -> Register Rx
    INCREMENT Rx
    STORE Register Rx -> MemLocation i // Keep Rx, i in sync

    // 2nd preInc
    LOAD MemLocation i -> Register Ry
    INCREMENT Ry
    STORE Register Ry -> MemLocation i // Keep Ry, i in sync

    ADD Rx,Ry,Rz
    STORE Register Rz -> MemLocation i
    // i = 3

    Here's an optimised version, with preloading and sharing of i:

    LOAD MemLocation i -> Register Rx

    // 1st preInc
    INCREMENT Rx
    STORE Register Rx -> MemLocation i // Keep Rx, i in sync

    // 2nd preInc
    INCREMENT Rx
    STORE Register Rx -> MemLocation i // Keep Rx, i in sync

    ADD Rx,Rx,Rz
    STORE Register Rz -> MemLocation i
    // i = 4

    The core of the problem is that when you use ++i or i++ inside of an expression, you're saying, I want to to modify i and pass the value to another part of the expression. Is i in RAM, or a register? Does the other part of the expression go back to i or just use it in the working register?

    Or do we just say, do whatever's fastest on my architecture, with full optimisation:

    // i is only a register, no RAM
    // i = 0;
    // i = ++i + ++i;
    CLR Rx
    INC Rx
    INC Rx
    ADD Rx,Rx,Rx
    // i=4
     
  23. Cue
    macrumors regular

    Joined:
    Mar 10, 2005
    Location:
    Edinburgh, UK
    #23
    Excellent post MarkCollette! Kudos.
     
  24. macrumors 6502

    Joined:
    Apr 16, 2003
    Location:
    Boston, MA
    #24
    Thanks for the detailed analysis. I'm not a computer scientist by trade, so I don't really know assembly and whatnot. Good to know, thanks again for breaking it down for us.
     
  25. macrumors 65816

    MarkCollette

    Joined:
    Mar 6, 2003
    Location:
    Calgary, Canada
    #25
    Thanks guys.

    I posted that because I wanted to show how certain programming problems are caused by limitations of how computers work, under the covers, such as this issue of synchronising variables in RAM and registers. This is also the root cause of why accessing variables in multiples threads is unsafe, and so is actually an important issue.
     

Share This Page