Pourquoi les langages purement fonctionnels n’utilisent-ils pas le comptage de références?

Dans les langages purement fonctionnels, les données sont immuables. Avec le comptage des références, la création d’un cycle de référence nécessite la modification des données déjà créées. Il semble que des langages purement fonctionnels puissent utiliser le comptage de références sans se soucier de la possibilité de cycles. Est-ce exact? Si oui, pourquoi pas eux?

Je comprends que le comptage des références est plus lent que celui des GC dans de nombreux cas, mais au moins cela réduit les temps de pause. Ce serait bien d’avoir la possibilité d’utiliser le comptage de références dans les cas où les temps de pause sont mauvais.

    Votre question est basée sur une hypothèse erronée. Il est parfaitement possible d’avoir des références circulaires et des données immuables. Prenons l’exemple C # suivant qui utilise des données immuables pour créer une référence circulaire.

    class Node { public readonly Node other; public Node() { other = new Node(this); } public Node(Node node) { other = node; } } 

    Ce type d’astuce peut être fait dans de nombreux langages fonctionnels et, par conséquent, tout mécanisme de collecte doit permettre la possibilité de références circulaires. Je ne dis pas qu’un mécanisme de comptage de ref est impossible avec une référence circulaire, mais simplement qu’il faut le traiter.

    Modifier par ephemient

    En réponse au commentaire … c’est sortingvial dans Haskell

     data Node a = Node { other :: Node a } recursiveNode = Node { other = recursiveNode } 

    et à peine plus d’efforts en SML.

     datatype 'a node = NODE of unit -> 'a node val recursiveNode : unit node = let fun mkRecursiveNode () = NODE mkRecursiveNode in mkRecursiveNode () end 

    Aucune mutation requirejse.

    Par rapport aux autres langages gérés tels que Java et C #, les langages purement fonctionnels allouent comme des fous . Ils allouent également des objects de tailles différentes. La stratégie d’atsortingbution la plus rapide consiste à allouer de l’espace libre contigu (parfois appelé “nursery”) et à réserver un registre matériel pour pointer vers l’espace libre disponible suivant. L’allocation du tas devient aussi rapide que l’allocation d’une stack.

    Le comptage de référence est fondamentalement incompatible avec cette stratégie d’allocation. Le comptage de références met des objects sur des listes libres et les reprend. Le comptage de références comporte également des frais généraux importants nécessaires à la mise à jour des compteurs ref lors de la création de nouveaux objects (ce qui, comme indiqué ci-dessus, est rendu fou par les langages fonctionnels).

    Le comptage des références a tendance à se faire très bien dans des situations comme celles-ci:

    • Presque toute la mémoire de tas est utilisée pour contenir des objects en direct.
    • L’affectation et l’affectation de pointeurs sont peu fréquentes par rapport aux autres opérations.
    • Les références peuvent être gérées sur un autre processeur ou ordinateur.

    Pour comprendre comment fonctionnent les meilleurs systèmes de comptage par comptage haute performance, consultez le travail de David Bacon et d’ Erez Petrank .

    Il y a quelques choses, je pense.

    • Il existe des cycles : “let rec” dans de nombreuses langues permet de créer des structures “circulaires”. En dehors de cela, l’immuabilité n’implique généralement pas de cycles, mais cela enfreint la règle.
    • Les décomptes sont mauvais dans les listes : je ne sais pas si la collection à comptage de référence fonctionne bien avec, par exemple, les longues structures à liste unique que vous trouvez souvent dans FP (par exemple, lent, besoin de récursivité, …)
    • D’autres stratégies ont des avantages : comme vous le mentionnez, d’autres stratégies de GC sont généralement meilleures pour la localité de la mémoire.

    (Il était une fois, je pense que je le savais peut-être vraiment, mais maintenant j’essaie de me souvenir / spéculer, alors ne prenez pas cela comme une autorité.)

    Est-ce exact?

    Pas assez. Vous pouvez créer des structures de données cycliques en utilisant une programmation purement fonctionnelle simplement en définissant des valeurs mutuellement récursives en même temps. Par exemple, dans OCaml:

     let rec xs = 0::ys and ys = 1::xs 

    Cependant, il est possible de définir des langages qui rendent impossible la création de structures cycliques par conception. Le résultat est connu sous le nom de segment de mémoire unidirectionnel et son principal avantage est que le nettoyage de la mémoire peut être aussi simple que le comptage des références.

    Si oui, pourquoi pas eux?

    Certaines langues interdisent les cycles et utilisent le comptage de références. Erlang et Mathematica sont des exemples.

    Par exemple, dans Mathematica, lorsque vous référencez une valeur, vous en faites une copie profonde afin que la mutation de l’original ne modifie pas la copie:

     In[1] := xs = {1, 2, 3} Out[1] = {1, 2, 3} In[2] := ys = xs Out[2] = {1, 2, 3} In[3] := xs[[1]] = 5 Out[3] = 5 In[4] := xs Out[4] = {5, 2, 3} In[5] := ys Out[5] = {1, 2, 3} 

    Considérez cette allégorie à propos de David Moon , un inventeur de la machine Lisp :

    Un jour, un élève est venu à Moon et a dit: “Je comprends comment faire un meilleur ramasse-miettes. Nous devons garder un compte de référence des pointeurs sur chaque cons.”

    Moon a patiemment raconté à l’étudiant l’histoire suivante:

    “Un jour, un étudiant est venu à Moon et a dit:” Je comprends comment faire un meilleur ramasse-miettes …

    Le comptage des références est BEAUCOUP plus lent que celui du GC car ce n’est pas bon pour le CPU. Et GC la plupart du temps peut attendre le temps d’inactivité et le GC peut également être simultané (sur un autre thread). Donc, c’est le problème – GC est le moins mauvais et beaucoup d’essais l’ont montré.