¿Es mejor asignar memoria en el poder de dos?

Question

Cuando usamos malloc() para asignar memoria, ¿deberíamos dar el tamaño que está en potencia de dos? ¿O simplemente le damos el tamaño exacto que necesitamos?
Como

//char *ptr= malloc(200); 
char *ptr= malloc(256);//instead of 200 we use 256 

Si es mejor dar el tamaño que está en el poder de dos, ¿cuál es el motivo? ¿Por qué es mejor?

Gracias

Editar

La razón de mi confusión es siguiente cita del blog de Joel Back to Basics

programadores inteligentes minimizan el potencial distruption de malloc por bloques siempre la asignación de memoria que son poderes de 2 en tamaño. Usted sabe , 4 bytes, 8 bytes, 16 bytes, 18446744073709551616 bytes, etc. Para razones que deberían ser intuitivo para cualquier persona que juega con Lego, esta minimiza la cantidad de raro la fragmentación que se produce en la libre cadena. Aunque puede parecer que esto desperdicia espacio, también es fácil ver cómo nunca desperdicia más del 50% de el espacio. Por lo tanto, su programa no utiliza más del doble de memoria que , lo cual no es tan grande como el acuerdo .

Lo siento, debería haber publicado la cita anterior. ¡Mis disculpas!

La mayoría de las respuestas, hasta ahora, dicen que asignar memoria en el poder de dos es una mala idea, entonces ¿en qué situación es mejor seguir el punto de Joel sobre malloc()? ¿Por qué dijo eso? ¿La sugerencia citada anteriormente está obsoleta ahora?

Explíquelo amablemente.
Gracias

Answer 1

Simplemente dé el tamaño exacto que necesita. La única razón por la cual un tamaño de potencia de dos podría ser "mejor" es permitir una asignación más rápida y/o evitar la fragmentación de la memoria.

Sin embargo, cualquier implementación no trivial de malloc que se preocupe por ser eficiente redondeará internamente las asignaciones de esta forma siempre y cuando sea apropiado hacerlo. No necesita preocuparse por "ayudar" malloc; malloc puede hacerlo bien por sí mismo.

Editar:

En respuesta a su cotización del Joel sobre el artículo de software, punto de Joel en esa sección (que es difícil de discernir correctamente sin el contexto que sigue el párrafo que usted ha citado) es que si esperas con frecuencia re -asignar un buffer, es mejor hacerlo multiplicativamente, en lugar de hacerlo de manera aditiva. Esto es, de hecho, exactamente lo que hacen las clases std::string y std::vector en C++ (entre otros).

La razón de que esto es una mejora no es porque usted está ayudando a cabo malloc proporcionando números convenientes, pero debido a la asignación de memoria es una operación costosa , y que está tratando de reducir al mínimo el número de veces que lo haces. Joel está presentando un ejemplo concreto de la idea de una compensación de tiempo-espacio. Argumenta que, en muchos casos en los que la cantidad de memoria necesaria cambia dinámicamente, es mejor perder algo de espacio (asignando hasta el doble de lo que necesita en cada expansión) para guardar tiempo que se requeriría para repetidamente vire exactamente n bytes de memoria, cada vez que necesite n más bytes.

El multiplicador no tiene que ser dos: puede asignar hasta tres veces más espacio que necesita y terminar con asignaciones en potencias de tres, o asignar hasta cincuenta y siete veces más espacio que usted necesita y termina con asignaciones en poderes de cincuenta y siete. Cuanta más asignación tenga, menos necesitará volver a asignar, pero perderá más memoria. Asignar en poderes de dos, que utiliza como mucho el doble de memoria que la necesaria, resulta ser una buena compensación de punto de partida hasta y a menos que tenga una mejor idea de cuáles son exactamente sus necesidades.

