Quanto sono comuni i riferimenti circolari? Il GC conteggio di riferimento funziona correttamente?

5

Quanto sono comuni i riferimenti circolari? Meno sono comuni, meno casi difficili si hanno se si scrive in una lingua con solo conteggio di riferimento-GC. Ci sono casi in cui non funzionerebbe bene per rendere uno dei riferimenti un riferimento "debole" in modo che il conteggio dei riferimenti funzioni ancora?

Sembra che dovresti essere in grado di usare un linguaggio solo con il conteggio dei riferimenti e i riferimenti deboli e fare in modo che le cose funzionino bene la maggior parte del tempo, con l'obiettivo dell'efficienza. Potresti anche avere strumenti per aiutarti a rilevare perdite di memoria causate da riferimenti circolari. Pensieri, qualcuno?

Sembra che Python usi il conteggio dei riferimenti (non so se usa occasionalmente o meno un collezionista di tracing) e so che Vala usa il conteggio dei riferimenti con riferimenti deboli; So che è stato fatto prima, ma quanto bene avrebbe funzionato?

    
posta compman 28.12.2010 - 16:13
fonte

8 risposte

2

I riferimenti deboli funzionano alla grande per i loop di interruzione, purché sia chiaro che viene eseguito un ciclo e finché lo sviluppatore provvede a farlo con un riferimento debole. Questo non è lo stesso di un GC più robusto, che ha lo scopo di gestire tali cose automaticamente in modo che lo sviluppatore non debba pensarci affatto.

    
risposta data 28.12.2010 - 16:24
fonte
6

How common are circular references?

Quanto sono comuni elenchi collegati doppiamente ?

It seems like you should be able to have a language only use reference counting and weak references and have things work just fine most of the time, with the goal of efficiency.

In questo caso, non pensi che le implementazioni conteggiate di riferimento sarebbero state comuni quando ti sei iscritto alla festa?

    
risposta data 28.12.2010 - 18:13
fonte
5

Sono molto comuni. Un esempio onnipresente sono strutture gerarchiche in cui ogni nodo ha un puntatore al suo genitore e, naturalmente, il genitore ha una collezione di suoi figli. Gli strumenti dell'interfaccia utente come Swing funzionano in questo modo.

    
risposta data 28.12.2010 - 16:17
fonte
2

Hai ragione, dovresti essere in grado di eseguire la garbage collection usando solo il conteggio dei riferimenti. Objective-C su iPhone è un esempio di piattaforma che fa proprio questo.

Perché non è fatto nella pratica? Poiché il codice sciatto e le perdite di memoria sono una realtà e il fatto di avere un computer con loro consente automaticamente a ogni maiale medio di scrivere codice che non esaurisce costantemente la memoria.

    
risposta data 28.12.2010 - 19:30
fonte
1

Modifica: riscritto per meglio esprimere il mio punto di vista.

1: Relazioni entità

Ho incontrato questo problema con le entità. Supponiamo che abbiano due classi, autore e articolo. Inoltre ho un render (Autore) e render (articolo) che restituiscono documenti html che descrivono entrambi gli elementi. L'autore avrà un elenco di articoli e l'articolo avrà informazioni sull'autore.

L'autore e l'articolo avranno un ciclo di riferimento. Possiamo tentare di risolvere questo ciclo introducendo un riferimento debole. Cosa succede se il riferimento è dall'autore all'articolo? Quindi il rendering (articolo) non manterrà i riferimenti all'Autore in vita e quindi l'oggetto verrà deallocato prima di essere utilizzato per ottenere il nome dell'autore. Ma, se il riferimento è da Articolo a Autore che funziona bene, ma render (Autore) non registrerà alcun riferimento contro Articolo e saranno deallocati prima che i loro titoli possano essere recuperati.

L'introduzione di riferimenti deboli risolve il problema fintanto che tutte le relazioni hanno una direzione definita in cui la direzione opposta è chiaramente secondaria. Ma alcune relazioni non funzionano in questo modo.

D'altra parte: Questo problema preciso deriva solo nei casi in cui abbiamo associazioni tra oggetti. Questo è ogni oggetto ha bisogno di tenere un riferimento reciproco all'altro. Forse la lingua potrebbe supportare tali associazioni in modo naturale e quindi dare loro un trattamento speciale con il conteggio dei riferimenti. Potrebbe essere fatto funzionare.

2: Strutture dati

Le strutture dati hanno spesso cicli di riferimento. L'esempio più comune è una lista doppiamente collegata. Inoltre, non è raro che la struttura ad albero abbia puntatori prossimi / precedenti nelle foglie per una rapida iterazione.

D'altra parte: sospetto che la maggior parte di questi cicli siano effettivamente interrotti dal funzionamento della struttura dati. Ad esempio, quando un oggetto viene rimosso da un elenco collegato, i due riferimenti al nodo verranno ripristinati eliminando così i riferimenti.

3: eliminazioni deterministiche

