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

Question

C ++ tiene std :: vector y Java tiene ArrayList, y muchos otros idiomas tienen su propia forma de matriz asignada dinámicamente. Cuando una matriz dinámica se queda sin espacio, que se reasignó en un área más grande y los viejos valores se copian en la nueva matriz. Una cuestión central para el desempeño de una gama tan amplia es la rapidez con la matriz crece en tamaño. Si siempre sólo crecen lo suficientemente grande como para adaptarse a la tendencia actual, que va a terminar la reasignación de cada vez. Así que tiene sentido para duplicar el tamaño de la matriz, o se multiplica por 1,5 veces digamos.

¿Hay un factor de crecimiento ideal? 2x? 1.5x? Por ideales quiero decir, mejor rendimiento de equilibrio matemáticamente justificado y memoria desperdiciada. Me doy cuenta de que, en teoría, dado que su aplicación podría tener cualquier distribución potencial de la empuja de que esto es algo dependiente de la aplicación. Pero tengo curiosidad por saber si hay un valor que es "generalmente" mejor, o se considera mejor dentro de algún tipo de restricción rigurosa.

He oído que hay un documento sobre este lugar, pero no he podido encontrarlo.

Answer 1

dependerá enteramente en el caso de uso. Qué te importa más acerca de la pérdida de tiempo la copia de datos alrededor (y reasignación de arrays) o la memoria adicional? ¿Por cuánto tiempo es la matriz va a durar? Si no va a estar por mucho tiempo, el uso de un buffer mayor bien puede ser una buena idea - la pena es de corta duración. Si se va a colgar alrededor (por ejemplo, en Java, entrar en las generaciones mayores y mayores) que es, obviamente, más de una sanción.

No hay tal cosa como un "factor de crecimiento ideal." No se trata sólo teóricamente depende de la aplicación, es definitivamente depende de la aplicación.

2 es un factor de crecimiento bastante común - Estoy bastante seguro de que es lo que utiliza ArrayList y List<T> en .NET. ArrayList<T> en Java utiliza 1.5.

EDIT: Como señala Erich, Dictionary<,> en .NET utiliza "el doble del tamaño luego aumentar al siguiente número primo" de modo que los valores hash se pueden distribuir razonablemente entre los cubos. (Estoy seguro de que he visto recientemente la documentación que sugiere que los números primos no son realmente tan grande para distribuir recipientes de hash, pero eso es un argumento para otra respuesta.)

Answer 2

Recuerdo haber leído hace muchos años la razón por 1,5 se prefiere más de dos, por lo menos tal como se aplica a C ++ (esto probablemente no se aplica a lenguajes administrados, donde el sistema de tiempo de ejecución puede reubicar objetos a voluntad).

El razonamiento es el siguiente:

1. Digamos que comienza con una asignación de 16 bytes.
2. Cuando se necesita más, asigna 32 bytes, a continuación, liberar 16 bytes. Esto deja un agujero de 16 bytes en la memoria.
3. Cuando se necesita más, asigna 64 bytes, liberando los 32 bytes. Esto deja un agujero de 48 bytes (si el 16 y 32 eran adyacente).
4. Cuando se necesita más, se puede asignar 128 bytes, la liberación de los 64 bytes. Esto deja un agujero 112 bytes (suponiendo que todas las asignaciones anteriores son adyacentes).
5. Y así y etcétera.

La idea es que, con una expansión 2x, no hay ningún punto en el tiempo que el agujero resultante es cada vez va a ser lo suficientemente grande como para volver a utilizar para la siguiente asignación. El uso de una asignación de 1,5 veces, tenemos este lugar:

1. Comience con 16 bytes.
2. Cuando se necesita más, destinar 24 bytes, a continuación, liberar el 16, dejando un agujero de 16 bytes.
3. Cuando se necesita más, destinar 36 bytes, a continuación, liberar el 24, dejando un agujero de 40 bytes.
4. Cuando se necesita más, destinar 54 bytes, a continuación, liberar el 36, dejando un agujero de 76 bytes.
5. Cuando se necesita más, destinar 81 bytes, a continuación, liberar el 54, dejando un agujero de 130 bytes.
6. Cuando se necesita más, utilizar 122 bytes (redondeando hacia arriba) desde el agujero de 130 bytes.

Answer 3

Lo ideal (en el límite como n → ∞), es la proporción de oro : φ = 1,618 ...

En la práctica, usted quiere algo cercano, al igual que 1,5.

