Pourquoi C ++ n'a-t-il pas de garbage collector?

270

Je ne pose pas cette question en raison des avantages de la collecte des ordures tout d'abord. Ma principale raison de demander ceci est que je sais que Bjarne Stroustrup a dit que C ++ aura un ramasse-miettes à un moment donné.

Cela dit, pourquoi n'a-t-il pas été ajouté? Il existe déjà des récupérateurs de place pour C ++. Est-ce juste une de ces choses de type «plus facile à dire qu'à faire»? Ou y a-t-il d'autres raisons pour lesquelles il n'a pas été ajouté (et ne sera pas ajouté en C ++ 11)?

Liens croisés:

Juste pour clarifier, je comprends les raisons pour lesquelles C ++ n'avait pas de garbage collector lors de sa création. Je me demande pourquoi le collecteur ne peut pas être ajouté.

Jason Baker
la source
26
C'est l'un des dix principaux mythes sur le C ++ que les haineux évoquent toujours. Le garbage collection n'est pas "intégré", mais il existe plusieurs façons simples de le faire en C ++. Poster un commentaire parce que d'autres ont déjà répondu mieux que moi ci-dessous :)
davr
5
Mais c'est tout l'intérêt de ne pas être intégré, vous devez le faire vous-même. Réalisation de haut en bas: encastrable, bibliothèque, fait maison. J'utilise C ++ moi-même, et certainement pas un haineux parce que c'est le meilleur langage du monde. Mais la gestion dynamique de la mémoire est pénible.
QBziZ
4
@Davr - Je ne suis pas un haineux C ++ et je n'essaie même pas de faire valoir que C ++ a besoin d'un garbage collector. Je demande parce que je sais que Bjarne Stroustrup a dit qu'il sera ajouté et était simplement curieux de savoir quelles étaient les raisons de ne pas le mettre en œuvre.
Jason Baker
1
Cet article The Boehm Collector for C and C ++ de Dr. Dobbs décrit un garbage collector open source qui peut être utilisé avec C et C ++. Il aborde certains des problèmes qui se posent avec l'utilisation d'un garbage collector avec des destructeurs C ++ ainsi que la bibliothèque standard C.
Richard Chambers
1
@rogerdpack: Mais ce n'est pas très utile maintenant (voir ma réponse ...), il est donc peu probable que les implémentations investissent pour en avoir un.
einpoklum

Réponses:

160

Un ramasse-miettes implicite aurait pu être ajouté, mais il n'a tout simplement pas été coupé. Probablement en raison non seulement des complications de mise en œuvre, mais aussi du fait que les gens ne sont pas parvenus à un consensus général assez rapidement.

Une citation de Bjarne Stroustrup lui-même:

J'avais espéré qu'un garbage collector qui pourrait être activé en option ferait partie de C ++ 0x, mais il y avait suffisamment de problèmes techniques que je dois faire avec juste une spécification détaillée de la façon dont un tel collecteur s'intègre avec le reste du langage , si fourni. Comme c'est le cas avec pratiquement toutes les fonctionnalités C ++ 0x, une implémentation expérimentale existe.

Il y a une bonne discussion du sujet ici .

Aperçu général:

C ++ est très puissant et vous permet de faire presque n'importe quoi. Pour cette raison, il ne vous pousse pas automatiquement de nombreux éléments susceptibles d'avoir un impact sur les performances. La récupération de place peut être facilement implémentée avec des pointeurs intelligents (objets qui enveloppent les pointeurs avec un compte de référence, qui se suppriment automatiquement lorsque le compte de référence atteint 0).

C ++ a été construit avec des concurrents à l'esprit qui n'avaient pas de ramasse-miettes. L'efficacité était la principale préoccupation que C ++ devait repousser la critique par rapport à C et à d'autres.

Il existe 2 types de ramassage des ordures ...

Récupération de place explicite:

C ++ 0x aura la récupération de place via des pointeurs créés avec shared_ptr

Si vous le voulez, vous pouvez l'utiliser, si vous ne le voulez pas, vous n'êtes pas obligé de l'utiliser.

Vous pouvez actuellement utiliser boost: shared_ptr également si vous ne voulez pas attendre C ++ 0x.

Ramasse-miettes implicite:

Cependant, il n'a pas de récupération de place transparente. Ce sera un point focal pour les futures spécifications C ++.

Pourquoi Tr1 n'a pas de récupération de place implicite?

Il y avait beaucoup de choses que tr1 de C ++ 0x aurait dû avoir, Bjarne Stroustrup dans des interviews précédentes a déclaré que tr1 n'en avait pas autant qu'il l'aurait souhaité.

Brian R. Bondy
la source
71
Je deviendrais un haineux si C ++ m'imposait un ramasse-miettes! Pourquoi les gens ne peuvent-ils pas utiliser smart_ptr's? Comment feriez-vous une fourche de style Unix de bas niveau, avec un garbage collector sur le chemin? D'autres choses seraient affectées comme le filetage. Python a son verrou d'interpréteur global, principalement en raison de sa collecte des ordures (voir Cython). Gardez-le hors de C / C ++, merci.
unixman83
26
@ unixman83: Le principal problème avec la collecte des ordures comptées par référence (ie std::shared_ptr) est les références cycliques, qui provoquent une fuite de mémoire. Par conséquent, vous devez utiliser soigneusement std::weak_ptrpour rompre les cycles, ce qui est désordonné. Le style de marquage et de balayage GC n'a pas ce problème. Il n'y a pas d'incompatibilité inhérente entre le threading / forking et le garbage collection. Java et C # ont tous deux un multithread préemptif hautes performances et un garbage collector. Il y a des problèmes avec les applications en temps réel et un garbage collector, car la plupart des garbage collector doivent arrêter le monde pour fonctionner.
Andrew Tomazos
9
"Le principal problème avec la collecte des ordures comptées par référence (c.-à-d. std::shared_ptr) Est les références cycliques" et des performances horribles qui sont ironiques car de meilleures performances sont généralement la justification de l'utilisation de C ++ ... flyingfrogblog.blogspot.co.uk/2011/01/…
Jon Harrop
11
Msgstr "Comment feriez-vous pour un style de fourche de bas niveau Unix". De la même manière que les langages GC'd comme OCaml le font depuis environ 20 ans ou plus.
Jon Harrop
9
"Python a son verrou d'interpréteur global principalement à cause de sa collecte des ordures". Argument de Strawman. Java et .NET ont tous deux des GC mais aucun n'a de verrous globaux.
Jon Harrop
149

