java - ¿Por qué el uso de diferentes constructores de ArrayList causa una tasa de crecimiento diferente de la matriz interna?

java-8 java-12

Question

Parece que me tropiezo con algo interesante en la implementación de ArrayList que no puedo entender. Aquí hay un código que muestra lo que quiero decir:

public class Sandbox {

    private static final VarHandle VAR_HANDLE_ARRAY_LIST;

    static {
        try {
            Lookup lookupArrayList = MethodHandles.privateLookupIn(ArrayList.class, MethodHandles.lookup());
            VAR_HANDLE_ARRAY_LIST = lookupArrayList.findVarHandle(ArrayList.class, "elementData", Object[].class);
        } catch (Exception e) {
            e.printStackTrace();
            throw new RuntimeException();
        }
    }

    public static void main(String[] args) {

        List<String> defaultConstructorList = new ArrayList<>();
        defaultConstructorList.add("one");

        Object[] elementData = (Object[]) VAR_HANDLE_ARRAY_LIST.get(defaultConstructorList);
        System.out.println(elementData.length);

        List<String> zeroConstructorList = new ArrayList<>(0);
        zeroConstructorList.add("one");

        elementData = (Object[]) VAR_HANDLE_ARRAY_LIST.get(zeroConstructorList);
        System.out.println(elementData.length);

    }
}

La idea es si creas una ArrayList como esta:

List<String> defaultConstructorList = new ArrayList<>();
defaultConstructorList.add("one");

Y mire dentro de lo que los elementData ( Object[] donde se guardan todos los elementos) informará 10 . Por lo tanto, agrega un elemento: obtiene 9 ranuras adicionales que no se utilizan.

Si, por otro lado, haces:

List<String> zeroConstructorList = new ArrayList<>(0);
zeroConstructorList.add("one");

agrega un elemento, el espacio reservado es solo para ese elemento , nada más.

Internamente esto se logra a través de dos campos:

/**
 * Shared empty array instance used for empty instances.
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 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 = {};

Cuando cree una ArrayList través de una new ArrayList(0) , se utilizará EMPTY_ELEMENTDATA .

Cuando creas un ArrayList través de un new Arraylist() , se usa DEFAULTCAPACITY_EMPTY_ELEMENTDATA .

La parte intuitiva desde dentro de mí: simplemente grita "eliminar DEFAULTCAPACITY_EMPTY_ELEMENTDATA " y dejar que todos los casos se manejen con EMPTY_ELEMENTDATA ; por supuesto el comentario del código:

Distinguimos esto de EMPTY_ELEMENTDATA para saber cuánto inflar cuando se agrega el primer elemento

tiene sentido, pero ¿por qué uno inflaría a 10 (mucho más de lo que pedí) y el otro a 1 (exactamente tanto como solicité)?

Incluso si usa List<String> zeroConstructorList = new ArrayList<>(0) , y continúa agregando elementos, eventualmente llegará a un punto donde elementData es más grande que el solicitado:

    List<String> zeroConstructorList = new ArrayList<>(0);
    zeroConstructorList.add("one");
    zeroConstructorList.add("two");
    zeroConstructorList.add("three");
    zeroConstructorList.add("four");
    zeroConstructorList.add("five"); // elementData will report 6, though there are 5 elements only

Pero la velocidad a la que crece es menor que en el caso del constructor predeterminado.

Esto me recuerda a la implementación de HashMap , donde el número de cubos es casi siempre más de lo que pediste; pero ahí se hace debido a la necesidad de "poder de dos" cubetas necesarias, aunque no es el caso aquí.

Entonces la pregunta es: ¿alguien puede explicarme esta diferencia?

Answer 1

pero ¿por qué uno inflaría a 10 (mucho más de lo que pedí) y el otro a 1 (exactamente tanto como solicité)

Probablemente porque la mayoría de las personas que crean listas quieren almacenar más de 1 elemento en ellas.

Ya sabes, cuando quieres exactamente una entrada, ¿por qué no usar Collections.singletonList() por ejemplo?

En otras palabras, creo que la respuesta es el pragmatismo . Cuando use el constructor predeterminado, el caso de uso típico sería que va a agregar tal vez unos pocos elementos rápidamente.

Significado: "desconocido" se interpreta como "unos pocos", mientras que "exactamente 0 (o 1)" se interpreta "hmm, exactamente 0 o 1".

Answer 2

Esto es más probable debido al caso de que los dos constructores tienen diferentes usos predeterminados percibidos.

El constructor predeterminado (vacío) asume que este será un " ArrayList típico". Por lo tanto, el número 10 se elige como una especie de heurística, también conocida como "cuál será el número promedio típico de elementos insertados que no ocupará demasiado espacio pero que no crecerá innecesariamente la matriz". Por otro lado, el constructor de capacidad tiene el presupuesto de "sabes lo que estás haciendo" o "sabes para qué utilizarás ArrayList for ". Por lo tanto, no existen heurísticas de este tipo.

Answer 3

La capacidad con el constructor predeterminado es 10 simplemente porque ArrayList() . Habría sido elegido como un compromiso razonable entre no utilizar demasiada memoria de forma instantánea y no tener que realizar muchas copias de matriz al agregar los primeros elementos.

El comportamiento cero es ligeramente especulativo, pero estoy bastante seguro con mi razonamiento aquí:

Es porque si inicializas explícitamente una ArrayList con un tamaño de cero, luego le agregas algo, estás diciendo "No estoy esperando que esta lista contenga mucho, si es que algo". Por lo tanto, tiene mucho más sentido hacer crecer la matriz de respaldo lentamente, como si se hubiera inicializado con un valor de 1, en lugar de tratarlo como si no tuviera ningún valor inicial especificado. Así que maneja el caso especial de hacerlo crecer a solo 1 elemento, y luego continúa con normalidad.

Para completar la imagen, se espera que un ArrayList inicializado explícitamente con un tamaño de 1 crezca mucho más lentamente (hasta el punto en que alcance el tamaño predeterminado de "10 elementos") que el predeterminado, de lo contrario no habría ninguna razón. Inicializarlo con un pequeño valor en primer lugar.

Answer 4

La respuesta breve a su pregunta es lo que hay en el documento de Java: tenemos dos constantes porque ahora necesitamos poder distinguir las dos inicializaciones diferentes más adelante, vea más abajo.

Por supuesto, en lugar de dos constantes, podrían haber introducido, por ejemplo, un campo booleano en ArrayList , private boolean initializedWithDefaultCapacity ; pero eso requeriría memoria adicional por instancia , lo que parece ir en contra del objetivo de guardar algunos bytes de memoria.

¿Por qué necesitamos distinguir esos dos?

En cuanto a ensureCapacity() , vemos lo que sucede con DEFAULTCAPACITY_EMPTY_ELEMENTDATA :

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It''s already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

Parece que se hace de esta manera para ser algo compatible con el comportamiento de la implementación anterior:

Si inicializó la lista con la capacidad predeterminada, se inicializará con una matriz vacía ahora, pero , tan pronto como se inserte el primer elemento, básicamente volverá al mismo comportamiento que la implementación anterior, es decir, después de la primera Se agrega el elemento, la matriz de respaldo tiene DEFAULT_CAPACITY y, a partir de ese momento, la lista se comporta como antes.

Si, por otro lado, especifica explícitamente una capacidad inicial, la matriz no ''salta'' a DEFAULT_CAPACITY pero crece relativamente a partir de su capacidad inicial especificada.

Me imagino que la razón de esta "optimización" puede ser en los casos en que sabe que solo almacenará uno o dos elementos (es decir, menos que DEFAULT_CAPACITY ) en la lista y que especifique la capacidad inicial en consecuencia; en estos casos, por ejemplo, para una lista de un solo elemento, solo obtiene una matriz de un solo elemento, en lugar de un tamaño DEFAULT_CAPACITY .

No me pregunte cuál es el beneficio práctico de guardar nueve elementos de matriz de un tipo de referencia. Puede ser de hasta 9 * 64 bits = 72 bytes de RAM por lista. Yeay ;-)

Answer 5

Si utiliza el constructor predeterminado, la idea es intentar equilibrar el uso de la memoria y la reasignación. Por lo tanto, se utiliza un tamaño predeterminado pequeño (10) que debería estar bien para la mayoría de las aplicaciones.

Si usa el constructor con un tamaño explícito, se supone que sabe lo que está haciendo. Si lo inicializas con 0, básicamente estás diciendo: Estoy bastante seguro de que esto permanecerá vacío o no crecerá más allá de muy pocos elementos.

Ahora, si observa las implementaciones de ensureCapacityInternal en openjdk ( link ), puede ver que solo la primera vez que agrega un elemento, esta diferencia entra en juego:

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

    ensureExplicitCapacity(minCapacity);
}

Si se utiliza el constructor predeterminado, el tamaño aumenta a DEFAULT_CAPACITY (10). Esto es para evitar demasiadas reasignaciones si se agregan múltiples elementos. Sin embargo, si creó explícitamente este ArrayList con tamaño 0, simplemente aumentará a tamaño 1 en el primer elemento que agregue. Esto es porque le dijiste que sabes lo que estás haciendo.

ensureExplicitCapacity simplemente las llamadas grow (con algunas verificaciones de rango / desbordamiento), así que echemos un vistazo a eso:

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Como puede ver, no solo crece a un tamaño específico, sino que trata de ser inteligente. Cuanto más grande sea el arreglo, más grande crecerá incluso si la minCapacity es solo 1 más grande que la capacidad actual. El razonamiento detrás de esto es simple: la probabilidad de que se agregue una cantidad de elementos es mayor si la lista ya es grande y viceversa. Esta es también la razón por la que ves los incrementos de crecimiento en 1 y luego en 2 después del quinto elemento.

Answer 6

Usted obtiene exactamente lo que solicitó, lo que se ha especificado, incluso en versiones anteriores, donde la implementación fue diferente:

ArrayList()

Construye una lista vacía con una capacidad inicial de diez.

ArrayList(int)

Construye una lista vacía con la capacidad inicial especificada.

Por lo tanto, la construcción del ArrayList con el constructor predeterminado le dará un ArrayList con una capacidad inicial de diez, por lo que siempre que el tamaño de la lista sea diez o más pequeño, nunca se necesitará una operación de cambio de tamaño.

En contraste, el constructor con el argumento int usará precisamente la capacidad especificada, sujeto a la creciente política que se especifica como

Los detalles de la política de crecimiento no se especifican más allá del hecho de que agregar un elemento tiene un costo de tiempo amortizado constante.

que se aplica incluso cuando se especifica una capacidad inicial de cero.

Java 8 agregó la optimización de que la creación de la matriz de diez elementos se pospone hasta que se agrega el primer elemento. Esto se dirige específicamente al caso común de que las instancias de ArrayList (creadas con la capacidad predeterminada) permanezcan vacías durante mucho tiempo o incluso durante toda su vida útil. Además, cuando la primera operación real es addAll , puede omitir la primera operación de cambio de tamaño de la matriz. Esto no afecta a las listas con una capacidad inicial explícita, ya que generalmente se eligen con cuidado.

Como se indica en esta respuesta :

Según nuestro equipo de análisis de rendimiento, aproximadamente el 85% de las instancias de ArrayList se crean con el tamaño predeterminado, por lo que esta optimización será válida para la mayoría de los casos.

La motivación fue optimizar con precisión estos escenarios, no tocar la capacidad predeterminada especificada, que se definió cuando se creó ArrayList . (Aunque JDK 1.4 es el primero que lo especifica explícitamente)