Asignación de almacenamiento dinámico de Java más rápido que C ++

Ya publiqué esta pregunta en SO y funcionó bien. Sin embargo, desafortunadamente se cerró (solo necesita un voto para volver a abrir), pero alguien sugirió que lo publique aquí, ya que es mejor, así que lo siguiente es literalmente una copia de la pregunta.

Estaba leyendo los comentarios sobre esta respuesta y vi esta cita.

La creación de instancias de objetos y las funciones orientadas a objetos son extremadamente rápidas de usar (más rápido que C ++ en muchos casos) porque están diseñadas desde el principio. y las colecciones son rápidas. Java estándar supera a C / C ++ estándar en esta área, incluso para el código C más optimizado.

Un usuario (con un representante realmente alto, podría agregar) defendió audazmente esta afirmación, afirmando que

1. la asignación del montón en Java es mejor que la de C ++

2. y agregó esta declaración defendiendo las colecciones en java

   Y las colecciones de Java son rápidas en comparación con las colecciones de C ++ debido en gran medida a los diferentes subsistemas de memoria.

Entonces, mi pregunta es si algo de esto puede ser realmente cierto, y si es así, ¿por qué la asignación del montón de Java es mucho más rápida?

Esta es una pregunta interesante, y la respuesta es compleja.

En general, creo que es justo decir que el recolector de basura JVM está muy bien diseñado y es extremadamente eficiente. Es probablemente el mejor sistema de administración de memoria de uso general .

C ++ puede vencer a JVM GC con asignadores de memoria especializados que están diseñados para fines específicos. Los ejemplos pueden ser:

• Asignadores de memoria por cuadro, que borran toda el área de memoria a intervalos periódicos. Estos se usan con frecuencia en juegos de C ++, por ejemplo, donde se usa un área de memoria temporal una vez por fotograma y se descarta inmediatamente.
• Asignadores personalizados que gestionan un grupo de objetos de tamaño fijo
• Asignación basada en pila (aunque tenga en cuenta que la JVM también lo hace en varias circunstancias, por ejemplo, mediante análisis de escape )

Los asignadores de memoria especializados están, por supuesto, limitados por definición. Por lo general, tienen restricciones en el ciclo de vida de los objetos y / o restricciones en el tipo de objeto que se puede administrar. La recolección de basura es mucho más flexible.

La recolección de basura también le brinda algunas ventajas significativas desde una perspectiva de rendimiento:

• La instanciación de objetos es de hecho extremadamente rápida. Debido a la forma en que los nuevos objetos se asignan secuencialmente en la memoria, a menudo requiere poco más que una adición de puntero, lo que sin duda es más rápido que los algoritmos de asignación de montón de C ++ típicos.
• Usted evita la necesidad de que los costes de gestión del ciclo de vida - por ejemplo, el recuento de referencias (a veces utilizado como una alternativa a GC) es extremadamente pobre desde una perspectiva de rendimiento ya que la incrementación frecuente y decremento de los recuentos de referencia añade una gran cantidad de sobrecarga de rendimiento (normalmente mucho más de GC) .
• Si usa objetos inmutables, puede aprovechar el uso compartido estructural para ahorrar memoria y mejorar la eficiencia de la memoria caché. Esto es muy utilizado por lenguajes funcionales en la JVM como Scala y Clojure. Es muy difícil hacer esto sin GC, porque es extremadamente difícil administrar la vida útil de los objetos compartidos. Si cree (como yo) que la inmutabilidad y el intercambio estructural son clave para construir grandes aplicaciones concurrentes, entonces esta es posiblemente la mayor ventaja de rendimiento de GC.
• Puede evitar copiar si todos los tipos de objeto y sus respectivos ciclos de vida son administrados por el mismo sistema de recolección de basura. Contraste con C ++, donde a menudo tiene que tomar copias completas de los datos porque el destino requiere un enfoque de administración de memoria diferente o tiene un ciclo de vida de objeto diferente.

Java GC tiene una desventaja importante: debido a que el trabajo de recolección de basura se difiere y se realiza en trozos de trabajo a intervalos periódicos, ocasiona pausas ocasionales de GC para recolectar basura, lo que puede afectar la latencia. Por lo general, esto no es un problema para las aplicaciones típicas, pero puede descartar Java en situaciones donde el tiempo real es un requisito (por ejemplo, control robótico). El tiempo real suave (por ejemplo, juegos, multimedia) generalmente está bien.

Esta no es una afirmación científica. Simplemente estoy reflexionando sobre este tema.

Una analogía visual es esta: le dan un apartamento (una unidad residencial) que está alfombrado. La alfombra está sucia. ¿Cuál es la forma más rápida (en términos de horas) para hacer que el piso del apartamento esté impecablemente limpio?

Respuesta: simplemente enrolle la alfombra vieja; tirar a la basura; y desplegar una alfombra nueva.

