How to avoid initialization of a large array

Question

I allocate a large array of doubles as

double[] x = new double[ n ];

where n is large, and I want to avoid initialization to save time. Is it possible?

Answer 1

Short answer: No. Arrays always get zeroed out when they are created.

If your profiling has shown this to be a major bottleneck, you could consider keeping a pool of array instances, with the length of each set to bigger than n will ever be. The problem would be that you then probably need a wrapper object to contain the data array and the actual length that is used, since you can no longer use data.length.

Answer 2

Can you use an ArrayList or something, and build your array as you need to add elements to it? That will save initialization time, if that is your issue.

ArrayList<double> x = new ArrayList<double>();

Answer 3

If you do not want to initialise a too long array, you may determine a limit for your array size which will not make you wait too much. I suggest to split a long array into smaller arrays. Define a list which keeps your arrays. If your array is filled, add it into your list. And go on to fill a new one.

import java.util.ArrayList;
import java.util.List;

public class Tester {
    private static final int LIMIT = 30;
    private static int index = 0;

    private static int[][] lookup;
    private static List<int[][]> list = new ArrayList<int[][]>();

    public static void main(String[] args) {
        lookup = new int[LIMIT][1];

        for (int i = 0; i <= 93; i++) {
            addToArr(i);
        }

        list.add(lookup);

        for (int[][] intArr : list) {
            for (int i = 0; i < intArr.length; i++) {
                System.out.print(intArr[i][0] + ",");
            }
        }
    }

    public static void addToArr(int value) {
        if (index == LIMIT) {
            list.add(lookup);
            lookup = new int[LIMIT][1];
            index = 0;
        }
        lookup [index++][0] = value;
    }
}

Prints:

0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

Answer 4

** WARNING ** UNSAFE ALTERNATIVE **

It's not an exact solution, but it could be a viable alternative. This method has some risks. But you might go this route if it's really absolutely necessary. This method is using an undocumented sun.misc.Unsafe class to allocate off-heap memory to store the double values. Off-heap meaning it's not garbage-collected, so you'll need to take care to deallocate the associated memory.

The following code is based on this blog post about sun.misc.Unsafe.

import java.lang.reflect.Field;

import sun.misc.Unsafe;

@SuppressWarnings("restriction")
public class SuperDoubleArray {

    private final static Unsafe unsafe = getUnsafe();
    private final static int INDEX_SCALE = 8;

    private long size;
    private long address;

    public SuperDoubleArray(long size) {
        this.size = size;
        address = unsafe.allocateMemory(size * INDEX_SCALE);
    }

    private static Unsafe getUnsafe() {
        try {
            Field singleoneInstanceField = Unsafe.class.getDeclaredField("theUnsafe");
            singleoneInstanceField.setAccessible(true);
            return (Unsafe) singleoneInstanceField.get(null);
        } catch (IllegalArgumentException | SecurityException 
                | NoSuchFieldException | IllegalAccessException e) {
            throw new RuntimeException(e);
        }
    }

    public void set(long i, double value) {
        unsafe.putDouble(address + i * INDEX_SCALE, value);
    }

    public double get(long idx) {
        return unsafe.getDouble(address + idx * INDEX_SCALE);
    }

    public long size() {
        return size;
    }

    public void deallocate() {
        unsafe.freeMemory(address);
    }

}

The following code will print some random double values coming from the unitialized memory.

SuperDoubleArray sda = new SuperDoubleArray(100);
for (int i=0; i<sda.size(); i++) {
    System.out.println(sda.get(i));
}
sda.deallocate();

There are no safety/range-checks, no nothing, you can easily crash the JVM with it, might not work with non-SUN JREs, might even stop working in future SUN JRE versions, but it might be the only solution in some cases. It can also allocate > Integer.MAX_VALUE sized pseudoarrays, unlike Java arrays.

java.nio.ByteBuffer.allocateDirect(...) actually uses the same Unsafe class behind the scenes to allocate byte buffers, and you could use ByteBuffer.allocateDirect(8*size).asDoubleBuffer() to adapt it to a DoubleBuffer, but ByteBuffer.allocateDirect(...) is still initializing the buffer with zeroes, so it might have a performance overhead.

