Dans Java 8, pourquoi la capacité par défaut d'ArrayList est-elle désormais nulle ?

Question

Si je me souviens bien, avant Java 8, la capacité par défaut de ArrayList était de 10.

Étonnamment, le commentaire sur le constructeur par défaut (void) dit toujours : Constructs an empty list with an initial capacity of ten.

De 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;
}

Answer 1

Techniquement, c'est 10 et non zéro, si vous admettez une initialisation paresseuse du tableau de sauvegarde. Voir :

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);
}

où

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

Ce à quoi vous faites référence est simplement l'objet tableau initial de taille zéro qui est partagé entre tous les objets initialement vides. ArrayList des objets. C'est-à-dire la capacité de 10 est garanti paresseusement une optimisation qui est également présente dans Java 7.

Certes, le contrat de constructeur n'est pas tout à fait exact. C'est peut-être la source de la confusion ici.

Contexte

Voici un courriel de Mike Duigou

J'ai posté une version mise à jour du patch pour les ArrayList et HashMap vides.

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

Cette mise en œuvre révisée introduit pas de nouveaux champs à l'une ou l'autre des classes. Pour ArrayList, l'allocation paresseuse du tableau de sauvegarde ne se produit que si la liste est créée à la taille par défaut. Selon notre équipe d'analyse des performances, environ 85 % des instances de ArrayList sont créées à la taille par défaut, de sorte que cette optimisation sera valable pour une écrasante majorité de cas.

Pour HashMap, une utilisation créative est faite du champ threshold pour suivre la taille initiale demandée jusqu'à ce que le tableau bucket soit nécessaire. Du côté de la lecture, le cas d'une carte vide est testé avec isEmpty(). En écriture, une comparaison de (table == EMPTY_TABLE) est utilisée pour détecter le besoin de gonfler le tableau de seaux. Dans readObject il y a un peu plus de travail pour essayer de choisir une capacité initiale efficace.

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

Answer 2

En java 8, la capacité par défaut de ArrayList est de 0 jusqu'à ce que l'on ajoute au moins un objet dans l'objet ArrayList (vous pouvez l'appeler initialisation paresseuse).

La question est maintenant de savoir pourquoi ce changement a été fait dans JAVA 8 ?

La réponse est d'économiser la consommation de mémoire. Des millions d'objets de type tableau sont créés dans les applications Java en temps réel. La taille par défaut de 10 objets signifie que nous allouons 10 pointeurs (40 ou 80 octets) pour le tableau sous-jacent à la création et que nous les remplissons avec des nuls. Un tableau vide (rempli de nulls) occupe beaucoup de mémoire.

L'initialisation paresseuse reporte cette consommation de mémoire jusqu'au moment où vous utiliserez réellement la liste de tableaux.

Veuillez consulter le code ci-dessous pour vous aider.

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

Article Capacité par défaut de ArrayList en Java 8 l'explique en détail.

Answer 3

Si la toute première opération effectuée avec un ArrayList est de passer addAll une collection comportant plus de dix éléments, tous les efforts déployés pour créer un tableau initial de dix éléments destiné à contenir le contenu de la liste de tableaux sont voués à l'échec. Chaque fois qu'un élément est ajouté à une ArrayList, il est nécessaire de tester si la taille de la liste résultante dépassera la taille du backing store ; permettre au backing store initial d'avoir une taille de zéro au lieu de dix fera échouer ce test une fois de plus dans la vie d'une liste dont la première opération est un "add" qui nécessiterait la création du tableau initial de dix éléments, mais ce coût est inférieur à celui de la création d'un tableau de dix éléments qui ne sera jamais utilisé.

Ceci étant dit, il aurait été possible d'améliorer encore les performances dans certains contextes s'il y avait une surcharge de "addAll" qui spécifiait combien d'éléments (s'il y en a) seraient probablement ajoutés à la liste après le présent, et qui pourrait utiliser cela pour influencer son comportement d'allocation. Dans certains cas, le code qui ajoute les derniers éléments à une liste aura une assez bonne idée que la liste n'aura jamais besoin d'espace au-delà. Il existe de nombreuses situations où une liste sera remplie une fois et ne sera plus jamais modifiée après cela. Si, au moment où le code sait que la taille finale d'une liste sera de 170 éléments, il dispose de 150 éléments et d'un backing store de taille 160, faire croître le backing store jusqu'à la taille 320 ne sera pas utile et le laisser à la taille 320 ou le réduire à 170 sera moins efficace que de le faire croître jusqu'à 170 lors de la prochaine allocation.

Answer 4

La question est "pourquoi ?".

Inspections du profilage de la mémoire (par exemple ( https://www.yourkit.com/docs/java/help/inspections_mem.jsp#sparse_arrays ) montre que les tableaux vides (remplis de nulls) occupent des tonnes de mémoire .

La taille par défaut de 10 objets signifie que nous allouons 10 pointeurs (40 ou 80 octets) pour le tableau sous-jacent lors de la création et que nous les remplissons de nuls. Les applications Java réelles créent des millions de listes de tableaux.

La modification introduite supprime^W reporte cette consommation de mémoire au moment où vous utiliserez effectivement la liste de tableaux.

Answer 5

Après la question ci-dessus, j'ai parcouru le document ArrayList de Java 8. J'ai constaté que la taille par défaut est toujours de 10 seulement.