Pour ajouter au débat ici.

Il existe des problèmes connus avec la récupération de place, et leur compréhension permet de comprendre pourquoi il n'y en a pas en C ++.

1. Performance?

La première plainte concerne souvent la performance, mais la plupart des gens ne réalisent pas vraiment de quoi ils parlent. Comme l'illustre Martin Beckettle problème, ce n'est peut-être pas la performance en soi, mais la prévisibilité de la performance.

Il existe actuellement 2 familles de GC largement déployées:

  • Type Mark-And-Sweep
  • Type de comptage de références

Le Mark And Sweepest plus rapide (moins d'impact sur les performances globales) mais il souffre d'un syndrome de "gel du monde": c'est-à-dire lorsque le GC entre en action, tout le reste est arrêté jusqu'à ce que le GC ait fait son nettoyage. Si vous souhaitez construire un serveur qui répond en quelques millisecondes ... certaines transactions ne seront pas à la hauteur de vos attentes :)

Le problème Reference Countingest différent: le comptage de références ajoute des frais généraux, en particulier dans les environnements multithreading car vous devez avoir un comptage atomique. De plus, il y a le problème des cycles de référence, vous avez donc besoin d'un algorithme intelligent pour détecter ces cycles et les éliminer (généralement mis en œuvre par un "gel du monde" aussi, bien que moins fréquent). En général, à ce jour, ce type (même s'il est normalement plus réactif ou plutôt gelant moins souvent) est plus lent que le Mark And Sweep.

J'ai vu un article d'implémenteurs Eiffel qui essayaient d'implémenter un Reference CountingGarbage Collector qui aurait une performance globale similaire à Mark And Sweepsans l'aspect "Freeze The World". Il fallait un thread séparé pour le GC (typique). L'algorithme était un peu effrayant (à la fin) mais le document a fait un bon travail en introduisant les concepts un par un et en montrant l'évolution de l'algorithme de la version "simple" à la version à part entière. Lecture recommandée si seulement je pouvais remettre mes mains sur le fichier PDF ...

2. L'acquisition de ressources est l'initialisation (RAII)

C'est un idiome courant en ce sens C++que vous encapsulerez la propriété des ressources dans un objet pour vous assurer qu'elles sont correctement libérées. Il est principalement utilisé pour la mémoire car nous n'avons pas de récupération de place, mais il est néanmoins utile dans de nombreuses autres situations:

  • serrures (multi-thread, file handle, ...)
  • connexions (à une base de données, à un autre serveur, ...)

L'idée est de bien contrôler la durée de vie de l'objet:

  • il doit être vivant tant que vous en avez besoin
  • il devrait être tué quand vous en aurez fini

Le problème du GC est que s'il aide avec le premier et garantit finalement que plus tard ... cet "ultime" peut ne pas être suffisant. Si vous libérez un verrou, vous aimeriez vraiment qu'il soit libéré maintenant, afin qu'il ne bloque plus aucun appel!

Les langues avec GC ont deux contournements:

  • n'utilisez pas GC lorsque l'allocation de pile est suffisante: c'est normalement pour des problèmes de performances, mais dans notre cas, cela aide vraiment car la portée définit la durée de vie
  • usingconstruire ... mais il est explicite (faible) RAII en C ++ RAII est implicite de sorte que l'utilisateur NE PEUT PAS faire l'erreur sans le savoir (en omettant le usingmot - clé)

3. Pointeurs intelligents

Les pointeurs intelligents apparaissent souvent comme une solution miracle pour gérer la mémoire C++. Souvent, j'ai entendu: nous n'avons pas besoin de GC après tout, car nous avons des pointeurs intelligents.

On ne peut plus se tromper.

Les pointeurs intelligents aident auto_ptret unique_ptrutilisent des concepts RAII, extrêmement utiles en effet. Ils sont si simples que vous pouvez les écrire vous-même assez facilement.

Cependant, quand il faut partager la propriété, cela devient plus difficile: vous pouvez partager entre plusieurs threads et il y a quelques problèmes subtils avec la gestion du compte. Par conséquent, on va naturellement vers shared_ptr.

C'est génial, c'est pour ça que Boost après tout, mais ce n'est pas une solution miracle. En fait, le principal problème shared_ptrest qu'il émule un GC implémenté par Reference Countingmais vous devez implémenter la détection de cycle par vous-même ... Urg

Bien sûr, il y a ce weak_ptrtruc, mais j'ai malheureusement déjà vu des fuites de mémoire malgré l'utilisation de à shared_ptrcause de ces cycles ... et lorsque vous êtes dans un environnement multi-thread, c'est extrêmement difficile à détecter!

4. Quelle est la solution?

Il n'y a pas de solution miracle, mais comme toujours, c'est définitivement faisable. En l'absence de GC, il faut être clair sur la propriété:

  • préfèrent avoir un seul propriétaire à un moment donné, si possible
  • sinon, assurez-vous que votre diagramme de classes n'a pas de cycle relatif à la propriété et cassez-les avec une application subtile de weak_ptr

Donc en effet, ce serait génial d'avoir un GC ... mais ce n'est pas un problème trivial. Et en attendant, nous avons juste besoin de retrousser nos manches.

