Counting down faster when looping?

[Tilman Bohn]

In message <[email protected]>,
jonck wrote on 8 Feb 2005 11:36:16 -0800:

[...]

For me the number of values in arr[] could go no larger than 14897979,
14897980 gave me an outOfMemoryError. You guys were talking about
having this value at 100000000, a number about 7 times larger, yet you
were (obviously) not getting an OutOfMemoryError.

You need to increase the memory allocation pool. On Sun's VM, this
is achieved by the options Xms and Xmx (initial and max, resp.) on
recent releases. For example:

java -Xms512m -Xmx512m Test

will run ok on my machine with 100000000.

Any ideas what could be causing this for me?

Yeah. The VM is running out of memory. Hence OutOfMemoryError. ;-)

 

[jonck]

Thank you, that did the trick.

 

[Bob]

[If it's indeed true, the next question would be: Is it also worth
while? (Any benchmark tests?)]

Not worthwhile on my machine.

A quick test of 2,000,000,000 iterations, one set in a ++i loop, one set
in a --i loop, both using final values so that loop time only was
measured, gave the following durations in milliseconds:

++i
2719, 2719, 2735, 2781, 2703, 2734, 2719, 2735

--i
2734, 2734, 2718, 2735, 2719, 2734, 2704, 2703


Which averages to

++i 2730.63 milliseconds
--i 2722.63 milliseconds

Which is a saving of 0.29%. I agree with the poster that said that
readability was more important than tiny performance gains.

 

[Steve Bosman]

Rene wrote:

I agree with your comments, but I wanted to point out that:

No one would code a loop like this:

(for int i = 0; i < longSlowComputation(); i++)
{
...

And so, when we code an array loop as:

(for int i = 0; i < array.length; i++)
{
...

I'm surprised I haven't seen the following suggestion in this thread so
far, that is coding the loop as
(for int i = 0, iMax=array.length; i < iMax; i++) {
...

My experience is that this is generally a very good practice when
determining the loop end is slow. I have just tried it with
array.length and I'm surprised that it does seem to make a minor
difference even then. Definitely more readable and maintainable than
reversing loops.

Steve

 

[bugbear]

I have seen the suggestion (in, for instance, AppPerfect) that counting
down rather than up when looping through an array will improve
performance. That is, doing it this way:

(1) for (int i=arr.length-1; i>=0; i--) {...}

would be slightly faster than this:

(2) for (int i=0; i<arr.length; i++) {...}

[I think it's got to do with testing against zero (which would be more
effective)].

That is what I've also heard. Though it's quite long since I last heard
that. IF this is the case, the difference is exactly one single
Maschine-Code instruction per iteration, ie (in pseudocode):

ADD counter, -lenght
TEST counter zero

instead of only

TEST counter zero

<nostalgia>
On many historic CPU's the "result was zero" flag is set by the
decrement operation itself, so no compare instruction was/is
needed at all.

Some cpu's went so far as do have a decrement counter and branch
if not zero instruction, which is (to say the least) well suited
to the decrementing form of the loop.

As was mentioned elsewehere, the "length" may not be in a simple
location, since the body of the loop may (or may not) change
the array, and hence it's length. These considerations may
prevent the optimiser moving the array length to a constant.
</nostalgia>

However, without a proven major speed benefit, I wouldn't worry.

In particular if the body of the loop is doing something
"significant" the loop overhead is the least of your worries.

BugBear

 

[bugbear]

I have seen the suggestion (in, for instance, AppPerfect) that counting
down rather than up when looping through an array will improve
performance. That is, doing it this way:

(1) for (int i=arr.length-1; i>=0; i--) {...}

would be slightly faster than this:

(2) for (int i=0; i<arr.length; i++) {...}

[I think it's got to do with testing against zero (which would be more
effective)].

My question is: Would this be true in a general sense (i.e. for all
JVMs)? To me, it seems that it would be possible to optimize a JVM also
for version (2) above...(?)

[If it's indeed true, the next question would be: Is it also worth
while? (Any benchmark tests?)]

Oh, BTW, running loops backwards can sometimes have unintended negative
performance consequences w.r.t memory cacheing at various
levels.

BugBear

 

[Walter Mitty]

I think that the "counting down" vs "counting up" philosophy is rooted in
ancient times when decrementing the register was a slightly faster an
operation than the incrementing one.

More to do with the comparison against the arrays length as opposed to a
check for zero.