"for" or "do-while" loop

Mar 24, 2006 at 8:54am

"for" or "do-while" loop

I read somewhere that in javascript the “do-while” loop, with a decremental iterator is faster than the “for” loop with an incremental iterator. I’m wondering if this is also true in java?

That is, will this:

int i = array.length;
do
{
…stuff…
–i;
}
while (i > 0);

be faster than this:

for(int i = 0;i < array.length;i++)
{
…do stuff…
}

The article didn’t really say why, except to mention that counting down is faster than counting up(??)
[head scratching] :-|

(Note that, in the javascript example I saw, the “–i” could also double as a conditional so that when –i reached zero it evaluated as “false”. However, in java I couldn’t get that to compile, as there was a type mismatch between the int iterator and the boolean while condition. I guess javascript is easier on typing(???)…)

J.

[ edit ]

actually, looking this over, if the decrement is really the issue, couldn’t I also do this:

for(int i = array.length;i > 0;i–)
{
…stuff…
}

Also, I’ve gone back to the article, and it does mention (without explanation) that the “flipped loop” is faster. Anybody know for sure?

#25045
Mar 24, 2006 at 9:16am

hi,

> int i = array.length;
> do
> {
> …stuff…
> –i;
> }
> while (i > 0);
if array is empty, you’re dead…

> for(int i = 0;i < array.length;i++)
> {
> …do stuff…
> }
don’t compare for and do..while.

for(a;b;c){d;}

is similar to

a;
while(b)
{
d;
c;
}

things to optimize are b and c.

using i
which is more expensive than just doing i>0 or i!=0
so counting down is more usefull in this case as the end condition is i>0

This “optimization” is not very usefull except in audio perform
functions. if d; is a very big calculation, then evaluating the
condition is nothing. If d is just copying a float from an array to
another, optimizing comparision is important.

regards,
Chris

#73199
Mar 24, 2006 at 9:27am

okay, thanks.

[BTW, trying this out I did figure out that "array.length" has to actually be "array.length - 1" in the decrementing version -- in case you were worried!]

But if optimizing “b” in “for(a;b;c){d;}” is important, then wouldn’t:

for(i = array.length -1; i > 0; i–)

be more efficient than:

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

simply because “array.length” has to be checked on each loop? Or is that just naive of me (that is, does the for loop just store the value of array.length once for the duration of the loop)?

J.

#73200
Mar 24, 2006 at 11:59am

jbmaxwell wrote:
> But if optimizing “b” in “for(a;b;c){d;}” is important, then
> wouldn’t:
>
> for(i = array.length -1; i > 0; i–)
>
> be more efficient than:
>
> for(i = 0; i < array.length; i++)

You lose readability that way, instead you could

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

which is more common if iterating a List sequentially (instead of using
iterator) because calls to size() are relatively costly.


Owen

#73201
Mar 24, 2006 at 11:59am

On 24-Mar-2006, at 10:28, jbmaxwell wrote:
> But if optimizing “b” in “for(a;b;c){d;}” is important, then wouldn’t:
>
> for(i = array.length -1; i > 0; i–)
>
> be more efficient than:
>
> for(i = 0; i < array.length; i++)
>
> simply because “array.length” has to be checked on each loop? Or is
> that just naive of me (that is, does the for loop just store the
> value of array.length once for the duration of the loop)?

Array.length is *probably* only evaluaated once and cached in a
register, unless there is a chance that the loop will add/delete
items to the array.

However, in general, comparisons with zero can be a tiny bit more
efficient than other comparisons.

OTOH, if you’re worrying about stuff like this, JavaScript is not the
language you want to be using. (a) JScript has all sorts of overhead
that is probably costing far more than the difference between pre-
and post-dec or comparison w/zero and (b) depending on the
implementation, may be doing lots of optimizations without you
knowing about it.

– P
————– http://www.bek.no/~pcastine/Litter/ ————-
Peter Castine +–> Litter Power & Litter Bundle for Jitter

