Loop Wisely - Writing faster loops

Tutorials with advanced 'difficulty' and more Lines of Code.

Loop Wisely - Writing faster loops

Postby plusminus » Wed Jul 16, 2008 9:59 am

Hello Community,

you probably often thought about what is the fastest/most efficient way of looping... :?:

So according to the DalvikVM designer Dan Bornstein these are the fastest ways of looping, sorted from fast to slow. (If you do it like 1, 2 or 3 you should not worry)
Syntax: [ Download ] [ Hide ]
Using java Syntax Highlighting
  1. // 1 (fastest)
  2.  
  3. for(int i = initializer; i >= 0; i--){ ... }
  4.  
  5.  
  6.  
  7. // 2
  8.  
  9. int limit = calculateLoopLimit();
  10.  
  11. for(int i = 0; i < limit; i++){ ... }
  12.  
  13.  
  14.  
  15. // 3
  16.  
  17. Type[] array = getMyArray();
  18.  
  19. for(Type obj : array){ ... }
  20.  
  21.  
  22.  
  23. // 4
  24.  
  25. for(int i = 0; i < array.length; i++){ ... }
  26.  
  27.  
  28.  
  29. // 5
  30.  
  31. for(int i = 0; i < this.var; i++){ ... }
  32.  
  33.  
  34.  
  35. // 6
  36.  
  37. for(int i = 0; i < obj.size(); i++){ ... }
  38.  
  39.  
  40.  
  41. // 7 (slowest)
  42.  
  43. Iterable<Type> list = getMyList();
  44.  
  45. for(Type obj : list){ ... }
Parsed in 0.033 seconds, using GeSHi 1.0.8.4


This is where I extracted that information from (jump to minute ~40):
[align=center][youtube]http://www.youtube.com/watch?v=ptjedOZEXPM[/youtube][/align]

Regards,
plusminus
Image
Image | Android Development Community / Tutorials
User avatar
plusminus
Site Admin
Site Admin
 
Posts: 2688
Joined: Wed Nov 14, 2007 8:37 pm
Location: Schriesheim, Germany

Top

Postby spokebloke » Wed Nov 19, 2008 10:41 pm

Syntax: [ Download ] [ Hide ]
Using java Syntax Highlighting
  1. try {
  2.  
  3.     for(int i = 0; ; ++i) {
  4.  
  5.     }
  6.  
  7. } catch (ArrayIndexOutOfBoundsException e)
  8.  
  9.     // Finished loop, do nothing
  10.  
  11. }
Parsed in 0.032 seconds, using GeSHi 1.0.8.4


Extra check against 0, or no check at all, hmm... Of course exception handling isn't cheap, but if you're worried about optimizing a loop, it's likely being executed pretty darn often anyway.
spokebloke
Freshman
Freshman
 
Posts: 3
Joined: Wed Nov 19, 2008 10:37 pm

Postby MrSnowflake » Wed Nov 19, 2008 11:44 pm

If the loop is 100000 items long, your exception handling solution is pretty cool, but otherwise (with small arrays) it's not very fast I guess.

Note on Arraylists: For Arraylists (actually Itetable) it's not adviced to use the enhanced for loop (for (T item:array)) you'd better do:
Syntax: [ Download ] [ Hide ]
Using java Syntax Highlighting
  1. int size = arraylist.count(); //or size I don't know out of my head.
  2.  
  3. for (int i = 0; i < size; ++i)
  4.  
  5.   arraylist.get(i);
Parsed in 0.034 seconds, using GeSHi 1.0.8.4

According to the docs, this is faster.
User avatar
MrSnowflake
Moderator
Moderator
 
Posts: 1439
Joined: Sat Feb 16, 2008 3:11 pm
Location: Flanders, Belgium

Postby spokebloke » Thu Nov 20, 2008 2:30 am

MrSnowflake wrote:If the loop is 100000 items long, your exception handling solution is pretty cool, but otherwise (with small arrays) it's not very fast I guess.

Note on Arraylists: For Arraylists (actually Itetable) it's not adviced to use the enhanced for loop (for (T item:array)) you'd better do:
Syntax: [ Download ] [ Hide ]
Using java Syntax Highlighting
  1. int size = arraylist.count(); //or size I don't know out of my head.
  2. for (int i = 0; i < size; ++i)
  3.   arraylist.get(i);
Parsed in 0.039 seconds, using GeSHi 1.0.8.4

According to the docs, this is faster.


