"for" or "do-while" loop


    Mar 24 2006 | 8:54 am
    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?

    • Mar 24 2006 | 9:16 am
      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
    • Mar 24 2006 | 9:27 am
      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.
    • Mar 24 2006 | 11:59 am
      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
    • Mar 24 2006 | 11:59 am
      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/
    • Mar 24 2006 | 12:14 pm
      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.
    • Mar 24 2006 | 2:08 pm
      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/
    • Mar 24 2006 | 2:22 pm
      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.
    • Mar 24 2006 | 2:37 pm
      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.
    • Mar 28 2006 | 1:20 am
      > > 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
    • Mar 28 2006 | 7:23 am
      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/
    • Mar 28 2006 | 3:04 pm
      "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.
    • Mar 28 2006 | 9:49 pm
      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.
    • Mar 29 2006 | 12:57 pm
      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
    • Mar 29 2006 | 1:29 pm
      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.
    • Mar 29 2006 | 7:03 pm
      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
    • Mar 29 2006 | 10:02 pm
      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.