La demostración de recolección de basura es más rápida que la administración manual de memoria

23

He leído en muchos lugares (diablos, incluso he escrito yo mismo) que la recolección de basura podría (en teoría) ser más rápida que la gestión manual de la memoria.

Sin embargo, mostrar es mucho más difícil de encontrar que contar.
Nunca he visto ningún fragmento de código que demuestre este efecto en acción.

¿Alguien tiene (o sabe dónde puedo encontrar) código que demuestre esta ventaja de rendimiento?

memory garbage-collection Mehrdad
fuente
55
El problema con la GC es que la mayoría de las implementaciones no son tan determinista 2 carreras pueden tener resultados muy diferentes, por no hablar de que es difícil de aislar las variables correctas para comparar
trinquete monstruo
@ratchetfreak: Si conoces algún ejemplo que solo sea más rápido (por ejemplo) el 70% del tiempo, también está bien para mí. Debe haber alguna forma de comparar los dos, al menos en términos de rendimiento (la latencia probablemente no funcionaría).
Mehrdad el
1
Bueno, esto es un poco complicado porque siempre puedes hacer manualmente lo que sea que le dé al GC una ventaja sobre lo que hiciste manualmente. ¿Quizás sea mejor restringir esto a herramientas de administración de memoria manual "estándar" (malloc () / free (), punteros propios, punteros compartidos con recuento, punteros débiles, sin asignadores personalizados)? O bien, si permite asignadores personalizados (que pueden ser más realistas o menos realistas, según el tipo de programador que asuma), imponga restricciones al esfuerzo que se aplica a esos asignadores. De lo contrario, la estrategia manual "copiar lo que hace el GC en este caso" siempre es al menos tan rápido como el GC.
1
Por "copiar lo que hace el GC" no quise decir "construir su propio GC" (aunque tenga en cuenta que esto es teóricamente posible en C ++ 11 y más allá, lo que introduce soporte opcional para un GC). Quise decir, como lo dije anteriormente en el mismo comentario, "haz lo que le da al GC una ventaja sobre lo que hiciste manualmente". Por ejemplo, si la compactación tipo Cheney ayuda mucho a esta aplicación, puede implementar manualmente un esquema de asignación + compactación similar, con punteros inteligentes personalizados para manejar la reparación del puntero. Además, con técnicas como una pila de sombra, puede hacer la búsqueda de raíz en C o C ++, a expensas de un trabajo adicional.
1
@ Ike: está bien. ¿Ves por qué hice la pregunta? Ese fue el punto central de mi pregunta: las personas tienen todo tipo de explicaciones que deberían tener sentido, pero todos tropiezan cuando les pides que brinden una demostración que demuestre que lo que dicen es correcto en la práctica. El punto principal de esta pregunta era mostrar de una vez por todas que esto realmente puede suceder en la práctica.
Mehrdad

Respuestas:

26

Consulte http://blogs.msdn.com/b/ricom/archive/2005/05/10/416151.aspx y siga todos los enlaces para ver a Rico Mariani vs Raymond Chen (ambos programadores muy competentes en Microsoft) duelo. . Raymond mejoraría el no administrado, Rico respondería optimizando lo mismo en los administrados.

Con un esfuerzo de optimización esencialmente cero, las versiones administradas comenzaron muchas veces más rápido que el manual. Finalmente, el manual superó al administrado, pero solo optimizando a un nivel al que la mayoría de los programadores no querrían ir. En todas las versiones, el uso de memoria del manual fue significativamente mejor que el administrado.