Answer 5

Like others have already mentioned, the simple answer is: no, you are not able to avoid the initialization part. Unless you are using some native allocation or using IntBuffer created as a view of a byte buffer will be direct if, and only if, the byte buffer itself is direct.

If you are not using any of them, then in order to allocate and initialize the array as quickly as possible you need to minimize the GC calls and you have to ensure that the JVM has the needed memory to store and work with that array.

In Albert Hendriks's case: static int[][] lookup = new int[113088217][2], without at least 2.3G (12+113088217*(12+2*4) bytes) of memory the JVM will not be able to allocate the needed space. Note that I didn't add the padding space (memory alignment) that is needed also.

To answer why lookup = new int[2*113088217]; performs quicker. It is because much less memory is handled, since we don't have the sub arrays (the header + the elements + the alignment for each sub array), only (2*113088217*4+12) bytes=~804M are needed.

Answer 6

As soon as you declare the "new double[n]" statement the array will initialize. There's no way around it.

If your doing this for the sake of optimizing then i employ you to readup on premature optimization. If your program isn't hitting a wall then it's not worth optimizing. And it's defenetly not the array you should be optimizing either.

Answer 7

You can use ArrayList to save time on initializing and then convert it to an array if you absolutely need to work on double array like this :

List<Double> withoutInitializing = new ArrayList<Double>();
Double[] nowYouConvert = (Double[]) withoutInitializing.toArray();

From Java docs:

toArray: Returns an array containing all of the elements in this list in proper sequence (from first to last element).

The returned array will be "safe" in that no references to it are maintained by this list. (In other words, this method must allocate a new array even if this list is backed by an array). The caller is thus free to modify the returned array.

This method acts as bridge between array-based and collection-based APIs.

Specified by: toArray() in Collection

Answer 8

Some workaround for how does not initialize array.

Make an array that is guaranteed to be larger than the largest possible number of entries, and partially fill it.

For example, you can decide that the user will never provide more than 100 input values. Then allocate an array of size 100:

final int VALUES_LENGTH = 100;
double[] values = new double[VALUES_LENGTH];

Then keep a companion variable that tells how many elements in the array are actually used.

int valuesSize = 0;

Now values.length is the capacity of the array values, and valuesSize is the current size of the array. Keep adding elements into the array, incrementing the valuesSize variable each time.

values[valuesSize] = x;
valuesSize++;

This way, valuesSize always contains the correct element count. The following code segment shows how to read numbers into a partially filled array.

int valuesSize = 0;
Scanner in = new Scanner(System.in);
while (in.hasNextDouble()) {
  if (valuesSize < values.length) {
    values[valuesSize] = in.nextDouble();
    valuesSize++;
  }
}

At the end of this loop, valuesSize contains the actual number of elements in the array.

For example, here is how you can read an arbitrarily long sequence numbers into an array, without running out of space:

int valuesSize = 0;
while (in.hasNextDouble()) {
   if (valuesSize == values.length) {
      values = Arrays.copyOf(values, 2 * values.length);
   }
   values[valuesSize] = in.nextDouble();
   valuesSize++;
}

Answer 9

As I understand the question, the real issue is with allocating a huge two dimensional array, as mentioned in the comments

"static int[][] lookup = new int[113088217][2]; does not work, while private final static int[][] lookup = new int[11308821][2]; (10 times less) goes in less than a second"

Assumoing this is correct, yes, for huge numbers it is bone slow. You are not allocating a singe block of 113088217 * 2 ints! You are allocating 113088217 individual arrays, which are Objects, each of which must be allocated on the heap: this means that over 100 million times the JVM is looking for space, marking it as used, possibly running GC when memory gets tight, etc... The arrays each take significant (in these huge numbers) additional memory, plus each of them contains 2 ints.

For this huge case:

1) Switch the indices, and go

static int[][] lookup = new int[2][113088217]

Instead of allocating 113 million arrays, this allocates two. When you do the lookups in the array, switch the two indices.

2) Make a 1D array and do the lookup yourself

static int[] lookup = new int[2*113088217];

This requires doing simple math to find the proper index. Instead of accessing the array directly, write a function to do the math, and the calling code should use that.