¿Qué estamos descuidando aquí?

• El costo de mudar las pertenencias personales existentes y luego mudarse.
  • Esto se conoce como el costo de "detener el mundo" de la recolección de basura.
• El costo de la alfombra nueva.
  • Que, casualmente para RAM, es gratis.

La recolección de basura es un tema enorme y hay muchas preguntas tanto en Programmers.SE como en StackOverflow.

En un tema secundario, un administrador de asignación C / C ++ conocido como TCMalloc junto con el recuento de referencias de objetos es teóricamente capaz de cumplir con las mejores afirmaciones de rendimiento de cualquier sistema GC.

La razón principal es que, cuando le pide a Java un nuevo conjunto de memoria, va directo al final del montón y le da un bloque. De esta manera, la asignación de memoria es tan rápida como la asignación en la pila (que es la forma en que lo hace la mayor parte del tiempo en C / C ++, pero aparte de eso ...)

Entonces las asignaciones son rápidas como cualquier cosa, pero ... eso no cuenta el costo de liberar la memoria. El hecho de que no libere nada hasta mucho más tarde no significa que no cueste mucho, y en el caso del sistema GC, el costo es mucho más que las asignaciones de montón 'normales', no solo GC tiene que recorrer todos los objetos para ver si están vivos o no, también debe liberarlos y (el gran costo) copiar la memoria para compactar el montón, para que pueda tener la asignación rápida al final mecanismo (o se quedaría sin memoria, C / C ++, por ejemplo, recorrerá el montón en cada asignación buscando el siguiente bloque de espacio libre que pueda ajustarse al objeto).

Esta es una razón por la cual los puntos de referencia de Java / .NET muestran un rendimiento tan bueno, pero las aplicaciones del mundo real muestran un rendimiento tan malo. Sólo hay que mirar las aplicaciones en mi teléfono - el muy rápido, los que responden son todas escritas utilizando el NDK, tanto por lo que incluso me sorprendió.

Las colecciones hoy en día pueden ser rápidas si todos los objetos se asignan localmente, por ejemplo, en un solo bloque contiguo. Ahora, en Java, simplemente no obtienes bloques contiguos ya que los objetos se asignan uno a la vez desde el extremo libre del montón. Puede terminar con ellos felizmente contiguos, pero solo por suerte (es decir, hasta el capricho de las rutinas de compactación del GC y cómo copia objetos). C / C ++, por otro lado, admite explícitamente asignaciones contiguas (a través de la pila, obviamente). En general, los objetos de almacenamiento dinámico en C / C ++ no son diferentes de los BTW de Java.

Ahora con C / C ++ puede ser mejor que los asignadores predeterminados que fueron diseñados para ahorrar memoria y usarla de manera eficiente. Puede reemplazar el asignador con un conjunto de grupos de bloques fijos, por lo que siempre puede encontrar un bloque que tenga exactamente el tamaño correcto para el objeto que está asignando. Recorrer el montón simplemente se convierte en una búsqueda de mapa de bits para ver dónde está un bloque libre, y la desasignación es simplemente restablecer un bit en ese mapa de bits. El costo es que usa más memoria a medida que asigna bloques de tamaño fijo, por lo que tiene un montón de bloques de 4 bytes, otro para bloques de 16 bytes, etc.

Eden Space

Entonces, mi pregunta es si algo de esto puede ser realmente cierto, y si es así, ¿por qué la asignación del montón de Java es mucho más rápida?

He estado estudiando un poco sobre cómo funciona el GC de Java, ya que es muy interesante para mí. Siempre estoy tratando de expandir mi colección de estrategias de asignación de memoria en C y C ++ (interesado en tratar de implementar algo similar en C), y es una forma muy, muy rápida de asignar muchos objetos de forma explosiva desde un perspectiva práctica pero principalmente debido a la multiproceso.

La forma en que funciona la asignación de Java GC es utilizar una estrategia de asignación extremadamente barata para asignar inicialmente objetos al espacio "Eden". Por lo que puedo decir, está usando un asignador secuencial de grupos.

Eso es mucho más rápido solo en términos de algoritmo y reducción de fallas de página obligatorias que las de uso general mallocen C o por defecto, agregando operator newC ++.

Pero los asignadores secuenciales tienen una debilidad evidente: pueden asignar fragmentos de tamaño variable, pero no pueden liberar ningún fragmento individual. Simplemente asignan de forma secuencial directa con relleno para alineación, y solo pueden purgar toda la memoria que asignaron a la vez. Por lo general, son útiles en C y C ++ para construir estructuras de datos que solo necesitan inserciones y no eliminaciones de elementos, como un árbol de búsqueda que solo necesita construirse una vez cuando se inicia un programa y luego se busca repetidamente o solo se agregan nuevas claves ( sin llaves quitadas).