btilly
fuente
+1 por citar un ejemplo real con código :) aunque el uso adecuado de las construcciones de C ++ (como swap) no es tan difícil, y probablemente lo lleve a usted con bastante facilidad en cuanto al rendimiento ...
Mehrdad
55
Es posible que pueda superar a Raymond Chen en rendimiento. Estoy seguro de que no puedo a menos que esté fuera de juego debido a una enfermedad, estoy trabajando muchas veces más duro y tuve suerte. No sé por qué no eligió la solución que tú hubieras elegido. Estoy seguro de que tenía razones para ello
hasta el
Copié el código de Raymond aquí , y para comparar, escribí mi propia versión aquí . El archivo ZIP que contiene el archivo de texto está aquí . En mi computadora, la mía se ejecuta en 14 ms y la de Raymond en 21 ms. A menos que haya hecho algo mal (que es posible), su código de 215 líneas es un 50% más lento que mi implementación de 48 líneas, incluso sin usar archivos mapeados en memoria o grupos de memoria personalizados (que sí utilizó). El mío es la mitad de largo que la versión C #. ¿Lo hice mal o observas lo mismo?
Mehrdad
1
@Mehrdad Al sacar una copia antigua de gcc en esta computadora portátil, puedo informar que ni su código ni el suyo se compilarán, y mucho menos hacer nada con él. El hecho de que no esté en Windows probablemente lo explica. Pero supongamos que sus números y código son correctos. ¿Realizan lo mismo en un compilador y una computadora de hace una década? (Mire cuando se escribió el blog). Quizás, quizás no. Supongamos que lo son, que él (siendo un programador de C) no sabía cómo usar C ++ correctamente, etc. ¿Qué nos queda?
btilly
1
Nos queda un programa razonable de C ++ que se puede traducir a la memoria administrada y acelerar. Pero donde la versión C ++ se puede optimizar y acelerar aún más. Lo que todos estamos de acuerdo es el patrón general que siempre ocurre cuando el código administrado es más rápido que el no administrado. Sin embargo, todavía tenemos un ejemplo concreto de código razonable de un buen programador que fue más rápido en una versión administrada.
btilly
5

La regla general es que no hay almuerzos gratis.

GC elimina el dolor de cabeza de la gestión manual de la memoria y reduce la probabilidad de cometer errores. Hay algunas situaciones en las que una estrategia de GC particular es la solución óptima para el problema, en cuyo caso no pagará ninguna penalización por usarlo. Pero hay otros donde otras soluciones serán más rápidas. Dado que siempre puedes simular abstracciones más altas desde un nivel más bajo, pero no al revés, puedes demostrar efectivamente que no hay forma de que las abstracciones más altas puedan ser más rápidas que las más bajas en el caso general.

GC es un caso especial de gestión manual de memoria

Puede ser mucho trabajo o más propenso a errores para obtener un mejor rendimiento de forma manual, pero esa es una historia diferente.

Guy Sirton
fuente
1
Eso no tiene sentido. Para darle un par de ejemplos concretos: 1) los asignadores y las barreras de escritura en los GC de producción son ensambladores escritos a mano porque C es demasiado ineficiente, entonces, ¿cómo va a superar eso de C, y 2) la eliminación de llamadas de cola es un ejemplo de optimización hecho en lenguajes de alto nivel (funcionales) que el compilador de C no hace y, por lo tanto, no se puede hacer en C. El recorrido de la pila es otro ejemplo de algo hecho por debajo del nivel de C por lenguajes de alto nivel.
Jon Harrop
2
1) Tendría que ver el código específico para comentar, pero si las asignaciones / barreras escritas a mano en ensamblador son más rápidas, use ensamblador escrito a mano. No estoy seguro de qué tiene que ver eso con GC. 2) Eche un vistazo aquí: stackoverflow.com/a/9814654/441099 el punto no es si algún lenguaje que no sea GC puede eliminar la recursión de cola por usted. El punto es que puedes transformar tu código para que sea tan rápido o más rápido. Es conveniente saber si el compilador de algún lenguaje específico puede hacer esto automáticamente por usted. En una abstracción lo suficientemente baja, siempre puede hacerlo usted mismo si lo desea.
Guy Sirton el
1
Ese ejemplo de llamada de cola en C solo funciona para el caso especial de una función que se llama a sí misma. C no puede manejar el caso general de funciones que se llaman entre sí. Pasar al ensamblador y asumir un tiempo infinito para el desarrollo es un tarpit de Turing.
Jon Harrop
3

Es fácil construir una situación artificial en la que el GC sea infinitamente más eficiente que los métodos manuales: simplemente organice que solo haya una "raíz" para el recolector de basura, y que todo sea basura, de modo que el paso del GC se complete al instante.

Si lo piensa, ese es el modelo utilizado cuando se recolecta basura la memoria asignada a un proceso. El proceso muere, toda su memoria es basura, hemos terminado. Incluso en términos prácticos, un proceso que se inicia, se ejecuta y muere sin dejar rastro podría ser más eficiente que uno que se inicia y se ejecuta para siempre.