If you keep reallocating them in an inner loop, that is going to affect performance, otherwise I think you will find the iterators to be preferable.
spokebloke
Freshman
Freshman
 
Posts: 3
Joined: Wed Nov 19, 2008 10:37 pm

Postby Danuubz » Fri Dec 05, 2008 10:34 pm

In my app Bookamak, I took a for-each loop with 'Element' classes (it contains every information about 'one' sheet on the pinboard). From there I extracted 6 String values per sheet necessary for rendering.

When there are >30 coloured sheet on the visible screen, scrolling screen gets a bit slower, so I tried to replace the for-each(Element) with a simple for-loop and String[] , in the hope of gaining performance.

The result was: scrolling became even slower :) especially with a small number of sheet, for-each works much better for me... so I returned to it.
Sticky Note Cork&Orc [Android Market] : http://www.youtube.com/watch?v=ewWaquAwZQY
User avatar
Danuubz
Experienced Developer
Experienced Developer
 
Posts: 78
Joined: Wed Dec 19, 2007 10:44 pm
Location: Germany

Postby rejser » Mon Mar 16, 2009 10:17 am

spokebloke wrote:
Syntax: [ Download ] [ Hide ]
Using java Syntax Highlighting
  1. try {
  2.     for(int i = 0; ; ++i) {
  3.     }
  4. } catch (ArrayIndexOutOfBoundsException e)
  5.     // Finished loop, do nothing
  6. }
Parsed in 0.044 seconds, using GeSHi 1.0.8.4


Extra check against 0, or no check at all, hmm... Of course exception handling isn't cheap, but if you're worried about optimizing a loop, it's likely being executed pretty darn often anyway.


Congratulations, that has to be the worst use of exceptions ever. Absolutely horrible.
rejser
Freshman
Freshman
 
Posts: 5
Joined: Mon Mar 16, 2009 9:51 am

Top

Postby MrSnowflake » Mon Mar 16, 2009 12:58 pm

rejser wrote:
spokebloke wrote:
Syntax: [ Download ] [ Hide ]
Using java Syntax Highlighting
  1. try {
  2.     for(int i = 0; ; ++i) {
  3.     }
  4. } catch (ArrayIndexOutOfBoundsException e)
  5.     // Finished loop, do nothing
  6. }
Parsed in 0.091 seconds, using GeSHi 1.0.8.4


Extra check against 0, or no check at all, hmm... Of course exception handling isn't cheap, but if you're worried about optimizing a loop, it's likely being executed pretty darn often anyway.


Congratulations, that has to be the worst use of exceptions ever. Absolutely horrible.
True, but for huge arrays, he does have a point :).
User avatar
MrSnowflake
Moderator
Moderator
 
Posts: 1439
Joined: Sat Feb 16, 2008 3:11 pm
Location: Flanders, Belgium

Postby keyserSoze » Thu Jul 09, 2009 11:39 am

rejser wrote:
spokebloke wrote:
Syntax: [ Download ] [ Hide ]
Using java Syntax Highlighting
  1. try {
  2.     for(int i = 0; ; ++i) {
  3.     }
  4. } catch (ArrayIndexOutOfBoundsException e)
  5.     // Finished loop, do nothing
  6. }
Parsed in 0.035 seconds, using GeSHi 1.0.8.4


Extra check against 0, or no check at all, hmm... Of course exception handling isn't cheap, but if you're worried about optimizing a loop, it's likely being executed pretty darn often anyway.


Congratulations, that has to be the worst use of exceptions ever. Absolutely horrible.



I would have thought this is quickest
Code: Select all
try {
while(true) {
...
i++}
} catch (ArrayIndexOutOfBounds e) {
//blah
}

quick but would only use on LARGE arrays.

NB wouldn't use this in j2me as alot of shit VMs don't take to any sort of exception well.
keyserSoze
Freshman
Freshman
 
Posts: 9
Joined: Tue Mar 17, 2009 6:06 pm

Re: Loop Wisely - Writing faster loops

Postby torryton » Wed Nov 09, 2011 3:16 pm

thanks for the quickest way!! highly apreciate :DI just couldn’t depart your site prior to suggesting that I extremely enjoyed the standard information a person provide for your visitors? Is gonna be back often to check up on new posts
User avatar
torryton
Freshman
Freshman
 
Posts: 6
Joined: Wed Nov 09, 2011 3:14 pm

Top

Return to Advanced Tutorials

Who is online

Users browsing this forum: No registered users and 6 guests