La razón es que usted quiere ser capaz de reutilizar los bloques de memoria de mayor edad, para aprovechar el almacenamiento en caché y evitar constantemente haciendo que el sistema operativo le dará más páginas de memoria. La ecuación que había resolver para asegurar esto se reduce a x ^{n - 1} - 1 = x ^{n + 1} - x ⁿ , cuya solución enfoques x = φ para grandes n .

Answer 4

Una aproximación al responder a preguntas como esto es sólo "trampa" y mirar lo que las bibliotecas populares hacerlo, bajo el supuesto de que una biblioteca ampliamente utilizado es, por lo menos, no hacer algo horrible.

Así que sólo la comprobación muy rápidamente, Ruby (1.9.1-p129) parece utilizar 1.5x al anexar a una matriz, y Python (2.6.2) utiliza 1.125x 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 anterior es el número de elementos de la matriz. Tenga en cuenta también que se añade a newsize new_allocated, por lo que la expresión con el operador ternario bitshifts y es en realidad el cálculo de la asignación de nuevo.

Answer 5

Digamos que crece el tamaño de la matriz por x. Así que supongamos que comienza con el tamaño T. La próxima vez que crece la matriz será T*x su tamaño. A continuación, se T*x^2 y así sucesivamente.

Si su objetivo es ser capaz de volver a utilizar la memoria que se ha creado antes, entonces usted quiere asegurarse de que la nueva memoria se puede asignar es menor que la suma de la memoria anterior se cancela la asignación. Por lo tanto, tenemos esta desigualdad:

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

Podemos eliminar T desde ambos lados. Así obtenemos la siguiente:

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

De manera informal, lo que decimos es que en la asignación nth, queremos que nuestro toda la memoria previamente desasignado sea mayor o igual que la necesidad de la memoria en la asignación de orden n para que podamos volver a utilizar la memoria previamente desasignado.

Por ejemplo, si queremos ser capaces de hacer esto en la tercera etapa (es decir, n=3), entonces tenemos

x^3 <= 1 + x 

Esta ecuación es verdadera para todos los x tal que 0 < x <= 1.3 (más o menos)

Vea lo x obtenemos para diferentes n de a continuación:

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 inferior a 2 desde x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2.

Answer 6

En realidad depende. Algunas personas analizan los casos de uso comunes para encontrar el número óptimo.

He visto 1,5x 2,0x phi x, y potencia de 2 usado antes.

Answer 7

Si usted tiene una distribución más longitudes de matriz, y tiene una función de utilidad que diga cuánto te gusta perder el espacio frente a la pérdida de tiempo, entonces definitivamente puede elegir un cambio de tamaño óptimo (y dimensionamiento inicial) estrategia.

La razón por la constante múltiplo simple se utiliza, es, obviamente, de manera que cada anexar ha amortizado tiempo constante. Pero eso no quiere decir que usted no puede utilizar una proporción diferente (más grande) para los pequeños tamaños.

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

No sé de cualquier duplicación (o 1.5 * ing) matrices que realmente capturan fuera de errores de memoria y crecen menos en ese caso. Parece que si has tenido una enorme sola matriz, que le gustaría hacer eso.

Yo añadiría además que si usted es mantener las matrices de tamaño variable el tiempo suficiente, y que favorezca el espacio con el tiempo, podría tener sentido para overallocate drásticamente (para la mayoría de los casos) al principio y luego reasignar a exactamente el tamaño correcto cuando ya está.

Answer 8

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

La relación entre el tiempo de CPU y de memoria es diferente en cada máquina, y así el factor variará de igual manera. Si usted tiene una máquina con gigabytes de RAM y una CPU lenta, copiando los elementos de una matriz nueva es mucho más caro que en una máquina rápida, lo que podría a su vez tienen menos memoria. Es una pregunta que puede ser contestada en teoría, para un equipo uniforme, lo que en escenarios reales que no ayuda en absoluto.

Answer 9

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

En primer lugar, esta es la multiplicación por 2: Tamaño << 1. Esta es la multiplicación por lo entre 1 y 2: int (float (tamaño) * x), donde x es el número, * está flotando aritmética de punto, y el procesador tiene que ejecutar instrucciones adicionales para la fundición entre flotador y int. En otras palabras, a pie de máquina, duplicación toma una sola instrucción, muy rápido para encontrar al nuevo tamaño. Multiplicando por algo entre 1 y 2 requiere al menos una instrucción para emitir tamaño a un flotador, una instrucción para multiplicar (que es la multiplicación de flotación, por lo que probablemente lleva por lo menos dos veces tantos ciclos, si no 4 o incluso 8 veces más), y una instrucción para echar hacia atrás a int, y que asume que su plataforma se puede realizar una operación matemática de flotador en los registros de propósito general, en lugar de requerir el uso de registros especiales. En resumen, usted debe esperar que los cálculos para cada asignación a tomar por lo menos 10 veces más que un simple desplazamiento a la izquierda. Si va a copiar una gran cantidad de datos durante la reasignación sin embargo, esto no podría hacer una gran diferencia.

