Java Forum / General / October 2006
Which is faster?
bobpreston@gmail.com - 06 Oct 2006 17:35 GMT Assuming I have the following:
byte[] bytes = new byte[100]; int pos = 0;
which is faster:
pos++; pos %= bytes.length;
or:
pos = ++pos % bytes.length;
Thanks in advance,
Bob
Thomas Kellerer - 06 Oct 2006 17:45 GMT bobpreston@gmail.com wrote on 06.10.2006 18:35:
> Assuming I have the following: > [quoted text clipped - 9 lines] > > pos = ++pos % bytes.length; Who cares?
bobpreston@gmail.com - 06 Oct 2006 17:53 GMT Thanks Thomas :) How's HSQLDB?
> bobpreston@gmail.com wrote on 06.10.2006 18:35: > > Assuming I have the following: [quoted text clipped - 12 lines] > > Who cares? Thomas Weidenfeller - 06 Oct 2006 18:12 GMT > Assuming I have the following: > > byte[] bytes = new byte[100]; > int pos = 0; > > which is faster: It does not matter. And if it would be really an important issue for you, you would measure it.
/Thomas
 Signature The comp.lang.java.gui FAQ: http://gd.tuwien.ac.at/faqs/faqs-hierarchy/comp/comp.lang.java.gui/ ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/computer-lang/java/gui/faq
bobpreston@gmail.com - 06 Oct 2006 18:42 GMT I don't believe measuring it on one platform is sufficient, since my program is deployed on many platforms. The code is in a method at the high end of the execution chain, which I would like to optimize as much as possible. If it truly doesn't matter, then I'll go with the more maintainable solution (since its a 1 liner):
pos = ++pos % bytes.length;
Bob
> > Assuming I have the following: > > [quoted text clipped - 11 lines] > http://gd.tuwien.ac.at/faqs/faqs-hierarchy/comp/comp.lang.java.gui/ > ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/computer-lang/java/gui/faq Oliver Wong - 06 Oct 2006 19:01 GMT [post re-ordered]
>> > Assuming I have the following: >> > [quoted text clipped - 8 lines] >I don't believe measuring it on one platform is sufficient, since my > program is deployed on many platforms. So measure it on enough platforms for it to be sufficient?
> The code is in a method at the > high end of the execution chain, which I would like to optimize as much > as possible. If it truly doesn't matter, then I'll go with the more > maintainable solution (since its a 1 liner): > > pos = ++pos % bytes.length; FWIW, I think this is less maintainable, as it is an expression which assigns to the same variable twice, which many programmers find confusing.
- Oliver
Christopher Benson-Manica - 06 Oct 2006 19:29 GMT > > pos = ++pos % bytes.length;
> FWIW, I think this is less maintainable, as it is an expression which > assigns to the same variable twice, which many programmers find confusing. Not to mention that programmers, such as myself, with a C or C++ background are likely to berate such code's author for invoking dreaded Undefined Behavior before realizing that Java at least improved the situation by guaranteeing the behavior of that code.
As a contradictory data point, however, it seems that IntelliJ will not generate an inspection warning on that code; I was sure it would have complained about the stylistic dubiousness of it, but apparently not.
 Signature C. Benson Manica | I *should* know what I'm talking about - if I cbmanica(at)gmail.com | don't, I need to know. Flames welcome.