Para programas prácticos, escritos en idiomas con recolección de basura, la ventaja de la recolección de basura no es la velocidad sino la corrección y la simplicidad.

ddyer
fuente
Si es fácil construir un ejemplo artificial, ¿le importaría mostrar uno simple?
Mehrdad el
1
@Mehrdad Él explicó una simple. Escriba un programa en el que la versión de GC no pueda ejecutar una basura antes de salir. La versión administrada de memoria manual será más lenta porque estaba rastreando y liberando cosas explícitamente.
btilly
3
@btilly: "Escriba un programa en el que la versión de GC no pueda ejecutar una basura antes de salir". ... no hacer la recolección de basura en primer lugar es una pérdida de memoria debido a la falta de un GC en funcionamiento, ¡no una mejora del rendimiento debido a la presencia de un GC! Es como llamar abort()a C ++ antes de que el programa salga. Es una comparación sin sentido; Ni siquiera estás recogiendo basura, solo estás dejando que la memoria se escape. No puedes decir que la recolección de basura es más rápida (o más lenta) si no estás recolectando basura para empezar ...
Mehrdad
Para hacer un ejemplo extremo, tendrías que definir un sistema completo con tu propio montón y gestión de montón, lo que sería un gran proyecto para estudiantes pero demasiado grande para caber en este margen. Le iría bastante bien escribiendo un programa que asigne y desasigne matrices de tamaño aleatorio, de una manera diseñada para ser estresante para los métodos de administración de memoria no gc.
ddyer
3
@Mehrdad No es así. El escenario es que la versión GC nunca alcanzó el umbral en el que habría realizado una ejecución, no es que no hubiera funcionado correctamente en un conjunto de datos diferente. Trivialmente va a ser muy bueno para la versión GC, aunque no es un buen predictor del rendimiento final.
btilly
2

Debe considerarse que GC no es solo una estrategia de administración de memoria; También exige todo el diseño del lenguaje y el entorno de tiempo de ejecución, que imponen costos (y beneficios). Por ejemplo, un lenguaje que admita GC debe compilarse en una forma en la que los punteros no se puedan ocultar del recolector de basura y, en general, donde no se puedan construir, excepto por primitivas del sistema cuidadosamente administradas. Otra consideración es la dificultad de mantener las garantías de tiempo de respuesta, ya que GC impone algunos pasos que se deben permitir que se ejecuten hasta su finalización.

En consecuencia, si tiene un idioma que es basura recolectada y compara la velocidad con la memoria administrada manualmente en el mismo sistema, aún tiene que pagar los gastos generales para admitir la recolección de basura, incluso si no lo está usando.

ddyer
fuente
2

Más rápido es dudoso. Sin embargo, puede ser ultrarrápido, imperceptible o más rápido si es compatible con hardware. Hubo diseños como ese para máquinas LISP hace mucho tiempo. Uno incorporó el GC en el subsistema de memoria del hardware como tal que la CPU principal no sabía que estaba allí. Al igual que muchos diseños posteriores, el GC se ejecutó simultáneamente con el procesador principal con poca o ninguna necesidad de pausas. Un diseño más moderno son las máquinas Azul Systems Vega 3 que ejecutan código Java mucho más rápido que las JVM que utilizan procesadores especialmente diseñados y un GC sin pausa. Busca en Google si quieres saber qué tan rápido puede ser GC (o Java).

Nick P
fuente
2

He trabajado bastante en esto y he descrito algo de esto aquí . Comparé el GC de Boehm en C ++, asignando usando mallocpero no liberando, asignando y liberando usando freey un GC de región de marca personalizado escrito en C ++ todos contra el GC de stock de OCaml que ejecuta un solucionador de n-reinas basado en listas. El GC de OCaml fue más rápido en todos los casos. Los programas C ++ y OCaml se escribieron deliberadamente para realizar las mismas asignaciones en el mismo orden.

Por supuesto, puede reescribir los programas para resolver el problema utilizando solo enteros de 64 bits y sin asignaciones. Aunque más rápido eso derrotaría el objetivo del ejercicio (que era predecir el rendimiento de un nuevo algoritmo GC en el que estaba trabajando usando un prototipo construido en C ++).

