Dlaczego w Javie 8 domyślna pojemność ArrayList wynosi teraz zero?

Jak pamiętam, przed Java 8 domyślna pojemność ArrayListwynosiła 10.

Co zaskakujące, komentarz dotyczący domyślnego (void) konstruktora nadal mówi: Constructs an empty list with an initial capacity of ten.

Od ArrayList.java:

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

...

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

Technicznie rzecz biorąc, nie jest 10to zero, jeśli przyznajesz się do leniwej inicjalizacji tablicy bazowej. Widzieć:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

gdzie

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

To, o czym mówisz, to po prostu początkowy obiekt tablicy o zerowej wielkości, który jest współdzielony przez wszystkie początkowo puste ArrayListobiekty. To 10znaczy pojemność jest leniwie gwarantowana , optymalizacja obecna również w Javie 7.

Trzeba przyznać, że umowa z wykonawcą nie jest do końca dokładna. Być może to jest tutaj źródłem nieporozumień.

tło

Oto e-mail od Mike'a Duigou

Wysłałem zaktualizowaną wersję pustej łatki ArrayList i HashMap.

http://cr.openjdk.java.net/~mduigou/JDK-7143928/1/webrev/

Ta poprawiona implementacja nie wprowadza żadnych nowych dziedzin do żadnej z klas. W przypadku ArrayList opóźnione przydzielanie tablicy zapasowej występuje tylko wtedy, gdy lista jest tworzona z domyślnym rozmiarem. Według naszego zespołu ds. Analizy wydajności około 85% instancji ArrayList jest tworzonych w domyślnym rozmiarze, więc ta optymalizacja będzie obowiązywać w przytłaczającej większości przypadków.

W przypadku HashMap, pole progowe jest wykorzystywane w kreacji do śledzenia żądanego rozmiaru początkowego do momentu, gdy będzie potrzebna tablica zasobnika. Po stronie odczytu pusty przypadek mapy jest testowany za pomocą isEmpty (). W przypadku rozmiaru zapisu porównanie (table == EMPTY_TABLE) jest używane w celu wykrycia potrzeby wypełnienia tablicy bucket. W readObject jest trochę więcej pracy, aby spróbować wybrać wydajną pojemność początkową.

Od: http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-April/015585.html

W java 8 domyślna pojemność ArrayList wynosi 0, dopóki nie dodamy co najmniej jednego obiektu do obiektu ArrayList (można to nazwać leniwą inicjalizacją).

Teraz pytanie brzmi, dlaczego ta zmiana została wprowadzona w JAVA 8?

Odpowiedzią jest oszczędność pamięci. Miliony obiektów z listami tablic są tworzone w aplikacjach Java w czasie rzeczywistym. Domyślny rozmiar 10 obiektów oznacza, że ​​przy tworzeniu przydzielamy 10 wskaźników (40 lub 80 bajtów) dla tablicy bazowej i wypełniamy je wartościami zerowymi. Pusta tablica (wypełniona zerami) zajmuje dużo pamięci.

Leniwa inicjalizacja odkłada to zużycie pamięci do momentu, gdy faktycznie użyjesz listy tablic.

Aby uzyskać pomoc, zobacz poniższy kod.

ArrayList al = new ArrayList();          //Size:  0, Capacity:  0
ArrayList al = new ArrayList(5);         //Size:  0, Capacity:  5
ArrayList al = new ArrayList(new ArrayList(5)); //Size:  0, Capacity:  0
al.add( "shailesh" );                    //Size:  1, Capacity: 10

public static void main( String[] args )
        throws Exception
    {
        ArrayList al = new ArrayList();
        getCapacity( al );
        al.add( "shailesh" );
        getCapacity( al );
    }

    static void getCapacity( ArrayList<?> l )
        throws Exception
    {
        Field dataField = ArrayList.class.getDeclaredField( "elementData" );
        dataField.setAccessible( true );
        System.out.format( "Size: %2d, Capacity: %2d%n", l.size(), ( (Object[]) dataField.get( l ) ).length );
}

