How long does it take to allocate an array (in Java)

Question

Just a general question about array allocation, primarily in Java but I imagine it is relevant to all programming languages:

How long does it take to allocate memory for an array of size n [in terms of O(n)]? I could imagine an implementation where the memory allocation happens in constant time: if you have a large quantity of empty memory you could just create a pointer to the first and last index of the new array, but is that how the memory is generally allocated? (Also, at least in Java, if you initialize an array of integers, all of the values in the array with be initially set to 0; does that mean that each of the indices in the array are individually set to equal 0, which would make the operation O(n)?)

Thanks.

Answer 1

I just ran a micro benchmark on hotspot - post JIT compilation, allocating an array (on an i7) takes:

• around 10 ns for an array of size 1
• around 400 ns for an array of size 10,000
• around 300,000 ns for an array of size 1,000,000

So to answer your question, it seems empirically that it is O(n) on hotspot.

Detailed results:

Benchmark                              Mode Thr    Cnt  Sec         Mean   Mean error    Units
c.a.p.ArrayVsList.createArray1         avgt   1      5    2       12.293        0.867  nsec/op
c.a.p.ArrayVsList.createArray10000     avgt   1      5    2      428.369        9.997  nsec/op
c.a.p.ArrayVsList.createArray1M        avgt   1      5    2   342972.975     7253.989  nsec/op

• creating an object in java, if your heap is large enough, is almost free (it roughly consists in offsetting a pointer)
• but the JVM seems to eagerly initialise all the items to null (or 0 for a primitive) at the time the array is created
• other JVMs might perform a lazier initialization

Answer 2

You have already answered the question by yourself, it is O(n) in Java since elements are initialized, while there are languages where this operation is O(1) since there is no initialization.

and just to be sure

public class ArrayTest {

  public static void main(String[] args) {
     int[] var = new int[5];
  }

}

produces

public class ArrayTest extends java.lang.Object{
public ArrayTest();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   return

public static void main(java.lang.String[]);
  Code:
   0:   iconst_5
   1:   newarray int
   3:   astore_1
   4:   return

}

and documentation says about newarray:

A new array whose components are of type atype and of length count is allocated from the garbage-collected heap. A reference arrayref to this new array object is pushed into the operand stack. Each of the elements of the new array is initialized to the default initial value for the type of the array (§2.5.1).