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

Question

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

为大小为 n [O(n)] 的数组分配内存需要多长时间？我可以想象一个内存分配在恒定时间内发生的实现:如果你有大量的空内存，你可以只创建一个指向新数组的第一个和最后一个索引的指针，但内存通常是这样分配的吗？ (此外，至少在 Java 中，如果您初始化一个整数数组，则该数组中的所有值最初都设置为 0；这是否意味着该数组中的每个索引都单独设置为等于 0，这将使操作复杂度为 O(n)?)

谢谢。

Answer 1

我刚刚运行了一个 micro benchmark在热点上 - 后 JIT 编译，分配一个数组(在 i7 上)需要:

• 大小为 1 的数组大约需要 10 ns
• 对于大小为 10,000 的数组大约需要 400 ns
• 对于大小为 1,000,000 的数组大约需要 300,000 ns

所以要回答你的问题，根据经验，热点上的时间似乎是 O(n)。

详细结果:

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

• 在 java 中创建一个对象，如果你的堆足够大，几乎是免费的(它大致包括偏移一个指针)
• 但 JVM 似乎急切地在创建数组时将所有项目初始化为 null(或 0 对于基元)
• 其他 JVM 可能会执行更惰性的初始化