PDA

View Full Version : 3? or 4?




notjustjay
Feb 15, 2006, 09:39 PM
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?



mwpeters8182
Feb 16, 2006, 12:46 PM
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)

jsw
Feb 16, 2006, 12:49 PM
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)
I think it's a compiler bug. The first ++n should have been stored as a result before the second ++n was evaluated.

notjustjay
Feb 16, 2006, 12:54 PM
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.

mwpeters8182
Feb 16, 2006, 12:58 PM
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

jsw
Feb 16, 2006, 01:09 PM
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
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.

Josh
Feb 16, 2006, 01:11 PM
Using Visual C++ 2005 here at work, I get 4 as well.

grapes911
Feb 16, 2006, 01:13 PM
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.

zimv20
Feb 16, 2006, 01:34 PM
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.

superbovine
Feb 16, 2006, 01:35 PM
snicker...


#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

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.

mwpeters8182
Feb 16, 2006, 01:36 PM
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.

That's true, that's really ugly code. How did this come up?

superbovine
Feb 16, 2006, 01:48 PM
That's true, that's really ugly code. How did this come up?

huh?

http://www.cppreference.com/operator_precedence.html

notjustjay
Feb 16, 2006, 02:05 PM
That's true, that's really ugly code. How did this come up?

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;

irrŠtišnal
Feb 16, 2006, 02:07 PM
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?

ok, let;s be serious

What's the value of i++ + i++? (http://www.research.att.com/~bs/bs_faq2.html#evaluation-order)

by Bjarne Stroustrup himslef...

it also addresses the issues of

v[i] = i++;

and

f(v[i],i++);

:D

jsw
Feb 16, 2006, 02:11 PM
ok, let;s be serious

What's the value of i++ + i++? (http://www.research.att.com/~bs/bs_faq2.html#evaluation-order)

by Bjarne Stroustrup himself
To quote:What's the value of i++ + i++?

It's undefined. Basically, in C and C++, if you read a variable twice in an expression where you also write it, the result is undefined. Don't do that. Another example is:
v[i] = i++;
Related example:
f(v[i],i++);
Here, the result is undefined because the order of evaluation of function arguments are undefined.
Having the order of evaluation undefined is claimed to yield better performing code. Compilers could warn about such examples, which are typically subtle bugs (or potential subtle bugs). I'm disappointed that after decades, most compilers still don't warn, leaving that job to specialized, separate, and underused tools.


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

MacDonaldsd
Feb 16, 2006, 02:19 PM
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?

Its more than likely because you put ++n rather n++ , that maybe why your getting a different value
and It is 3

ChrisA
Feb 16, 2006, 02:21 PM
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.

zimv20
Feb 16, 2006, 02:47 PM
yes, as i said, it's undefined.

mwpeters8182
Feb 16, 2006, 03:44 PM
huh?

http://www.cppreference.com/operator_precedence.html

I know operator precedence. I was wondering why this conversation came up, as no one would code like that in real life situations.

Catfish_Man
Feb 17, 2006, 01:02 AM
I know operator precedence. I was wondering why this conversation came up, as no one would code like that in real life situations.

http://thedailywtf.com/

Unfortunately, code much worse than the OP shows up in real life :(

mwpeters8182
Feb 17, 2006, 07:14 AM
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.

MarkCollette
Feb 22, 2006, 10:27 PM
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.

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:


=
/ \
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

Cue
Feb 23, 2006, 04:44 AM
Excellent post MarkCollette! Kudos.

mwpeters8182
Feb 23, 2006, 11:40 AM
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.

MarkCollette
Feb 23, 2006, 12:34 PM
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.

mbabauer
Feb 23, 2006, 07:53 PM
Honestly, this looks like a difference in how the respective compilers try to optimize code. I don't think this has to do so much with the order that the pieces are interpreted as much as the compiler trying to save some bytes of memory.

Think about it this way. WHY would the compiler think both 'n' vars were the same? The only answer is that it seems the compiler saw the first ++n, then the second and said "instead of putting this in its own register, lets save a little and use the same one".

Perhaps some optimization to minimize memory footprint is turned on in one compiler but not the other?

zimv20
Feb 23, 2006, 08:42 PM
Perhaps some optimization to minimize memory footprint is turned on in one compiler but not the other?
it's already been explained, quite thoroughly.

darkwing
Feb 24, 2006, 11:45 AM
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.

Mark, your post reminded me of my programming language concepts class. I wanted to take compiler design last quarter, but it didn't fit my schedule. They don't offer the graduate version again before I'll be finished, so oh well. Maybe I'll come back and take it just for fun.

Great post. :)

bbarnhart
Feb 25, 2006, 05:15 PM
http://thedailywtf.com/

Unfortunately, code much worse than the OP shows up in real life :(

Thanks for this link. I didn't know about this site and it cracked me up. Reading the site and seeing the submissions for bad code it makes me think of my job and this person I worked with.

zimv20
Feb 25, 2006, 05:27 PM
this person I worked with.
'person', singular? either you're very lucky or have worked in only one place, with a small developer staff. :-)