He pasado muchos años en la industria portando código C ++ real a lenguajes administrados. En casi todos los casos, observé mejoras sustanciales en el rendimiento, muchas de las cuales probablemente se debieron a la gestión manual de la memoria del GC. La limitación práctica no es lo que se puede lograr en un microbenchmark, sino lo que se puede lograr antes de una fecha límite y los lenguajes basados ​​en GC ofrecen mejoras de productividad tan enormes que nunca miré hacia atrás. Todavía uso C y C ++ en dispositivos integrados (microcontroladores) pero incluso eso está cambiando ahora.

Jon Harrop
fuente
+1 gracias. ¿Dónde podemos ver y ejecutar el código de referencia?
Mehrdad
El código está disperso por el lugar. Publiqué la
Jon Harrop
1
Hay resultados para ambos hilos seguros e inseguros allí.
Jon Harrop
1
@Mehrdad: "¿Has eliminado tales posibles fuentes de error?". Sí. OCaml tiene un modelo de compilación muy simple sin optimizaciones como el análisis de escape. La representación de OCaml del cierre es en realidad sustancialmente más lenta que la solución C ++, por lo que realmente debería usar una costumbre List.filtercomo lo hace C ++. Pero sí, ciertamente tiene toda la razón en que algunas operaciones de RC pueden eludirse. Sin embargo, el mayor problema que veo en la naturaleza es que las personas no tienen tiempo para realizar tales optimizaciones a mano en grandes bases de códigos industriales.
Jon Harrop
2
Si, absolutamente. No hay esfuerzo adicional para escribir, pero escribir código no es el cuello de botella con C ++. Mantener el código es. Mantener el código con este tipo de complejidad incidental es una pesadilla. La mayoría de las bases de códigos industriales son millones de líneas de código. Simplemente no quieres tener que lidiar con eso. He visto a personas convertir todo shared_ptrsolo para corregir errores de concurrencia. El código es mucho más lento pero, bueno, ahora funciona.
Jon Harrop
-1

Tal ejemplo necesariamente tiene un mal esquema de asignación de memoria manual.

Asumir el mejor recolector de basura GC. Internamente tiene métodos para asignar memoria, determinar qué memoria se puede liberar y métodos para finalmente liberarla. Juntos, estos toman menos tiempo que todos GC; se pasa algún tiempo en los otros métodos de GC.

Ahora considere un asignador manual que usa el mismo mecanismo de asignación que GC, y cuya free()llamada simplemente deja de lado la memoria que se liberará por el mismo método que GC. No tiene una fase de exploración, ni tiene ninguno de los otros métodos. Necesariamente lleva menos tiempo.

MSalters
fuente
2
Un recolector de basura a menudo puede liberar muchos objetos, sin tener que poner la memoria en un estado útil después de cada uno. Considere la tarea de eliminar de una lista de matriz todos los elementos que cumplan un determinado criterio. Eliminar un solo elemento de una lista de N elementos es O (N); eliminando M elementos de una lista de N, uno a la vez es O (M * N). Sin embargo, eliminar todos los elementos que cumplen un criterio en una sola pasada por la lista es O (1).
supercat
@supercat: freetambién puede recolectar lotes. (Y, por supuesto, eliminar todos los elementos que cumplen un criterio sigue siendo O (N), aunque solo sea por el recorrido de la lista en sí)
MSalters
Eliminar todos los elementos que cumplen un criterio es al menos O (N). Es correcto que freepodría funcionar en un modo de recopilación por lotes si cada elemento de memoria tuviera un indicador asociado, aunque el GC todavía puede salir adelante en algunas situaciones. Si uno tiene M referencias que identifican L elementos distintos de un conjunto de N cosas, el tiempo para eliminar cada referencia a la que no existe ninguna referencia y consolidar el resto es O (M) en lugar de O (N). Si uno tiene M espacio adicional disponible, la constante de escala puede ser bastante pequeña. Además, la compactación en un sistema GC sin escaneo requiere ...
supercat
@supercat: Bueno, ciertamente no es O (1) como dice tu última oración en el primer comentario.
MSalters
1
@MSalters: "¿Y qué evitaría que un esquema determinista tenga una guardería?". Nada. El recolector de basura de rastreo de OCaml es determinista y utiliza un vivero. Pero no es "manual" y creo que está haciendo mal uso de la palabra "determinista".
Jon Harrop