Jak długo trzeba czekać, aby przydzielić tablicę (w Javie)

Question

tylko ogólne pytanie dotyczące alokacji tablicy, głównie w Javie, ale wyobrażam sobie, że jest istotne dla wszystkich języków programowania:

Jak długo trzeba czekać, aby przydzielić pamięci dla tablicy o rozmiarze n [w znaczeniu O (n)]? Mogę sobie wyobrazić implementację, w której przydzielanie pamięci odbywa się w stałym czasie: jeśli masz dużą ilość pustej pamięci, możesz po prostu utworzyć wskaźnik do pierwszego i ostatniego indeksu nowej tablicy, ale w jaki sposób ogólnie jest przydzielana pamięć? (Także w Javie, jeśli zainicjujesz tablicę liczb całkowitych, wszystkie wartości w tablicy będą początkowo ustawione na 0, oznacza to, że każdy z indeksów w tablicy jest indywidualnie ustawiony na 0, co oznaczałoby wykonać operację O (n)?)

Dzięki.

Answer 1

prostu prowadził micro benchmark na hotspot - po JIT kompilację, przydział tablicę (na i7) wykonuje:

• około 10 ns dla macierzy o rozmiarze 1
• około 400 ns tablica rozmiarów 10000
• około 300.000 ns dla tablicy wielkości 1.000.000

Tak, aby odpowiedzieć na pytanie, wydaje się empirycznie, że jest O (n) na hotspot.

Szczegółowe wyniki:

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 

• tworzenia obiektu w Javie, jeśli kupie jest na tyle duża, jest prawie za darmo (to z grubsza polega na kompensowaniu wskaźnik)
• ale JVM wydaje się chętnie inicjowanie wszystkich przedmiotów do null (lub 0 dla prymitywne) w momencie tablica jest tworzony
• inne JVMs może przeprowadzić inicjalizację Lazier

Answer 2

Sam już odpowiedziałeś na pytanie, jest O(n) w Javie, ponieważ elementy są inicjowane, podczas gdy istnieją języki, w których ta operacja jest O(1), ponieważ nie ma inicjalizacji.

i po prostu mieć pewność,

public class ArrayTest { 

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

} 

produkuje

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 

} 

i dokumentacja mówi o newarray:

Nowa macierz, której elementy są typu Atype i długości liczba jest równa przydzielona z kupki zbierającej śmieci. Referenceref do ten nowy obiekt tablicy jest wciśnięty do stosu operandów. Każdy element z nowej tablicy to inicjalizowany do domyślnej wartości początkowej dla typu macierzy (§ 2.5.1).

Answer 3

AFAIK, przydział tablicy jest zawsze O (n) do maksymalnego rozmiaru, jaki możesz mieć. Wynika to z faktu, że koszt wyzerowania pamięci to również O (n). Istnieje kilka sztuczek, które system może zrobić, aby przyspieszyć ten proces. Oznacza to, że nie musi wyzerowywać każdego bajtu, może wyzerować całe strony za pomocą niektórych wirtualnych sztuczek pamięciowych, ale mimo to jest to również O (n).