Complejidad temporal de la asignación de memoria

La complejidad de tiempo para un asignador de pilas puede ser diferente en diferentes sistemas, dependiendo de lo que podrían estar optimizando.

En los sistemas de escritorio, el asignador de montones probablemente utiliza una mezcla de diferentes estrategias que incluyen el almacenamiento en caché de asignaciones recientes, listas de lookaside para tamaños de asignación comunes, contenedores de trozos de memoria con ciertas características de tamaño, etc. para intentar mantener el tiempo de asignación bajo, pero también mantener la fragmentación manejable. Ver las notas para malloc de Doug Lea implementación para una visión general de las diversas técnicas que se utilizan: http://g.oswego.edu/dl/html/malloc.html

Para sistemas más simples, se podría 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 localizar bloques libres en tiempo O (log N) ( http://www.oocities.org/wkaras/heapmm/heapmm.html).

Un sistema en tiempo real podría usar un asignador de montones como TLSF (Two-Level Segregate Fit), que tiene un costo de asignación O(1): http://www.gii.upv.es/tlsf /

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

Dicho esto, 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 menos de 1k están en una lista, los bloques de 1k a 10k están en otra lista y así sucesivamente).

Esto sigue siendo O (n) sin embargo, solo con un menor n.

Estaría interesado en ver su fuente que hay una asignación de montón que no tiene límites (si, con eso, quiere decir que podría tomar para siempre).

Solo echa un vistazo a 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 "devuelve el primer bloque de List(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 (List(2n))) tendría que dividirse con ambos bloques resultantes de n bytes que se ponen en la Lista(n), y este efecto podría ondular a través de todos los tamaños availlable, haciendo una complejidad de O(ns) donde ns es el número de diferentes tamaños availlable, y ns = log (N) donde N es 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 un número de bloques han sido asignados y desasignados, la complejidad es O(1).

Solo dos observaciones:

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

• No es cierto que la política de "mejor ajuste" (encontrar el bloque apretado) sea 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. (buena investigación tema).