Pourquoi les langages fonctionnels non purement utiliser le comptage de référence?

StackOverflow https://stackoverflow.com/questions/791437

Question

Dans les langues purement fonctionnelles, les données sont immuables. Avec comptage de référence, la création d'un cycle de référence nécessite la modification des données déjà créées. Il semble que purement langages fonctionnels peuvent utiliser le comptage de référence sans se soucier de la possibilité de cycles. Am est juste? Si oui, pourquoi pas?

Je comprends que le comptage de référence est plus lent que GC dans de nombreux cas, mais au moins il réduit les temps de pause. Il serait agréable d'avoir la possibilité d'utiliser le comptage de référence dans les cas où les temps de pause sont mauvais.

Était-ce utile?

La solution

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 donc tout mécanisme de collecte doit faire face à la possibilité de références circulaires. Je ne dis pas un mécanisme de comptage ref est impossible avec une référence circulaire, juste qu'il doit être traité.

Modifier par ephemient

En réponse au commentaire ... ceci est assez trivial dans Haskell 

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

et à peine plus d'effort dans SML. 

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

Aucune mutation nécessaire.

Autres conseils

Par rapport à d'autres langues gérées comme Java et C #, langages purement fonctionnels allouent comme un fou . Ils attribuent également des objets de différentes tailles. La stratégie d'allocation la plus rapide connue est d'allouer de l'espace libre contigu (parfois appelé une « pépinière ») et de réserver un registre de matériel pour pointer vers le prochain espace libre disponible. Allocation du tas devient aussi vite que l'allocation d'une pile.

Le compte de référence est fondamentalement incompatible avec cette stratégie d'allocation. comptage Ref met des objets sur les listes libres et les redécolle. comptage Ref a également des frais généraux importants nécessaires pour mettre à jour compte ref comme de nouveaux objets sont créés (qui, comme indiqué ci-dessus, purs langages fonctionnels font comme un fou).

Le compte de référence tend à faire très bien dans des situations comme celles-ci:

  • Presque toute la mémoire de tas est utilisé pour tenir des objets vivants.
  • Allocation et affectation du pointeur sont rares par rapport à d'autres opérations.
  • Les références peuvent être gérés sur un autre processeur ou ordinateur.

Pour comprendre comment les meilleurs systèmes de comptage ref haute performance fonctionnent aujourd'hui, regardez le travail de David Bacon et Erez Petrank .

Il y a quelques petites choses, je pense.

  • Il sont cycles : "let rec" dans de nombreuses langues ne permet des structures "circulaires" à créer. En dehors de cela, immuabilité ne signifie généralement pas de cycles, mais cela brise la règle.
  • Ref-compte sont mauvais à la liste : Je ne sais pas que la collecte compté référence fonctionne bien avec par exemple longue structures liste simplement chaînée vous souvent trouverez dans FP (par exemple lent, doivent assurer récursif queue, ...)
  • D'autres stratégies ont des avantages : Comme vous faites allusion, d'autres stratégies de GC sont encore généralement mieux pour la localisation de mémoire

(une fois je pense que je peut-être vraiment « savait », mais maintenant je suis en train de se rappeler / spéculer, alors ne prenez pas cela comme une autorité.)

cette allégorie a parlé David lune , un inventeur de Lisp machine:

  

Un jour, un étudiant est venu à la Lune et dit: «Je comprends comment faire un meilleur éboueur Nous devons garder un compte de référence des pointeurs à chaque contre. »

     

Lune patiemment dit l'étudiant l'histoire suivante:

     
    

"Un jour, un étudiant est venu à la Lune et dit: « Je comprends comment faire un meilleur éboueur ...

  
  

Am est juste?

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

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

Cependant, il est possible de définir des langages qui ne permettent pas de créer des structures cycliques par la conception. Le résultat est connu comme tas unidirectionnel et son principal avantage est que la collecte des ordures peut être aussi simple que le comptage de référence.

  

Si oui, pourquoi pas?

Certaines langues n'interdisent les cycles et utiliser le comptage de référence. Erlang et Mathematica sont des exemples.

Par exemple, dans Mathematica lorsque vous faites référence à une valeur que vous faites une copie en profondeur de celui-ci si l'original muter ne mute 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}

Le compte de référence est beaucoup plus lent que GC parce qu'il est pas bon pour CPU. Et GC la plupart du temps peut attendre que le temps de repos et aussi GC peut être simultanée (sur un autre thread). Voilà donc le problème -. GC est moins mal et beaucoup d'essais montré que

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top