Allocation de tas Java plus rapide que C ++

J'ai déjà posté cette question sur SO et ça s'est bien passé. Il a malheureusement été fermé (il n'a besoin que d'un vote pour rouvrir), mais quelqu'un a suggéré de le poster ici car il convient mieux, ce qui suit est littéralement une copie de la question

Je lisais les commentaires sur cette réponse et j'ai vu cette citation.

L'instanciation d'objets et les fonctionnalités orientées objet sont extrêmement rapides à utiliser (plus rapides que C ++ dans de nombreux cas) car elles sont conçues dès le début. et les collections sont rapides. Le Java standard bat le C / C ++ standard dans ce domaine, même pour le code C le plus optimisé.

Un utilisateur (avec un représentant très élevé, pourrais-je ajouter) a hardiment défendu cette affirmation, déclarant

1. l'allocation de tas en java est meilleure que celle de C ++

2. et ajouté cette déclaration défendant les collections en java

   Et les collections Java sont rapides par rapport aux collections C ++, en grande partie à cause du sous-système de mémoire différent.

Ma question est donc de savoir si tout cela peut être vrai, et si oui, pourquoi l'allocation de tas de Java est-elle beaucoup plus rapide?

C'est une question intéressante, et la réponse est complexe.

Dans l'ensemble, je pense qu'il est juste de dire que le garbage collector JVM est très bien conçu et extrêmement efficace. C'est probablement le meilleur système de gestion de mémoire à usage général .

C ++ peut battre le JVM GC avec des allocateurs de mémoire spécialisés qui sont conçus à des fins spécifiques. Des exemples pourraient être:

