¿Cuál es la tasa de crecimiento ideal para una matriz dinámicamente asignada?

Recuerdo haber leído hace muchos años por qué se prefiere 1.5 a dos, al menos como se aplica a C++ (esto probablemente no se aplica a los lenguajes administrados, donde el sistema de tiempo de ejecución puede reubicar objetos a voluntad).

El razonamiento es este:

1. Digamos que empiezas con una asignación de 16 bytes.
2. Cuando necesite más, asigne 32 bytes, luego libere 16 bytes. Esto deja un agujero de 16 bytes en la memoria.
3. Cuando se necesita más, se asignan 64 bytes, liberando los 32 bytes. Este deja un agujero de 48 bytes (si los 16 y 32 eran adyacentes).
4. Cuando se necesita más, se asignan 128 bytes, liberando los 64 bytes. Esto deja un agujero de 112 bytes (suponiendo que todas las asignaciones anteriores son adyacentes).
5. Y así y así sucesivamente.

La idea es que, con una expansión 2x, no hay ningún punto en el tiempo que el agujero resultante va a ser lo suficientemente grande como para reutilizar para la siguiente asignación. Usando una asignación 1.5 x, tenemos esto en su lugar:

1. Comience con 16 byte.
2. Cuando necesite más, asigne 24 bytes, luego libere los 16, dejando un agujero de 16 bytes.
3. Cuando necesite más, asigne 36 bytes, luego libere los 24, dejando un agujero de 40 bytes.
4. Cuando necesite más, asigne 54 bytes, luego libere los 36, dejando un agujero de 76 bytes.
5. Cuando necesite más, asigne 81 bytes, luego libere los 54, dejando un agujero de 130 bytes.
6. Cuando necesite más, use 122 bytes (redondeando) del agujero de 130 bytes.

Idealmente (en el límite como n → ∞), es la proporción áurea: ϕ = 1.618...

En la práctica, quieres algo cercano, como 1.5.

La razón es que desea poder reutilizar bloques de memoria antiguos, para aprovechar el almacenamiento en caché y evitar constantemente que el sistema operativo le dé más páginas de memoria. La ecuación que había resolver para asegurar que esto se reduce a x^{n - 1} - 1 = x^{n + 1} - xⁿ, cuya solución enfoques x = ϕ para grandes n.

Un enfoque al responder preguntas como esta es simplemente "hacer trampa" y ver lo que hacen las bibliotecas populares, bajo la suposición de que una biblioteca ampliamente utilizada, al menos, no está haciendo algo horrible.

Así que simplemente comprobando muy rápidamente, Ruby (1.9.1-p129) parece usar 1.5 x cuando se agrega a una matriz, y Python (2.6.2) usa 1.125 x más una constante (en Objects/listobject.c):

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
} else {
    new_allocated += newsize;
}

newsize arriba está el número de elementos en la matriz. Nótese bien que newsize se añade a new_allocated, por lo que la expresión con el bitshifts y operador ternario es realmente sólo el cálculo de la asignación excesiva.

Digamos que aumentas el tamaño de la matriz por x. Así que supongamos que empiezas con size T. La próxima vez que crezca el array su tamaño será T*x. Entonces será T*x^2 y así sucesivamente.

Si su objetivo es poder reutilizar la memoria que se ha creado anteriormente, entonces debe asegurarse de que la nueva memoria que asigne sea menor que la suma de la memoria anterior que desasignó. Por lo tanto, tenemos esta desigualdad:

T*x^n <= T + T*x + T*x^2 + ... + T*x^(n-2)

Podemos quitar T de ambos lados. Así que tenemos esto:

x^n <= 1 + x + x^2 + ... + x^(n-2)

Informalmente, lo que decimos es que en la asignación nth, queremos que toda nuestra memoria previamente desasignada sea mayor o igual a la necesidad de memoria en la enésima asignación para que podamos reutilizar la memoria previamente desasignada.

Por ejemplo, si queremos ser capaces de hacer esto en el 3er paso (es decir, n=3), entonces tenemos

