How To Write Faster Loops

/*
 * How To Write Faster Loops (after Dan Bornstein, Google Engineer)
 * 
 * - http://www.youtube.com/watch?v=ptjedOZEXPM
 *
 */

/* 1 (fastest) */
for (int i = initializer; i >= 0; i--) { ... }
 
/* 2 */
int limit = calculateLoopLimit();
for (int i = 0; i < limit; i++) { ... }

/* 3 */
Type[] array = getMyArray();
for (Type obj : array) { ... }

/* 4 */
for (int i = 0; i < array.length; i++) { ... }

/* 5 */
for (int i = 0; i < this.var; i++) { ... }

/* 6 */
for (int i = 0; i < obj.size(); i++) { ... }

/* 7 (slowest) */
Iterable<Type> list = getMyList();
for (Type obj : list) { ... }

17 Comments

#
codemunky - April 2, 2009 at 1:17 a.m.

Actually,

for (int i = initializer; i >= 0; --i) { ... }

is faster

#
fredmorcos - April 2, 2009 at 1:24 a.m.

i second that :) although i come to think, does it matter in java?

#
Anonymous Coward - April 2, 2009 at 1:37 a.m.

Actually,
your compiler should turn this into exactly the same code. If it does not you should switch compilers.

The whole post is pretty misleading anyway, since most of the time you do substantial work inside the loop and thus should pick the variant that causes the least overhead in that code...

#
Alan - April 2, 2009 at 5:27 a.m.

Does it make no difference what language is used, or why otherwise have you not mentioned that detail?

#
Max - April 2, 2009 at 6:14 p.m.

Assuming the compiler doesn't already notice this optimization, wouldn't

int i = size
while (i-- > 0) { ... }

be faster than the #1 entry?

#
Eric Burke - April 13, 2009 at 1:13 a.m.

To the people talking about "changing compilers" or "will the compiler optimize this", please note that this post is talking about Dalvik on Android, not a classic Java compiler. The rules are different.

Having said that, I sure hope future generations of Dalvik can optimize these sorts of things. This reminds me of the JDK 1.0 days.

#
Eric Burke - April 13, 2009 at 3:30 a.m.

Disregard my comment above, Dan Morrill set me straight on Twitter http://twitter.com/morrildl/status/1505732758

#
very9music - May 3, 2009 at 9:13 a.m.

for (int i = 0; i < this.var; i++) { ... }
This is the fastest way.

#
poss3x - May 19, 2009 at 8:59 p.m.

Can anybody post the timestamp for the related video when Bornstein is talking about the loop performance?
I am curious why the '--i'-loop should be faster than '++i'-loop, but I do not like to assist the entire video. I would expect that both loops are identical in execution time.

#
chris - May 20, 2009 at 12:51 a.m.

I think it is faster because of the comparison with 0, which takes just 1 cpu cycle. The comparison with another variable is more expensive...

#
Fred Grott - May 30, 2009 at 4:22 p.m.

The fastest loop via --i has to do with how dalvik treats stuff..

remember in normal java VM terms a loop with --i does a certain thing to the stack..ie pop?

those moves on and off the stack are optimized in dalvik and thus the loop with the less moves on and off the simulated stack in java bytecode will of course be faster in dalvik.

#
Henry Dominik - August 16, 2009 at 8:30 p.m.

These loops are something that we're all used to, so am not sure there's anything new there.

That said, this still seems ok #
# for (int i = 0; i < array.length; i++) { ... }

#
ma_as - August 30, 2009 at 9:17 p.m.

Is this slower, faster or same as 7?

for(Iterator<T> it=list.iterator(); it.hasNext(); ){
T t = it.next();
...
}

#
poss3x - November 4, 2009 at 8:54 p.m.

@ma_as
slower! you call two functions in your loop clauses. That's always a bad idea.
And keep in mind that iterators cause additional object creation. So I consider them evil when performance counts.

See also http://developer.android.com/guide/practices/design/performance.html#cache_fields

cache what can be cached... even field lookups.

#
Bearpaw - January 1, 2010 at 7:05 p.m.

Thanks for sharing

#
Frye boots - February 19, 2010 at 3:55 p.m.

Faster. Love it. Thanks

#
mbt shoes - February 24, 2010 at 3:13 p.m.

Great info.

Add a Comment