• Allocateurs de mémoire par trame, qui effacent toute la zone de mémoire à intervalles périodiques. Celles-ci sont fréquemment utilisées dans les jeux C ++, par exemple, où une zone de mémoire temporaire est utilisée une fois par trame et immédiatement supprimée.
• Allocateurs personnalisés gérant un pool d'objets de taille fixe
• Allocation basée sur la pile (bien que la JVM le fasse également dans diverses circonstances, par exemple via une analyse d'échappement )

Les allocateurs de mémoire spécialisés sont, bien entendu, limités par définition. Ils ont généralement des restrictions sur le cycle de vie des objets et / ou des restrictions sur le type d'objet qui peut être géré. La collecte des ordures est beaucoup plus flexible.

La récupération de place vous offre également quelques avantages importants du point de vue des performances:

• L' instanciation d' objets est en effet extrêmement rapide. En raison de la façon dont les nouveaux objets sont alloués séquentiellement en mémoire, cela nécessite souvent un peu plus d'un ajout de pointeur, ce qui est certainement plus rapide que les algorithmes d'allocation de tas C ++ typiques.
• Vous évitez les coûts de gestion du cycle de vie - par exemple, le comptage de références (parfois utilisé comme alternative au GC) est extrêmement médiocre du point de vue des performances, car l'incrémentation et la décrémentation fréquentes des comptages de référence ajoutent beaucoup de frais généraux de performance (généralement beaucoup plus que le GC) .
• Si vous utilisez des objets immuables, vous pouvez profiter du partage structurel pour économiser de la mémoire et améliorer l'efficacité du cache. Ceci est largement utilisé par les langages fonctionnels sur la JVM comme Scala et Clojure. Il est très difficile de le faire sans GC, car il est extrêmement difficile de gérer la durée de vie des objets partagés. Si vous croyez (comme moi) que l'immuabilité et le partage structurel sont essentiels pour créer de grandes applications simultanées, alors c'est sans doute le plus grand avantage de performances du GC.
• Vous pouvez éviter la copie si tous les types d'objets et leurs cycles de vie respectifs sont gérés par le même système de récupération de place. Contrairement à C ++, où vous devez souvent prendre des copies complètes des données car la destination nécessite une approche de gestion de la mémoire différente ou a un cycle de vie d'objet différent.

Java GC présente un inconvénient majeur: comme le travail de collecte des ordures est différé et effectué par intervalles de travail à intervalles périodiques, il provoque des pauses occasionnelles du GC pour collecter les ordures, ce qui peut affecter la latence. Ce n'est généralement pas un problème pour les applications typiques, mais peut exclure Java dans des situations où le temps réel dur est une exigence (par exemple, un contrôle robotique). Le temps réel doux (par exemple, jeux, multimédia) est généralement OK.

Ce n'est pas une affirmation scientifique. Je donne simplement matière à réflexion sur cette question.

Une analogie visuelle est la suivante: on vous donne un appartement (un logement) qui est recouvert de moquette. Le tapis est sale. Quel est le moyen le plus rapide (en termes d'heures) de rendre le sol de l'appartement étincelant de propreté?

Réponse: enroulez simplement le vieux tapis; désinvolte; et déroule un nouveau tapis.

Que négligeons-nous ici?

• Le coût du déménagement des effets personnels existants, puis de leur emménagement.
  • C'est ce qu'on appelle le coût «stop-the-world» de la collecte des ordures.
• Le coût du nouveau tapis.
  • Ce qui, par coïncidence pour la RAM, est gratuit.

La récupération de place est un sujet énorme et il y a beaucoup de questions dans Programmers.SE et StackOverflow.

Sur un problème secondaire, un gestionnaire d'allocation C / C ++ connu sous le nom de TCMalloc avec le comptage de référence d'objet est théoriquement capable de répondre aux meilleures revendications de performances de tout système GC.

La raison principale est que, lorsque vous demandez à Java un nouveau bloc de mémoire, il va directement à la fin du tas et vous donne un bloc. De cette façon, l'allocation de mémoire est aussi rapide que l'allocation sur la pile (c'est ainsi que vous le faites la plupart du temps en C / C ++, mais à part cela ..)

Les allocations sont donc rapides, mais ... cela ne compte pas le coût de la libération de la mémoire. Ce n'est pas parce que vous ne libérez rien avant bien plus tard que cela ne coûte pas cher, et dans le cas du système GC, le coût est beaucoup plus élevé que les allocations de tas «normales» - non seulement le Le GC doit parcourir tous les objets pour voir s'ils sont vivants ou non, il doit également les libérer et (le gros coût) copier la mémoire pour compacter le tas - afin que vous puissiez avoir l'allocation rapide à la fin (ou vous manqueriez de mémoire, C / C ++ par exemple parcourra le tas sur chaque allocation à la recherche du prochain bloc d'espace libre qui peut contenir l'objet).

C'est l'une des raisons pour lesquelles les benchmarks Java / .NET affichent de si bonnes performances, alors que les applications du monde réel affichent de si mauvaises performances. Je n'ai qu'à regarder les applications sur mon téléphone - celles qui sont vraiment rapides et réactives sont toutes écrites en utilisant le NDK, tellement même que j'ai été surpris.

De nos jours, les collections peuvent être rapides si tous les objets sont alloués localement, par exemple dans un seul bloc contigu. Maintenant, en Java, vous n'obtenez tout simplement pas de blocs contigus car les objets sont alloués un par un à partir de l'extrémité libre du tas. Vous pouvez vous retrouver avec eux joyeusement contigus, mais seulement par chance (c'est-à-dire jusqu'au caprice des routines de compactage GC et comment il copie les objets). C / C ++, d'autre part, prend explicitement en charge les allocations contiguës (via la pile, évidemment). Généralement, les objets tas en C / C ++ ne sont pas différents du BTW de Java.

Maintenant, avec C / C ++, vous pouvez faire mieux que les allocateurs par défaut qui ont été conçus pour économiser de la mémoire et l'utiliser efficacement. Vous pouvez remplacer l'allocateur par un ensemble de pools de blocs fixes, afin de toujours trouver un bloc qui a exactement la bonne taille pour l'objet que vous allouez. Marcher dans le tas devient juste une question de recherche de bitmap pour voir où se trouve un bloc libre, et la désallocation redéfinit simplement un bit dans ce bitmap. Le coût est que vous utilisez plus de mémoire que vous allouez dans des blocs de taille fixe, vous avez donc un tas de blocs de 4 octets, un autre pour des blocs de 16 octets, etc.

Eden Space

Ma question est donc de savoir si tout cela peut être vrai, et si oui, pourquoi l'allocation de tas de Java est-elle beaucoup plus rapide?

J'étudie un peu le fonctionnement du Java GC car c'est très intéressant pour moi. J'essaie toujours d'élargir ma collection de stratégies d'allocation de mémoire en C et C ++ (intéressé à essayer d'implémenter quelque chose de similaire en C), et c'est un moyen très, très rapide d'allouer beaucoup d'objets de manière éclatée à partir d'un perspective pratique mais principalement due au multithreading.

La façon dont fonctionne l'allocation Java GC consiste à utiliser une stratégie d'allocation extrêmement bon marché pour allouer initialement des objets à l'espace "Eden". D'après ce que je peux dire, il utilise un allocateur de pool séquentiel.

C'est beaucoup plus rapide juste en termes d'algorithme et de réduction des défauts de page obligatoires que pour un usage général mallocen C ou par défaut, en jetant operator newen C ++.

Mais les allocateurs séquentiels ont une faiblesse flagrante: ils peuvent allouer des morceaux de taille variable, mais ils ne peuvent pas libérer de morceaux individuels. Ils allouent simplement de façon séquentielle droite avec un remplissage pour l'alignement et ne peuvent purger que toute la mémoire qu'ils ont allouée en même temps. Ils sont généralement utiles en C et C ++ pour construire des structures de données qui ne nécessitent que des insertions et pas de suppression d'éléments, comme un arbre de recherche qui ne doit être construit qu'une seule fois lorsqu'un programme démarre puis est recherché à plusieurs reprises ou seulement de nouvelles clés ont été ajoutées ( aucune clé retirée).

Ils peuvent également être utilisés même pour les structures de données qui permettent de supprimer des éléments, mais ces éléments ne seront pas réellement libérés de la mémoire car nous ne pouvons pas les désallouer individuellement. Une telle structure utilisant un allocateur séquentiel consommerait simplement de plus en plus de mémoire, sauf si elle avait une passe différée où les données étaient copiées sur une nouvelle copie compactée à l'aide d'un allocateur séquentiel séparé (et c'est parfois une technique très efficace si un allocateur fixe gagnait pas pour une raison quelconque - allouez simplement séquentiellement une nouvelle copie de la structure de données et videz toute la mémoire de l'ancienne).

Collection

Comme dans l'exemple de structure de données / pool séquentiel ci-dessus, ce serait un énorme problème si Java GC n'allouait que de cette façon, même s'il est super rapide pour une allocation en rafale de nombreux morceaux individuels. Il ne serait pas en mesure de libérer quoi que ce soit jusqu'à ce que le logiciel soit arrêté, auquel cas il pourrait libérer (purger) tous les pools de mémoire en une seule fois.

Ainsi, au lieu de cela, après un seul cycle GC, un passage est effectué à travers des objets existants dans l'espace "Eden" (alloués séquentiellement), et ceux qui sont encore référencés sont ensuite alloués à l'aide d'un allocateur plus général capable de libérer des morceaux individuels. Ceux qui ne sont plus référencés seront simplement désalloués lors du processus de purge. Donc, fondamentalement, c'est "copier des objets hors de l'espace Eden s'ils sont encore référencés, puis purger".

Cela serait normalement assez cher, donc c'est fait dans un thread d'arrière-plan séparé pour éviter de bloquer de manière significative le thread qui a initialement alloué toute la mémoire.

Une fois la mémoire copiée hors de l'espace Eden et allouée à l'aide de ce schéma plus coûteux qui peut libérer des morceaux individuels après un cycle GC initial, les objets se déplacent vers une région de mémoire plus persistante. Ces morceaux individuels sont ensuite libérés dans les cycles GC suivants s'ils cessent d'être référencés.

La vitesse

Donc, en termes simples, la raison pour laquelle le GC Java pourrait très bien surpasser C ou C ++ lors de l'allocation de tas droite est parce qu'il utilise la stratégie d'allocation totalement dégénéralisée la moins chère dans le thread demandant l'allocation de mémoire. Ensuite, il enregistre le travail plus coûteux que nous aurions normalement besoin de faire lors de l'utilisation d'un allocateur plus général comme directement mallocpour un autre thread.

Donc, conceptuellement, le GC doit en fait faire plus de travail dans l'ensemble, mais il le répartit sur tous les threads afin que le coût total ne soit pas payé d'avance par un seul thread. Il permet au thread allouant de la mémoire de le faire très bon marché, puis de reporter les vraies dépenses nécessaires pour faire les choses correctement afin que les objets individuels puissent réellement être libérés sur un autre thread. En C ou C ++ lorsque nous mallocou appelons operator new, nous devons payer le coût intégral à l'avance dans le même thread.

C'est la principale différence, et pourquoi Java pourrait très bien surpasser le C ou le C ++ en utilisant uniquement des appels naïfs à mallocou operator newpour allouer un tas de petits morceaux individuellement. Bien sûr, il y aura généralement des opérations atomiques et un verrouillage potentiel lorsque le cycle GC démarrera, mais il est probablement un peu optimisé.

Fondamentalement, l'explication simple se résume à payer un coût plus élevé dans un seul thread ( malloc) par rapport à payer un coût moins cher dans un seul thread, puis à payer le coût plus lourd dans un autre qui peut fonctionner en parallèle ( GC). En tant qu'inconvénient, cela signifie que vous avez besoin de deux indirections pour passer de la référence d'objet à l'objet comme requis pour permettre à l'allocateur de copier / déplacer la mémoire sans invalider les références d'objet existantes, et vous pouvez également perdre la localité spatiale une fois que la mémoire de l'objet est déplacé hors de l'espace "Eden".

Enfin et surtout, la comparaison est un peu injuste car le code C ++ n'alloue normalement pas une cargaison d'objets individuellement sur le tas. Un code C ++ décent a tendance à allouer de la mémoire pour de nombreux éléments dans des blocs contigus ou sur la pile. S'il alloue un bateau de petits objets un par un sur la boutique gratuite, le code est merdique.

Tout dépend de qui mesure la vitesse, de la vitesse de mise en œuvre qu'ils mesurent et de ce qu'ils veulent prouver. Et ce qu'ils comparent.

Si vous regardez simplement l'allocation / la désallocation, en C ++, vous pourriez avoir 1 000 000 d'appels vers malloc et 1 000 000 d'appels vers free (). En Java, vous auriez 1 000 000 d'appels à new () et un garbage collector s'exécutant dans une boucle pour trouver 1 000 000 d'objets qu'il peut libérer. La boucle peut être plus rapide que l'appel free ().

D'un autre côté, malloc / free s'est amélioré à d'autres moments, et généralement malloc / free ne définit qu'un bit dans une structure de données distincte, et est optimisé pour malloc / free se produisant dans le même thread, donc dans un environnement multithread aucune variable de mémoire partagée sont utilisés dans de nombreux cas (et les variables de verrouillage ou de mémoire partagée sont très coûteuses).

D'un autre côté, il y a des choses comme le comptage de références dont vous pourriez avoir besoin sans garbage collection, et qui ne viennent pas gratuitement.