iCE: Sequencing, Recording & |home | chez nous|
Interface Building for |bei uns | i nostri|
Max/MSP Extremely cool http://www.castine.de

http://www.dspaudio.com/

#73202
Mar 24, 2006 at 12:14pm

Owen,

“for (int i =0, n = array.length; i < n; i++)"

That’s a good idea… didn’t realize you could do that! Also, this seems to imply that the value for the loop condition (i.e. array.length) is not cached, but is checked each time through the loop. Yes? If so, that’s very good to know. Anyway, I’ll probably apply the above format more often — at least for larger, more frequently used loops with a “.length” end condition.

thanks!

———————————————————— —

Peter,

Sorry I wasn’t very clear. I’m doing this all in java, it’s just that the article I was reading about optimization was referring to javascript. Two fairly different beasts, I know!

cheers,

J.

#73203
Mar 24, 2006 at 2:08pm

On 24-Mar-2006, at 12:59, Owen Green wrote:
>> for(i = array.length -1; i > 0; i–)
>> be more efficient than:
>> for(i = 0; i < array.length; i++)
>
> You lose readability that way, instead you could

Readability is a matter of custom and taste, but on second reading,
the first snippet is just plain wrong. It should be

for (i = array.length; i > 0; i -= 1)

(eminently readable in my book)

Whether you express the decrement as postdec, predec, or explicit
subtraction is not the point. The point is you want to run through
the loop array.length times. Look at the code snippets and consider
what happens if array.length is zero and one. Then use induction to
verify correctness (or lack thereof).

I’ll spare y’all the sermon on why post/predec are Work of the Devil
(or K&R, which amounts pretty much to the same thing).

Added points if you recognize the reference to Cage.

– P.

————– http://www.bek.no/~pcastine/Litter/ ————-
Peter Castine +–> Litter Power & Litter Bundle for Jitter

iCE: Sequencing, Recording & |home | chez nous|
Interface Building for |bei uns | i nostri|
Max/MSP Extremely cool http://www.castine.de

http://www.dspaudio.com/

#73204
Mar 24, 2006 at 2:22pm

there’s also a fancy new j1.5 foreach construct:
for (Object curr : objects) {}

like iterators, but easier!

also don’t forget to only optimize only what needs optimization*.
just because someone says something is better somewhere doesn’t mean
that’s always the case, esp. if it mucks with your code readability.

*roughly speaking. but this discussion is about java & javascript, so
I think it’s a fair comment.

r.

#73205
Mar 24, 2006 at 2:37pm

I’m guessing that the for-each would require some wrapper object for my boring old String[] arrays(??).
Interesting to keep in mind though.

As far as optimization goes, my issue is that I’m doing things in java that should probably be done in C or C++. I just don’t know those languages, and I’m not up for the headache of learning them at the moment (one day, but not today!).
So, optimization is actually pretty important in my case. I mean, I got a noticable performance gain by getting rid of a couple of “post()” calls… jeez! I guess they’re pretty expensive. But it’s kind of ironic that the calls I was using to debug my app are, in fact, the cause of the bugs!

The other thing about optimization is that I’d just like to understand how to do it, and when, and why. After all, if you have 30 loops, and they’re all being done in a way that could be more efficient, then fixing the lot of them would presumably give a worthwhile improvement. No?

As far as my loops go, it turns out that the structure of the data actually requires an increment (not decrement) — I had forgotten that little point! So I’m going to give Owen’s suggestion a try.

thanks,

J.

#73206
Mar 28, 2006 at 1:20am

>
> The other thing about optimization is that I’d just like to
> understand how to do it, and when, and why.

how: matter of taste/experience. For instance, creating a lot of
objects in a tight loop in java is often not very
efficient. You could instead have an object pool of precreated
instances of the object you need and
grab them when needed.Of course this involves more book keeping and
is more error prone.