Matthieu M.
la source
2
J'aimerais pouvoir accepter deux réponses! C'est tout simplement génial. Une chose à souligner, en ce qui concerne les performances, le GC qui s'exécute dans un thread séparé est en fait assez courant (il est utilisé en Java et .Net). Certes, cela pourrait ne pas être acceptable dans les systèmes embarqués.
Jason Baker
14
Seulement deux types? Comment copier les collectionneurs? Collectionneurs générationnels? Collectionneurs simultanés variés (y compris le tapis roulant dur en temps réel de Baker) Divers collectionneurs hybrides? Homme, la pure ignorance dans l'industrie de ce domaine m'étonne parfois.
JUSTE MON AVIS correct
12
Ai-je dit qu'il n'y avait que 2 types? J'ai dit qu'il y en avait 2 qui étaient largement déployés. Pour autant que je sache, Python, Java et C # utilisent tous des algorithmes Mark et Sweep maintenant (Java avait un algorithme de comptage de référence). Pour être encore plus précis, il me semble que C # utilise Generational GC pour les cycles mineurs, Mark And Sweep pour les cycles majeurs et Copying pour combattre la fragmentation de la mémoire; mais je dirais que le cœur de l'algorithme est Mark And Sweep. Connaissez-vous un langage courant qui utilise une autre technologie? Je suis toujours content d'apprendre.
Matthieu M.
3
Vous venez de nommer une langue dominante qui en utilise trois.
JUSTE MON AVIS correct le
3
La principale différence est que le GC générationnel et incrémentiel n'a pas besoin d'arrêter le monde pour fonctionner, et vous pouvez les faire fonctionner sur des systèmes à un seul thread sans trop de surcharge en effectuant occasionnellement une itération de la traversée de l'arborescence lors de l'accès aux pointeurs GC (le facteur peut être déterminé par le nombre de nouveaux nœuds, ainsi qu'une prévision de base de la nécessité de collecter). Vous pouvez aller encore plus loin dans GC en incluant des données sur l'endroit où dans le code la création / modification du nœud s'est produite, ce qui pourrait vous permettre d'améliorer vos prédictions, et vous obtenez gratuitement Escape Analysis avec.
Keldon Alleyne
56

Quel genre? Doit-il être optimisé pour les contrôleurs de lave-linge intégrés, les téléphones portables, les postes de travail ou les superordinateurs?
Doit-il prioriser la réactivité de l'interface graphique ou le chargement du serveur?
Doit-il utiliser beaucoup de mémoire ou beaucoup de CPU?

C / c ++ est utilisé dans trop de circonstances différentes. Je soupçonne que quelque chose comme booster les pointeurs intelligents sera suffisant pour la plupart des utilisateurs

Edit - Les ramasse-miettes automatiques ne sont pas tellement un problème de performances (vous pouvez toujours acheter plus de serveurs), c'est une question de performances prédictibles.
Ne pas savoir quand le GC va entrer en action, c'est comme employer un pilote de ligne narcoleptique, la plupart du temps ils sont formidables - mais quand vous avez vraiment besoin de réactivité!

Martin Beckett
la source
6
Je vois certainement votre point, mais je me sens obligé de demander: Java n'est-il pas utilisé dans à peu près autant d'applications?
Jason Baker, le
35
Non. Java n'est pas adapté aux applications hautes performances, pour la simple raison qu'il n'a pas de garanties de performances au même titre que C ++. Vous le trouverez donc dans un téléphone portable, mais vous ne le trouverez pas dans un commutateur cellulaire ou un superordinateur.
Zathrus
11
Vous pouvez toujours acheter plus de serveurs, mais vous ne pouvez pas toujours acheter plus de CPU pour le téléphone portable déjà dans la poche du client!
Crashworks
8
Java a fait beaucoup de rattrapage de performances en termes d'efficacité CPU. Le problème vraiment insoluble est l'utilisation de la mémoire, Java est intrinsèquement moins efficace en mémoire que C ++. Et cette inefficacité est due au fait que ce sont des ordures ménagères. Le nettoyage de la mémoire ne peut pas être à la fois rapide et efficace en mémoire, un fait qui devient évident si vous examinez la vitesse de fonctionnement des algorithmes GC.
Nate CK
2
@Zathrus java peut gagner sur le débit b / c du jit d'optimisation, mais pas la latence (boo en temps réel), et certainement pas l'empreinte mémoire.
gtrak
34

L'une des principales raisons pour lesquelles C ++ n'a pas intégré la récupération de place est qu'il est très difficile de faire fonctionner la récupération de place avec les destructeurs. Pour autant que je sache, personne ne sait vraiment vraiment comment le résoudre complètement. Il y a beaucoup de problèmes à régler:

  • durée de vie déterministe des objets (le comptage des références vous donne cela, mais pas GC. Bien que ce ne soit pas si grave).
  • que se passe-t-il si un destructeur lance lorsque l'objet est en train d'être ramassé? La plupart des langages ignorent cette exception, car il n'y a vraiment pas de bloc catch pour pouvoir le transporter, mais ce n'est probablement pas une solution acceptable pour C ++.
  • Comment l'activer / le désactiver? Naturellement, ce serait probablement une décision de compilation, mais le code qui est écrit pour GC vs le code qui est écrit pour NOT GC va être très différent et probablement incompatible. Comment conciliez-vous cela?

Ce ne sont là que quelques-uns des problèmes rencontrés.

Greg Rogers
la source
17
GC et destructeurs est un problème résolu, par un joli pas de côté de Bjarne. Les destructeurs ne fonctionnent pas pendant le GC, car ce n'est pas le but du GC. GC en C ++ existe pour créer la notion de mémoire infinie , pas d'infinies autres ressources.
MSalters
2
Si les destructeurs ne s'exécutent pas, cela change complètement la sémantique du langage. Je suppose qu'au moins vous auriez besoin d'un nouveau mot-clé "gcnew" ou quelque chose pour que vous autorisiez explicitement cet objet à être GC (et donc vous ne devriez pas l'utiliser pour encapsuler des ressources en plus de la mémoire).
Greg Rogers
7
C'est un faux argument. Étant donné que C ++ a une gestion de mémoire explicite, vous devez déterminer quand chaque objet doit être libéré. Avec GC, ce n'est pas pire; le problème est plutôt réduit à déterminer quand certains objets sont libérés, à savoir les objets qui nécessitent des considérations spéciales lors de la suppression. L'expérience de la programmation en Java et C # révèle que la grande majorité des objets ne nécessitent aucune considération particulière et peuvent être laissés en toute sécurité au GC. Il s'avère que l'une des principales fonctions des destructeurs en C ++ est de libérer des objets enfants, que GC gère automatiquement pour vous.
Nate CK
2
@ NateC-K: Une chose qui est améliorée dans GC vs non-GC (peut-être la plus grande chose) est la capacité d'un système GC solide à garantir que chaque référence continuera à pointer vers le même objet tant que la référence existe. L'appel Disposeà un objet peut le rendre impossible, mais les références qui pointaient vers l'objet quand il était vivant continueront de le faire après sa mort. En revanche, dans les systèmes non GC, les objets peuvent être supprimés tant que des références existent, et il n'y a rarement aucune limite aux ravages qui peuvent être causés si l'une de ces références est utilisée.
supercat
22

Bien que ce soit une vieille question, il y a encore un problème que je ne vois personne avoir résolu du tout: la collecte des ordures est presque impossible à spécifier.

