j++ or ++j in for loop
Is there much of a difference between ++j and j++ within a for loop decleration?
eg for(int j; j<max; ++j){}
I have being some practise algorythms over at topcoder, and looking at some of the top scoring entries they all seem to use ++j, where as i use j++.
I know i may be reading to much into this, and couldn't see what effect this would have on the written alogrythms, but just wanted to check if i was missing something obvious!>
[466 byte] By [
techyounga] at [2007-11-27 4:48:13]
In that case, no. Where it matters would be:int j = 0;for(int i = 0; i < max; i++){System.out.println("this is line " + (j++)); // or ++j}j++ uses j and then increments it, ++j increments j and then uses it.
My personal preference is to never ever write something like I wrote above. To me it's clouding the issue. Reading that makes you pause and think what is going on. Still need to know that, though.
I always would do this:
for(...) {
j++; // or ++j
System.out.println("this is line " + j);
}
or flip the lines, as appropriate.
or consider reading the content of an arraywith ++j you will miss the first index of the table
In the case of a for-loop initializer, it doesn't matter which form you use. It only matters when you're relying on the value of the expression. The pre-increment form returns (or evaluates to) the newly-incremented value, but the post-increment form returns the old value, then increments the variable.
A good rule of thumb is not to use the pre-increment version unless you have a very good reason to. Switching between the two indiscriminately just makes your code harder to read and more susceptible to bugs.
>A good rule of thumb is not to use the pre-increment version unless you have a very good reason to.
? You are not referring to its use in the for loop, are you?
for (int i = 0 i < MAX; ++i)
I thought it was agreed that it *really* didn't make any difference there, so use either.
Well, I don't know what difference it makes on a Java VM, but when considering the low-level details, the difference between ++i and i++ does matter.
When using i++, there is a temporary variable which is required so that the actual value of i can be saved, i is then incremented, and the saved value of i is then returned.
When using ++i, there isn't any temporary variable needed because we only care about the value of i after the incrementation. Thus we increment i and then return its new value.
Inside a for loop, there is absolutely no need to know the previous value of "i" during the incrementation part. Thus using ++i is always the best choice so we can avoid using a temporary variable for nothing. I really do hope that the Java Compiler optimizes every for loop using i++ so that it actually uses ++i, but since I can't be bothered to read the specifications, I prefer to write ++i every time and be sure my for loop is working as I expect.
It is wrong to assume that using ++i in a for loop will skip the first index.
Worrying about micro-efficiencies is a waste of time. A good compiler will take care of that.
That's something you can't assume when you code under a Real Time environment ;)
> I really do hope that
> the Java Compiler optimizes every for loop using i++
> so that it actually uses ++i, but since I can't be
> bothered to read the specifications, I prefer to
> write ++i every time and be sure my for loop is
> working as I expect.
The specification does not mandate that optimization.
> I thought it was agreed that it *really* didn't
> make any difference there, so use either.
It doesn't make any difference, which is another way of saying you don't have a good reason to do it that way. The worst that will happen in this case is that someone will ask why you used that form instead of the much more common post-increment form. If that person is a n00b, you might find yourself taking several minutes to explain why it doesn't matter which form you use. If it's an opinionated older programmer, you could get mired in a long and pointless argument. Why deal with any of that if you don't have to?
^_^
> Well, I don't know what difference it makes on a Java
> VM, but when considering the low-level details, the
> difference between ++i and i++ does matter.
If you don't know what difference it makes, how can you say that there is a difference?
You might want to read up on how the JVM works. It's a stack based architecture, so the only difference is the ordering of the iload and iinc operations.
Do you have an example of a language somewhere that actually creates a temporary variable? I could understand your concern in this case, but can't believe there are professional compiler writers who would actually do this (at least on a machine that has registers).
> Well, I don't know what difference it makes on a Java
> VM, but when considering the low-level details, the
> difference between ++i and i++ does matter.
>
Perhaps.
> That's something you can't assume when you code under
> a Real Time environment ;)
Then it is is something you should actually test rather than guessing about it.
Using the Sun 1.6 compiler there is no difference. So on a Real Time env then that should matter to you.
-
java code
-
public static void test(int n)
{
for (int i=0; i < 10; i++)
{}
}
public static void test1(int n)
{
for (int i=0; i < 10; ++i)
{}
}
-
javap -c output
-
public static void test(int);
Code:
0:iconst_0
1:istore_1
2:iload_1
3:bipush 10
5:if_icmpge14
8:iinc1, 1
11: goto2
14: return
public static void test1(int);
Code:
0:iconst_0
1:istore_1
2:iload_1
3:bipush 10
5:if_icmpge14
8:iinc1, 1
11: goto2
14: return
> If you don't know what difference it makes, how can
> you say that there is a difference?
Read more carefully, I didn't say I didn't know what difference it makes, I said I didn't know the difference it makes on a Java VM. I do know what assembly code is generated when writing i++ and ++i.
> You might want to read up on how the JVM works. It's
> a stack based architecture, so the only difference is
> the ordering of the iload and iinc
> operations.
As I said, I don't really care about knowing if the Java Compiler performs the optimization because I prefer doing the optimization manually. This way, if someone compiles my code on a different compiler for whatever reasons, I'm not depending on some specific compiler's optimizations.
> Do you have an example of a language somewhere that
> actually creates a temporary variable? I could
> understand your concern in this case, but can't
> believe there are professional compiler writers who
> would actually do this (at least on a machine that
> has registers).
Saying it "creates a temporary variable" wasn't really precise, what happens when C++ code gets compiled into assembly is the following:
the value of the variable being post-incremented is moved to a separate registry
the variable is incremented
the old value is returned as a result
So the difference between post-incrementation and pre-incrementation in terms of hardware is of 1 machine instruction and 1 registry usage.
> Then it is is something you should actually test
> rather than guessing about it.
I'm not guessing about it. I am considering there are no optimizations and I make sure I do the optimization manually. This way, I know my code will be optimized when I compile it with both a Compiler that does the optimization and a Compiler that doesn't.
Yet I'm glad to know that the standard Java Compiler protects me from all those who use i++ in for loops when I download their software! :P
> > Then it is is something you should actually test
> > rather than guessing about it.
>
> I'm not guessing about it. I am considering there
> are no optimizations and I make sure I do the
> optimization manually. This way, I know my code will
> be optimized when I compile it with both a Compiler
> that does the optimization and a Compiler that
> doesn't.
The specification makes no guarantees about how the byte codes are generated.
Thus i++ could actually use the following code (byte codes)
int temp = i
temp += 10
temp -=5
temp -=4
So obviously you should be using i=i+1 in such a case.
So exactly how are you determining other cases when you write your code such that it is optimized but yet doesn't depend on the compiler?
> The specification makes no guarantees about how the
> byte codes are generated.
>
> Thus i++ could actually use the following code (byte
> codes)
>
> int temp = i
> temp += 10
> temp -=5
> temp -=4
>
> So obviously you should be using i=i+1 in such a
> case.
It could, but this example is pretty extreme.
> So exactly how are you determining other cases when
> you write your code such that it is optimized but yet
> doesn't depend on the compiler?
Other cases include invariants inside loops. Instead of declaring an invariant inside a loop, always make sure to declare it outside of the loop even though some Compilers are able to perform this kind of optimization.
There are many other cases where good compilers will be able to Optimize, but where you can't assume all compilers do.
So basically, write your code the same way your compiler would optimize it.
> So basically, write your code the same way your compiler would optimize it.o_OThat sounds both impractical and unreasonable. One typically doesn't know how the Java compiler will optimize one's code. ~
Detail what you mean...
I don't see how using pre-incrementation in a for loop, or how declaring my invariants outside of a loop could be impratical and unreasonable.
Since you edited before I posted, here's my edit too:
One typically doesn't know unless he's taken Compiler classes or has bothered reading documentation on how to optimize code.
> Read more carefully, I didn't say I didn't know what
> difference it makes, I said I didn't know the
> difference it makes on a Java VM. I do know what
> assembly code is generated when writing i++ and ++i.
And what assembly code is generated for those?
More correctly: what assembly code, what processor architecture, and what compiler?
> As I said, I don't really care about knowing if the
> Java Compiler performs the optimization because I
> prefer doing the optimization manually.
Without knowing how the compiler generates code, how can you possibly "optimize" the input to that compiler?
> the value of the variable being post-incremented is
> moved to a separate registry
> the variable is incremented
> the old value is returned as a result
Again: what processor and what compiler?
Because GCC certainly doesn't do this on the 80x86, and it's one of the more commonly used compiler/processor combinations I can think of.
Not to mention that what a particular C++ compiler does is meaningless for Java.
And, oh by the way, "real time" doesn't mean "run as fast as you can."
> And what assembly code is generated for those?
>
> More correctly: what assembly code, what processor
> architecture, and what compiler?
Just write up a test case for yourself if you don't believe me. Write a C++ program which creates a vector, fills in a few values, retrieve an iterator and then try post-incrementing that iterator and try pre-incrementing it. When debugging this small piece of code, you'll notice the post-incrementation goes through the Copy Constructor of the Iterator while the pre-incrementation doesn't.
> Without knowing how the compiler generates code, how
> can you possibly "optimize" the input to that
> compiler?
Because I know the way post-incrementation and pre-incrementation is done and I understand the overhead implied by the post-incrementation versus pre-incrementation.
> Again: what processor and what compiler?
>
> Because GCC certainly doesn't do this on the 80x86,
> and it's one of the more commonly used
> compiler/processor combinations I can think of.
>
> Not to mention that what a particular C++ compiler
> does is meaningless for Java.
It's not meaningless. Java didn't reinvent the wheel about how to go and increment variables.
>
> And, oh by the way, "real time" doesn't mean "run as
> fast as you can."
Duh... real time is about being able to guarantee the execution time of your code to meet very precise requirements. Thus you could end up with trouble if you guarantee some time measure because your code was optimized by a compiler and it fails to meet that time measure when compiled with a compiler which doesn't perform the optimization.
> Detail what you mean...
>
> I don't see how using pre-incrementation in a for
> loop, or how declaring my invariants outside of a
> loop could be impratical and unreasonable.
The advice to "write your code the way your compiler would optimize it" is impractical and unreasonable. You don't know how the Java compiler will optimize your code until after you've analyzed the resulting byte codes.
> One typically doesn't know unless he's taken Compiler
> classes or has bothered reading documentation on how
> to optimize code.
Taking a compiler class isn't going to tell you how a particular version of a Java compiler is going to optimize your code.
Dalzhim: "I don't know what difference it makes on a Java VM..."
Dalzhim: "I really do hope that the Java Compiler optimizes..."
If you don't know how the compiler will optimize your code, there's no way to write your code the way the compiler would optimize it.
> I am considering there are no optimizations and I make sure I do the optimization manually.
Please read the following:
[url=http://java.sun.com/developer/technicalArticles/Interviews/goetz_qa.html]Writing Better Code: A Conversation With Sun Microsystems Technology Evangelist Brian Goetz[/url]
Q: So how can developers write Java code that performs well?
A: The answer may seem counterintuitive. Often, the way to write fast code in Java applications is to write dumb code -- code that is straightforward, clean, and follows the most obvious object-oriented principles. This has to do with the nature of dynamic compilers, which are big pattern-matching engines. Because compilers are written by humans who have schedules and time budgets, the compiler developers focus their efforts on the most common code patterns, because that's where they get the most leverage. So if you write code using straightforward object-oriented principles, you'll get better compiler optimization than if you write gnarly, hacked-up, bit-banging code that looks really clever but that the compiler can't optimize effectively.
So clean, dumb code often runs faster than really clever code, contrary to what developing in C might have taught us. In C, clever source code turns into the expected idiom at the machine-code level, but it doesn't work that way in Java applications. I'm not saying that the Java compiler is too dumb to translate clever code into the appropriate machine code. It actually optimizes Java code more effectively than does C.
My advice is this: Write simple straightforward code and then, if the performance is still not "good enough", optimize. But implicit in the concept of "good enough" is that you need to have clear performance metrics. Without them, you'll never know when you're done optimizing. You'll also need a realistic, repeatable, testing program in place to determine if you're meeting your metrics. Once you can test the performance of your program under actual operating conditions, then it's OK to start tweaking, because you'll know if your tweaks are helping or not. But assuming "Oh, gee, I think if I change this, it will go faster" is usually counterproductive in Java programming.
Because Java code is dynamically compiled, realistic testing conditions are crucial. If you take a class out of context, it will be compiled differently than it will in your application, which means performance must be measured under realistic conditions. So performance metrics should be tied to indices that have business value -- transactions per second, mean service time, worst-case latency -- factors that your customers will perceive. Focusing on performance characteristics at the micro level is often misleading and difficult to test, because it's hard to make a realistic test case for some small bit of code that you've taken out of context.
~
> Just write up a test case for yourself if you don't
> believe me. Write a C++ program which creates a
> vector, fills in a few values, retrieve an iterator
> and then try post-incrementing that iterator and try
> pre-incrementing it. When debugging this small piece
> of code, you'll notice the post-incrementation goes
> through the Copy Constructor of the Iterator while
> the pre-incrementation doesn't.
C++ isn't Java. Just write up a test case for yourself if you don't believe me.
> Because I know the way post-incrementation and
> pre-incrementation is done...
You apparently don't know how it's handled in Java.
> It's not meaningless. Java didn't reinvent the wheel
> about how to go and increment variables.
Just to revisit, you seem to extol writing code the way the Java compiler would optimize it, but you don't know how the Java compiler optimizes code.
~
> Just write up a test case for yourself if you don't
> believe me. Write a C++ program which creates a
> vector, fills in a few values, retrieve an iterator
> and then try post-incrementing that iterator and try
> pre-incrementing it. When debugging this small piece
> of code, you'll notice the post-incrementation goes
> through the Copy Constructor of the Iterator while
> the pre-incrementation doesn't.
And you think this convoluted case involving C++ objects applies to Java primitives how?
For that matter, how do you think it applies to C/C++ primitives?
> Because I know the way post-incrementation and
> pre-incrementation is done and I understand the
> overhead implied by the post-incrementation versus
> pre-incrementation.
Sorry, but you really haven't given any indication of that.
> It's not meaningless. Java didn't reinvent the wheel
> about how to go and increment variables.
Actually, it did. The JVM spec defines a processor architecture (among other things). That architecture is very different from the 80x86, which is very different from the MC68000, which is very different from any number of other processor architectures.
Trying to say that the way one compiler does things on one architecture can be used as a guide for a different compiler and architecture (looking at primitives now, not C++ objects) is a really great way to de-optimize your code.
> Duh... real time is about being able to guarantee
> the execution time of your code to meet very precise
> requirements. Thus you could end up with trouble if
> you guarantee some time measure because your code was
> optimized by a compiler and it fails to meet that
> time measure when compiled with a compiler which
> doesn't perform the optimization.
Then you should probably be writing assembly language
... oh wait, I'm remembering something from my days of writing real-time code in assembly language ...
yeah, there are these little things like pipelines ... and caches ... and interrupt latencies ... all important things. Strange, but I can't remember pre- versus post-increment as an issue.
...or, if you're really unlucky, you could get stuck with a tedious explanation and a long, pointless argument.:D
Perhaps this is a better explaination:
j++ is worse than ++j because...
with j++, the VM sees the j first and says "okay, what do you want me to do with this?", then sees the ++ and says "oh, that's what you want... why didn't you just say so in the first place."
with ++j, the VM sees the ++ and says "okay, I have to increment something, give it to me", then it sees j and knows what to do.
The latter results in less under-it's-breath muttering, which results in less distraction in it's train of thought, and thus better performance. Not to mention a more mentally balanced VM.
(do I really need to say I'm joking?)
Message was edited by:
bsampieri
> Inside a for loop, there is absolutely no need to
> know the previous value of "i" during the
> incrementation part. Thus using ++i is always the
> best choice so we can avoid using a temporary
> variable for nothing. I really do hope that
> the Java Compiler optimizes every for loop using i++
> so that it actually uses ++i, but since I can't be
> bothered to read the specifications, I prefer to
> write ++i every time and be sure my for loop is
> working as I expect.
In a typical program, how big a difference does it make if every loop uses ++i vs. every loop using i++? 20%? 10%? 1%? 0.00001%?
You say we're saving a single instruction, IIRC. One instruction per loop iteration. Wow.
jverda at 2007-7-21 21:13:39 >
> > And what assembly code is generated for those?
> >
> > More correctly: what assembly code, what processor
> > architecture, and what compiler?
>
> Just write up a test case for yourself if you don't
> believe me. Write a C++ program which creates a
> vector, fills in a few values, retrieve an iterator
> and then try post-incrementing that iterator and try
> pre-incrementing it. When debugging this small piece
> of code, you'll notice the post-incrementation goes
> through the Copy Constructor of the Iterator while
> the pre-incrementation doesn't.
>
You are comparing an operation on one of the standard library collections to a primitive operation?
>
> > Without knowing how the compiler generates code, how
> > can you possibly "optimize" the input to that
> > compiler?
>
> Because I know the way post-incrementation and
> pre-incrementation is done and I understand the
> overhead implied by the post-incrementation versus
> pre-incrementation.
You don't understand it if you are comparing an operation on a primitive to that of an object.
Incrementation:
After checking out the Java Language specification by myself and comparing the two different bytecode sequences for pre-incrementation and post-incrementation, I realized there is indeed no overhead implied when performing post-incrementation rather than pre-incrementation. Thus the compiler doesn't even need to actually optimize anything when the result from a post-incrementation is used.
I couldn't have been more wrong stating that pre-incrementation was better than post-incrementation.
Invariants inside loops:
On the other hand, using another TestCase, I confirmed that the Java Compiler doesn't perform any optimizations concerning invariants inside loops. Thus, the following TestCase results in 11 bytecode operations performed inside the loop in the case where you don't optimize manually, and it involves 9 bytecode operations performed inside the loop in the case you optimize manually. These 2 additional operations are 1 push and 1 pop ( iload_x and istore_x ) which could have been avoided.
public class InvariantTest {
public void invariantOutside() {
int invariant = 2;
for(int i = 0; i < 10; ++i) {
int j = i + invariant;
}
}
public void invariantInside() {
for(int i = 0; i < 10; ++i) {
int invariant = 2;
int j = i + invariant;
}
}
}
Compiled from "InvariantTest.java"
public class InvariantTest extends java.lang.Object{
public InvariantTest();
Code:
0:aload_0
1:invokespecial#1; //Method java/lang/Object."<init>":()V
4:return
public void invariantOutside();
Code:
0:iconst_2
1:istore_1
2:iconst_0
3:istore_2
4:iload_2
5:bipush10
7:if_icmpge20
10:iload_2
11:iload_1
12:iadd
13:istore_3
14:iinc2, 1
17:goto4
20:return
public void invariantInside();
Code:
0:iconst_0
1:istore_1
2:iload_1
3:bipush10
5:if_icmpge20
8:iconst_2
9:istore_2
10:iload_1
11:iload_2
12:iadd
13:istore_3
14:iinc1, 1
17:goto2
20:return
}
My conclusion:
Before talking about any optimizations ever again, I'll first check out the resulting bytecode by myself and I'll make sure they are really effective. Thus I agree that I was wrong concerning my belief that pre-incrementation was faster than post-incrementation, hopefully both of them are just as effective so it doesn't hurt choosing any of them.
As far as the conversion with Java Technology Evangelist Brian Goetz is involved, I do not intend on stopping the optimization of invariants inside loops because obviously, the compiler isn't yet ready to optimize all the dumb code that can be written.
PS: All of the following has been done using the compiler from Java 1.6.0_01
> You are comparing an operation on one of the standard
> library collections to a primitive operation?
I am not trying to compare an object with a primitive. The goal of using this object was to show that there was a temporary holder used in the post-incrementation of variables in C++ and it is easy to notice it when your debugger takes you through a class' constructor inside an incrementation operator.
>
> As far as the conversion with Java Technology
> Evangelist Brian Goetz is involved, I do not intend
> on stopping the optimization of invariants inside
> loops because obviously, the compiler isn't yet ready
> to optimize all the dumb code that can be written.
You should read that quote again.
You should note also that invariant optimization is very easy to do and that the hotspot compiler (in the VM not javac) very likely does it.
You might also try your test again by making the invariant final.
> Before talking about any optimizations ever again, I'll first check out the resulting bytecode by myself and I'll make sure they are really effective.
Sounds like a plan. I'd recommend following Goetz' advice, though, as merely looking at the bytecode is unlikely to give you an accurate picture of your application's performance as a whole.
~
> You should note also that invariant optimization is
> very easy to do and that the hotspot compiler (in the
> VM not javac) very likely does it.
But now we are guessing again aren't we? ;) I guess I'll do some reading on the subject later tonight...
> You might also try your test again by making the
> invariant final.
Making the invariant final in both cases results in the same bytecode which is shorter than the bytecode generated by both cases without the final keyword. Here's the listing:
public class InvariantTest {
public void invariantOutside() {
final int invariant = 2;
for(int i = 0; i < 10; ++i) {
int j = i + invariant;
}
}
public void invariantInside() {
for(int i = 0; i < 10; ++i) {
final int invariant = 2;
int j = i + invariant;
}
}
}
Compiled from "InvariantTest.java"
public class InvariantTest extends java.lang.Object{
public InvariantTest();
Code:
0:aload_0
1:invokespecial#1; //Method java/lang/Object."<init>":()V
4:return
public void invariantOutside();
Code:
0:iconst_0
1:istore_2
2:iload_2
3:bipush10
5:if_icmpge18
8:iload_2
9:iconst_2
10:iadd
11:istore_3
12:iinc2, 1
15:goto2
18:return
public void invariantInside();
Code:
0:iconst_0
1:istore_1
2:iload_1
3:bipush10
5:if_icmpge18
8:iload_1
9:iconst_2
10:iadd
11:istore_3
12:iinc1, 1
15:goto2
18:return
}
So overall, the best choice remains using the final keyword to make sure invariants are optimized appropriately. Learning never ends.
> > You should note also that invariant optimization is
> > very easy to do and that the hotspot compiler (in the
> > VM not javac) very likely does it.
>
> But now we are guessing again aren't we? ;)
But in this case the only way to determine it is by following Goetz' advice. Because it is a runtime optmizer.
> But now we are guessing again aren't we?
Yep. Attempting evaluate production performance bottlenecks by browsing source and bytecodes isn't likely to give useful results.
> So overall, the best choice remains using the final
> keyword to make sure invariants are optimized
> appropriately.
In my personal and professional opinion, the best choice is to write clean, simple code, and address performance bottlenecks as they arise and only after they are confirmed through the use of appropriate metrics and a profiler.
~
> > You are comparing an operation on one of the
> standard
> > library collections to a primitive operation?
>
> I am not trying to compare an object with a
> primitive. The goal of using this object was to show
> that there was a temporary holder used in the
> post-incrementation of variables in C++ and it is
> easy to notice it when your debugger takes you
> through a class' constructor inside an incrementation
> operator.
You are missing the point however.
What a compiler does for a object operator is significantly different than what it does for a primitive operator.
Comparing them is not valid.
Most (perhaps all) C++ compilers will generate assembly if you provide the correct command line parameter. You should use that to see what a C++ compiler does with a primitive operator.