Menciona de paso que esto ayuda a reducir la "fragmentación en la cadena libre", pero la razón es más por el número y la uniformidad de las asignaciones que se realizan, que por su tamaño exacto. Por un lado, cuantas más veces asigne y desasigne memoria, más probabilidades tendrá de fragmentar el montón, sin importar el tamaño que esté asignando. En segundo lugar, si tiene varios búferes que está cambiando de tamaño dinámicamente utilizando el mismo algoritmo de cambio de tamaño multiplicativo, es probable que si uno cambia el tamaño de 32 a 64 y otro cambia de 16 a 32, la reasignación del segundo pueda caber justo donde el primero solía ser. Este no sería el caso si uno cambió el tamaño de 25 a 60 y el otro de 16 a 26.

Y de nuevo, nada de lo que él está hablando aplica si va a realizar el paso de asignación solo una vez .

Answer 2

puede han sido cierto una vez, pero ciertamente no es mejor.

Simplemente asigne la memoria que necesita, cuando la necesite y libere la unidad tan pronto como haya terminado.

Hay demasiados programas que son derrochadores de recursos, no hagas tuyo uno de ellos.

Answer 3

Esto depende totalmente de la implementación dada libc de malloc(3). Depende de esa implementación reservar trozos de pila en el orden que considere oportuno.

Para responder a la pregunta, no, no es "mejor" (¿aquí con "mejor" quiere decir ...?). Si el tamaño que solicita es demasiado pequeño, malloc(3) se reservará un trozo más grande internamente, por lo que simplemente conserve su tamaño exacto.

Answer 4

Es algo irrelevante.

Malloc realmente asigna un poco más de memoria de la que usted solicita, ya que tiene sus propios encabezados para tratar. Por lo tanto, el almacenamiento óptimo es probablemente algo así como 4k-12 bytes ... pero eso varía según la implementación.

En cualquier caso, no hay razón para que acumule más almacenamiento del que necesita como técnica de optimización.

Answer 5

Usted puede querer asignar memoria en términos del tamaño de palabra del procesador; no cualquier viejo poder de 2 servirá.

Si el procesador tiene una palabra de 32 bits (4 bytes), luego asigne en unidades de 4 bytes. Asignar en términos de 2 bytes puede no ser útil ya que el procesador prefiere que los datos comiencen en un límite de 4 bytes.

Por otro lado, esto puede ser una micro-optimización. La mayoría de las bibliotecas de asignación de memoria están configuradas para devolver la memoria que está alineada en la posición correcta y dejarán la menor cantidad de fragmentación. Si asigna 15 bytes, la biblioteca puede rellenar y asignar 16 bytes. Algunos asignadores de memoria tienen grupos diferentes según el tamaño de asignación.

En resumen, asigne la cantidad de memoria que necesita. Deje que la biblioteca/administrador de asignación maneje la cantidad real por usted. Ponga más energía en la corrección y robustez que preocuparse por estos temas triviales.

Answer 6

Con la cantidad actual de memoria y su velocidad, ya no creo que sea relevante.

Además, si va a asignar memoria con frecuencia, es mejor que considere la agrupación de memoria personalizada/preasignación.

Answer 7

Siempre está probando ...

Usted puede tratar de un programa de "muestra" que asigna memoria en un bucle. De esta forma puede ver si su compilador asigna mágicamente memoria en potencias de 2. Con esa información, puede tratar de asignar la misma cantidad de memoria total usando las 2 estrategias: bloques de tamaño aleatorio y potencia de 2 bloques de tamaño.

Sin embargo, esperaría diferencias, si las hubiera, para grandes cantidades de memoria.

Answer 8

Si está asignando algún tipo de búfer expandible donde necesita seleccionar un número para las asignaciones iniciales, entonces sí, las potencias de 2 son buenos números para elegir. Si necesita asignar memoria para struct foo, entonces solo malloc (sizeof (struct foo)). La recomendación para asignaciones de potencia de 2 proviene de la ineficacia de la fragmentación interna, pero las implementaciones de malloc modernas destinadas a sistemas de multiprocesador están empezando a utilizar agrupaciones locales de CPU para asignaciones lo suficientemente pequeñas como para que importen, lo que evita la contención de bloqueo que solía resultado cuando varios hilos intentan malloc al mismo tiempo, y pasan más tiempo bloqueados debido a la fragmentación.

