Speed of loops
Hi, this is a rather odd question but I just need to know.
When I use for or while loops for arrays I do this
for (int i = 0; i < array.length; i++){
//code here
}
int i = 0;
while (i < array.length){
//code here
}
but a colleague of mine said that declaring the length of the array and using that actually makes it faster, i.e.
int arrayLength = array.length;
for (int i = 0; i < arrayLength; i++){
//code here
}
you get the drift.
I personally think that there is no difference but he says that there was. Is there a way of checking of there really is a difference? Or does anyone know the answer?
Thanks.
Desmond
[1216 byte] By [
sandridera] at [2007-11-27 6:55:09]
Your colleague is right, but I wouldn't declare a special integer to keep it outside of a for-statement. Ask your colleague why he/she thinks it's necessary to gain such a small amount of time.
Try running this:
public class SillyTest {
static void testA(int[] array, int numTests) {
System.out.print("testA(), numTests="+numTests);
long start = System.currentTimeMillis();
while(numTests-- > 0) {
for(int i = 0; i < array.length; i++) {}
}
long elapsed = System.currentTimeMillis()-start;
System.out.print(", time="+elapsed+"\n");
}
static void testB(int[] array, int numTests) {
System.out.print("testB(), numTests="+numTests);
long start = System.currentTimeMillis();
int arrayLength = array.length;
while(numTests-- > 0) {
for(int i = 0; i < arrayLength; i++) {}
}
long elapsed = System.currentTimeMillis()-start;
System.out.print(", time="+elapsed+"\n");
}
public static void main(String[] args) {
int[] array = new int[1000000];
int tests = 1000;
testA(array, tests);
testB(array, tests);
testB(array, tests);
testA(array, tests);
}
}
The difference will be very tiny. For it to be noticeable, you'd have to be doing very many iterations and what you do inside the loop body would have to be very little--you probably couldn't do anything useful inside the loop body and still notice the difference.
In addition, I wouldn't be surprised if this is the kind of thing that hotspot could optimize, so that the actual code being executed is the same in both cases.
You colleague should worry less about microoptimizations and more about writing clear code.
jverda at 2007-7-12 18:30:29 >
Guys,Does this "micro-gain" also hold true for List.size() ?Thanx. Keith.
> Guys,
>
> Does this "micro-gain" also hold true for List.size()
> ?
>
> Thanx. Keith.
The difference might be more noticeable there, since it's a method call, and I don't know if it's a candidate for optimizing away.
However, that method call will still be very fast, so your loop body would have to be doing almost nothing for the method call to make a difference, AND you should almost never be calling list.size() in an iteration over a list anyway. You'd normally be calling iterator.hasNext(), or if you're using the enhanced for loop, not calling anything directly.
jverda at 2007-7-12 18:30:29 >
> The difference might be more noticeable there, since
> it's a method call
Yeah, I thought as much... I don't suppose you would know what the "cost" of a method call is?... I suspect the answer is "Too small to worry about." Right? ... I'll adapt the above posted test harness to check up on that.
> However, that method call will still be very fast, so
> your loop body would have to be doing almost nothing
> for the method call to make a difference
Yep. Thanx.
> AND you
> should almost never be calling list.size() in an
> iteration over a list anyway. You'd normally be
> calling iterator.hasNext();
I'm a dirty old ANSI C programmer, so I still tend to use a for i loop, unless/until I think to use something else... is this actually wrong? ... or just considered "poor form"... or is it a just a matter of "personal preference".
> or if you're using the
> enhanced for loop, not calling anything directly.
Unfortunately, most of my work is on the previous version of Weblogic, which limits us to java 1.4 ... so I'm try to not form any 1.6 habits, yet.
Thank you again for your insight.
Keith.
> ...
> Yeah, I thought as much... I don't suppose you would
> know what the "cost" of a method call is?... I
> suspect the answer is "Too small to worry about."
> Right? ... I'll adapt the above posted test harness
> to check up on that.
>
When doing that, also run a test where you're really doing something inside that for-statement with the contents of that List (a simple charAt(int) in case of a List<String>, for example). As jverd mentioned, if you do (almost) nothing in the for-statement, the difference between the two could be noticeable, but when you're calling something inside of it, I doubt it.
> > AND you
> > should almost never be calling list.size() in an
> > iteration over a list anyway. You'd normally be
> > calling iterator.hasNext();
>
> I'm a dirty old ANSI C programmer, so I still tend to
> use a for i loop, unless/until I think to use
> something else... is this actually wrong? ... or just
> considered "poor form"... or is it a just a matter of
> "personal preference".
If you're using size(), that suggests you're using get(i). This is bad form, as not all Lists are good at random access. If you have a LinkedList instead of an ArrayList, iteration time goes to O(N^2).
for (Iterator iter = myCollection.iterator(); iter.hasNext();) {
Thing thing = (Thing)iter.next();
thing.doStuff();
}
This works for all collections.
jverda at 2007-7-12 18:30:29 >
Here's some similar tests on the relative cost of "iterating" a List...
package forums;
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Arrays;
public class SillyTest {
static void testA(List<Integer> list, int numTests) {
System.out.print("testA("+list.size()+"), numTests="+numTests);
long start = System.currentTimeMillis();
while(numTests-- > 0) {
for(int i=0; i<list.size(); i++) {}
}
System.out.print(", time="+(System.currentTimeMillis()-start)+"\n");
}
static void testB(List><Integer> list, int numTests) {
System.out.print("testB("+list.size()+"), numTests="+numTests);
long start = System.currentTimeMillis();
int listSize = list.size();
while(numTests-- > 0) {
for(int i=0; i<listSize; i++) {}
}
System.out.print(", time="+(System.currentTimeMillis()-start)+"\n");
}
static void testIterator(List><Integer> list, int numTests) {
System.out.print("testC("+list.size()+"), numTests="+numTests);
long start = System.currentTimeMillis();
while(numTests-- > 0) {
for(Iterator it = list.iterator(); it.hasNext(); it.next()) {}
}
System.out.print(", time="+(System.currentTimeMillis()-start)+"\n");
}
static void testForeach(List<Integer> list, int numTests) {
System.out.print("testD("+list.size()+"), numTests="+numTests);
long start = System.currentTimeMillis();
while(numTests-- > 0) {
for(Integer i : list) {}
}
System.out.print(", time="+(System.currentTimeMillis()-start)+"\n");
}
public static void main(String[] args) {
int tests = 1000;
Integer[] array = new Integer[1000000];
List<Integer> list = Arrays.asList(array);
testA(list, tests);
testB(list, tests);
testIterator(list, tests);
testForeach(list, tests);
}
}
The results are rather interesting...
testA(1000000), numTests=1000, time=9157
testB(1000000), numTests=1000, time=1515
testC(1000000), numTests=1000, time=35688
testD(1000000), numTests=1000, time=36922
I've run this a few times without very similar results (+/- about 5% variance).
it looks like for(int i=0; i<=listSize; i++) is pretty clear winner, being nearly 25 times than the sinner 1.6's for each loop... Oops!
It uses the fixed sized list returned by Arrays.toList() ... I don't know how that performs compared to an ArrayList() for example. Hmmm.
Hmmm, now that I think of it, I suspect that this test is bunkum because testA and testB don't create (and throw away) the million Integer objects... and I suspect that what's actually taking the time... not the list iteration.
So I'm comparing grapefruit with blueberries.
Cheers guys, it's past my bedtime. :-)
Keith.
Try it with LinkedList instead of ArrayList.
jverda at 2007-7-12 18:30:29 >
There are a few statistical anomalies--probably owing to GC or other activities on my computer, or a mistake on my part--but it seems to me that, for the most part, unless you do something stupid like get() on a LinkedList, you're saving at most 10s or 100s of millis on 10s of millions of elements--when doing almost nothing during each iteration. If we do anything even moderately significant, the time to do the "real work" dwarfs any iteration style differences.
This is as expected. Iterate in the way that's clearest, simplest, most "standard." Save the micro-opts until you determine that you really need them and that they'll really help.
elems: 10,000
hotspot priming: no
loop body: empty
iterateArrayWithDotLength 0 ms
iterateArrayWithConstant 0 ms
iterateArrayListWithEnhancedFor 16 ms
iterateArrayListOldSchool 0 ms
iterateArrayListWithGetAndSize0 ms
iterateArrayListWithGetAndConstant0 ms
iterateLinkedListWithEnhancedFor 15 ms
iterateLinkedListOldSchool0 ms
iterateLinkedListWithGetAndSize 141 ms
iterateLinkedListWithGetAndConstant 140 ms
elems: 100,000
hotspot priming: no
loop body: empty
See how get() on LinkedList blew up? O(N^2), baby! I'll remove those tests hereafter, or it will never finish.
iterateArrayWithDotLength 0 ms
iterateArrayWithConstant 0 ms
iterateArrayListWithEnhancedFor 31 ms
iterateArrayListOldSchool 0 ms
iterateArrayListWithGetAndSize0 ms
iterateArrayListWithGetAndConstant0 ms
iterateLinkedListWithEnhancedFor 16 ms
iterateLinkedListOldSchool0 ms
iterateLinkedListWithGetAndSize 14,922 ms
iterateLinkedListWithGetAndConstant14,860 ms
elems: 1,000,000
hotspot priming: no
loop body: empty
iterateArrayWithDotLength 0 ms
iterateArrayWithConstant 0 ms
iterateArrayListWithEnhancedFor 47 ms
iterateArrayListOldSchool31 ms
iterateArrayListWithGetAndSize32 ms
iterateArrayListWithGetAndConstant15 ms
iterateLinkedListWithEnhancedFor 16 ms
iterateLinkedListOldSchool31 ms
elems: 25,000,000
hotspot priming: no
loop body: empty
iterateArrayWithDotLength62 ms
iterateArrayWithConstant 31 ms
iterateArrayListWithEnhancedFor 984 ms
iterateArrayListOldSchool828 ms
iterateArrayListWithGetAndSize 579 ms
iterateArrayListWithGetAndConstant 313 ms
iterateLinkedListWithEnhancedFor 1,750 ms
iterateLinkedListOldSchool516 ms
elems: 25,000,000
hotspot priming: no
loop body: Integer.intValue()
iterateArrayWithDotLength172 ms
iterateArrayWithConstant125 ms
iterateArrayListWithEnhancedFor 968 ms
iterateArrayListOldSchool890 ms
iterateArrayListWithGetAndSize 641 ms
iterateArrayListWithGetAndConstant 406 ms
iterateLinkedListWithEnhancedFor750 ms
iterateLinkedListOldSchool609 ms
elems: 25,000,000
hotspot priming: yes
loop body: Integer.intValue()
iterateArrayWithDotLength141 ms
iterateArrayWithConstant109 ms
iterateArrayListWithEnhancedFor1,781 ms
iterateArrayListOldSchool891 ms
iterateArrayListWithGetAndSize 641 ms
iterateArrayListWithGetAndConstant 406 ms
iterateLinkedListWithEnhancedFor641 ms
iterateLinkedListOldSchool594 ms
elems: 25,000,000
hotspot priming: yes
loop body: new Double(array[ix].toString().length() * element.toString().length()).toString();
iterateArrayWithDotLength21,344 ms
iterateArrayWithConstant21,422 ms
iterateArrayListWithEnhancedFor 30,782 ms
iterateArrayListOldSchool11,907 ms
iterateArrayListWithGetAndSize22,860 ms
iterateArrayListWithGetAndConstant22,532 ms
iterateLinkedListWithEnhancedFor 25,235 ms
iterateLinkedListOldSchool11,469 ms
Latest version of the code. Modified it as I went along for priming or not, loop body or not, etc.
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.*;
public class IterationTest {
static long startTime;
static long stopTime;
static final int MILLION = 1000000;
static final int numElems = 25 * MILLION;
static List<Integer> arrayList = new ArrayList<Integer>(numElems);
static {
for (int ix = 0; ix < numElems; ix++) {
arrayList.add(Integer.valueOf(ix));
}
}
static List<Integer> linkedList = new LinkedList<Integer>(arrayList);
static Integer[] array = arrayList.toArray(new Integer[numElems]);
public static void main(String[] args) throws Exception {
wildAssGuessAtPrimingHotspot();
System.out.printf("elems: %,d\n", numElems);
System.out.println("hotspot priming: yes");
System.out.println("loop body: new Double(array[ix].toString().length() * element.toString().length()).toString();");
System.out.println();
iterateArrayWithDotLength();
timeMethod("iterateArrayWithDotLength");
iterateArrayWithConstant();
timeMethod("iterateArrayWithConstant");
iterateArrayListWithEnhancedFor();
timeMethod("iterateArrayListWithEnhancedFor");
iterateArrayListOldSchool();
timeMethod("iterateArrayListOldSchool");
iterateArrayListWithGetAndSize();
timeMethod("iterateArrayListWithGetAndSize");
iterateArrayListWithGetAndConstant();
timeMethod("iterateArrayListWithGetAndConstant");
iterateLinkedListWithEnhancedFor();
timeMethod("iterateLinkedListWithEnhancedFor");
iterateLinkedListOldSchool();
timeMethod("iterateLinkedListOldSchool");
//timeMethod("iterateLinkedListWithGetAndSize");
//timeMethod("iterateLinkedListWithGetAndConstant");
}
static void wildAssGuessAtPrimingHotspot() {
iterateArrayWithDotLength();
iterateArrayWithConstant();
iterateArrayListWithEnhancedFor();
iterateArrayListOldSchool();
iterateArrayListWithGetAndSize();
iterateArrayListWithGetAndConstant();
iterateLinkedListWithEnhancedFor();
iterateLinkedListOldSchool();
//iterateLinkedListWithGetAndSize();
//iterateLinkedListWithGetAndConstant();
System.out.println("Done priming hotspot");
System.out.println();
}
static void timeMethod(String methodName)
throws SecurityException, NoSuchMethodException, IllegalArgumentException, IllegalAccessException, InvocationTargetException {
Method method = IterationTest.class.getDeclaredMethod(methodName, new Class[0]);
startTime();
method.invoke(null, new Object[0]);
stopTime(methodName);
}
static void startTime() {
startTime = System.currentTimeMillis();
}
static void stopTime(String msg) {
stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.printf("%-40s %,6d ms\n", msg, elapsedTime);
}
static void iterateArrayWithDotLength () {
for (int ix = 0; ix < array.length; ix++) {
new Double(array[ix].toString().length() * array[ix].toString().length()).toString();
}
}
static void iterateArrayWithConstant() {
for (int ix = 0; ix < numElems; ix++) {
new Double(array[ix].toString().length() * array[ix].toString().length()).toString();
}
}
static void iterateArrayListWithEnhancedFor() {
for (Integer elem : arrayList) {
new Double(elem.toString().length() * elem.toString().length()).toString();
}
}
static void iterateArrayListOldSchool() {
for (Iterator iter = arrayList.iterator(); iter.hasNext();) {
new Double(iter.next().toString().length() * iter.next().toString().length()).toString();
}
}
static void iterateArrayListWithGetAndSize() {
for (int ix = 0; ix < arrayList.size(); ix++) {
new Double(arrayList.get(ix).toString().length() * arrayList.get(ix).toString().length()).toString();
}
}
static void iterateArrayListWithGetAndConstant() {
for (int ix = 0; ix < numElems; ix++) {
new Double(arrayList.get(ix).toString().length() * arrayList.get(ix).toString().length()).toString();
}
}
static void iterateLinkedListWithEnhancedFor() {
for (Integer elem : linkedList) {
new Double(elem.toString().length() * elem.toString().length()).toString();
}
}
static void iterateLinkedListOldSchool() {
for (Iterator iter = linkedList.iterator(); iter.hasNext();) {
new Double(iter.next().toString().length() * iter.next().toString().length()).toString();
}
}
static void iterateLinkedListWithGetAndSize() {
for (int ix = 0; ix < linkedList.size(); ix++) {
linkedList.get(ix);
}
}
static void iterateLinkedListWithGetAndConstant() {
for (int ix = 0; ix < numElems; ix++) {
linkedList.get(ix);
}
}
}
jverda at 2007-7-12 18:30:29 >
> Hmmm, now that I think of it, I suspect that this test is bunkum...Unfortunately that's very common with programs that try to do benchmarks. But it's good that you noticed that before you decided to use the results as a guide to programming style.
Gentlemen,
Firstly, Thanx heaps to everyone for all your thoughts...
@jverd
Thank you for the thoughtfull (more complete) test regimen, and that test harness, it's universal. Wow!. I shall go forth and reuse it ;-)
RE: > ... using get(i) ... is bad form, as not all Lists are good
> at random access ... [especially] LinkedList.
AND: > the way that's clearest, simplest, most "standard."
> Save the micro-opts until you determine that you really need
> them and that they'll really help.
Yeah, I get the point, which I paraphrase as "To make your code reusable, you don't rely on the performance characteristics of a particular implementation of an interface where a "generic" alternative exists, unless of course it's absolutely necessary to resolve an specific identified performance bottleneck. So, using a generic iterator is generally better practice than using the equivalent for i loop, which relies heavily on ArrayList's fast random access to get the element."
Here's my results from running your IterationTest.java with 500,000 elements ...
C:\Documents and Settings\Keith>java -cp "c:/java/home/classes" forums.SillyTest_jverdsNotSoSillyVersion
elems: 500,000
hotspot priming: NO
loop body: new Double(${ELEM}.toString().length() * ${ELEM}.toString().length()).toString();
iterateArrayWithDotLength375 ms
iterateArrayWithConstant344 ms
iterateArrayListWithEnhancedFor 391 ms
iterateArrayListOldSchool203 ms
iterateArrayListWithGetAndSize 390 ms
iterateArrayListWithGetAndConstant 375 ms
iterateLinkedListWithEnhancedFor360 ms
iterateLinkedListOldSchool187 ms
iterateLinkedListWithGetAndSize 1,182,172 ms //about 20 minutes... ouch!
iterateLinkedListWithGetAndConstant1,164,594 ms //about 20 minutes... ouch again!
iterateLinkedListOldSchool 187 ms //verses
iterateLinkedListWithGetAndSize 1,182,172 ms //about 20 minutes... ouch!
I think the point is well made... The O(n^2) linkedList.get(i) is 250000000000 slower than an iterator.next... Wow!
@prometheuzz
RE: > run a test where you're really doing something inside that
> for-statement
Ummm yep, Sorry, I didn't read your reply 6, or jverds 7th symphony before I posted my reply 8 (the one with my SillyTest code). I take the point, and have applied it to the SillyTest harness below.
@DrClap
RE: > > Hmmm, now that I think of it, I suspect that this test is bunkum...
> Unfortunately that's very common with programs that try to do
> benchmarks. But it's good that you noticed that before you
> decided to use the results as a guide to programming style.
So, Here's the lastest version of my version of the silly test harness, and the results of half a dozen runs over a million elements.
package forums;
// Version 2 ... which, does something in the loop
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Arrays;
public class SillyTest {
static void testListSizeMethod(List<Integer> list, int numTests) {
long start = System.currentTimeMillis();
while(numTests-- > 0) {
for(int i=0; i<list.size(); i++) {
int j = list.get(i).intValue();
}
}
System.out.print("TEST: list.size() ="+(System.currentTimeMillis()-start)+"\n");
}
static void testListSizeVariable(List><Integer> list, int numTests) {
long start = System.currentTimeMillis();
int listSize = list.size();
while(numTests-- > 0) {
for(int i=0; i<listSize; i++) {
int j = list.get(i);
}
}
System.out.print("TEST: listSize ="+(System.currentTimeMillis()-start)+"\n");
}
static void testIterator(List><Integer> list, int numTests) {
long start = System.currentTimeMillis();
while(numTests-- > 0) {
for(Iterator it=list.iterator(); it.hasNext(); ) {
int j = ((Integer)it.next()).intValue();
}
}
System.out.print("TEST: iterator ="+(System.currentTimeMillis()-start)+"\n");
}
static void testForeach(List<Integer> list, int numTests) {
long start = System.currentTimeMillis();
while(numTests-- > 0) {
for(Integer i : list) {
int j = i.intValue();
}
}
System.out.print("TEST: for each ="+(System.currentTimeMillis()-start)+"\n");
}
private static final int ELEMENTS = 1000000;
public static void main(String[] args) {
int tests = 1000;
long start = 0L;
System.out.println("INFO: array size = "+ELEMENTS);
start = System.currentTimeMillis();
Integer[] array = new Integer[1000000];
System.out.print("INIT: new Integer[] ="+(System.currentTimeMillis()-start)+"\n");
start = System.currentTimeMillis();
for(int i=0; i<array.length; i++) {
array[i] = new Integer(i);
}
System.out.print("INIT: array[i]=i = "+(System.currentTimeMillis()-start)+"\n");
start = System.currentTimeMillis();
List><Integer> list = Arrays.asList(array);
System.out.print("INIT: asList() ="+(System.currentTimeMillis()-start)+"\n");
testListSizeMethod(list, tests);
testListSizeVariable(list, tests);
testIterator(list, tests);
testForeach(list, tests);
}
}
/***************************************************************************************************
TEST RESULTS - AMD64 Dual 3800+ with 2Gig on XPpro(32)
-
TEST NUMBER#1#2#3#4#5#6TOTALAVERAGE
INIT: new Integer[]1515 0 0 0 030 5
INIT: array[i]=i 2665162812662662651,860310
INIT: asList() 00 0 0 0 0 0 0
TEST: list.size()22,46922,73422,51522,51622,40622,438135,07822,513
TEST: listSize 12,73413,12512,82912,82812,76613,26677,54812,925
TEST: iterator 32,50033,82932,64032,37532,62532,625196,59432,766
TEST: for each 34,29733,26532,93834,04735,68735,906206,14034,357
TOTAL102,281 103,484101,203102,032103,750104,500617,250102,875
INFO: array size = 1000000
***************************************************************************************************/
Cheers All (& fangs agin). Keith.
PS: @OP... sorry for high-jacking your thread... I hope you where finished with it.
> @jverd
> Thank you for the thoughtfull (more complete) test
> regimen, and that test harness, it's universal. Wow!.
> I shall go forth and reuse it ;-)
You're quite welcome.
The test harness was born out of sheer laziness--often a good character attribute for a programmer, according to Larry Wall.
> eah, I get the point, which I paraphrase as "To make
> your code reusable, you don't rely on the performance
> characteristics of a particular implementation of an
> interface where a "generic" alternative exists,
> unless of course it's absolutely necessary to resolve
> an specific identified performance bottleneck. So,
> using a generic iterator is generally better practice
> than using the equivalent for i loop, which
> relies heavily on ArrayList's fast random access to
> get the element."
Sounds about right.
> I think the point is well made... The O(n^2)
> linkedList.get(i) is 250000000000 slower than an
> iterator.next... Wow!
Not necessarily slower in general. For small lists, you won't notice the difference.
But Big-O notation isn't about how long something takes. It's about how fast the CPU or memory usage grows relative to how fast your input size grows. Since the time for this is O(N^2), if you make your list 100 times bigger, you'll make the time 10,000 times bigger.
If a 10,000 element list takes 10 seconds, a 1,000,000 element list will take about 3 hours. For the other O(N) approaches, however, that change from a 10,000 element to a 1,000,000 element list will only change the time from 10 seconds to about 20 minutes. Bumping that to 5,000,000 means going from 3 hours to 3 days vs. going from 20 minutes to an hour and a half.
Thanks for following up with your own tests and results.
EDIT: I think I buggered up the math. I'll leave fixing it (multiplying seconds by 10,000 and turning it into a meaningful measure of time) as an exercise for the reader. :-P
Message was edited by:
jverd
jverda at 2007-7-12 18:30:29 >
