¿Se puede despreciar el costo de GC al analizar el tiempo de ejecución de las estructuras de datos en el peor de los casos especificadas en un lenguaje de programación recolectado como basura?

Me acabo de dar cuenta de que he estado asumiendo que la respuesta a mi pregunta es "sí", pero no tengo una buena razón. Me imagino que tal vez haya un recolector de basura que probablemente solo presente peor desaceleración. ¿Hay alguna referencia definitiva que pueda citar? En mi caso, estoy trabajando en una estructura de datos puramente funcional y uso Standard ML, si estos detalles son importantes.$O(1)$

¿Y quizás esta pregunta sería aún más relevante cuando se aplica a las estructuras de datos especificadas en, digamos, Java? ¿Quizás hay algunas discusiones relevantes en los algoritmos / libros de texto de estructura de datos que usan Java? (Sé que Sedgewick tiene una versión Java, pero solo tengo acceso a la versión C).

Sí, gc se amortiza en tiempo constante. Supongamos que tiene un algoritmo que se ejecuta por tiempo con un conjunto de trabajo pico de tamaño k . Ahora, tenga en cuenta que puede asignar como máximo O ( n ) palabras durante la ejecución del programa, y ​​que el costo de tiempo de ejecutar un recolector de basura de copia es O ( k ) (es decir, el costo de un gc es proporcional al total cantidad de datos en vivo). Entonces, si ejecuta el gc la mayoría de las veces O ( n / k ) , entonces el costo total del tiempo de ejecución está limitado por O ( n $n$$k$$O(n)$$O(k)$$O(n/k)$$O(n)$, lo que significa que el costo amortizado del gc es constante. Entonces, si tiene un colector de estilo Cheney, con cada semiespacio de tamaño , entonces es fácil ver que no se puede invocar una colección completa más de una vez cada n / k pasos, ya que asignar k palabras toma O ( k ) tiempo, y el conjunto de trabajo nunca excede el tamaño k , lo que le da el límite que desea. Esto justifica ignorar los problemas de gc.$2k$$n/k$$k$$O(k)$$k$

Sin embargo, un caso en el que la presencia o ausencia de gc no es ignorable es cuando se escriben estructuras de datos sin bloqueo. Muchas estructuras de datos modernas sin bloqueo pierden deliberadamente memoria y dependen de gc para su corrección. Esto se debe a que a un nivel alto, la forma en que funcionan es copiar algunos datos, hacer un cambio en ellos e intentar actualizarlos atómicamente con una instrucción CAS, y ejecutar esto en un bucle hasta que el CAS tenga éxito. Agregar la desasignación determinista a estos algoritmos los hace mucho más complejos, por lo que las personas a menudo no se molestan (especialmente porque a menudo están dirigidos a entornos similares a Java).

EDITAR: si desea límites no amortizados, el cobrador de Cheney no lo hará: escanea todo el conjunto en vivo cada vez que se invoca. La palabra clave para google es "recolección de basura en tiempo real" y Djikstra et al. y Steele dio los primeros recolectores de marca y barrido en tiempo real, y Baker dio el primer gc de compactación en tiempo real.

@article {dijkstra1978fly,
  title = {{Recolección de basura sobre la marcha: un ejercicio de cooperación}},
  autor = {Dijkstra, EW y Lamport, L. y Martin, AJ y Scholten, CS y Steffens, EFM},
  journal = {Comunicaciones de la ACM},
  volumen = {21},
  número = {11},
  páginas = {966--975},
  issn = {0001-0782},
  año = {1978},
  editor = {ACM}
}

@article {steele1975multiprocesamiento,
  title = {{Multiprocesamiento compactando la recolección de basura}},
  autor = {Steele Jr, GL},
  journal = {Comunicaciones de la ACM},
  volumen = {18},
  número = {9},
  páginas = {495--508},
  issn = {0001-0782},
  año = {1975},
  editor = {ACM}
}

@article {baker1978list,
  title = {{Procesamiento de listas en tiempo real en una computadora en serie}},
  autor = {Baker Jr, HG},
  journal = {Comunicaciones de la ACM},
  volumen = {21},
  número = {4},
  páginas = {280--294},
  issn = {0001-0782},
  año = {1978},
  editor = {ACM}
}

$O(n)$

$O(1)$

La referencia definitiva de recolección de basura es:

• Recolección de basura por Richard Jones y Rafael Lin

Ben Zorn hizo un trabajo midiendo los costos reales de diferentes algoritmos de recolección de basura, aunque el siguiente artículo es más reciente y presenta una comparación mucho más completa:

• Mitos y realidades: el impacto en el rendimiento de la recolección de basura , SM Blackburn, P. Cheng y KS McKinley, Conferencia ACM SIGMETRICS sobre sistemas informáticos de medición y modelado, páginas 25 a 36, ​​Nueva York, NY, junio de 2004.

Para más ver:

• Una teoría unificada de recolección de basura , Bacon, Cheng y Rajan, Conferencia ACM sobre Programación Orientada a Objetos, Sistemas, Lenguajes y Aplicaciones, Vancouver, BC, Canadá, pp. 50-68, 2004.