Lew - 07 Oct 2006 18:23 GMT >>> pos = ++pos % bytes.length;
>> FWIW, I think this is less maintainable, as it is an expression which >> assigns to the same variable twice, which many programmers find confusing. Then they aren't very good programmers. In fact, I recommend that one use this type of example as an interview question to avoid hiring those who find it confusing.
> Not to mention that programmers, such as myself, with a C or C++ > background are likely to berate such code's author for invoking > dreaded Undefined Behavior Slightly O-T, but doesn't C[++] guarantee behavior across the assignment, i.e., that the right side is fully evaluated before storing to the left?
As you point out, Java does make this guarantee.
Just to complicate matters, there's another idiom that replaces the overhead of the mod operator and second assignment with the overhead of a test-and-branch:
if ( ++pos == bytes.length ) { pos = 0; }
- Lew
Lew - 07 Oct 2006 18:27 GMT > if ( ++pos == bytes.length ) > { > pos = 0; > } I should've read Chris Uppal's post before sending mine.
> BTW, when you do measure (if you bother), don't forget to test a version > without the modulus operator: [quoted text clipped - 10 lines] > time -- it depends on whether the optimiser in the JIT (if any, on your target > platforms) spots the repeated use of bytes.length by itself. I agree with his use of testing for >= rather than ==.
- Lew
Eric Sosman - 07 Oct 2006 21:20 GMT >> if ( ++pos == bytes.length ) >> { [quoted text clipped - 25 lines] > > I agree with his use of testing for >= rather than ==. It makes me wonder, queasily, whether the next line ought to read `pos -= bytes.length' or even `pos %= bytes.length'. Context is king ...
 Signature Eric Sosman esosman@acm-dot-org.invalid
Chris Uppal - 08 Oct 2006 10:52 GMT > > I agree with his use of testing for >= rather than ==. > > It makes me wonder, queasily, whether the next line ought > to read `pos -= bytes.length' or even `pos %= bytes.length'. ??
I know my code is not always to everybody's taste, but it has been quite a while since someone last complained that it caused feelings of incipient nausea...
-- chris
P.S. In case it isn't obvious: I'm not offended, just curious.
Eric Sosman - 08 Oct 2006 14:41 GMT >>>I agree with his use of testing for >= rather than ==. >> [quoted text clipped - 10 lines] > > P.S. In case it isn't obvious: I'm not offended, just curious. We're considering two alternative code snippets:
Alternative EQ: if (++pos == bytes.length) pos = 0;
Alternative GE: if (++pos >= bytes.length) pos = 0;
Neither can be deemed "correct" or "incorrect" in isolation, of course: it is necessary to look at the rest of the code to see how `pos' is computed and used. Nonetheless, the form of EQ strongly suggests its purpose: the index `pos' is cycling through the positions of the array `bytes'. In the rest of the code it would be startling to find `pos' declared as a `float', or set to Integer.MAX_VALUE, or set to a negative value (other than, possibly, -1 at the very beginning), or advanced more than once per iteration of the loop that almost certainly encloses the code. We've seen things like EQ before, and we know how the form is used.
Alternative GE causes me to wonder whether there's a legitimate way for `pos' to become large, how large it might become, and what the significance of a large value might be. I wonder whether the programmer who wrote GE instead of EQ might be guarding against some devious pathway that could change `pos' before arriving at this piece of code, and I start looking for that pathway. I also find myself thinking that if `pos==bytes.length' cycles back to zero, perhaps `pos==bytes.length+1' should cycle back to 1 instead of zero, or `pos==bytes.length+n' should cycle back to n -- after all, this is a form I've seen before, too, in situations like searching through open-addressed hash tables.
So when I see alternative GE instead of EQ I start asking "Why?" and this disrupts my reading of the code. Only a very little bit, to be sure, since I've had many years' practice at reading code and a tiny trivial matter like this one won't bother me very long.
One tiny final point: Java, unlike many languages I've used, checks array indices for validity. Because of this, there might be a very small advantage to using alternative EQ instead of GE, the idea being that if there is in fact a bug somewhere that makes `pos' large before arriving at the code snippet, GE will "throw a blanket" over the bug if it executes before the bad `pos' value actually gets used. EQ, on the other hand, will let the bad value survive to be exposed by an ArrayIndexOutOfBoundsException, possibly leading to earlier detection and repair of the programming error. Maybe.
Tempest in a teapot, really.
 Signature Eric Sosman esosman@acm-dot-org.invalid
Stefan Ram - 08 Oct 2006 15:08 GMT >if (++pos == bytes.length) >if (++pos >= bytes.length) >the significance of a large value might be. I wonder whether the >programmer who wrote GE instead of EQ might be guarding against >some devious pathway that could change `pos' before arriving at >this piece of code, and I start looking for that pathway. I also The ">=" is more defensive, but some avoid it for exactly this reason: They /want/ their code to fail when pos>bytes.length in order to detect such an illegal state as early as possible.
>large before arriving at the code snippet, GE will "throw a blanket" >over the bug if it executes before the bad `pos' value actually gets Yes, this is what I just meant to say.
Another reason to prefer one of the two are formal program proofs: If the postcondition "pos == bytes.length" is needed for the proof, then it is helpful to use "if( pos == bytes.length )", because then the postcondition is obviously fulfilled.
Chris Uppal - 09 Oct 2006 11:54 GMT > So when I see alternative GE instead of EQ I start asking "Why?" > and this disrupts my reading of the code. Only a very little bit, > to be sure, since I've had many years' practice at reading code and > a tiny trivial matter like this one won't bother me very long. Thanks for the explanation.
FWIW, I don't agree (although it's an interesting issue in a small way) -- I would find an == test distracting, 'cos I'd have to check the rest of the code to ensure that pos couldn't be incremented off the end...
I suppose it's a question of whether you prefer the weakest possible condition (within reason) for taking the true branch, or the weakest possible condition for taking the false branch.
-- chris
Arne Vajhøj - 08 Oct 2006 01:00 GMT >>>> pos = ++pos % bytes.length;
> Slightly O-T, but doesn't C[++] guarantee behavior across the > assignment, i.e., that the right side is fully evaluated before storing > to the left? No.
The C++ standard say that you can only modify a variable once between sequence points (in this case the entire line).
If one do it anyway, then it is "undefined behaviour".
Arne
Christopher Benson-Manica - 08 Oct 2006 03:38 GMT > Slightly O-T, but doesn't C[++] guarantee behavior across the assignment, > i.e., that the right side is fully evaluated before storing to the left? No. If you're so inclined, you might find the C faqs on this topic to be of interest, starting with http://c-faq.com/expr/ieqiplusplus.html. As another poster mentioned, the C++ standard makes similar (non) guarantees.
 Signature C. Benson Manica | I *should* know what I'm talking about - if I cbmanica(at)gmail.com | don't, I need to know. Flames welcome.
