Java Forum / General / April 2007
Quick way to initialize array with all zeros
001 - 31 Mar 2007 14:43 GMT I want to initialize a large array with 0's... do I have to use a for-loop or is there some trick to accomplish this?
Patricia Shanahan - 31 Mar 2007 14:59 GMT > I want to initialize a large array with 0's... do I have to use a for-loop > or is there some trick to accomplish this? new int[n] is an all zero int array of size n. If you have an existing array and need to reinitialize it to zero, use Arrays.fill.
Patricia
Andrew Thompson - 31 Mar 2007 15:28 GMT > > I want to initialize a large array with 0's... do I have to use a for-loop > > or is there some trick to accomplish this? > > new int[n] is an all zero int array of size n. If you have an existing > array and need to reinitialize it to zero, use Arrays.fill. I 'object' to such simplistic answers to what is effectively a complex question. My first question for the OP would be, what do you mean by 'quick'?
There are two potential meanings, AFAIU. 1) quick to code. 2) quick to run.
The first is inconsequential, the only point to writing a shorter method is for the purposes of code clarity (which has little to do with 'quick').
And for the second, I am not convinced that Arrays.fill() takes less CPU cycles.
Here is the test code/results I am seeing.. <sscce> import java.util.Arrays;
class InitialiseToZero {
public static void main(String[] args) { int length = 10000001; int[] intArray = new int[length]; long startTimeOfLoop = System.currentTimeMillis(); for (int ii=0; ii<length; ii++) { intArray[ii] = 1; } long endTimeOfLoop = System.currentTimeMillis();
long startTimeOfFill = System.currentTimeMillis(); Arrays.fill( intArray, 0 ); long endTimeOfFill = System.currentTimeMillis();
System.out.println( "Time to loop " + (endTimeOfLoop - startTimeOfLoop) ); System.out.println( "Time to fill " + (endTimeOfFill - startTimeOfFill) ); } } </sscce>
Time to loop 94 Time to fill 140 Press any key to continue . . .
Time to loop 140 Time to fill 110 Press any key to continue . . .
Time to loop 125 Time to fill 140 Press any key to continue . . .
Time to loop 125 Time to fill 109 Press any key to continue . . .
Time to loop 141 Time to fill 141 Press any key to continue . . .
Out of five runs (Java 1.6 on WinXP on an AMP XP 1800 CPU), the loop was faster on two occasions, slower on two, and equal on the last.
'Six of one - half a dozen of the other.' as I see it.
Andrew T.
Andrew Thompson - 31 Mar 2007 15:35 GMT ..
> Out of five runs (Java 1.6 on WinXP on an AMP .. (Ooops!)
amD the CPU manufacturarers, as opposed to some Australian insurance company.
Andrew T.
Andrew Thompson - 31 Mar 2007 16:21 GMT > > > I want to initialize a large array with 0's... do I have to use a for-loop > > > or is there some trick to accomplish this? [quoted text clipped - 9 lines] > 1) quick to code. > 2) quick to run. D'oh! In my (mild) irritation I forgot to mention two important things.
1) Premature optimization
These types of questions smack of premature optimization. Code for clarity and let the JIT do its job until such times as a *profiler* indicates a bottleneck based on the array initialisation.
2) (Stressing) code clarity
The Array.fill() method would be preferable for code clarity. Why code three lines, for something that can be expressed in one?
Andrew T.
George Cherry - 31 Mar 2007 18:08 GMT >> > I want to initialize a large array with 0's... do I have to use a >> > for-loop [quoted text clipped - 45 lines] > } > </sscce> Why did you fill the int array with 1's in the for loop test and 0's in the Arrays.fill test?
George
Andrew Thompson - 31 Mar 2007 18:28 GMT On Apr 1, 4:05 am, "George Cherry" < ..
> Why did you fill the int array with 1's in the for loop test > and 0's in the Arrays.fill test? "Because I'm evil".
LOL, sometimes I crack me up. ;-)
Why not? I was (ever so slightly) worried that the JIT compiler would notice the inefficiency of doing something that had already been done, and ignore the second call. (muses) maybe I should have put all 'random' values..
Andrew T.
George Cherry - 31 Mar 2007 18:43 GMT > On Apr 1, 4:05 am, "George Cherry" < > .. [quoted text clipped - 9 lines] > doing something that had already been done, and > ignore the second call. Oh. (Are JIT compilers that smart?)
> (muses) maybe I should > have put all 'random' values.. Or--at least--initialize a different array in each test.
George
Andrew Thompson - 31 Mar 2007 18:50 GMT On Apr 1, 4:37 am, "George Cherry" <GWCherryHatesGreenEggsAndS...@alum.mit.edu> wrote:
> > On Apr 1, 4:05 am, "George Cherry" < > > .. > >> Why did you fill the int array with 1's in the for loop test > >> and 0's in the Arrays.fill test? ...
> > Why not? I was (ever so slightly) worried that > > the JIT compiler would notice the inefficiency of > > doing something that had already been done, and > > ignore the second call. > > Oh. (Are JIT compilers that smart?) Dunno' And further, I am not prepared to waste time philosiphising about it.
> > (muses) maybe I should > > have put all 'random' values.. > > Or--at least--initialize a different array in > each test. Well.. altered code, different test results, would be more than welcome on this thread..
How about it?
"Let the (altered) code (and test results) do the talkin'"
(Anything short of that, is just theoretical bullsh*t, as far as I am concerned.)
Andrew T.
Patricia Shanahan - 31 Mar 2007 20:07 GMT ...
> Well.. altered code, different test results, > would be more than welcome on this thread.. [quoted text clipped - 3 lines] > "Let the (altered) code (and test results) do > the talkin'" OK, here's a new version. It does a new call, with a new array instance, for each test. I tested three approaches:
trustTheJVM - Assumes that the result of "new int[size]" is already an array of zeros, as required by the JLS.
fill - Use Arrays.fill.
loop - Explicit loop initialization.
Here are my results, times in nanoseconds:
10 trustTheJVM Mean time 2299.21 Min time 1955 Max time 5028 10 fill Mean time 4299.44 Min time 2793 Max time 149739 10 loop Mean time 2539.42 Min time 2235 Max time 4191 100 trustTheJVM Mean time 4570.47 Min time 2514 Max time 90514 100 fill Mean time 13918.03 Min time 2793 Max time 785016 100 loop Mean time 6483.99 Min time 2234 Max time 248635 1000 trustTheJVM Mean time 3363.56 Min time 2514 Max time 7543 1000 fill Mean time 39021.77 Min time 6425 Max time 2438019 1000 loop Mean time 6727.09 Min time 5588 Max time 9498 10000 trustTheJVM Mean time 25777.05 Min time 8101 Max time 769372 10000 fill Mean time 56093.72 Min time 43022 Max time 219582 10000 loop Mean time 65363.09 Min time 37993 Max time 1270553 100000 trustTheJVM Mean time 250601.74 Min time 60622 Max time 5836775 100000 fill Mean time 560487.44 Min time 529676 Max time 1038121 100000 loop Mean time 499658.44 Min time 480508 Max time 696178 1000000 trustTheJVM Mean time 1.653218217E7 Min time 14147608 Max time 20662123 1000000 fill Mean time 2.132354819E7 Min time 18011507 Max time 28056639 1000000 loop Mean time 2.159381985E7 Min time 19357209 Max time 45192057 10000000 trustTheJVM Mean time 8.072149119E7 Min time 78537636 Max time 87638792 10000000 fill Mean time 1.3643357179E8 Min time 132609870 Max time 145655943 10000000 loop Mean time 1.3610318625E8 Min time 132324919 Max time 143016501
"trustTheJVM" is the clear winner, and should be used unless there is a need to reinitialize the array after it has been modified.
For small arrays, if reinitialization is needed, "loop" wins over "fill" by a reasonable margin.
For large arrays, "loop" and "fill" have similar performance.
I still stand by my original advice - for long arrays, if possible, depend on the original initialization implicit in "new int[size]". If that is not possible, use Arrays.fill. It is one line and has the intent specified by the method name.
The only case in which I would prefer to loop is for very frequent calls to a method with a small array with performance dominated by the array initialization.
The rest of this article is the source code for my tests:
import java.util.Arrays;
public class InitialiseToZero {
public static void main(String[] args) { int[] sizes = {10,100,1000,10000,100000,1000000,10000000}; timeArrayInit[] methods = {trustTheJVM,fill,loop}; int repeatCount = 100; for(int size: sizes){ for(timeArrayInit method: methods){ method.reset(); } for(int i=0; i<repeatCount; i++){ for(timeArrayInit method: methods){ method.time(size); } } for(timeArrayInit method: methods){ System.out.println(method.getReport(size)); } } }
private static timeArrayInit trustTheJVM = new timeArrayInit(){ String getName(){ return "trustTheJVM"; } int timee(int size){ int[] data = new int[size]; return data[size/2]; } };
private static timeArrayInit fill = new timeArrayInit(){ String getName(){ return "fill"; } int timee(int size){ int[] data = new int[size]; Arrays.fill(data,0); return data[size/2]; } };
private static timeArrayInit loop = new timeArrayInit(){ String getName(){ return "loop"; } int timee(int size){ int[] data = new int[size]; for(int i=0; i<size; i++){ data[i] = 0; } return data[size/2]; } };
private static abstract class timeArrayInit { abstract int timee(int size);
abstract String getName();
long totalTime = 0;
long minTime = Long.MAX_VALUE;
long maxTime = 0;
long calls = 0;
void time(int size) { long start = System.nanoTime(); int result = timee(size); long end = System.nanoTime(); if (result != 0) { System.err.printf("Error in method %s result %d%n", getName(), result); } else { long time = end - start; totalTime += time; if (time < minTime) { minTime = time; } if (time > maxTime) { maxTime = time; } calls++; } }
void reset(){ totalTime = 0; minTime = Long.MAX_VALUE; maxTime = 0; calls = 0; }
public String getReport(int size) { StringBuilder builder = new StringBuilder(); builder.append(size); builder.append(" "+getName()); builder.append(" Mean time "+totalTime/(double)calls); builder.append(" Min time "+minTime); builder.append(" Max time "+maxTime); return builder.toString(); } } }
Andrew Thompson - 31 Mar 2007 20:11 GMT ...
> > Well.. altered code, different test results, > > would be more than welcome on this thread.. ..
> OK, here's a new version. It does a new call, with a new array > instance, for each test. I tested three approaches: Way cool. That should give the OP much to chew over (me as well). Thanks.
Andrew T.
Arne Vajhøj - 31 Mar 2007 23:37 GMT > "trustTheJVM" is the clear winner, and should be used unless there is a > need to reinitialize the array after it has been modified. [quoted text clipped - 3 lines] > > For large arrays, "loop" and "fill" have similar performance. No surprise since Arrays.fill use the same loop but has a couple of extra calls.
Arne
Mark Thornton - 01 Apr 2007 12:57 GMT >> "trustTheJVM" is the clear winner, and should be used unless there is a >> need to reinitialize the array after it has been modified. [quoted text clipped - 6 lines] > No surprise since Arrays.fill use the same loop but > has a couple of extra calls. Just because the code looks the same does not mean it will have the same performance when one implementation is part of the standard library. The JVM might replace library implementations with an accelerated form (intrinsic). Thus Patricia is correct to test the actual performance of these methods, and that performance might change in a future JVM.
Mark Thornton
Arne Vajhøj - 01 Apr 2007 18:18 GMT >>> "trustTheJVM" is the clear winner, and should be used unless there is a >>> need to reinitialize the array after it has been modified. [quoted text clipped - 11 lines] > JVM might replace library implementations with an accelerated form > (intrinsic). And ?
I would still be more surprised if it did that than if it did not.
> Thus Patricia is correct to test the actual performance of > these methods, and that performance might change in a future JVM. And ?
Java and all other languages I am aware of does not make any promises about future performance characteristics.
Arne
Patricia Shanahan - 31 Mar 2007 22:02 GMT >> On Apr 1, 4:05 am, "George Cherry" < >> .. [quoted text clipped - 10 lines] > > Oh. (Are JIT compilers that smart?) I don't know about the current state of JIT compilers.
Dead code elimination is the optimization that I've most often seen cause benchmark collapse. It's happened often enough that I make a habit of always doing SOMETHING externally visible with the result of the timed calculation.
Patricia
001 - 31 Mar 2007 20:44 GMT Yes, you're right... I really mean quick to run as that's the most important thing in life isn't it? Thanks for all your responses guys! The thing is I didn't have to reinitialize it... I only wanted to initialize it once... (but I thought relying on the zero's when an array is declared would result in a compile-time error and I am therefore really sorry to find out only now that that wasn't the case! (as it is with normal variables)).
>> > I want to initialize a large array with 0's... do I have to use a >> > for-loop [quoted text clipped - 75 lines] > > Andrew T. Andrew Thompson - 01 Apr 2007 13:13 GMT >Yes, you're right... Who is? Please refrain from top-posting in future, I find it most confusing. <http://www.physci.org/codes/javafaq.html#toppost>
>..I really mean quick to run as that's the most important >thing in life isn't it? No, it is not. Code that is very fast to run, but has bugs, might be useless compared to code that is 10% slower, but works flawlessy.
( Would you prefer a baniking app. that is 10% slower, but never makes mistakes, or one that is 10% faster, but sometimes clears your accounts? ;)
As such, the 'code clarity' point I mentioned earlier, might help prevent those bugs, and therefore would be the strategy I would pursue.
 Signature Andrew Thompson http://www.athompson.info/andrew/
Oliver Wong - 04 Apr 2007 20:28 GMT > I really mean quick to run as that's the most important thing in life > isn't it? If that were the case, you probably wouldn't be programming in Java. Instead, you'd be designing dedicated hardware to perform the task.
> Thanks for all your responses guys! The thing is I didn't have to > reinitialize it... I only wanted to initialize it once... (but I thought > relying on the zero's when an array is declared would result in a > compile-time error and I am therefore really sorry to find out only now > that that wasn't the case! (as it is with normal variables)). Fields are automatically initialized to default values (0 for integers, false for booleans, etc.) Local variables are not automatically initialized at all (not even with random values).
Perhaps you're thinking of C?
- Oliver
Mike Schilling - 05 Apr 2007 06:18 GMT >> I really mean quick to run as that's the most important thing in life >> isn't it? [quoted text clipped - 14 lines] > > Perhaps you're thinking of C? The point, which might be considered subtle, is that in
void method() { int[] array = new int[20];
the only local variable is the reference to the array. The members of the array are all fields of the array object.
Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
|
|