when: after your code already works as expected and is as bug free
and well designed as possible.

why: because you are in a situation where you can get a SIGNIFICANT
improvement in speed/efficiency
and that speed is a required. It is often stupid to destroy the
maintainability/legibility of your code for a
speedup of 5 or 10 percent.

just my limited 2 cents!
topher

#73207
Mar 28, 2006 at 7:23am

On 24-Mar-2006, at 15:37, jbmaxwell wrote:
> I mean, I got a noticable performance gain by getting rid of a
> couple of “post()” calls…

The context-switch between the Java world and the “real” Max world is
known to be expensive. A post() in the middle of your code is a
context-switch.

This is not a “bug”, it’s simply the way the world works. It didn’t
cause your work to crash, nor did it introduce errors. It just took
processing time.

Compared to that, worrying about whether you’re predec’ing or
postdec’ing in loops is ridiculous, particularly if it leads you to
introduce errors into your code. The phrase “penny-wise, pound-
foolish” comes to mind. Worrying about whether array.length is cached
in a register is something you should leave to your Java compiler and
the byte-code interpreter.

If you’re really concerned about code efficiency, you need to spend
some time with Knuth or Wirth or some other solid books on
programming technique. Bentley’s _Programming Pearls_ books are
probably the most readable.

> After all, if you have 30 loops, and they’re all being done in a
> way that could be more efficient, then fixing the lot of them would
> presumably give a worthwhile improvement. No?

Not necessarily.

Bentley tells the story of one “optimization” that caused a bug in a
working program. The punchline is that the bug didn’t turn up until
five months after the “optimization” had been implemented because the
piece of code that had been “optimized” was not called one single
time by the computer in the intervening period.

Think about that.

> The other thing about optimization is that I’d just like to
> understand how to do it, and when, and why.

People look at optimizing code when there is a demonstrable
performance problem that needs to be dealt with. Then they analyze
*where* the bottlenecks are and address them. Serious optimization
involves profiling code, incrementally adding proposed optimizations,
and testing the effect of the changes.

Nothing against developing efficient programming techniques, but the
first skill in that park is writing code that is correct.

– P

————– http://www.bek.no/~pcastine/Litter/ ————-
Peter Castine +–> Litter Power & Litter Bundle for Jitter

iCE: Sequencing, Recording & |home | chez nous|
Interface Building for |bei uns | i nostri|
Max/MSP Extremely cool http://www.castine.de

http://www.dspaudio.com/

#73208
Mar 28, 2006 at 3:04pm

“This is not a “bug”, it’s simply the way the world works.”

Yes, understood… I actually wasn’t implying that this was a bug in Max, but rather that this was the cause of what I had (mis)interpreted to be a bug in my program — though not really a bug, just generally poor performance.

“People look at optimizing code when there is a demonstrable
performance problem that needs to be dealt with. Then they analyze *where* the bottlenecks are and address them.”

This is precisely the stage I’m at now. I’ve got my app running, but with pretty poor performance — as in, more instances starts the app hiccupping, and more rapid input eventually hangs Max with a spinning ball (though both appear to be cured by removing the post() calls). I was assuming that this was an event backlog problem, and wondered if it was being caused by the time my java code was taking to get it’s part of the work done. So I started looking into the overall java program flow, as well as various optimizations, to try to speed things up.

Anyway, although I’ve learned what little I know about writing code from reading various books, I’m still self-taught, and thus always wondering whether I’ve done things in the most efficient way. Also, there’s so much mud-slinging to be found about poor performance in java vs. C/C++ that I think I’m suffering under the (vague) impression that every line of java code must be as tight as humanly possible if I ever intend to do anything more than print address lables. (It feels a bit like walking out onto the court at The French Open holding a wooden racket.)
But then suddenly I stumble upon an article that claims to quadruple java performance through optimization, and so on — I buy loads of herbal viagra, 10,000 shares of some stock that’s about to go through the roof, and send my banking information to that guy in Nigeria (or wherever he is now)… You get the idea.