Una ragione per usare il conteggio dei riferimenti è che si ottengono cancellazioni deterministiche. Gli oggetti saranno cancellati in tempi prevedibili. Ciò significa che puoi fare cose come chiudere file, rilasciare blocchi, ecc. Perché sai che gli oggetti verranno eliminati in modo tempestivo.

Il problema è che questo tende a rompersi. Se accidentalmente creo un ciclo i miei file non vengono chiusi e le mie serrature non vengono rilasciate. Inoltre, non ricevo errori come risultato di ciò.

Questo non è davvero un problema con il conteggio dei riferimenti. È un caso in cui il vantaggio (eliminazioni deterministiche) non funziona davvero lasciandomi con meno motivi per volere il conteggio dei riferimenti.

D'altra parte: si potrebbe sostenere che il vero problema è che non abbiamo effettuato test automatici per garantire che gli oggetti siano stati distrutti. Se avessi una cosa del genere saremmo informati quando questo non ha funzionato.

4: velocità

Un altro motivo per cui il conteggio dei riferimenti è perché è più veloce. Tuttavia, sembra che questo non sia effettivamente vero. Tutti gli incrementi e decrementi sono in realtà piuttosto costosi. (Diventa molto brutto quando si inizia a considerare il threading.) Quindi non è chiaro che qui si ottenga un vantaggio in termini di velocità. In effetti, potrebbe essere più veloce usare un'altra tecnica GC.

5: Convenience

Se si lavora in un linguaggio di conteggio dei riferimenti, devo preoccuparmi di non creare cicli di riferimento. Mi sono trovato a creare cicli su base regolare. Nella maggior parte dei casi ho potuto risolvere questo problema introducendo un riferimento debole. Ma perché preoccuparsi? Sembra che ci siano alcuni vantaggi nel contare i conteggi, ma non sembra che si siano verificati (Vedi 3 & 4) Di conseguenza, non sembra valsa la pena di combattere i cicli.

In conclusione

Il conteggio dei riferimenti semplicemente non sembra fornire abbastanza benefici rispetto alle tipiche implementazioni dei GC per compensare il mal di testa in più che fornisce ai programmatori.

    
risposta data 02.01.2011 - 23:58
fonte
0

Python e Objective-C usano il conteggio dei riferimenti e sono le lingue dietro alcuni importanti lavori nel software. Come con qualsiasi altra strategia di raccolta dei rifiuti, le implementazioni di conteggio dei riferimenti possono essere ottimizzate per renderle efficienti per il caso comune.

Le lingue che optano per il conteggio dei riferimenti di solito includono diverse strutture di dati importanti nella definizione del linguaggio o nelle librerie standard, quindi i programmatori non possono pensare a come avviene la gestione della memoria.

    
risposta data 28.12.2010 - 20:19
fonte
0

È possibile utilizzare il conteggio dei riferimenti per qualsiasi oggetto che non può mai riferirsi a se stesso, in modo transitorio. Questo è simile al tipo di analisi euristica che puoi fare per determinare che una funzione è non rientranti, quindi può essere chiamata senza ricorso a uno stack in un ambiente a thread singolo.

In un linguaggio tipizzato staticamente sicuro per il tipo, questo può essere determinato staticamente. Se è possibile ordinare un set di classi concrete in modo che le proprietà di ciascuna classe possano contenere solo riferimenti a classi successive, allora tale insieme di tipi può essere conteggiato con riferimento.

Quindi, data una classe Java point,

final class Point {
  double x;
  double y;
}

Sappiamo che la classe non contiene riferimenti, quindi una VM potrebbe allocare% istanze diPoint in un blocco di memoria conteggiato di riferimento come ottimizzazione.

E dato una semplice classe come

final class Person {
  String name;
}

poiché sappiamo che String non può riferirsi a Person , potremmo fare un'ottimizzazione di conteggio di riferimento simile per istanze di Person .

Ma la seguente classe non può essere conteggiata come riferimento:

final class Pair {
  Object a;
  Object b;
}

perché a potrebbe una coppia o potrebbe essere un oggetto che fa riferimento a Pair .

La seguente classe non può essere contata conteggio:

final class Tuple {
  List<Object> items;
}

poiché gli articoli potrebbero contenere riferimenti a Tuple s oppure a oggetti che possono contenere riferimenti a Tuple s.

    
risposta data 08.01.2011 - 16:30
fonte
0

In realtà dipende dalla lingua.

Le lingue (come la maggior parte dei linguaggi funzionali) che sottolineano l'immutabilità delle strutture dati sono, per loro natura, aciclici (poiché un valore può riferirsi solo a valori precedenti).

Pertanto, scommetto che Reference Counting è ottimo per loro:)

Esistono altre ottimizzazioni che GC può offrire. Ad esempio un GC in grado di spostare i dati in memoria potrebbe essere in grado di ottenere valori "collegati" più vicini tra loro, che migliorano gli accessi alla cache durante il calcolo.

    
risposta data 09.01.2011 - 13:20
fonte

Leggi altre domande sui tag