En particulier, la norme C ++ prend bien soin de spécifier le langage en termes de comportement observable de l'extérieur, plutôt que de la façon dont l'implémentation réalise ce comportement. Dans le cas de la collecte des ordures, cependant, il n'y a pratiquement aucun comportement observable de l'extérieur.

L' idée générale de la récupération de place est qu'elle doit faire une tentative raisonnable pour garantir la réussite d'une allocation de mémoire. Malheureusement, il est essentiellement impossible de garantir que toute allocation de mémoire réussira, même si vous avez un garbage collector en fonctionnement. Cela est vrai dans une certaine mesure dans tous les cas, mais particulièrement dans le cas de C ++, car il n'est (probablement) pas possible d'utiliser un collecteur de copie (ou quelque chose de similaire) qui déplace les objets en mémoire pendant un cycle de collecte.

Si vous ne pouvez pas déplacer des objets, vous ne pouvez pas créer un seul espace mémoire contigu à partir duquel effectuer vos allocations - et cela signifie que votre tas (ou magasin gratuit, ou tout ce que vous préférez l'appeler) peut, et le fera probablement , se fragmentent avec le temps. Ceci, à son tour, peut empêcher une allocation de réussir, même s'il y a plus de mémoire disponible que la quantité demandée.

Bien qu'il soit possible de trouver une garantie qui dit (en substance) que si vous répétez exactement le même modèle d'allocation à plusieurs reprises, et qu'il a réussi la première fois, il continuera à réussir lors des itérations suivantes, à condition que la mémoire allouée est devenu inaccessible entre les itérations. C'est une garantie si faible qu'elle est essentiellement inutile, mais je ne vois aucun espoir raisonnable de la renforcer.

Néanmoins, il est plus fort que ce qui a été proposé pour C ++. La proposition précédente [avertissement: PDF] (qui a été supprimée) ne garantissait rien du tout. Dans 28 pages de proposition, ce que vous avez obtenu en termes de comportement observable de l'extérieur était une seule note (non normative) disant:

[Remarque: pour les programmes de récupération de place, une implémentation hébergée de haute qualité doit tenter de maximiser la quantité de mémoire inaccessible qu'elle récupère. —Fin note]

Du moins pour moi, cela soulève une sérieuse question de retour sur investissement. Nous allons casser le code existant (personne ne sait exactement combien, mais certainement pas mal), imposer de nouvelles exigences sur les implémentations et de nouvelles restrictions sur le code, et ce que nous obtenons en retour est très probablement rien du tout?

Même au mieux, nous obtenons des programmes qui, basés sur tests avec Java , nécessiteront probablement environ six fois plus de mémoire pour fonctionner à la même vitesse qu'ils le font actuellement. Pire encore, la collecte des ordures faisait partie de Java depuis le début - C ++ impose suffisamment de restrictions au récupérateur de déchets pour qu'il aura certainement un rapport coûts / avantages encore pire (même si nous allons au-delà de ce que la proposition garantit et supposons qu'il y en aura). certains avantages).

Je résumerais la situation mathématiquement: c'est une situation complexe. Comme tout mathématicien le sait, un nombre complexe se compose de deux parties: réelle et imaginaire. Il me semble que nous avons ici des coûts qui sont réels, mais des avantages qui sont (au moins surtout) imaginaires.

Jerry Coffin
la source
Je suppose que même si l'on spécifie que pour un fonctionnement correct, tous les objets doivent être supprimés et que seuls les objets qui ont été supprimés seraient éligibles pour la collecte, le support du compilateur pour la collecte des ordures de suivi des références pourrait toujours être utile, car un tel langage pourrait garantir que l'utilisation d'un pointeur supprimé (référence) serait garantie pour intercepter, plutôt que de provoquer un comportement indéfini.
supercat
2
Même en Java, le GC n'est pas vraiment spécifié pour faire quoi que ce soit d'utile AFAIK. Cela pourrait vous appeler free(où je veux dire freeanalogue au langage C). Mais Java ne garantit jamais d'appeler les finaliseurs ou quelque chose comme ça. En fait, C ++ fait bien plus que Java pour exécuter les écritures de base de données de validation, le vidage des descripteurs de fichiers, etc. Java prétend avoir "GC", mais les développeurs Java doivent appeler méticuleusement close()tout le temps et ils doivent être très conscients de la gestion des ressources, en faisant attention de ne pas appeler close()trop tôt ou trop tard. C ++ nous en libère. ... (suite)
Aaron McDaid
2
.. mon commentaire il y a un instant ne vise pas à critiquer Java. J'observe simplement que le terme «ramassage des ordures» est un terme très étrange - il signifie beaucoup moins que les gens ne le pensent et il est donc difficile d'en discuter sans être clair sur ce qu'il signifie.
Aaron McDaid
@AaronMcDaid Il est vrai que GC n'aide pas du tout avec les ressources non-mémoire. Heureusement, ces ressources sont allouées assez rarement par rapport à la mémoire. De plus, plus de 90% d'entre eux peuvent être libérés dans la méthode qui les a alloués, donc le try (Whatever w=...) {...}résout (et vous obtenez un avertissement lorsque vous oubliez). Les autres sont également problématiques avec RAII. Appeler close()"tout le temps" signifie peut-être une fois par dizaines de milliers de lignes, donc ce n'est pas si mal, alors que la mémoire est allouée presque sur chaque ligne Java.
maaartinus
15

Si vous voulez un ramasse-miettes automatique, il existe de bons ramasse-miettes commerciaux et du domaine public pour C ++. Pour les applications où la récupération de place est appropriée, C ++ est un excellent langage de récupération de place avec une performance qui se compare favorablement aux autres langues de récupération de place. Voir Le langage de programmation C ++ (4e édition) pour une discussion sur le garbage collection automatique en C ++. Voir aussi Hans-J. Site de Boehm pour la collecte des ordures C et C ++ ( archive ).

De plus, C ++ prend en charge les techniques de programmation qui permettent à la gestion de la mémoire d'être sûre et implicite sans garbage collector . Je considère la collecte des ordures comme un dernier choix et une manière imparfaite de gérer la gestion des ressources. Cela ne signifie pas qu'il n'est jamais utile, mais simplement qu'il existe de meilleures approches dans de nombreuses situations.

La source: http://www.stroustrup.com/bs_faq.html#garbage-collection

Quant à savoir pourquoi il ne l'a pas intégré, si je me souviens bien, il a été inventé avant que GC ne soit la chose , et je ne pense pas que le langage aurait pu avoir GC pour plusieurs raisons (IE rétrocompatibilité avec C)

J'espère que cela t'aides.

Rayne
la source
"avec une performance qui se compare favorablement avec les autres langues récupérées". Citation?
Jon Harrop
1
Mon lien a été rompu. J'ai écrit cette réponse il y a 5 ans.
Rayne
1
Ok, j'espérais une vérification indépendante de ces affirmations, c'est-à-dire pas par Stroustrup ou Boehm. :-)
Jon Harrop
12

Stroustrup a fait de bons commentaires à ce sujet lors de la conférence Going Native 2013.

Passez à environ 25m50 dans cette vidéo . (Je recommanderais en fait de regarder la vidéo en entier, mais cela passe aux choses sur la collecte des ordures.)

Lorsque vous avez une langue vraiment géniale qui rend facile (et sûr, et prévisible, et facile à lire et facile à enseigner) pour traiter les objets et les valeurs de manière directe, en évitant l'utilisation (explicite) du tas, alors vous ne voulez même pas la collecte des ordures.

Avec le C ++ moderne, et les trucs que nous avons en C ++ 11, la récupération de place n'est plus souhaitable, sauf dans des circonstances limitées. En fait, même si un bon garbage collector est intégré à l'un des principaux compilateurs C ++, je pense qu'il ne sera pas utilisé très souvent. Il sera plus facile , pas plus difficile, d'éviter le GC.

Il montre cet exemple:

void f(int n, int x) {
    Gadget *p = new Gadget{n};
    if(x<100) throw SomeException{};
    if(x<200) return;
    delete p;
}

Ce n'est pas sûr en C ++. Mais c'est aussi dangereux en Java! En C ++, si la fonction revient tôt, le deletene sera jamais appelé. Mais si vous aviez un ramasse-miettes complet, comme en Java, vous obtenez simplement une suggestion que l'objet sera détruit "à un moment donné dans le futur" ( mise à jour: c'est encore pire que cela. Java ne fonctionne paspromettre d'appeler le finaliseur jamais - il ne sera peut-être jamais appelé). Ce n'est pas suffisant si Gadget contient un descripteur de fichier ouvert, ou une connexion à une base de données, ou des données que vous avez mises en mémoire tampon pour être écrites dans une base de données à un stade ultérieur. Nous voulons que le gadget soit détruit dès qu'il est terminé, afin de libérer ces ressources dès que possible. Vous ne voulez pas que votre serveur de base de données se débat avec des milliers de connexions de base de données qui ne sont plus nécessaires - il ne sait pas que votre programme a fini de fonctionner.

Alors, quelle est la solution? Il existe quelques approches. L'approche évidente, que vous utiliserez pour la grande majorité de vos objets est:

void f(int n, int x) {
    Gadget p = {n};  // Just leave it on the stack (where it belongs!)
    if(x<100) throw SomeException{};
    if(x<200) return;
}

Cela prend moins de caractères à taper. Cela ne doit pas newgêner. Il ne vous oblige pas à taper Gadgetdeux fois. L'objet est détruit à la fin de la fonction. Si c'est ce que vous voulez, c'est très intuitif. Gadgets se comportent comme intou double. Prévisible, facile à lire, facile à enseigner. Tout est une «valeur». Parfois une grande valeur, mais les valeurs sont plus faciles à enseigner parce que vous n'avez pas cette chose "d'action à distance" que vous obtenez avec des pointeurs (ou des références).

La plupart des objets que vous créez sont destinés à être utilisés uniquement dans la fonction qui les a créés et peut-être passés en tant qu'entrées aux fonctions enfants. Le programmeur ne devrait pas avoir à penser à la «gestion de la mémoire» lorsqu'il retourne des objets, ou autrement partage des objets entre des parties largement séparées du logiciel.

La portée et la durée de vie sont importantes. La plupart du temps, c'est plus facile si la durée de vie est la même que la portée. C'est plus facile à comprendre et à enseigner. Lorsque vous voulez une durée de vie différente, il devrait être évident en lisant le code que vous faites cela, en utilisant shared_ptrpar exemple. (Ou renvoyer des objets (volumineux) par valeur, en exploitant la sémantique de mouvement ou unique_ptr.

Cela peut sembler un problème d'efficacité. Et si je veux retourner un gadget foo()? La sémantique de mouvement de C ++ 11 facilite le retour de gros objets. Il suffit d'écrire Gadget foo() { ... }et cela fonctionnera et fonctionnera rapidement. Vous n'avez pas besoin de &&vous embêter, renvoyez simplement les choses par valeur et le langage pourra souvent faire les optimisations nécessaires. (Même avant C ++ 03, les compilateurs ont remarquablement bien évité la copie inutile.)

Comme Stroustrup l'a dit ailleurs dans la vidéo (paraphrase): "Seul un informaticien insisterait pour copier un objet, puis détruire l'original. (L'auditoire rit). Pourquoi ne pas simplement déplacer l'objet directement vers le nouvel emplacement? C'est ce que les humains (pas les informaticiens) s’attendent. "

Lorsque vous pouvez garantir qu'une seule copie d'un objet est nécessaire, il est beaucoup plus facile de comprendre la durée de vie de l'objet. Vous pouvez choisir la politique de durée de vie que vous souhaitez et la récupération de place est là si vous le souhaitez. Mais lorsque vous comprendrez les avantages des autres approches, vous constaterez que la collecte des ordures est au bas de votre liste de préférences.

Si cela ne fonctionne pas pour vous, vous pouvez utiliser unique_ptr, ou à défaut, shared_ptr. Un C ++ 11 bien écrit est plus court, plus facile à lire et à enseigner que de nombreux autres langages en matière de gestion de la mémoire.

Aaron McDaid
la source
1
GC ne doit être utilisé que pour les objets qui n'acquièrent pas de ressources (c'est-à-dire demander à d'autres entités de faire des choses en leur nom "jusqu'à nouvel ordre"). Si Gadgetne demande rien d'autre pour faire quoi que ce soit en son nom, le code d'origine serait parfaitement sûr en Java si l' deleteinstruction vide de sens (vers Java) était supprimée.
supercat
@supercat, les objets avec des destructeurs ennuyeux sont intéressants. (Je n'ai pas défini «ennuyeux», mais essentiellement des destructeurs qui n'ont jamais besoin d'être appelés, sauf pour libérer de la mémoire). Il peut être possible pour un compilateur individuel de traiter shared_ptr<T>spécialement lorsqu'il Test «ennuyeux». Il pourrait décider de ne pas gérer réellement un compteur de références pour ce type et d'utiliser plutôt GC. Cela permettrait au GC d'être utilisé sans que le développeur n'en ait besoin. A shared_ptrpourrait simplement être considéré comme un pointeur GC, pour convenir T. Mais il y a des limites à cela, et cela ralentirait de nombreux programmes.
Aaron McDaid du
Un bon système de type doit avoir différents types pour les objets de tas gérés par GC et RAII, car certains modèles d'utilisation fonctionnent très bien avec l'un et très mal avec l'autre. En .NET ou Java, une instruction string1=string2;s'exécutera très rapidement quelle que soit la longueur de la chaîne (ce n'est littéralement rien de plus qu'un chargement de registre et un magasin de registres), et ne nécessite aucun verrouillage pour garantir que si l'instruction ci-dessus est exécutée alors qu'elle string2est en cours d'écriture, string1conservera l'ancienne ou la nouvelle valeur, sans comportement indéfini).
supercat
En C ++, l'affectation d'un shared_ptr<String>nécessite beaucoup de synchronisation en arrière-plan, et l'affectation d'un Stringpeut se comporter bizarrement si une variable est lue et écrite simultanément. Les cas où l'on voudrait écrire et lire Stringsimultanément ne sont pas très courants, mais peuvent survenir si, par exemple, un code souhaite rendre les rapports d'état en cours disponibles pour d'autres threads. En .NET et Java, de telles choses "fonctionnent" simplement.
supercat
1
@curiousguy rien n'a changé, sauf si vous prenez les bonnes précautions, Java permet toujours d'appeler le finaliseur dès que le constructeur a fini. Voici un exemple concret: « finalize () fait appel à des objets fortement accessibles en Java 8 ». La conclusion est de ne jamais utiliser cette fonctionnalité, que presque tout le monde accepte d'être une erreur de conception historique de la langue. Lorsque nous suivons ce conseil, le langage fournit le déterminisme que nous aimons.
Holger
11

Parce que le C ++ moderne n'a pas besoin de garbage collection.

La réponse de Bjarne Stroustrup à la FAQ à ce sujet dit :

Je n'aime pas les ordures. Je n'aime pas jeter de détritus. Mon idéal est d'éliminer le besoin d'un ramasse-miettes en ne produisant aucun déchet. C'est désormais possible.


La situation, pour le code écrit ces jours-ci (C ++ 17 et suivant les directives officielles de base ) est la suivante:

  • La plupart du code lié à la propriété de la mémoire se trouve dans les bibliothèques (en particulier celles qui fournissent des conteneurs).
  • La plupart des codes utilisant la propriété de la mémoire suivent le modèle RAII , donc l'allocation est faite lors de la construction et la désallocation lors de la destruction, ce qui se produit lorsque vous quittez la portée dans laquelle quelque chose a été alloué.
  • Vous n'allouez ni ne désallouez explicitement directement la mémoire .
  • Les pointeurs bruts ne possèdent pas de mémoire (si vous avez suivi les instructions), vous ne pouvez donc pas fuir en les faisant circuler.
  • Si vous vous demandez comment vous allez passer les adresses de départ des séquences de valeurs en mémoire - vous le ferez avec un span ; aucun pointeur brut nécessaire.
  • Si vous avez vraiment besoin d'un "pointeur" propriétaire, vous utilisez les pointeurs intelligents de la bibliothèque standard de C ++ - ils ne peuvent pas fuir et sont décemment efficaces (bien que l'ABI puisse entraver cela). Vous pouvez également transmettre la propriété au-delà des limites de l'étendue avec des "pointeurs de propriétaire" . Ceux-ci sont rares et doivent être utilisés explicitement; mais une fois adoptés - ils permettent une belle vérification statique contre les fuites.

"Oh ouais? Mais qu'en est-il de ...

... si j'écris simplement du code comme nous écrivions autrefois en C ++? "

En effet, vous pouvez simplement ignorer toutes les directives et écrire du code d'application qui fuit - et il se compilera et s'exécutera (et fuira), comme toujours.

Mais ce n'est pas une situation de «ne pas faire ça», où le développeur est censé être vertueux et exercer beaucoup de maîtrise de soi; il n'est tout simplement pas plus simple d'écrire du code non conforme, ni plus rapide à écrire, ni plus performant. Peu à peu, il deviendra également plus difficile à écrire, car vous feriez face à un "décalage d'impédance" croissant avec ce que le code conforme fournit et attend.

... si je reintrepret_cast? Ou faire de l'arithmétique pointeur complexe? Ou d'autres piratages? "

En effet, si vous y pensez, vous pouvez écrire du code qui gâche les choses malgré un bon comportement avec les directives. Mais:

  1. Vous le feriez rarement (en termes d'emplacements dans le code, pas nécessairement en termes de fraction de temps d'exécution)
  2. Vous ne le feriez qu'intentionnellement, pas accidentellement.
  3. Cela se démarquera dans une base de code conforme aux directives.
  4. C'est le genre de code dans lequel vous contourneriez le GC dans une autre langue de toute façon.

... le développement de la bibliothèque? "

Si vous êtes un développeur de bibliothèque C ++, vous écrivez du code dangereux impliquant des pointeurs bruts, et vous devez coder avec soin et responsabilité - mais ce sont des morceaux de code autonomes écrits par des experts (et plus important encore, examinés par des experts).


Donc, c'est comme Bjarne l'a dit: Il n'y a vraiment aucune motivation à collecter les déchets en général, comme vous tous, mais assurez-vous de ne pas produire de déchets. GC devient un non-problème avec C ++.

Cela ne veut pas dire que le GC n'est pas un problème intéressant pour certaines applications spécifiques, lorsque vous souhaitez utiliser des stratégies d'allocation et de désallocation personnalisées. Pour ceux que vous voudriez une allocation et une désallocation personnalisées, pas un GC au niveau de la langue.

einpoklum
la source
Eh bien, il en a besoin (GC) si vous broyez des chaînes. Imaginez que vous avez de grands tableaux de chaînes (pensez à des centaines de mégaoctets) que vous construisez au coup par coup, puis que vous les traitez et les reconstruisez en différentes longueurs, en supprimant celles qui ne sont pas utilisées, en combinant d'autres, etc. I savoir parce que j'ai dû passer à des langues de haut niveau pour faire face. (Bien sûr, vous pouvez également créer votre propre GC).
www-0av-Com
2
@ user1863152: C'est un cas dans lequel un allocateur personnalisé serait utile. Cela ne nécessite toujours pas de GC intégrant la langue ...
einpoklum
à einpoklum: vrai. C'est juste du cheval pour les cours. Mon exigence était de traiter des gallons changeants dynamiquement de renseignements sur les passagers des transports. Sujet fascinant. Se résume vraiment à la philosophie du logiciel.
www-0av-Com
GC, comme le monde Java et .NET l'ont découvert, a enfin un énorme problème - il ne évolue pas. Lorsque vous avez des milliards d'objets vivants en mémoire comme nous le faisons de nos jours avec tout logiciel non trivial, vous devrez commencer à écrire du code pour cacher des choses au GC. C'est un fardeau d'avoir GC en Java et .NET.
Zach Saw
10

L'idée derrière C ++ était que vous ne paieriez aucun impact sur les performances des fonctionnalités que vous n'utilisez pas. Ainsi, l'ajout de garbage collection aurait signifié que certains programmes s'exécutent directement sur le matériel comme le fait C et d'autres au sein d'une sorte de machine virtuelle d'exécution.

Rien ne vous empêche d'utiliser une certaine forme de pointeurs intelligents liés à un mécanisme tiers de récupération de place. Il me semble me rappeler que Microsoft a fait quelque chose comme ça avec COM et cela ne s'est pas bien passé.

Uri
la source
2
Je ne pense pas que GC nécessite une VM. Le compilateur peut ajouter du code à toutes les opérations de pointeur pour mettre à jour un état global, tandis qu'un thread distinct s'exécute en arrière-plan en supprimant les objets selon les besoins.
user83255
3
Je suis d'accord. Vous n'avez pas besoin d'une machine virtuelle, mais la seconde où vous commencez à avoir quelque chose à gérer votre mémoire pour vous comme ça en arrière-plan, j'ai l'impression que vous avez laissé les "fils électriques" réels et que vous avez une sorte de situation de machine virtuelle.
Uri
4

L'un des principes fondamentaux du langage C d'origine est que la mémoire est composée d'une séquence d'octets, et que le code n'a qu'à se soucier de ce que signifient ces octets au moment exact où ils sont utilisés. Le C moderne permet aux compilateurs d'imposer des restrictions supplémentaires, mais C inclut - et C ++ conserve - la possibilité de décomposer un pointeur en une séquence d'octets, d'assembler toute séquence d'octets contenant les mêmes valeurs dans un pointeur, puis d'utiliser ce pointeur pour accéder à l'objet précédent.

Bien que cette capacité puisse être utile - voire indispensable - dans certains types d'applications, un langage qui inclut cette capacité sera très limité dans sa capacité à prendre en charge tout type de collecte de déchets utile et fiable. Si un compilateur ne sait pas tout ce qui a été fait avec les bits qui composent un pointeur, il n'aura aucun moyen de savoir si des informations suffisantes pour reconstruire le pointeur peuvent exister quelque part dans l'univers. Étant donné qu'il serait possible que ces informations soient stockées de manière à ce que l'ordinateur ne puisse pas y accéder même s'il les connaissait (par exemple, les octets constituant le pointeur auraient pu être affichés à l'écran suffisamment longtemps pour que quelqu'un puisse écrire) vers le bas sur un morceau de papier), il peut être littéralement impossible pour un ordinateur de savoir si un pointeur pourrait éventuellement être utilisé à l'avenir.

Une particularité intéressante de nombreux cadres récupérés par les déchets est qu'une référence d'objet n'est pas définie par les modèles de bits qui y sont contenus, mais par la relation entre les bits contenus dans la référence d'objet et d'autres informations détenues ailleurs. En C et C ++, si le modèle de bits stocké dans un pointeur identifie un objet, ce modèle de bits identifiera cet objet jusqu'à ce que l'objet soit explicitement détruit. Dans un système GC typique, un objet peut être représenté par un modèle de bits 0x1234ABCD à un moment donné, mais le cycle GC suivant peut remplacer toutes les références à 0x1234ABCD par des références à 0x4321BABE, après quoi l'objet serait représenté par ce dernier modèle. Même si l'on devait afficher le modèle de bits associé à une référence d'objet, puis le relire plus tard à partir du clavier,

supercat
la source
C'est un très bon point, j'ai récemment volé quelques morceaux de mes pointeurs car sinon il y aurait des quantités stupides de ratés de cache.
Passer By
@PasserBy: Je me demande combien d'applications qui utilisent des pointeurs 64 bits bénéficieraient davantage de l'utilisation de pointeurs 32 bits mis à l'échelle comme références d'objet, ou bien de conserver presque tout dans 4 Go d'espace d'adressage et d'utiliser des objets spéciaux pour stocker / récupérer des données à partir de haut stockage à grande vitesse au-delà? Les machines ont suffisamment de RAM pour que la consommation de RAM des pointeurs 64 bits n'ait pas d'importance, sauf qu'elles avalent deux fois plus de cache que les pointeurs 32 bits.
supercat
3

Toutes les discussions techniques compliquent trop le concept.

Si vous mettez automatiquement GC en C ++ pour toute la mémoire, envisagez quelque chose comme un navigateur Web. Le navigateur Web doit charger un document Web complet ET exécuter des scripts Web. Vous pouvez stocker des variables de script Web dans l'arborescence de documents. Dans un GRAND document dans un navigateur avec de nombreux onglets ouverts, cela signifie que chaque fois que le GC doit effectuer une collecte complète, il doit également numériser tous les éléments du document.

Sur la plupart des ordinateurs, cela signifie que des DÉFAUTS DE PAGE se produiront. Donc, la raison principale, pour répondre à la question est que des DÉFAUTS DE PAGE se produiront. Vous le saurez comme lorsque votre PC commence à faire beaucoup d'accès au disque. C'est parce que le GC doit toucher beaucoup de mémoire afin de prouver les pointeurs invalides. Lorsque vous avez une application de bonne foi utilisant beaucoup de mémoire, devoir analyser tous les objets chaque collection est un ravage en raison des défauts de page. Une erreur de page survient lorsque la mémoire virtuelle doit être relue dans la RAM à partir du disque.

La bonne solution consiste donc à diviser une application en parties qui ont besoin de GC et celles qui n'en ont pas besoin. Dans le cas de l'exemple de navigateur Web ci-dessus, si l'arborescence de documents a été allouée avec malloc, mais que le javascript a fonctionné avec GC, chaque fois que le GC démarre, il ne scanne qu'une petite partie de la mémoire et tous les éléments PAGED OUT de la mémoire pour l'arborescence des documents n'a pas besoin d'être paginée.

Pour mieux comprendre ce problème, recherchez la mémoire virtuelle et la façon dont elle est implémentée dans les ordinateurs. Il s'agit du fait que 2 Go sont disponibles pour le programme quand il n'y a pas vraiment beaucoup de RAM. Sur les ordinateurs modernes avec 2 Go de RAM pour un système 32BIt, ce n'est pas un problème à condition qu'un seul programme soit en cours d'exécution.

Comme exemple supplémentaire, considérons une collection complète qui doit tracer tous les objets. Vous devez d'abord analyser tous les objets accessibles via les racines. Analysez ensuite tous les objets visibles à l'étape 1. Analysez ensuite les destructeurs en attente. Revenez ensuite à toutes les pages et désactivez tous les objets invisibles. Cela signifie que de nombreuses pages peuvent être échangées à plusieurs reprises.

Donc, ma réponse pour faire court est que le nombre de DÉFAUTS DE PAGE qui se produisent à la suite de toucher toute la mémoire rend impossible le GC complet pour tous les objets dans un programme et donc le programmeur doit voir GC comme une aide pour des choses comme les scripts et le travail de base de données, mais faites des choses normales avec la gestion manuelle de la mémoire.

Et l'autre raison très importante est bien sûr les variables globales. Pour que le collecteur sache qu'un pointeur de variable globale se trouve dans le GC, il faudrait des mots-clés spécifiques, et donc le code C ++ existant ne fonctionnerait pas.

Bob Holmes
la source
3

RÉPONSE COURTE: Nous ne savons pas comment effectuer la collecte des ordures de manière efficace (avec un temps et un espace supplémentaires mineurs) et correctement tout le temps (dans tous les cas possibles).

LONG RÉPONSE: Tout comme C, C ++ est un langage système; cela signifie qu'il est utilisé lorsque vous écrivez du code système, par exemple un système d'exploitation. En d'autres termes, C ++ est conçu, tout comme C, avec les meilleures performances possibles comme cible principale. Le standard du langage n'ajoutera aucune fonctionnalité susceptible d'entraver l'objectif de performance.

Cela met en pause la question: pourquoi la collecte des ordures entrave les performances? La principale raison est que, en ce qui concerne la mise en œuvre, nous [les informaticiens] ne savons pas comment faire la collecte des ordures avec un minimum de frais généraux, dans tous les cas. Par conséquent, il est impossible pour le compilateur C ++ et le système d'exécution d'effectuer une collecte de déchets efficace tout le temps. D'un autre côté, un programmeur C ++ devrait connaître sa conception / implémentation et il est la meilleure personne pour décider de la meilleure façon de faire la collecte des ordures.

Enfin, si le contrôle (matériel, détails, etc.) et les performances (temps, espace, puissance, etc.) ne sont pas les principales contraintes, alors C ++ n'est pas l'outil d'écriture. D'autres langages pourraient mieux servir et offrir une gestion d'exécution [cachée] plus importante, avec les frais généraux nécessaires.

Sqandr
la source
3

Lorsque nous comparons C ++ avec Java, nous voyons que C ++ n'a pas été conçu avec le Garbage Collection implicite à l'esprit, alors que Java l'était.

Avoir des choses comme des pointeurs arbitraires dans C-Style est non seulement mauvais pour les implémentations GC, mais cela détruirait également la compatibilité descendante pour une grande quantité de C ++ - code hérité.

En plus de cela, C ++ est un langage qui est destiné à s'exécuter en tant qu'exécutable autonome au lieu d'avoir un environnement d'exécution complexe.

Dans l'ensemble: oui, il pourrait être possible d'ajouter Garbage Collection à C ++, mais dans un souci de continuité, il est préférable de ne pas le faire.

Mike76
la source
1
Libérer de la mémoire et exécuter des destructeurs sont des problèmes trop distincts. (Java n'a pas de destructeurs, ce qui est un PITA.) GC libère de la mémoire, il n'exécute pas de dtors.
curiousguy
0

Principalement pour deux raisons:

  1. Parce qu'il n'en a pas besoin (à mon humble avis)
  2. Parce qu'il est à peu près incompatible avec RAII, qui est la pierre angulaire de C ++

C ++ propose déjà la gestion manuelle de la mémoire, l'allocation de pile, RAII, les conteneurs, les pointeurs automatiques, les pointeurs intelligents ... Cela devrait suffire. Les récupérateurs sont destinés aux programmeurs paresseux qui ne veulent pas passer 5 minutes à réfléchir à qui devrait posséder quels objets ou quand les ressources devraient-elles être libérées. Ce n'est pas ainsi que nous faisons les choses en C ++.

Marc Coll
la source
Il existe de nombreux algorithmes (plus récents) qui sont intrinsèquement difficiles à mettre en œuvre sans garbage collection. Le temps passa. L'innovation provient également de nouvelles perspectives qui correspondent bien aux langages de haut niveau (collecte des ordures). Essayez de rétroporter l'un de ces éléments vers C ++ sans GC, vous remarquerez les bosses sur la route. (Je sais que je devrais donner des exemples, mais je suis un peu pressé en ce moment. Désolé. Un auquel je pense en ce moment tourne autour des structures de données persistantes, où le comptage des références ne fonctionnera pas.).
BitTickler
0

Imposer la collecte des ordures est vraiment un changement de paradigme de bas en haut niveau.

Si vous regardez la façon dont les chaînes sont gérées dans un langage avec garbage collection, vous constaterez qu'elles autorisent UNIQUEMENT des fonctions de manipulation de chaînes de haut niveau et n'autorisent pas l'accès binaire aux chaînes. Autrement dit, toutes les fonctions de chaîne vérifient d'abord les pointeurs pour voir où se trouve la chaîne, même si vous ne dessinez qu'un octet. Donc, si vous effectuez une boucle qui traite chaque octet d'une chaîne dans une langue avec garbage collection, il doit calculer l'emplacement de base plus le décalage pour chaque itération, car il ne peut pas savoir quand la chaîne a été déplacée. Ensuite, vous devez penser aux tas, piles, fils, etc.

www-0av-Com
la source