java - 分配一个数组需要多长时间（在 Java 中）

Question

只是一个关于数组分配的一般问题，主要是在 Java 中，但我想它与所有编程语言有关：

为大小为 n 的数组分配内存需要多长时间 [以 O(n) 为单位]？我可以想象一个内存分配在恒定时间内发生的实现：如果你有大量的空内存，你可以创建一个指向新数组的第一个和最后一个索引的指针，但内存通常是如何分配的？（另外，至少在 Java 中，如果你初始化一个整数数组，数组中的所有值最初都设置为 0；这是否意味着数组中的每个索引都单独设置为 0，这将进行操作 O(n)？）

谢谢。

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

您已经自己回答了这个问题，O(n)因为元素已初始化，所以它是在 Java 中，而有些语言O(1)因为没有初始化而进行此操作。

只是为了确定

public class ArrayTest {

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

}

生产

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

}

和文档说newarray：

从垃圾收集堆中分配一个新数组，其组件类型为 atype 且长度为 count。对这个新数组对象的引用 arrayref 被推入操作数堆栈。新数组的每个元素都被初始化为数组类型的默认初始值 （第 2.5.1 节）。

Answer 3

AFAIK，数组分配总是 O(n) 直到你可以拥有的最大大小。这是因为将内存清零的成本也是 O(n)。系统可以采取一些技巧来加快速度。即它不必将每个字节都归零，它可以使用一些虚拟内存技巧将整个页面归零，但即便如此，这也是 O(n)。