Al asignar solo lo que necesita, se asegura de que las estructuras de datos estén empaquetadas más densamente en la memoria, lo que mejora la tasa de aciertos de caché, que tiene un impacto mucho mayor en el rendimiento que la fragmentación interna. Existen escenarios con implementaciones de malloc muy antiguas y sistemas multiprocesador de muy alta gama donde las asignaciones de relleno explícito pueden proporcionar una aceleración, pero sus recursos en ese caso se emplearían mejor para obtener una mejor implementación de malloc en ese sistema. El preajuste también hace que el código sea menos portátil y evita que el usuario o el sistema seleccionen el comportamiento malloc en tiempo de ejecución, ya sea programáticamente o con variables de entorno.

La optimización prematura es la raíz de todos los males.

Answer 9

sólo para jugar al abogado del diablo, así es como lo hace Qt:

Supongamos que añadimos 15000 caracteres a la cadena QString.Entonces los siguientes 18 reasignaciones (fuera de un posible 15 000) se producen cuando QString se queda sin espacio: 4, 8, 12, 16, 20, 52, 116, 244, 500, 1012, 2036, 4084, 6132 , 8180, 10228, 12276, 14324, 16372. Al final, QString tiene 16372 caracteres Unicode asignados, 15000 de los cuales están ocupados.

los valores anteriores pueden parecer un poco extraño, pero aquí están los principios rectores :

QString asigna 4 caracteres a la vez hasta que alcance el tamaño 20. De 20 a 4084, que avanza con la duplicación el tamaño cada vez. Más precisamente, se avanza a la siguiente potencia de dos, menos 12. (Algunos asignadores de memoria realizan peor cuando se le solicite exactas potencias de dos, debido a que utilizan unos bytes por bloque para la contabilidad.) A partir de 4084 en adelante, avanza por bloques de 2048 caracteres (4096 bytes). Este tiene sentido porque sistemas operativos modernos no copian los datos completos al reasignar un almacenamiento intermedio; las páginas de memoria física son simplemente reordenadas, y solo los datos en la primera y la última página de realmente necesitan se copian.

Me gusta la forma en que anticipan las características del sistema operativo en el código que está diseñado para funcionar bien desde los teléfonos inteligentes a granjas de servidores. Dado que son personas más inteligentes que yo, supongo que dicha función está disponible en todos los sistemas operativos modernos.

Answer 10

Debe usar realloc() en lugar de malloc() al reasignar. http://www.cplusplus.com/reference/clibrary/cstdlib/realloc/

¿Utiliza siempre una potencia de dos? Depende de lo que esté haciendo tu programa. Si necesita reprocesar toda su estructura de datos cuando crece a una potencia de dos, sí tiene sentido. De lo contrario, simplemente asigna lo que necesitas y no acaparas la memoria.

Answer 11

Cuando estoy asignación de un búfer que puede que tenga que seguir creciendo para dar cabida a los datos de tamaño, que aún desconocida, comienzo con una potencia de 2 menos 1, y cada vez que se queda sin espacio, con REALLOC dos veces el tamaño anterior más 1. Esto hace que nunca tenga que preocuparse por desbordamientos de enteros; el tamaño solo puede desbordarse cuando el tamaño anterior era SIZE_MAX, en cuyo punto la asignación ya habría fallado, y 2*SIZE_MAX+1 == SIZE_MAX de todos modos.

Por el contrario, si acabo de utilizar una potencia de 2 y la doblo cada vez, puedo obtener con éxito un búfer de 2^31 bytes y reasignarlo a un búfer de 0 bytes la próxima vez que duplique el tamaño.

Como algunas personas han comentado acerca de poder-de-2-menos-12 que es bueno para ciertas implementaciones de malloc, también se podría comenzar con una potencia de 2 menos 12, luego duplicarla y agregar 12 en cada paso ...

Por otro lado, si solo está asignando pequeños búferes que no necesitarán crecer, solicite exactamente el tamaño que necesita. No intentes adivinar qué es bueno para malloc.