And in cyberspace, only the poor folks on the Max list can hear me scream.

Thanks for the reading tips!

cheers,

J.

#73209
Mar 28, 2006 at 9:49pm

On 06-03-28, at 1104, jbmaxwell wrote:
>
> This is precisely the stage I’m at now. I’ve got my app running,
> but with pretty poor performance — as in, more instances starts
> the app hiccupping, and more rapid input eventually hangs Max with
> a spinning ball (though both appear to be cured by removing the post
> () calls).
>
as a general rule of thumb, post(“max!”) and it’s friends in whatever
language it might be (printf(“c”), println(“java”)) are expensive,
especially if they get flushed all the way through to screen/disk
each time. they’re good for spot-check debugging, or if there’s no
way to attach a real debugger, but they will seriously slow things down.

best,
r.

#73210
Mar 29, 2006 at 12:57pm

On 28-Mar-2006, at 17:04, jbmaxwell wrote:
> Also, there’s so much mud-slinging to be found about poor
> performance in java vs. C/C++ that I think I’m suffering under the
> (vague) impression that every line of java code must be as tight as
> humanly possible if I ever intend to do anything more than print
> address lables.

Java (and even C++) do have overhead that C doesn’t have. The people
implementing these languages (and JavaScript, and LISP, and…) have
put a lot of effort minimizing that overhead. In some circumstance
you won’t have a noticeable performance penalty, sometimes you will
notice it.

Two sugestions:

1) Jon Bentley’s _Programming Pearls_ and _More Programming Pearls_
contain lots of tips, encouragement, and good examples. Both for
writing efficient code and *correct* code (which is slightly
different from “code that works”… read the books and you’ll
understand what I mean!) Bentley was a lot more fun to read than the
academic texts I chewed through when studying CS and still managed to
cover most of the same ground as two+ years of Software Engineering.
The books are a little old, but I would still recommend them.

2) If you can identify certain sections of the code that are slowing
you down, you could post them here, with a verbal description of what
you’re trying to do. You might get some helpful suggestions.

– Peter

#73211
Mar 29, 2006 at 1:29pm

Thanks for the encouragement, Peter.

I may post some code at some piont, but I’m affraid my application of object-oriented design is pretty grim. Or maybe just non-existent. Pretty little boxes I can handle, but objects in code still mess with my head. So, my java code looks as procedural as it could, I’d imagine.

BTW, what do you suppose “lables” might be?

cheers,

J.

ps — I’ll find those books asap.

#73212
Mar 29, 2006 at 7:03pm

Btw, I think that Topher has had some success getting the Java
profiler tools working with mxj, which may be of use to you. In
addition, Apple’s Shark profiler is invaluable in terms of analyzing
what is taking up the most CPU, even just identifying which Max/MSP
objects are taking the most cycles. Typically you can tell which
externs by looking at the function names: _
such as zl_bang would indicate time taken in the zl object’s bang
method. Shark is part of Apple’s CHUD package, which can be
downloaded from the Apple developer site (I believe that now you need
to login to ADC to download, but it’s free to setup an ADC user account)

Best of luck,
Joshua

#73213
Mar 29, 2006 at 10:02pm

Hey, that’s a good tip about Shark. I’ve played around with it a little, but never with Max, so I didn’t realize it could look at Max in depth. I’ll take a peek tomorrow.

thanks!

Actually, I thought I was going to attempt another ground-up re-write (for the 4th time now) and even started drafting out a new approach. But I found that once I looked at what I’d already done again, from a different angle (that is, the angle of someone preparing to burn the whole bloody thing to the ground), there were actually some pretty simple things I was able to do to make everything work much more efficiently. I’m still working at it, but all-in-all the performance is pretty acceptable now.

cheers,

J.

#73214

You must be logged in to reply to this topic.