También se pueden usar incluso para estructuras de datos que permiten que se eliminen elementos, pero esos elementos en realidad no se liberarán de la memoria ya que no podemos desasignarlos individualmente. Dicha estructura que usa un asignador secuencial solo consumiría más y más memoria, a menos que tuviera un pase diferido donde los datos se copiaron en una copia nueva y compacta usando un asignador secuencial separado (y eso a veces es una técnica muy efectiva si un asignador fijo ganara hágalo por alguna razón: simplemente asigne secuencialmente una nueva copia de la estructura de datos y descargue toda la memoria de la anterior).

Colección

Al igual que en el ejemplo de estructura de datos / grupo secuencial anterior, sería un gran problema si Java GC solo se asigna de esta manera, aunque es súper rápido para una asignación de ráfaga de muchos fragmentos individuales. No podría liberar nada hasta que se cierre el software, momento en el que podría liberar (purgar) todos los grupos de memoria de una sola vez.

Entonces, en cambio, después de un solo ciclo de GC, se hace un pase a través de los objetos existentes en el espacio "Eden" (asignado secuencialmente), y los que todavía están referenciados luego se asignan usando un asignador de propósito más general capaz de liberar fragmentos individuales. Los que ya no están referenciados simplemente serán desasignados en el proceso de purga. Básicamente, es "copiar objetos del espacio del Edén si todavía están referenciados y luego purgarlos".

Esto normalmente sería bastante costoso, por lo que se realiza en un subproceso de fondo separado para evitar detener significativamente el subproceso que originalmente asignó toda la memoria.

Una vez que la memoria se copia del espacio de Eden y se asigna utilizando este esquema más costoso que puede liberar fragmentos individuales después de un ciclo de GC inicial, los objetos se mueven a una región de memoria más persistente. Esos trozos individuales se liberan en los siguientes ciclos de GC si dejan de ser referenciados.

Velocidad

Entonces, en términos generales, la razón por la que el GC de Java podría superar a C o C ++ en la asignación directa de almacenamiento dinámico es porque está utilizando la estrategia de asignación más barata y totalmente degeneralizada en el subproceso que solicita asignar memoria. Luego ahorra el trabajo más costoso que normalmente tendríamos que hacer cuando usamos un asignador más general como el directomalloc para otro hilo.

Conceptualmente, el GC en realidad tiene que hacer más trabajo en general, pero lo distribuye a través de subprocesos para que el costo total no se pague por adelantado por un solo subproceso. Permite que el hilo que asigna memoria lo haga súper barato, y luego difiere el gasto real requerido para hacer las cosas correctamente para que los objetos individuales puedan liberarse a otro hilo. En C o C ++ cuando llamamos malloco operator newtenemos que pagar el costo total por adelantado dentro del mismo hilo.

Esta es la principal diferencia, y por qué Java podría superar a C o C ++ usando llamadas ingenuas malloco operator newasignar un montón de fragmentos pequeños individualmente. Por supuesto, típicamente habrá algunas operaciones atómicas y algunos bloqueos potenciales cuando se inicie el ciclo GC, pero probablemente esté optimizado bastante.

Básicamente, la explicación simple se reduce a pagar un costo más alto en un solo hilo ( malloc) versus pagar un costo más barato en un solo hilo y luego pagar el costo más alto en otro que puede ejecutarse en paralelo ( GC). Como inconveniente, hacer las cosas de esta manera implica que se requieren dos direcciones indirectas para ir de la referencia del objeto al objeto, según sea necesario, para permitir que el asignador copie / mueva la memoria sin invalidar las referencias existentes del objeto, y también puede perder la ubicación espacial una vez que la memoria del objeto es se mudó del espacio "Edén".

Por último, pero no menos importante, la comparación es un poco injusta porque el código C ++ normalmente no asigna una gran cantidad de objetos individualmente en el montón. El código C ++ decente tiende a asignar memoria para muchos elementos en bloques contiguos o en la pila. Si asigna un bote lleno de pequeños objetos uno a la vez en la tienda gratuita, el código es simple.

Todo depende de quién mide la velocidad, qué velocidad de implementación miden y qué quieren probar. Y lo que comparan.

Si solo observa la asignación / desasignación, en C ++ puede tener 1,000,000 de llamadas a malloc y 1,000,000 de llamadas a free (). En Java, tendría 1,000,000 de llamadas a new () y un recolector de basura ejecutándose en un bucle que encuentra 1,000,000 de objetos que puede liberar. El bucle puede ser más rápido que la llamada free ().

Por otro lado, malloc / free ha mejorado en otro momento, y típicamente malloc / free solo establece un bit en una estructura de datos separada, y está optimizado para que malloc / free ocurra en el mismo hilo, por lo que en un entorno multiproceso no hay variables de memoria compartida se usan en muchos casos (y las variables de bloqueo o memoria compartida son muy caras).

Por otro lado, hay cosas como el conteo de referencias que puede necesitar sin la recolección de basura, y eso no es gratis.