performance - sistemas - segmentacion de memoria
¿Alguna información difícil sobre GC versus rendimiento explícito de la gestión de memoria? (15)
Aquí hay muchos argumentos diferentes. Quiero comenzar dejando en claro que no se puede hacer una comparación 1: 1. Cada uno tiene sus pros y sus contras, y cualquier fragmento de código será más apropiado para uno u otro sistema. Eso es tanto como decir que, por el contrario, debe saber si tiene GC o no para escribir un código eficiente.
Mi argumento es que debes conocer tu entorno y tu código de manera acorde . Eso hará que tu código sea eficiente. Pasar de un paradigma al otro y codificar el mismo estilo hará que su código sea más ineficiente que lo que el GC realmente ayuda / quita.
Caso:
Un programa genera miles de asignaciones de memoria de montón para objetos de vida corta. Es decir, asigna y desasigna muchas veces, con diferentes tamaños de objetos.
En un entorno que no sea de GC, para cada asignación terminaría llamando malloc, y eso requiere ubicar en la lista de fragmentos de memoria libres la más adecuada (de acuerdo con la implementación específica de malloc). La memoria se usa y luego se libera con free [o new / delete in C ++ ...]. El costo de la administración de la memoria es el costo de localizar los fragmentos.
En un entorno GC, con un GC móvil como java o .net, después de cada GC, toda la memoria libre es contigua. El costo de adquirir memoria para un objeto es barato, realmente barato (<10 instrucciones de CPU en Java VM). En cada ejecución del GC, solo los objetos vivos se ubican y se mueven al comienzo de la región de memoria apropiada (generalmente es una región diferente a la original). El costo de la administración de la memoria es principalmente el costo de mover todos los objetos alcanzables (vivos). Ahora, la premisa es que la mayoría de los objetos tienen una vida corta, por lo que al final el costo puede ser menor que el de un sistema que no es de GC. Un millón de objetos asignados y liberados (olvidados) en un solo monto de ejecución de GC sin costo adicional.
Conclusión: en los lenguajes de GC, puede crear todos los objetos locales en el montón. Ellos son baratos. Por otro lado, en sistemas que no son GC, un conjunto de asignaciones, desasignaciones y nuevas asignaciones es costoso. La memoria está fragmentada y el costo de malloc aumenta ... En sistemas que no son de GC, debe usar la pila tanto como sea posible, utilizando el montón de necesidad.
Eso tiene otra implicación. La gente acostumbrada a uno de los dos sistemas de memoria tenderá a escribir programas ineficientes en el otro. Están acostumbrados a algunos modismos que probablemente sean malos en el otro sistema.
Un ejemplo claro es que un programador no administrado que se usa para asignar un objeto y reutilizar (reiniciar sus punteros internos con nuevos elementos según se requiera) se usa para esa forma de pensar: la asignación es costosa, la reutilización es barata. Ahora, si el mismo código exacto se mueve a un entorno GC generacional (Java, .net - ambos son move-generational-GC), se obtiene un efecto divertido. En Java generational GC, el sistema realizará colecciones menores solo en las generaciones más jóvenes, solo procesando generaciones anteriores en colecciones completas. Pero un objeto en la generación joven podría ser referido por objetos de la generación anterior, por lo que se debe realizar un trabajo adicional para realizar un seguimiento de estas referencias antiguas. En particular, en el recolector de basura Java 1.4.1, el sistema marcará la tarjeta de memoria (subparte de la página) donde reside el objeto viejo y luego incluirá todas las tarjetas marcadas para su procesamiento durante la colección menor, aumentando efectivamente la cantidad de trabajo que el GC tiene que funcionar y posiblemente tenga un impacto en el rendimiento.
El objeto estaba vivo durante 1, 2, 3 ... GC se ejecuta, y se movió muchas veces, finalmente se mueve a la generación anterior, donde no se moverá en cada carrera de GC, pero puede permanecer allí ... pero, por desgracia, el programador obliga al objeto a ser más joven. Se mueve una vez más, y se volverá a mover cada vez que el GC se ejecute hasta el momento en que vuelva a envejecer.
Para hacer una comparación sensata, debería llegar a los programadores que conocen el entorno y escribir diferentes piezas de código que resuelven el mismo problema con los mismos algoritmos con diferentes conjuntos de ideas acerca de la administración de la memoria. Luego compara los resultados de ambos.
Recientemente leí el excelente artículo " The Transactional Memory / Garbage Collection Analogy " de Dan Grossman. Una frase realmente llamó mi atención:
En teoría, la recolección de basura puede mejorar el rendimiento al aumentar la localidad espacial (debido a la reubicación de objetos), pero en la práctica pagamos un costo de rendimiento moderado por los beneficios de ingeniería de software.
Hasta entonces, mi sentimiento siempre había sido muy vago al respecto. Una y otra vez, ves reclamos de que GC puede ser más eficiente, así que siempre mantuve esa noción en mi cabeza. Después de leer esto, empecé a tener serias dudas.
Como un experimento para medir el impacto en los lenguajes de GC, algunas personas tomaron algunos programas de Java, rastrearon la ejecución y luego reemplazaron la recolección de elementos no utilizados con administración de memoria explícita. Según esta revisión del artículo sobre Lambda lo último , descubrieron que GC siempre era más lento. Los problemas de memoria virtual hicieron que GC pareciera aún peor, ya que el recopilador toca con regularidad muchas más páginas de memoria que el programa en ese punto, y por lo tanto causa un gran intercambio.
Esto es todo experimental para mí. ¿Alguien, y en particular en el contexto de C ++, realizó un punto de referencia integral de rendimiento de GC cuando se compara con la administración de memoria explícita?
Particularmente interesante sería comparar cómo varios grandes proyectos de código abierto, por ejemplo, funcionan con o sin GC. ¿Alguien ha oído hablar de tales resultados antes?
EDITAR: Y por favor, concéntrese en el problema de rendimiento , no en por qué existe GC o por qué es beneficioso.
Aclamaciones,
Carl
PD. En caso de que ya esté sacando el lanzallamas: no estoy tratando de descalificar a GC, solo estoy tratando de obtener una respuesta definitiva a la pregunta sobre el rendimiento.
Aquí hay un experimento que me gusta ejecutar:
- Inicie un programa escrito en un entorno recolectado de basura (como .NET o Java).
- Inicie un programa similar escrito en un entorno que no sea basura (como C o C ++).
- Use los programas y vea cuál es más receptivo.
Mejora de la objetividad: haz que tu abuela haga el paso 3.
Está muy bien citar el rendimiento teórico de las implementaciones óptimas de GC, pero el hecho es que en los escenarios del mundo real, los programas escritos en lenguajes recolectados no funcionan tan bien como las aplicaciones nativas. Esta es la razón por la cual los proyectos grandes en los que el rendimiento se traduce directamente en la experiencia del usuario todavía se programa en C ++. El ejemplo clásico de esto es la programación de juegos.
Otro ejemplo, quizás contradictorio, de esto es el Eclipse IDE. Si bien puede estar escrito en Java, el subsistema gráfico completo tuvo que ser reescrito para producir un rendimiento aceptable. La solución: hacer elementos GUI ligeros envoltorios alrededor de componentes nativos (C / C ++) ( SWT ).
Entiendo el sorteo de entornos recogidos de basura. La administración de la memoria es difícil de resolver. Y mucho trabajo. La conclusión es la siguiente: saber cómo se supone que se comporta su programa le da a usted (el programador) una ventaja sobre una máquina que intenta adivinar .
Como señala @dribeas, la mayor "confusión" del experimento en el trabajo (de Hertz & Berger) es que el código siempre se escribe bajo algunas "suposiciones implícitas" sobre lo que es barato y lo que es costoso. Además de confundir, la metodología experimental (ejecutar un programa Java fuera de línea, crear un oráculo de duración de los objetos, volver a formar parte de las llamadas aloac / libres ''ideales'') es bastante brillante e iluminador. (Y mi opinión personal es que la confusión no disminuye demasiado sus resultados).
Personalmente, mi intuición es que usar un tiempo de ejecución de GC-ed significa aceptar un golpe de rendimiento de factor-de-tres a tu aplicación (el GC será 3 veces más lento). Pero el verdadero panorama de los programas está plagado de confusiones, y es probable que encuentre una gran cantidad de datos dispersos si pudiera realizar el experimento "ideal" en muchos programas en muchos dominios de aplicaciones, con GC a veces ganando y Manual a menudo ganando . (Y el paisaje cambia continuamente; ¿cambiarán los resultados cuando el núcleo múltiple (y el software diseñado para multinúcleo) sea el principal?)
Ver también mi respuesta a
Are there statistical studies that indicates that Python is "more productive"?
which has the thesis that "due to so many confounds, all evidence about software engineering is anecdotal".
Después de la discusión de otra respuesta, una desventaja que resulta es que GC puede alterar la complejidad asintótica. El comentario de Soru lo declaró implícitamente sin ejemplos, y un comentario no es suficiente para explicarlo. Gracias a Jon Harrop por el ejemplo, sugirió comentarios útiles sobre esta respuesta. Sin embargo, un buen GC aún debería amortizar los costos (dada la memoria suficiente, como siempre), como explico al final.
Con un sistema GC, cuando su buen código O (N) resulta en basura para el GC de una manera patológica que lo convierte en O (tamaño de pila), puede ser más difícil resolver lo que está pasando mal.
En primer lugar, esto sucede a menudo cuando el tamaño del conjunto de trabajo está cerca del tamaño máximo de almacenamiento dinámico. El GC se invoca con demasiada frecuencia y, por lo tanto, todo se ralentiza. Instala el plugin Scala para Eclipse y lo sentirás.
Por lo general, sin embargo, tener suficiente espacio de memoria y un GC generacional lo previenen, si su algoritmo solo produce una gran cantidad de basura rápidamente detectable como tal: no sobrevivirá el tiempo suficiente para salir del vivero.
Aquí hay un ejemplo para una excepción a eso: tomemos "map f list", y supongamos que cada aplicación de f consume memoria activa, guardando una referencia al valor devuelto en una tabla hash. La complejidad asintótica, aquí, todavía debe ser O (1).
El GC generacional no podrá liberar memoria al recolectar el vivero, por lo tanto, se invoca periódicamente una colección mayor (O (contenido del montón)). Por lo tanto, obtenemos que el tiempo de ejecución es al menos proporcional a (tamaño de contenido de almacenamiento) * n * (espacio consumido por cada llamada a f) / (tamaño de vivero).
El GC en realidad aumentará el tamaño del vivero hasta el máximo especificado, y luego lo anterior ocurre de nuevo por lo suficientemente grande. Sin embargo, si el máximo especificado es Big-Theta (tamaño de heap máximo) y, por lo tanto, Omega (tamaño de contenido de heap), las colecciones principales se vuelven infrecuentes y el costo de las colecciones menores es proporcional a los datos producidos (y por lo tanto al tiempo de ejecución necesario para producir ellos). Esto es similar a cuando necesita copiar un contenedor para cambiar su tamaño: si crece lo suficiente, puede amortizar el costo de copiado (o de GC) y hacerlo comparable al costo necesario para generar la copia.
Toda esta respuesta no tiene en cuenta la cuestión de los tiempos de pausa: las colecciones se vuelven infrecuentes pero son largas. Supone implícitamente que el tiempo de escaneo de la pila es constante, pero debería serlo, a menos que el algoritmo no sea recursivo de cola y, por lo tanto, tenga problemas de todas formas con las entradas grandes consideradas aquí.
Finalmente, no se trata de recolectores de basura incrementales. Resuelven el problema desde la raíz, pero se usan principalmente para GC en tiempo real, debido a la sobrecarga que agregan a las lecturas de memoria. Azul System resolvió esto en su propia HW personalizada con su Pauseless GC, gracias al soporte de HW para optimizar esta sobrecarga. También afirmaron recientemente haber resuelto el problema también para x86, consulte este "comunicado de prensa" y este artículo . Pero definitivamente está en desarrollo y no se ejecuta sin cambios en el sistema operativo. Cuando se haya hecho eso, y si el rendimiento es como sugieren, tal vez el problema se resuelva también para nosotros los mortales normales.
El artículo de Berger está siendo citado mucho, pero está comparando los recolectores de basura reales con un algoritmo puramente teórico, fuera de línea, óptimo. Entonces, si bien puede decirle algo acerca de los límites teóricos, dice muy poco sobre el rendimiento de los recolectores de basura reales frente a las implementaciones reales de malloc y free . Un estudio que me gusta mejor tomó programas reales y comparó malloc explícito y free con el recolector de basura conservador de Hans Boehm:
El costo medido de la recolección de basura conservadora por Ben Zorn
Este estudio no es perfecto, y Zorn tiene cuidado de señalar que si los programas sabían que estaban utilizando un recolector de basura, algunos podrían hacerse más rápido. Pero los datos duros son los siguientes: - En los programas reales escritos originalmente para usar malloc y versiones free , recolectadas en la basura, se ejecutan a aproximadamente la misma velocidad pero requieren el doble de memoria. Zorn argumenta bastante convincentemente que si sabes que tienes GC, puedes hacer las cosas más rápido, pero es difícil eliminar la penalización de la memoria.
Aprendí más de este cuidadoso estudio experimental que del estudio de Berger sobre un administrador de memoria ideal e intransferible.
El costo de la asignación de memoria es generalmente mucho más bajo en un modelo de memoria recolectada de basura, luego cuando se usa nuevo o malloc explícitamente porque los recolectores de basura generalmente preasignan esta memoria. Sin embargo, los modelos de memoria explícitos también pueden hacer esto (usando grupos de memoria o áreas de memoria); haciendo que el costo de la asignación de memoria sea equivalente a una adición de puntero.
Como Raymond Chen y Rico Mariani señalaron, los lenguajes administrados tienden a llevar a cabo los idiomas no administrados en el caso general. Sin embargo, después de presionarlo, el lenguaje no administrado puede y eventualmente superará al lenguaje GC / Jitted.
Lo mismo también es evidente en Computer Language Shootout porque aunque C ++ tiende a clasificarse más alto que Java la mayoría de las veces, a menudo verá implementaciones de C ++ que saltan a través de varios aros (como grupos de objetos) para lograr un rendimiento óptimo. Sin embargo, los lenguajes recogidos de basura tienden a tener implementaciones más simples y fáciles de seguir porque el GC es mejor para asignar (fragmentos pequeños) de memoria.
Sin embargo, el rendimiento no es la mayor diferencia cuando se trata de GC versus no GC; podría decirse que es la finalización determinística (o RIIA) de lenguajes no GC (y contados de referencia) el argumento más importante para la administración de memoria explícita porque generalmente se usa para fines distintos a la administración de memoria (como liberar bloqueos, cerrar archivos o manejadores de ventanas). etcétera). ''Recientemente'', sin embargo, C # introdujo el constructo using / IDisposable para hacer exactamente esto.
Otro problema con la recolección de basura es que los sistemas que utilizan tienden a ser bastante complejos para evitar fugas de memoria. Sin embargo, esto también hace que sea mucho más difícil depurar y rastrear una vez que tiene una pérdida de memoria (sí, incluso los lenguajes recolectados pueden tener fugas de memoria).
Por otro lado, el lenguaje recogido de basura puede hacer lo más óptimo en el momento más óptimo (o aproximadamente) sin tener que cargar al desarrollador con esa tarea. Esto significa que desarrollar un lenguaje de GC puede ser más natural, para que pueda enfocarse más en el problema real .
En teoría, GC puede ser más rápido en algunos casos, pero nunca he visto eso, y dudo que lo haga. Además, C ++ con GC como el Boehm GC probablemente siempre será más lento porque es conservador. Con todo el puntero toqueteando en C ++, el GC tiene que pretender que todo es un puntero. Con un lenguaje como Java, puede saber exactamente qué es y qué no es un puntero, por lo que puede tener el potencial de ser más rápido.
En teoría, un programa bien perfilado puede informar a un subsistema GC inteligente para alcanzar las aceleraciones descritas sobre la administración de memoria manual. Estas aceleraciones pueden no ser visibles sin largos tiempos de ejecución, para amortizar el costo de inicio fijo de GC.
En la práctica, probablemente NO se den cuenta de estas aceleraciones con las implementaciones actuales de GC. Además, NO obtendrá una respuesta definitiva, porque siempre habrá escenarios patológicamente malos para ambos casos.
Es el hecho de que los desarrolladores son humanos y se pierden cosas que causaron la necesidad de recolectores de basura en primer lugar. Dicho esto, permítanme decir que la recolección de basura siempre será más lenta que la administración de memoria explícita y perfecta . Y la recolección de basura a menudo puede ser más rápida que la administración imperfecta de memoria explícita dado el hecho de que los recolectores de basura limpian las cosas que los desarrolladores tienden a olvidar.
Esto se convierte en otra guerra de llamas con mucho "mi instinto". Algunos datos duros para variar (los documentos contienen detalles, puntos de referencia, gráficos, etc.):
http://www.cs.umass.edu/~emery/pubs/04-17.pdf dice:
"Conclusión. La controversia sobre el impacto en el rendimiento de la recolección de basura ha eclipsado por mucho tiempo los beneficios de ingeniería de software que proporciona. Este documento presenta un administrador de memoria oracular basado en simulación y seguimiento. Utilizando este marco, ejecutamos una variedad de puntos de referencia de Java sin alterar usando recolección de basura y Gestión de memoria explícita Comparando tiempo de ejecución, consumo de espacio y huellas de memoria virtual, encontramos que cuando el espacio es abundante, el rendimiento del tiempo de ejecución de la recolección de basura puede ser competitivo con la gestión de memoria explícita, e incluso puede superarlo hasta en un 4%. esa copia de recolección de basura puede requerir seis veces la memoria física que las asignaciones de Lea o Kingsley para proporcionar un rendimiento comparable ".
Cuando tienes suficiente memoria, copiar GC es más rápido que explícito free() - http://www.cs.ucsb.edu/~grze/papers/gc/appel87garbage.pdf
También depende del idioma que usas: Java tendrá que reescribir mucho (pila, objetos, generaciones) en cada colección y escribir un CG multiproceso que no tenga que detener al mundo en JVM sería un gran logro. Por otro lado, obtienes eso casi gratis en Haskell, donde el tiempo de GC rara vez será> 5%, mientras que el tiempo de alloc es casi 0. Realmente depende de lo que estés haciendo y en qué entorno.
GC siempre será más lento que la alternativa extrema: gestión de memoria perfecta y no determinista.
Las preguntas son:
- ¿Las diferencias son lo suficientemente grandes como para discutir?
- ¿Los inconvenientes de una técnica son suficientes para que consideremos seriamente la otra?
Hay otras áreas en las que los subsistemas gestionados se han ganado a través de los no administrados:
En general, un programa siempre se ejecutará más despacio en un sistema operativo multitarea que en uno unitario, o en una computadora sin sistema operativo.
En general, un programa siempre se ejecutará más despacio en un sistema con memoria virtual que en uno sin él.
Excepto en circunstancias extremas, ¿consideramos seriamente los sistemas informáticos sin VM y sin un sistema operativo?
La diferencia fundamental entre gc y cualquier implementación de malloc es que gc realiza un seguimiento de los objetos asignados , mientras que malloc básicamente realiza un seguimiento de los objetos asignados (a través de "listas libres", etc., que necesitaban recolectar bloques de memoria liberados para devolverlos rápidamente después malloc''s): algunas implementaciones malloc incluso no tienen posibilidad (en sus partes internas) de enumerar todos los bloques asignados por diseño. Como consecuencia, cualquier posible implementación de gc (no importa cuán bien pueda ser), siempre tendrá complejidad O (somefunc (N)), donde N es un conteo de objetos asignados, mientras que la mayoría de las implementaciones de malloc tienen complejidad O (1). Por lo tanto, cuando el número de objetos asignados (a la vez) aumenta cada vez más, la degradación del rendimiento de cualquier gc es inevitable (pero, por supuesto, el rendimiento puede cambiarse por consumo de memoria adicional). [Después de todo, es obvio que los bloques de memoria libres siempre tienen una sobrecarga de mantenimiento nula en contraste con los bloques / objetos asignados.] Esta es una falla fundamental de cualquier gc, ya que recoge la basura :), mientras que malloc mantiene nongarbage (:.
PD Por malloc me refiero no solo a la llamada función C específica, sino a cualquier rutina explícita de asignación de memoria. Además, me gustaría señalar que los lenguajes de programación sin gc incorporados ofrecen muchas formas de envolver las llamadas explícitas malloc / free (new / delete) (por ejemplo, std :: shared_ptr en C ++ o ARC en Obj-C) Esto hace que el código del programa sea similar al de los lenguajes basados en gc, pero desde el punto de vista del rendimiento es mucho más cercano (casi equivalente) a la asignación de memoria explícita. (Sé que incluso el simple recuento de referencias puede considerarse como una forma de recolección de basura, pero en este post de gc me refiero a una implementación más rica en funciones (al menos con detección automática de ciclos de referencia), que requiere un seguimiento de todos objetos asignados, por lo que no considero wrappers como std :: shared_ptr como gc (al menos en esta publicación)).
Un problema pragmático es que con MM explícito generalmente es mucho más fácil hacer un perfil, identificar el cuello de botella y resolverlo.
Con un sistema GC, cuando su buen código O (N) resulta en basura para el GC de una manera patológica que lo convierte en O (tamaño de pila), puede ser más difícil resolver lo que está pasando mal. Algunas veces incluso tan difícil como arreglar una corrupción de memoria.
Ver también
http://prog21.dadgum.com/40.html
which discusses the "sufficiently smart" compiler. The landscape of CS/software is riddled with ideas/techiques which can be in theory more performant than the status-quo. But it''s all snake oil.
GC is expensive today, and may always be.
Side note: another interesting experiment to run, that I haven''t seen people try, is to compare with just leaking. Call alloc and never free. It''s an interesting alternative.
Except for long-running server apps, you''ll never run out of memory in practice, the OS will just start using disk for virtual memory (machines have effectively infinite memory, up to the limits of virtual address space, which I think is huge now with 64-bit machines). This highlights that a GC is nothing more than a device for improving locality. Leaked/dead objects don''t "hurt" when you have infinite memory, except that memory comes in hierarchies and you want to keep the ''live'' objects nearby and fast and the ''dead'' objects on the faraway/slow memory. If each object was allocated on a different page, then the OS virtual memory system would effective be a GC.