Which is faster?

[bobpreston]

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]

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;

Who cares?

 

[bobpreston]

Thanks Thomas How's HSQLDB?

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;

Who cares?

 

[Thomas Weidenfeller]

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

 

[bobpreston]

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:

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

 

[Oliver Wong]

[post re-ordered]

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.

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]

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.

 

[Patricia Shanahan]

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;

"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]

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

 

[Lew]

pos = ++pos % bytes.length;

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]

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:

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.

I agree with his use of testing for >= rather than ==.

- Lew

 

[Eric Sosman]

I should've read Chris Uppal's post before sending mine.



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 ...

 

[=?ISO-8859-1?Q?Arne_Vajh=F8j?=]

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]

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.

 

[Chris Uppal]

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.

 

[Daniel Thoma]

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

 

[Eric Sosman]

Eric Sosman wrote:




??

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.

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.

 

[Stefan Ram]

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.

 

[Karl Uppiano]

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

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.

 

[Chris Uppal]

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