Response: - 
Size:  0, Capacity:  0
Size:  1, Capacity: 10

Artykuł Domyślna pojemność ArrayList w Javie 8 wyjaśnia to szczegółowo.

Jeśli pierwszą operacją wykonywaną na addAlltablicy ArrayList jest przekazanie kolekcji, która ma więcej niż dziesięć elementów, wszelkie wysiłki włożone w utworzenie początkowej tablicy dziesięcioelementowej przechowującej zawartość ArrayList zostaną wyrzucone przez okno. Za każdym razem, gdy coś jest dodawane do ArrayList, konieczne jest sprawdzenie, czy rozmiar wynikowej listy przekroczy rozmiar magazynu zapasowego; zezwolenie początkowemu magazynowi zapasowemu na rozmiar zerowy zamiast dziesięciu spowoduje niepowodzenie tego testu o jeden dodatkowy czas w okresie istnienia listy, której pierwszą operacją jest „dodawanie”, co wymagałoby utworzenia początkowej tablicy dziesięciu elementów, ale ten koszt wynosi mniej niż koszt stworzenia tablicy składającej się z dziesięciu elementów, która nigdy nie zostanie wykorzystana.

To powiedziawszy, w niektórych kontekstach byłoby możliwe dalsze polepszenie wydajności, gdyby istniało przeciążenie „addAll”, które określało, ile elementów (jeśli w ogóle) zostanie prawdopodobnie dodanych do listy po bieżącej, a które mogłyby wykorzystać to, aby wpłynąć na zachowanie alokacji. W niektórych przypadkach kod, który dodaje kilka ostatnich pozycji do listy, będzie miał całkiem niezły pomysł, że lista nigdy nie będzie potrzebować żadnej spacji poza nią. Jest wiele sytuacji, w których lista zostanie zapełniona raz i nigdy nie będzie później modyfikowana. Jeśli w punkcie kod wie, że ostateczny rozmiar listy wyniesie 170 elementów, to ma ona 150 elementów i magazyn zapasowy o rozmiarze 160,

Pytanie brzmi „dlaczego?”.

Inspekcje profilowania pamięci (na przykład ( https://www.yourkit.com/docs/java/help/inspections_mem.jsp#sparse_arrays ) pokazują, że puste (wypełnione zerami) tablice zajmują mnóstwo pamięci.

Domyślny rozmiar 10 obiektów oznacza, że ​​przy tworzeniu przydzielamy 10 wskaźników (40 lub 80 bajtów) dla tablicy bazowej i wypełniamy je wartościami zerowymi. Prawdziwe aplikacje java tworzą miliony list tablicowych.

Wprowadzona modyfikacja usuwa ^ W odłóż to zużycie pamięci do momentu, w którym faktycznie użyjesz listy tablic.

Po powyższym pytaniu przejrzałem dokument ArrayList Java 8. Okazało się, że domyślny rozmiar to nadal tylko 10.

Domyślny rozmiar tablicy ArrayList w JAVA 8 to nadal 10. Jedyną zmianą wprowadzoną w JAVA 8 jest to, że jeśli koder dodaje elementy mniejsze niż 10, wówczas pozostałe puste miejsca tablicy arraylist nie są określane jako puste. Mówiąc tak, ponieważ sam przeszedłem przez tę sytuację i zaćmienie, spojrzałem na tę zmianę JAVA 8.

Możesz uzasadnić tę zmianę, patrząc na poniższy zrzut ekranu. Widać na nim, że rozmiar ArrayList jest określony jako 10 w Object [10], ale liczba wyświetlanych elementów to tylko 7. Pozostałe elementy o wartości zerowej nie są tutaj wyświetlane. W JAVA 7 poniższy zrzut ekranu jest taki sam z tylko jedną zmianą, która polega na tym, że wyświetlane są również elementy wartości null, dla których koder musi napisać kod do obsługi wartości null, jeśli iteruje pełną listę tablic, podczas gdy w JAVA 8 to obciążenie jest usuwane z szef kodera / programisty.

Link do zrzutu ekranu.