optimization - Tiempo de complejidad de la asignación de memoria
memory-management malloc (5)
Creo que generalmente sería O (n) donde n es el número de bloques de memoria disponibles (ya que tiene que escanear los bloques de memoria disponibles para encontrar uno adecuado).
Habiendo dicho eso, he visto optimizaciones que pueden hacerlo más rápido, específicamente manteniendo múltiples listas de bloques disponibles dependiendo de sus rangos de tamaño (por lo que los bloques de menos de 1k están en una lista, los bloques de 1k a 10k están en otra lista, etc. )
Esto sigue siendo O (n) sin embargo, solo con un n más pequeño.
Me interesaría ver tu fuente que hay una asignación de montón que no tiene límites (si, con eso, quieres decir que podría llevar una eternidad).
¿Cuál es la complejidad temporal de la asignación de memoria dinámica utilizando new, malloc, etc.? Sé muy poco sobre cómo se implementan los asignadores de memoria, pero supongo que la respuesta es que depende de la implementación. Por lo tanto, responda por algunos de los casos / implementaciones más comunes.
Editar: Recuerdo vagamente haber oído que la asignación del montón no tiene límites en el peor de los casos, pero estoy realmente interesado en el caso promedio / típico.
La complejidad de tiempo para un asignador de montón puede ser diferente en diferentes sistemas, dependiendo de para qué se puedan optimizar.
En los sistemas de escritorio, el asignador de montones probablemente usa una combinación de diferentes estrategias, incluidas asignaciones recientes de almacenamiento en caché, listados de tamaños de asignación comunes, contenedores de fragmentos de memoria con ciertas características de tamaño, etc. para intentar mantener el tiempo de asignación pero también mantener la fragmentación manejable. Vea las notas para la implementación de malloc de Doug Lea para una descripción general de las diversas técnicas que se usan: http://g.oswego.edu/dl/html/malloc.html
Para sistemas más simples, se puede usar una estrategia de primer ajuste o mejor ajuste, con los bloques libres almacenados en una lista vinculada (lo que daría un tiempo de O (N) siendo N el número de bloques libres). Pero un sistema de almacenamiento más sofisticado, como un árbol AVL, podría usarse para poder ubicar bloques libres en el tiempo O (log N) ( http://www.oocities.org/wkaras/heapmm/heapmm.html ).
Un sistema en tiempo real puede usar un asignador de montón como TLSF (ajuste segregado de dos niveles), que tiene un costo de asignación O (1): http://www.gii.upv.es/tlsf/
Solo dos comentarios:
http://www.gii.upv.es/tlsf/ es O (1) en el sentido de que no tiene un solo bucle; y maneja hasta 2Gb. Aunque es realmente difícil de creer, solo revisa el código.
No es cierto que la política de "mejor ajuste" (encontrar el bloque ajustado) sea la más adecuada para lograr una fragmentación pequeña. Está lejos de ser trivial demostrar esta afirmación, de hecho no se ha probado formalmente, pero hay muchas evidencias que van en esa dirección. (buen tema de investigación).
Solo mira cómo funcionan los asignadores típicos.
Un asignador de bump-the-pointer funciona en O (1) , y es un pequeño '' 1 '' en eso.
Para un asignador de almacenamiento segregado, la asignación de k bytes significa "devolver el primer bloque de la Lista ( n )" donde List ( n ) es la lista de bloques de n bytes donde n> = k . Puede encontrar que List ( n ) está vacío, por lo que un bloque de la lista siguiente (List ( 2n )) debería dividirse con los dos bloques resultantes de n bytes puestos en List ( n ), y este efecto podría fluctuar. a través de todos los tamaños disponibles, para una complejidad de O (ns) donde ns es el número de diferentes tamaños disponibles, y ns = log (N) donde N es el tamaño del tamaño de bloque más grande disponible, por lo que incluso eso sería pequeño. En la mayoría de los casos, especialmente después de que se han asignado y desasignado varios bloques, la complejidad es O (1) .
Una de las cosas que debes tener en cuenta al tratar con la notación O es que a menudo es muy importante entender qué es n . Si el n es algo relacionado con algo que puede controlar (por ej .: la cantidad de elementos en una lista que desea ordenar), entonces tiene sentido mirarlo detenidamente.
En la mayoría de las implementaciones de montón, tu n es la cantidad de fragmentos contiguos de memoria que maneja el administrador. Esto definitivamente no es algo típicamente bajo el control del cliente. Lo único que el cliente realmente tiene control es el tamaño del trozo de memoria que desea. A menudo, esto no guarda relación con la cantidad de tiempo que tarda el asignador. Una n grande podría asignarse tan rápidamente como una n pequeña, o podría llevar mucho más tiempo, o incluso podría no ser válida. Todo esto podría cambiar por el mismo n dependiendo de cómo entraron las asignaciones y desasignaciones previas de otros clientes. Así que en realidad, a menos que esté implementando un montón, la respuesta correcta es que no es determinista .
Esta es la razón por la cual los programadores en tiempo real intentan evitar la asignación dinámica (después del inicio).