Complejidad de tiempo de la asignación de memoria

Question

¿Cuál es la complejidad temporal de la asignación dinámica de memoria usando new, malloc, etc.? Sé muy poco acerca de cómo se implementan los asignadores de memoria, pero supongo que la respuesta es que depende de la implementación. Por lo tanto, responda algunos de los casos / implementaciones más comunes.

Editar: Recuerdo vagamente haber escuchado 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.

Answer 1

Una de las cosas que debe tener en cuenta al tratar con la notación O es que a menudo es muy importante comprender qué es n . Si el n es algo relacionado con algo que puede controlar (por ejemplo: el número de elementos en una lista que desea ordenar), entonces tiene sentido mirarlo detenidamente.

En la mayoría de las implementaciones de almacenamiento dinámico, su n es la cantidad de fragmentos de memoria contiguos que maneja el administrador. Esto es decididamente no algo típicamente bajo control del cliente. La única n sobre la que el cliente realmente tiene control es el tamaño de la memoria que desea. A menudo, esto no tiene relación con la cantidad de tiempo que tarda el asignador. Un n grande podría asignarse tan rápidamente como un n pequeño, o podría tomar mucho más tiempo, o incluso podría ser inservible. Todo esto podría cambiar para el mismo n dependiendo de cómo ingresaron las asignaciones y desasignaciones anteriores de otros clientes. Entonces, realmente, a menos que esté implementando un montón, entonces 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).

Answer 2

La complejidad de tiempo para un asignador de almacenamiento dinámico puede ser diferente en diferentes sistemas, dependiendo de para qué se esté optimizando.

En los sistemas de escritorio, el asignador de almacenamiento dinámico probablemente utiliza una combinación de diferentes estrategias que incluyen el almacenamiento en caché de asignaciones recientes, listas de búsqueda para tamaños de asignación comunes, contenedores de fragmentos de memoria con ciertas características de tamaño, etc. para intentar mantener un tiempo de asignación bajo pero también mantener fragmentación manejable. Consulte las notas sobre la implementación de malloc de Doug Lea para obtener una descripción general de las diversas técnicas que se utilizan: http: //g.oswego.edu/dl/html/malloc.html

Para sistemas más simples, se puede utilizar una estrategia de primer ajuste o mejor ajuste, con los bloques libres almacenados en una lista vinculada (lo que daría un tiempo O (N) con N siendo el número de bloques libres). Pero se podría usar un sistema de almacenamiento más sofisticado, como un árbol AVL, para poder localizar bloques libres en el tiempo O (log N) ( http://www.oocities.org/wkaras/heapmm/heapmm.html ).

Un sistema en tiempo real podría usar un asignador de almacenamiento dinámico como TLSF (ajuste de segregación de dos niveles), que tiene un costo de asignación O (1): http://www.gii.upv.es/tlsf/

Answer 3

Creo que generalmente sería O (n) donde n es el número de bloques de memoria disponibles (ya que debe escanear los bloques de memoria disponibles para encontrar uno adecuado).

Dicho esto, he visto optimizaciones que pueden acelerarlo, manteniendo específicamente varias listas de bloques disponibles en función 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 y así sucesivamente).

Sin embargo, esto sigue siendo O (n), solo con una n más pequeña.

Me interesaría ver en su fuente que hay una asignación de montón que no tiene límites (si, con eso, quiere decir que podría llevar una eternidad).

Answer 4

Simplemente vea cómo funcionan los asignadores típicos.

Un asignador de bump-the-pointer funciona en O (1) , y es un pequeño ' 1 '.

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 . podría encontrar que la Lista ( n ) está vacía, por lo que un bloque de la siguiente lista (Lista ( 2n )) debería ser se divide con los dos bloques resultantes de n bytes que se colocan en la Lista ( n ), y este efecto podría ondular a través de todos los tamaños disponibles, lo que genera un 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 de el 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 hayan asignado y desasignado varios bloques, la complejidad es O (1) .

Answer 5

Solo dos comentarios:

• TLSF es O (1) en el sentido de que no tiene un bucle único; y maneja hasta 2Gb. Aunque es realmente difícil de creer, solo verifique el código.

• No es cierto que el "mejor ajuste" La política (encontrar el bloque apretado) es la más adecuada para lograr una pequeña fragmentación 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).