x^3 <= 1 + x 

Esta ecuación es verdadera para todo x tal que 0 < x <= 1.3 (aproximadamente)

Ver lo que x obtenemos para diferentes n abajo:

n  maximum-x (roughly)

3  1.3

4  1.4

5  1.53

6  1.57

7  1.59

22 1.61

Tenga en cuenta que el factor de crecimiento tiene que ser menor que 2 desde x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2.

Realmente depende. Algunas personas analizan casos de uso común para encontrar el número óptimo.

He visto 1.5 x 2.0 x phi x, y el poder de 2 utilizado antes.

Si tiene una distribución sobre longitudes de matriz, y tiene una función de utilidad que dice cuánto le gusta perder espacio frente a perder tiempo, entonces definitivamente puede elegir una estrategia de redimensionamiento óptima (y dimensionamiento inicial).

La razón por la que se usa el múltiplo constante simple, es obviamente para que cada apéndice tenga tiempo constante amortizado. Pero eso no significa que no pueda usar una proporción diferente (más grande) para tamaños pequeños.

En Scala, puede anular loadFactor para el estándar tablas hash de biblioteca con una función que mira el tamaño actual. Curiosamente, las matrices de tamaño variable solo se duplican, que es lo que la mayoría de la gente hace en la práctica.

No conozco ninguna matriz de duplicación (o 1.5*ing) que realmente atrape errores de memoria y crezca menos en ese caso. Parece que si tuvieras una sola matriz enorme, querrías hacer eso.

Añadiría además que si usted está manteniendo los arrays redimensionables alrededor el tiempo suficiente, y usted favorece el espacio en el tiempo, podría tener sentido a sobreasigne dramáticamente (para la mayoría de los casos) inicialmente y luego reasigne exactamente al tamaño correcto cuando haya terminado.

Estoy de acuerdo con Jon Skeet, incluso mi amigo theorycrafter insiste en que se puede demostrar que esto es O(1) cuando se establece el factor a 2x.

La relación entre el tiempo de cpu y la memoria es diferente en cada máquina, por lo que el factor variará igual. Si tiene una máquina con gigabytes de ram y una CPU lenta, copiar los elementos a una nueva matriz es mucho más caro que en una máquina rápida, que a su vez podría tener menos memoria. Es una pregunta que se puede responder en teoría, para un computadora uniforme, que en escenarios reales no te ayuda en absoluto.

Sé que es una vieja pregunta, pero hay varias cosas que todo el mundo parece estar perdiendo.

Primero, esta es la multiplicación por 2: tamaño cualquier cosa entre 1 y 2: int(float(size) * x), donde x es el número, el * es matemática de punto flotante, y el procesador tiene que ejecutar instrucciones adicionales para lanzar entre float e int. En otras palabras, a nivel de la máquina, doblar requiere una sola instrucción muy rápida para encontrar el nuevo tamaño. Multiplicar por algo entre 1 y 2 requiere al menos una instrucción para lanzar tamaño a un flotador, una instrucción para multiplicar (que es la multiplicación de flotadores, por lo que probablemente toma al menos el doble de ciclos, si no 4 o incluso 8 veces más), y una instrucción para lanzar de nuevo a int, y eso asume que su plataforma puede realizar matemáticas de flotación en los registros de propósito general, en lugar de requerir el uso de registros especiales. En resumen, usted debe esperar las matemáticas para cada asignación para tomar al menos 10 veces más tiempo que un simple cambio a la izquierda. Sin embargo, si está copiando muchos datos durante la reasignación, esto podría no hacer mucha diferencia.

