¿Es mejor asignar memoria en el poder de dos?

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

Supongamos que añadimos 15000 caracteres a la cadena QString. Entonces las siguientes 18 reasignaciones (de un posible 15000) ocurre 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, el QString tiene 16372 caracteres Unicode asignados, 15000 de los cuales están ocupados.

Los valores anteriores pueden parece un poco extraño, pero aquí están los guías principios:

QString asigna 4 caracteres a tiempo hasta que alcance la talla 20. Desde 20 a 4084, avanza duplicando la tamaño cada vez. Más precisamente, se avanza a la siguiente potencia de dos, menos 12. ( Algunos asignadores de memoria realizar peor cuando se solicita exacta poderes de dos , porque utilizan unos pocos bytes por bloque para contabilidad.) A partir de 4084, avanza por bloques de 2048 caracteres (4096 byte). Este tiene sentido porque funcionamiento moderno los sistemas no copian todos los datos al reasignar un búfer ; las páginas de memoria física son simplemente reordenado, y solo los datos en el primera y última página realmente necesita ser copiado.

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

Podría haber sido cierto una vez, pero ciertamente no es mejor.

Solo tiene que asignar la memoria que necesita, cuando la necesita y liberarla tan pronto como haya terminado.

Hay demasiados programas que derrochan recursos - no hagas del tuyo uno de ellos.

Es algo irrelevante.

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

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

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

Si el procesador tiene una palabra de 32 bits (4 bytes), entonces asigne en unidades de 4 bytes. La asignación 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 un 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á la menor cantidad de fragmentación. Si asigna 15 bytes, la biblioteca puede rellenar y asignar 16 bytes. Algunos asignadores de memoria tienen diferentes grupos según el tamaño de la 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.

Cuando estoy asignando un búfer que puede necesitar seguir creciendo para acomodar datos de tamaño aún desconocido, comienzo con una potencia de 2 menos 1, y cada vez que se queda sin espacio, reasigno con el doble del tamaño anterior más 1. Esto hace que nunca tenga que preocuparme por los desbordamientos de enteros; el tamaño solo puede desbordarse cuando el tamaño anterior era SIZE_MAX, momento en el que la asignación ya habría fallado, y 2*SIZE_MAX+1 == SIZE_MAX de todos modos.

En contraste, si solo usara una potencia de 2 y la duplicara cada vez, podría obtener con éxito un búfer de 2^31 bytes y luego reasignar a un búfer de 0 bytes la próxima vez que duplique el tamaño.

Como algunas personas han comentado que power-of-2-minus-12 es bueno para ciertas implementaciones malloc, uno podría igualmente comenzar con una potencia de 2 menos 12, luego duplicarla y agregar 12 en cada paso...

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

Esto depende totalmente de la implementación dada libc de malloc(3). Depende de esa implementación reservar trozos de montón en el orden que crea conveniente.

Para responder a la pregunta - no, no es "mejor" (aquí por "mejor" quieres decir ...?). Si el tamaño que pides es demasiado pequeño, malloc(3) reservará un trozo más grande internamente, así que solo quédate con tu tamaño exacto.

Con la cantidad de memoria de hoy y su velocidad no creo que sea relevante más.

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

Siempre Hay pruebas...

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

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

Si está asignando algún tipo de búfer expandible donde necesita elegir algún 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 simplemente malloc(sizeof (struct foo)). La recomendación para las asignaciones de potencia de 2 se deriva de la ineficiencia de la fragmentación interna, pero las implementaciones malloc modernas destinadas a sistemas multiprocesadores están comenzando a usar pools locales de CPU para asignaciones lo suficientemente pequeñas como para esto importa, lo que evita la contención de bloqueo que solía resultar cuando varios hilos intentaban malloc al mismo tiempo, y pasar más tiempo bloqueado debido a la fragmentación.

Al asignar solo lo que necesita, se asegura de que las estructuras de datos se empaqueten con mayor densidad en la memoria, lo que mejora la tasa de aciertos de caché, lo que tiene un impacto mucho mayor en el rendimiento que la fragmentación interna. Existen escenarios con implementaciones malloc muy antiguas y multiprocesador de muy alta gama los sistemas donde explícitamente las asignaciones de relleno pueden proporcionar una aceleración, pero sus recursos en ese caso se gastarían mejor para obtener una mejor implementación de malloc y ejecutándose en ese sistema. El relleno previo también hace que su 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 mediante programación o con variables de entorno.

La optimización prematura es la raíz de todo mal.

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

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