Perché non puramente linguaggi funzionali usano il conteggio di riferimento?

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

Domanda

In linguaggi puramente funzionali, i dati è immutabile. Con il conteggio di riferimento, creando un ciclo di riferimento richiede la modifica dei dati già creati. Sembra puramente linguaggi funzionali potrebbero utilizzare conteggio riferimento senza preoccuparsi della possibilità di cicli. Am è giusto? Se sì, perché non è vero?

Ho capito che il conteggio di riferimento è più lento di GC in molti casi, ma almeno riduce tempi di pausa. Sarebbe bello avere la possibilità di utilizzare il conteggio di riferimento nei casi in cui i tempi di pausa sono cattivi.

È stato utile?

Soluzione

La tua domanda si basa su un presupposto errato. E 'perfettamente possibile avere riferimenti circolari e dati immutabili. Si consideri il seguente esempio C # che utilizza i dati immutabili per creare un riferimento circolare. 

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

Questo tipo di trucco può essere fatto in molti linguaggi funzionali e, quindi, qualsiasi meccanismo di raccolta deve fare i conti con la possibilità di riferimenti circolari. Non dico un meccanismo di conteggio ref è impossibile con un riferimento circolare, solo che deve essere trattata.

Modifica da ephemient

In risposta al commento ... questo è banale in Haskell 

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

e malapena qualsiasi sforzo in più in SML. 

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

No mutazione richiesto.

Altri suggerimenti

Rispetto ad altre lingue gestite come Java e C #, lingue puramente funzionali allocano come un matto . Allocano anche oggetti di diverse dimensioni. La strategia di allocazione veloce noto è allocare spazio contiguo (talvolta chiamato "vivaio") e per prenotare un registro hardware per puntare al successivo spazio libero disponibile. Allocazione dal mucchio diventa veloce come allocazione da una pila.

conteggio di riferimento è fondamentalmente incompatibile con questa strategia di allocazione. conteggio Ref mette oggetti nelle liste liberi e li porta di nuovo. conteggio Ref ha anche notevoli spese generali necessarie per aggiornare i conteggi ref come vengono creati nuovi oggetti (che, come notato sopra, puro linguaggi funzionali fanno come un matto).

conteggio di riferimento tende a fare molto bene in situazioni come queste:

  • Quasi tutta la memoria heap è utilizzato per contenere gli oggetti dal vivo.
  • ripartizione ed assegnazione puntatore sono frequenti rispetto alle altre operazioni.
  • I riferimenti possono essere gestiti in un altro processore o computer.

Per capire come i migliori sistemi di ref-conteggio ad alte prestazioni di lavoro di oggi, cercare il lavoro di David bacon e Erez Petrank .

Ci sono alcune cose, credo.

  • Ci sono cicli : "let rec" in molte lingue fa permettono strutture "circolari" da creare. Oltre a questo, l'immutabilità solito non implica alcun ciclo, ma questo rompe la regola.
  • Ref-conti sono affatto male liste : Non so che la raccolta di riferimento contato funziona bene con per esempio lungo le strutture che si trovano spesso in FP singolarmente-linked-list (per esempio lenta, necessità di garantire ricorsiva in coda, ...)
  • Altre strategie avere benefici : Come si allude ad, altre strategie GC sono ancora solito meglio per località memoria

(C'era una volta penso che forse davvero 'sapevo' questo, ma ora sto cercando di ricordare / speculare, in modo da non prendere questo come qualsiasi autorità.)

questa allegoria ha parlato di David luna , un inventore della Lisp Machine :

  

Un giorno uno studente è venuto a Luna e ha detto: "Ho capito come fare una migliore garbage collector Dobbiamo mantenere un conteggio di riferimento dei puntatori ad ogni cons."

     

Luna pazientemente ha detto lo studente la seguente storia:

     
    

"Un giorno uno studente è venuto a Luna e ha detto: 'ho capito come fare una migliore garbage collector ...

  
  

Am è giusto?

Non proprio. È possibile creare strutture di dati ciclici con programmazione puramente funzionale semplicemente definendo valori mutuamente ricorsive allo stesso tempo. Per esempio, in OCaml: 

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

Tuttavia, è possibile definire le lingue che rendono impossibile la creazione di strutture cicliche di progettazione. Il risultato è noto come mucchio unidirezionale e il suo vantaggio principale è che garbage collection può essere semplice come il conteggio di riferimento.

  

Se è così, perché non è vero?

Alcune lingue vietano cicli e utilizzare il conteggio di riferimento. Erlang e Mathematica sono esempi.

Per esempio, in Mathematica quando si fa riferimento a un valore che si fare una copia completa di esso in modo mutando l'originale non mutare la copia: 

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}

conteggio di riferimento è molto più lenta di GC perché non è buono per la CPU. E GC maggior parte del tempo può attendere per il tempo di inattività e anche GC può essere simultanea (su un altro thread). Ecco, questo è il problema -. GC è meno male e un sacco di tentativi dimostrato che

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top