Сколько времени занимает выделение массива (в Java)

Просто общий вопрос о распределении массива, прежде всего в Java, но я думаю, что он имеет отношение ко всем языкам программирования:

Сколько времени занимает выделение памяти для массива размером n [в терминах O (n)]? Я мог представить себе реализацию, в которой распределение памяти происходит в постоянное время: если у вас есть большое количество пустой памяти, вы можете просто создать указатель на первый и последний индекс нового массива, но так ли, как обычно выделяется память? (Кроме того, по крайней мере, на Java, если вы инициализируете массив целых чисел, все значения в массиве с исходным значением равны 0, означает ли это, что каждый из индексов в массиве индивидуально установлен равным 0, что сделать операцию O (n)?)

Спасибо.

Ответы

Ответ 1

Я просто запустил микро-тест в компиляции JIT-hotspot-post, выделение массива (на i7) занимает:

  • около 10 нс для массива размером 1
  • около 400 нс для массива размером 10 000
  • около 300 000 нс для массива размером 1 000 000

Итак, чтобы ответить на ваш вопрос, , кажется эмпирически, что это O (n) на hotspot.

Подробные результаты:

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 могут выполнять более ленивую инициализацию

Ответ 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 и счетчик длины выделенных из собранной мусором кучи. Референтный массив для этот новый объект массива помещается в стек операнда. Каждыйэлементы нового массива инициализируются исходным значением по умолчаниюдля типа массива (п. 2.5.1).

Ответ 3

AFAIK, распределение массива всегда равно O (n) до максимального размера, который вы можете иметь. Это связано с тем, что стоимость обнуления памяти равна O (n). Есть несколько уловок, которые система может сделать, чтобы сделать это быстрее. т.е. ему не нужно обнулять каждый байт, он может обнулить целые страницы, используя некоторые трюки с виртуальной памятью, но даже это также O (n).