Allocation de tas Java plus rapide que C ++

13

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?

aaronman
la source
Vous pouvez trouver ma réponse à une question similaire sur SO SO utile / pertinente.
Daniel Pryden
1
C'est trivial: avec Java (ou tout autre environnement géré et restreint), vous pouvez déplacer des objets et mettre à jour des pointeurs vers eux, c'est-à-dire optimiser pour une meilleure localité de cache de manière dynamique. Avec C ++ et son arithmétique de pointeur avec des bitcasts non contrôlés, tous les objets sont épinglés à leur emplacement pour toujours.
SK-logic
3
Je n'ai jamais pensé entendre quelqu'un dire que la gestion de la mémoire Java est plus rapide car elle copie constamment la mémoire. soupir.
gbjbaanb
1
@gbjbaanb, avez-vous déjà entendu parler de la hiérarchie de la mémoire? Cache pour pénalité manquée? Vous rendez-vous compte qu'un allocateur à usage général coûte cher, alors qu'une allocation de première génération n'est qu'une opération d'ajout?
SK-logic
1
Bien que cela puisse être quelque peu vrai dans certains cas, il manque le point qu'en java vous allouez tout sur le tas et en c ++ vous allouez beaucoup d'objets sur la pile qui peut être encore beaucoup plus rapide.
JohnB

Réponses:

23

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.

mikera
la source
il existe des bibliothèques spécialisées dans la zone c ++ qui résolvent ce problème. L'exemple probablement le plus célèbre pour cela est SmartHeap.
Tobias Langner
5
Le temps réel doux ne signifie pas que vous êtes prêt à vous arrêter généralement . Cela signifie simplement que vous pouvez suspendre / réessayer dans une situation vraiment mauvaise - généralement inattendue - au lieu d'un arrêt / plantage / échec. Personne ne souhaite utiliser un lecteur de musique en pause. Le problème de la pause GC est qu'elle se produit généralement et de façon imprévisible . De cette manière, la pause GC n'est pas acceptable, même pour une application en temps réel doux. La pause GC n'est acceptable que lorsque les utilisateurs ne se soucient pas de la qualité de l'application. Et de nos jours, les gens ne sont plus tellement naïfs.
Eonil
1
Veuillez publier des mesures de performance pour appuyer vos affirmations, sinon nous comparons des pommes et des oranges.
JBRWilkinson
1
@Demetri Mais en réalité, cela ne se produit que si le cas se produit trop (et encore une fois, même de manière imprévisible!) À moins que vous ne puissiez satisfaire certaines contraintes peu pratiques. En d'autres termes, C ++ est beaucoup plus facile pour toute situation en temps réel.
Eonil
1
Pour être complet: il existe un autre inconvénient du GC en termes de performances: comme dans la plupart des GC existants, la libération de mémoire se produit dans un autre thread qui est susceptible de s'exécuter sur un cœur différent, cela signifie que les GC entraînent des coûts d'invalidation du cache importants pour la synchronisation. Caches L1 / L2 entre différents cœurs; de plus, sur les serveurs majoritairement NUMA, les caches L3 doivent également être synchronisés (et via Hypertransport / QPI, aïe (!)).
No-Bugs Hare
3

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.

rwong
la source
en fait, c ++ 11 a même un garbage collection ABI , c'est assez similaire à certaines des réponses que j'ai obtenues sur SO
aaronman
C'est la crainte de casser les programmes C / C ++ existants (bases de code, tels que les noyaux Linux et les bibliothèques archaic_but_still_economically_important telles que libtiff) qui a entravé les progrès de l'innovation langagière en C ++.
rwong
Cela a du sens, je suppose que c ++ 17 ce sera plus complet, mais la vérité est qu'une fois que vous avez vraiment appris à programmer en c ++, vous n'en voulez même plus, peut-être qu'ils peuvent trouver un moyen de combiner les deux idiomes bien
aaronman
Vous rendez-vous compte qu'il existe des éboueurs qui n'arrêtent pas le monde? Avez-vous pris en compte les implications en termes de performances de la compactification (côté GC) et de la fragmentation de segment (pour les allocateurs C ++ génériques)?
SK-logic
2
Je pense que le principal défaut de cette analogie est que ce que GC fait réellement est de trouver les bits sales, de les couper et de voir ensuite les bits restants ensemble pour créer un nouveau tapis.
svick
3

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.

gbjbaanb
la source
2
On dirait que vous ne comprenez pas du tout les GC. Considérez le scénario le plus typique - des centaines de petits objets sont constamment alloués, mais seulement une douzaine d'entre eux survivront pendant plus d'une seconde. De cette façon, il n'y a absolument aucun coût à libérer la mémoire - cette douzaine est copiée de la jeune génération (et compactée, comme avantage supplémentaire), et le reste est éliminé sans frais. Et, soit dit en passant, le pathétique Dalvik GC n'a rien à voir avec les GC modernes et à la pointe de la technologie que vous trouverez dans les implémentations JVM appropriées.
SK-logic
1
Si l'un de ces objets libérés se trouve au milieu du tas, le reste du tas sera compacté pour récupérer l'espace. Ou dites-vous que le compactage GC ne se produit que si c'est le meilleur des cas que vous décrivez? Je sais que les GC générationnels font beaucoup mieux ici, sauf si vous libérez un objet au milieu des générations ultérieures, auquel cas l'impact peut être relativement important. Il y avait quelque chose écrit par un Microsoftie qui a travaillé sur leur GC que j'ai lu qui décrivait les compromis du GC lors de la création d'un GC générationnel. Je vais voir si je peux le retrouver.
gbjbaanb du
1
De quel "tas" parlez-vous? La plupart des déchets sont récupérés au stade de la jeune génération, et la plupart des avantages de performance proviennent exactement de cette compactification. Bien sûr, il est principalement visible sur un profil d'allocation de mémoire typique de la programmation fonctionnelle (de nombreux petits objets de courte durée). Et, bien sûr, il existe de nombreuses possibilités d'optimisation pas encore tout à fait explorées - par exemple, une analyse de région dynamique qui peut transformer automatiquement les allocations de tas dans un certain chemin en allocations de pile ou de pool.
SK-logic
3
Je ne suis pas d'accord avec votre affirmation selon laquelle l'allocation de tas est «aussi rapide que la pile» - l'allocation de tas nécessite une synchronisation des threads et la pile ne le fait pas (par définition)
JBRWilkinson
1
Je suppose que oui, mais avec Java et .net, vous voyez mon point - vous n'avez pas à parcourir le tas pour trouver le prochain bloc gratuit, donc c'est beaucoup plus rapide à cet égard, mais oui - vous avez raison, il doit être verrouillé, ce qui nuira aux applications filetées.
gbjbaanb
2

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.


la source
0

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.

gnasher729
la source