En segundo lugar, y probablemente el gran problema: Todo el mundo parece dar por sentado que la memoria que está siendo liberado es tanto contigua a sí mismo, así como contigua a la memoria recién asignada. A menos que usted es pre-asignar toda la memoria sí mismo y luego usarlo como una piscina, esto no es casi ciertamente el caso. El sistema operativo podría ocasionalmente terminar haciendo esto, pero la mayoría de las veces, no va a ser suficiente fragmentación del espacio libre que cualquier sistema de medio decente gestión de memoria será capaz de encontrar un pequeño agujero en su memoria solo en forma. Una vez que llegue a la parte realmente trozos, que son más propensos a terminar con piezas contiguas, pero para entonces, sus asignaciones son lo suficientemente grande que no se está haciendo con frecuencia suficiente para que se importa. En resumen, es divertido imaginar que el uso de algún número ideal permitirá el uso más eficiente del espacio de memoria libre, pero en realidad, no va a suceder a menos que el programa se está ejecutando en el metal desnudo (como en, no hay ningún sistema operativo por debajo de ella haciendo todas las decisiones).

Mi respuesta a la pregunta? No, no hay un número ideal. Es lo que la aplicación específica que en realidad nadie siquiera lo intenta. Si su objetivo es el uso de memoria ideales, que son bastante fuera de suerte. Para obtener un rendimiento, las asignaciones de menos frecuentes, son mejores, pero si fuimos solo con eso, podrían multiplicar por 4 o incluso 8! Por supuesto, cuando Firefox se salta el uso de 1 GB a 8 GB en una sola toma, la gente va a quejarse, por lo que ni siquiera tiene sentido. Aquí hay algunas reglas básicas que pasarían sin embargo:

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

No overthink. Si usted acaba de pasar 4 horas tratando de encontrar la manera de hacer algo que ya se ha hecho, que acaba de perder su tiempo. Totalmente sinceramente, si había una opción mejor que 2 *, hubiera sido hecho en el vector de la clase C ++ (y muchos otros lugares) hace décadas.

Por último, si realmente desea optimizar, no se preocupe por las cosas pequeñas. Hoy en día, nadie se preocupa de 4 KB de memoria que se está perdido, a no ser que se está trabajando en sistemas embebidos. Al llegar a 1 GB de objetos que se encuentran entre 1 MB y 10 MB cada uno, duplicación es probablemente demasiado (me refiero, es decir, entre 100 y 1.000 objetos). Si se puede estimar la tasa esperada de expansión, puede nivelar hacia fuera a una tasa de crecimiento lineal en un punto determinado. Si espera que alrededor de 10 objetos por minuto, y luego cada vez mayor a los 5 a 10 tamaños de objetos por paso (una vez cada 30 segundos a un minuto) es PRobably bien.

Lo que todo se reduce a decir, no más de pensar que, optimizar lo que puede, y personalizar a su aplicación (y la plataforma) si es necesario.

Answer 10

Otros dos centavos

• La mayoría de las computadoras tienen memoria virtual! En la memoria física puede hacer que las páginas al azar por todas partes que se muestran como un único espacio contiguo en la memoria virtual del programa. La resolución del direccionamiento indirecto se realiza por el hardware. agotamiento de la memoria virtual era un problema en los sistemas de 32 bits, pero en realidad no es un problema. Por lo que llenar el agujero no es una preocupación más (excepto en entornos especiales). Puesto que Windows 7 incluso Microsoft soporta 64 bits sin esfuerzo adicional. @ 2011
• O (1) se alcanza con cualquier r > 1 factor. prueba matemática misma funciona no sólo para 2 como parámetro.
• r = 1,5 se puede calcular con old*3/2 lo que no hay necesidad de operaciones de coma flotante. (Lo digo porque /2 compiladores lo reemplazará con desplazamiento de bits en el código ensamblador generado si lo consideran oportuno.)
• MSVC fue por r = 1,5, por lo que hay al menos un compilador importante que no utiliza 2 como relación.

Como se ha mencionado por alguien se siente mejor que 2 8. Y también se siente mejor que 2 1.1.

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