Patricia Shanahan - 06 Oct 2006 19:54 GMT > I don't believe measuring it on one platform is sufficient, since my > program is deployed on many platforms. The code is in a method at the [quoted text clipped - 3 lines] > > pos = ++pos % bytes.length; "Code is usually clearer when each expression contains at most one side effect, as its outermost operation..." http://java.sun.com/docs/books/jls/second_edition/html/expressions.doc.html#4779
This line is particularly bad, because both side effects modify pos, and the one done by ++pos is dead - only the value of the expression is ever used.
What is wrong with this?
pos = (pos + 1) % bytes.length;
As far as performance is concerned, I would examine the method in terms of two key issues:
1. Cache hit vs. cache miss.
2. Conditional branches, and especially conditional branch predictability.
A single cache miss, or a mispredicted branch, will cost far, far more than changes in exactly how you do a little arithmetic, using the same data.
Patricia
Chris Uppal - 07 Oct 2006 12:15 GMT > I don't believe measuring it on one platform is sufficient, since my > program is deployed on many platforms. Which is sensible, but if you can't measure it on all your target platforms, then how do you expect us to know which is faster without even knowing what those platforms are, or which are most important to you ?
> The code is in a method at the > high end of the execution chain, which I would like to optimize as much > as possible. If it truly doesn't matter, then I'll go with the more > maintainable solution (since its a 1 liner): It is perfectly possible (though, I'd guess, not too likely) that if this code is in the inner loop of your application then its speed is critical for the overall app. If you suspect that might be the case then /measure/ it.
BTW, when you do measure (if you bother), don't forget to test a version without the modulus operator:
if (++pos >= bytes.length) pos = 0;
It involves a branch (but one which, I imagine, would normally be correctly predicted by the CPU -- if you are running on a machine with instruction pipelining and branch prediction), but saves a mod operation. You (unless you know a lot more about your target architectures than you have said) can't guess which is quicker, so -- again -- you have to measure it. I might be worth putting bytes.length into a local variable too, OTOH that might be a waste of time -- it depends on whether the optimiser in the JIT (if any, on your target platforms) spots the repeated use of bytes.length by itself.
But, whatever you do, DON'T use:
> I'll go with the more > maintainable solution (since its a 1 liner): > > pos = ++pos % bytes.length; It pre-increments pos and assigns to it -- which is just daft.
-- chris
Daniel Thoma - 08 Oct 2006 14:34 GMT > which is faster: Both versions are exactly equally fast, since the produced bytecode is the same:
0: bipush 100 2: newarray byte 4: astore_1 5: iconst_0 6: istore_2 7: iinc 2, 1 10: iload_2 11: aload_1 12: arraylength 13: irem 14: istore_2
Do you really have a good reason for worrying about such details? I ask because there aren't many good reasons out there...
Daniel
Karl Uppiano - 08 Oct 2006 19:23 GMT >> which is faster: > Both versions are exactly equally fast, since the produced bytecode is [quoted text clipped - 16 lines] > > Daniel Ha! I suspected as much - the bytecodes are the same! Obsessing over the fine points at the language level is almost always a waste of time. You may have to re-tune your code every time you change compilers, change runtimes, or change platforms. Spend that time coming up with a better overall design.
Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
|
|