Segundo, y probablemente el gran trampolín: Todo el mundo parece asumir que la memoria que se está liberando es contigua consigo misma, así como contigua con la memoria recién asignada. A menos que esté pre-asignando toda la memoria usted mismo y luego usándola como un pool, este no es el caso. El sistema operativo podría ocasionalmente terminar haciendo esto, pero la mayoría de las veces, va a haber suficiente fragmentación de espacio libre que cualquier sistema de gestión de memoria medio decente será capaz de encontrar un pequeño agujero donde su memoria simplemente encajará. Una vez que llegues a trozos realmente pequeños, es más probable que termines con piezas contiguas, pero para entonces, tus asignaciones son lo suficientemente grandes como para que no las hagas con la frecuencia suficiente para que ya importe. En resumen, es divertido imaginar que el uso de algunos ideal number permitirá el uso más eficiente del espacio de memoria libre, pero en realidad, no va a suceder a menos que su programa se esté ejecutando en bare metal (como en, no hay ningún sistema operativo debajo de él tomando todas las decisiones).

Mi respuesta a la pregunta? No, no hay un número ideal. Es tan específica de la aplicación que nadie realmente ni siquiera lo intenta. Si tu objetivo es el uso ideal de la memoria, estás prácticamente sin suerte. Para el rendimiento, las asignaciones menos frecuentes son mejores, pero si fuimos solo con eso, podríamos multiplicar por 4 o incluso 8! Por supuesto, cuando Firefox salta de usar 1 GB a 8 GB de una sola vez, la gente se va a quejar, por lo que ni siquiera tiene sentido. Aquí hay algunas reglas de oro que me gustaría seguir sin embargo:

Si no puede optimizar el uso de memoria, al menos no desperdicie los ciclos del procesador. Multiplicar por 2 es al menos un orden de magnitud más rápido que hacer matemáticas de coma flotante. Puede que no haga una gran diferencia, pero al menos hará alguna diferencia (especialmente al principio, durante las asignaciones más frecuentes y más pequeñas).

No lo pienses demasiado. Si usted acaba de pasar 4 horas tratando de averiguar cómo hacer algo que ya se ha hecho, que acaba de perder su tiempo. Sinceramente, si hubiera una opción mejor que *2, se habría hecho en la clase vectorial C++ (y en muchos otros lugares) hace décadas.

Por último, si realmente quieres optimizar, no te preocupes por las cosas pequeñas. Hoy en día, a nadie le importa 4KB de la memoria se desperdicia, a menos que estén trabajando en sistemas embebidos. Cuando llegas a 1GB de objetos que están entre 1MB y 10MB cada uno, duplicar es probablemente demasiado (quiero decir, eso es entre 100 y 1,000 objetos). Si puede estimar la tasa de expansión esperada, puede nivelarla a una tasa de crecimiento lineal en un punto determinado. Si espera alrededor de 10 objetos por minuto, entonces crecer a 5 a 10 tamaños de objeto por paso (una vez cada 30 segundos a un minuto) probablemente esté bien.

Lo que todo en resumen, no lo pienses demasiado, optimiza lo que puedas y personaliza tu aplicación (y plataforma) si es necesario.

Otros dos centavos

• La mayoría de las computadoras tienen memoria virtual! En la memoria física puede tener páginas aleatorias en todas partes que se muestran como un único espacio contiguo en la memoria virtual de su programa. La resolución de la indirección es realizada por el hardware. El agotamiento de la memoria virtual era un problema en los sistemas de 32 bits, pero en realidad ya no es un problema. Así que llenar el agujero ya no es una preocupación (excepto los entornos especiales). Desde Windows 7 incluso Microsoft soporta 64 bits sin esfuerzo adicional. @ 2011
• O(1) se alcanza con cualquier r > 1 factor. La misma prueba matemática funciona no solo para 2 como parámetro.
• r = 1.5 se puede calcular con old*3/2 por lo que no hay necesidad de operaciones de coma flotante. (Digo /2 porque los compiladores lo reemplazarán con cambios de bits en el código de ensamblado generado si lo consideran conveniente.)
• MSVC fue para r = 1.5, por lo que hay al menos un compilador principal que no usa 2 como relación.

Como lo mencionó alguien 2 se siente mejor que 8. Y también 2 se siente mejor que 1.1.

Mi sensación es que 1.5 es un buen valor predeterminado. Aparte de eso, depende del caso específico.