En informática , el conteo de referencias es una técnica de programación que consiste en almacenar la cantidad de referencias , punteros o controladores a un recurso, como un objeto, un bloque de memoria, espacio en disco y otros.
En los algoritmos de recolección de basura , los recuentos de referencias se pueden usar para desasignar objetos que ya no son necesarios.
La principal ventaja del conteo de referencias sobre la recolección de basura de rastreo es que los objetos se recuperan tan pronto como ya no se pueden referenciar, y de forma incremental, sin pausas prolongadas para los ciclos de recolección y con una vida útil claramente definida de cada objeto. En aplicaciones en tiempo real o sistemas con memoria limitada, esto es importante para mantener la capacidad de respuesta. El conteo de referencias también es una de las formas más simples de administración de memoria para implementar. También permite una administración efectiva de recursos que no son de memoria, como los objetos del sistema operativo, que a menudo son mucho más escasos que la memoria (los sistemas de recolección de basura de rastreo usan finalizadores para esto, [ cita requerida ] pero la recuperación demorada puede causar problemas). Los conteos de referencias ponderados son una buena solución para la recolección de basura de un sistema distribuido.
Los ciclos de recolección de basura se activan con demasiada frecuencia si el conjunto de objetos activos llena la mayor parte de la memoria disponible; [ cita requerida ] requiere espacio adicional para ser eficiente. [ cita requerida ] El rendimiento del conteo de referencias no se deteriora a medida que disminuye la cantidad total de espacio libre. [2]
Los recuentos de referencias también son información útil para usar como entrada para otras optimizaciones en tiempo de ejecución. Por ejemplo, los sistemas que dependen en gran medida de objetos inmutables, como muchos lenguajes de programación funcional, pueden sufrir una penalización de eficiencia debido a las copias frecuentes. [ cita requerida ] Sin embargo, si el compilador (o sistema en tiempo de ejecución ) sabe que un objeto en particular tiene solo una referencia (como lo hace la mayoría en muchos sistemas), y que la referencia se pierde al mismo tiempo que se crea un nuevo objeto similar (como en la declaración de anexión de cadena str ← str + "a"), puede reemplazar la operación con una mutación en el objeto original.
El conteo de referencias en forma ingenua tiene tres desventajas principales sobre la recolección de basura de rastreo, y ambas requieren mecanismos adicionales para mejorarlas:
Además de esto, si la memoria se asigna desde una lista libre, el conteo de referencias sufre de una localidad deficiente. El conteo de referencias por sí solo no puede mover objetos para mejorar el rendimiento de la memoria caché, por lo que los recolectores de alto rendimiento también implementan un recolector de basura de rastreo. La mayoría de las implementaciones (como las de PHP y Objective-C) sufren de un rendimiento de caché deficiente ya que no implementan la copia de objetos. [3]
Cuando se trabaja con esquemas de recolección de basura, a menudo es útil pensar en el gráfico de referencia , que es un gráfico dirigido donde los vértices son objetos y hay un borde de un objeto A a un objeto B si A contiene una referencia a B. También tenemos un vértice o vértices especiales que representan las variables locales y las referencias contenidas en el sistema de tiempo de ejecución, y ningún borde va nunca a estos nodos, aunque los bordes pueden ir desde ellos a otros nodos.
En este contexto, el recuento de referencia simple de un objeto es el grado de entrada de su vértice. Eliminar un vértice es como recolectar un objeto. Solo se puede hacer cuando el vértice no tiene aristas entrantes, por lo que no afecta el grado de salida de ningún otro vértice, pero puede afectar el grado de entrada de otros vértices, lo que hace que sus objetos correspondientes también se recopilen si su grado de entrada también se convierte en 0 como resultado.
El componente conectado que contiene el vértice especial contiene los objetos que no se pueden recolectar, mientras que otros componentes conectados del gráfico solo contienen basura. Si se implementa un algoritmo de recolección de basura con recuento de referencias, entonces cada uno de estos componentes de basura debe contener al menos un ciclo; de lo contrario, se habrían recolectado tan pronto como su recuento de referencias (es decir, la cantidad de aristas entrantes) cayera a cero.
Aumentar o disminuir el recuento de referencias cada vez que se crea o se destruye una referencia puede afectar significativamente el rendimiento. Las operaciones no solo llevan tiempo, sino que también dañan el rendimiento de la memoria caché y pueden generar burbujas en la canalización . Incluso las operaciones de solo lectura, como calcular la longitud de una lista, requieren una gran cantidad de lecturas y escrituras para las actualizaciones de referencias con un recuento de referencias ingenuo.
Una técnica sencilla es que el compilador combine varias actualizaciones de referencias cercanas en una sola. Esto es especialmente eficaz para referencias que se crean y se destruyen rápidamente. Sin embargo, se debe tener cuidado de colocar la actualización combinada en la posición correcta para evitar una liberación prematura.
El método Deutsch-Bobrow de recuento de referencias aprovecha el hecho de que la mayoría de las actualizaciones de recuento de referencias se generan, de hecho, mediante referencias almacenadas en variables locales. Ignora estas referencias y solo cuenta las referencias en las estructuras de datos, pero antes de que se pueda eliminar un objeto con un recuento de referencias de cero, el sistema debe verificar con un escaneo de la pila y los registros que no exista ninguna otra referencia a él.
Otra técnica ideada por Henry Baker implica incrementos diferidos [4] , en la que las referencias que se almacenan en variables locales no incrementan inmediatamente el recuento de referencias correspondiente, sino que lo difieren hasta que sea necesario. Si dicha referencia se destruye rápidamente, entonces no hay necesidad de actualizar el contador. Esto elimina una gran cantidad de actualizaciones asociadas con referencias de corta duración (como el ejemplo anterior de recuento de longitud de lista). Sin embargo, si dicha referencia se copia en una estructura de datos, entonces el incremento diferido debe realizarse en ese momento. También es fundamental realizar el incremento diferido antes de que el recuento del objeto baje a cero, para evitar una liberación prematura.
Levanoni y Petrank obtuvieron una reducción drástica de la sobrecarga en las actualizaciones de contadores . [5] [6] Introducen el método de coalescencia de actualizaciones que fusiona muchas de las actualizaciones de recuento de referencias redundantes. Considere un puntero que en un intervalo dado de la ejecución se actualiza varias veces. Primero apunta a un objeto O1, luego a un objeto O2, y así sucesivamente hasta que al final del intervalo apunta a algún objeto On. Un algoritmo de recuento de referencias normalmente ejecutaría rc(O1)--, rc(O2)++, rc(O2)--, rc(O3)++, rc(O3)--, ..., rc(On)++. Pero la mayoría de estas actualizaciones son redundantes. Para tener el recuento de referencias evaluado correctamente al final del intervalo es suficiente realizar rc(O1)--y rc(On)++. El resto de las actualizaciones son redundantes.
En 2001, Levanoni y Petrank demostraron cómo utilizar dicha fusión de actualizaciones en un recopilador de recuento de referencias. Al utilizar la fusión de actualizaciones con un tratamiento adecuado de los nuevos objetos, se eliminan más del 99 % de las actualizaciones de contadores en las pruebas de rendimiento típicas de Java.
Curiosamente, la fusión de actualizaciones también elimina la necesidad de emplear operaciones atómicas durante las actualizaciones de punteros en un entorno concurrente, lo que resuelve los problemas de recuento de referencias en un entorno concurrente. Por lo tanto, la fusión de actualizaciones resuelve el tercer problema del recuento de referencias ingenuo (es decir, una sobrecarga costosa en un entorno concurrente). Levanoni y Petrank presentaron un algoritmo mejorado que puede ejecutarse simultáneamente con aplicaciones multiproceso que emplean solo una sincronización fina. [7]
El método de recuento de referencias ulteriores de Blackburn y McKinley de 2003 [8] combina el recuento de referencias diferido con un vivero de copias, y observa que la mayoría de las mutaciones de puntero se producen en objetos jóvenes. Este algoritmo logra un rendimiento comparable al de los recopiladores de copias generacionales más rápidos con los tiempos de pausa reducidos del recuento de referencias.
Tal vez la forma más obvia de manejar los ciclos de referencia es diseñar el sistema para evitar su creación. Un sistema puede prohibir explícitamente los ciclos de referencia; los sistemas de archivos con enlaces duros suelen hacerlo. El uso juicioso de referencias "débiles" (no contabilizadas) también puede ayudar a evitar los ciclos de retención; el marco Cocoa , por ejemplo, recomienda utilizar referencias "fuertes" para las relaciones padre-hijo y referencias "débiles" para las relaciones hijo-padre. [9]
Los sistemas también pueden estar diseñados para tolerar o corregir de alguna manera los ciclos que crean. Los desarrolladores pueden diseñar código para "destruir" explícitamente las referencias en una estructura de datos cuando ya no se necesitan, aunque esto tiene el costo de requerir que rastreen manualmente la vida útil de esa estructura de datos. Esta técnica se puede automatizar creando un objeto "propietario" que realiza el desmantelamiento cuando se destruye; por ejemplo, el destructor de un objeto Graph podría eliminar los bordes de sus GraphNodes, rompiendo los ciclos de referencia en el gráfico. Los ciclos incluso se pueden ignorar en sistemas con vidas cortas y una pequeña cantidad de basura cíclica, particularmente cuando el sistema se desarrolló utilizando una metodología de evitar estructuras de datos cíclicas siempre que sea posible, generalmente a expensas de la eficiencia.
Los científicos informáticos también han descubierto formas de detectar y recopilar ciclos de referencia automáticamente, sin necesidad de realizar cambios en el diseño de la estructura de datos. Una solución sencilla es utilizar periódicamente un recolector de basura de rastreo para recuperar ciclos; dado que los ciclos suelen constituir una cantidad relativamente pequeña de espacio recuperado, el recolector se puede ejecutar con mucha menos frecuencia que con un recolector de basura de rastreo normal.
Bacon describe un algoritmo de recolección de ciclos para el conteo de referencias que tiene similitudes con los recolectores de rastreo, incluidos los mismos límites de tiempo teóricos. Se basa en la observación de que un ciclo solo se puede aislar cuando un recuento de referencia se decrementa a un valor distinto de cero. Todos los objetos en los que esto ocurre se colocan en una lista de raíces y luego, periódicamente, el programa busca ciclos entre los objetos alcanzables desde las raíces. Sabe que ha encontrado un ciclo que se puede recolectar cuando al decrementar todos los recuentos de referencias en un ciclo de referencias, todos ellos se reducen a cero. [10] Una versión mejorada de este algoritmo de Paz et al. [11] puede ejecutarse simultáneamente con otras operaciones y mejorar su eficiencia mediante el uso del método de actualización por coalescencia de Levanoni y Petrank. [5] [6]
Aunque es posible aumentar los recuentos de referencias simples de diversas maneras, a menudo se puede encontrar una mejor solución realizando el recuento de referencias de una manera fundamentalmente diferente. Aquí describimos algunas de las variantes del recuento de referencias y sus ventajas e inconvenientes.
En el recuento de referencias ponderadas, a cada referencia se le asigna un peso y cada objeto no registra la cantidad de referencias que lo remiten, sino el peso total de las referencias que lo remiten. La referencia inicial a un objeto recién creado tiene un peso grande, como 2 16 . Siempre que se copia esta referencia, la mitad del peso va a la nueva referencia y la otra mitad se queda con la referencia anterior. Dado que el peso total no cambia, no es necesario actualizar el recuento de referencias del objeto.
Al destruir una referencia, el peso total se reduce en el peso de esa referencia. Cuando el peso total se convierte en cero, se destruyen todas las referencias. Si se intenta copiar una referencia con un peso de 1, la referencia debe "obtener más peso" sumando el peso total y luego agregando este nuevo peso a la referencia y luego dividiéndolo. Una alternativa en esta situación es crear un objeto de referencia de indirección , cuya referencia inicial se crea con un peso grande que luego se puede dividir.
La propiedad de no tener que acceder a un recuento de referencias cuando se copia una referencia es particularmente útil cuando el recuento de referencias del objeto es costoso de acceder, por ejemplo, porque está en otro proceso, en el disco o incluso en una red. También puede ayudar a aumentar la concurrencia al evitar que muchos subprocesos bloqueen un recuento de referencias para aumentarlo. Por lo tanto, el recuento de referencias ponderado es más útil en aplicaciones paralelas, multiproceso, de base de datos o distribuidas.
El problema principal del conteo de referencias ponderado simple es que, para destruir una referencia, todavía es necesario acceder al conteo de referencias y, si se destruyen muchas referencias, esto puede provocar los mismos cuellos de botella que buscamos evitar. Algunas adaptaciones del conteo de referencias ponderado intentan evitar esto transfiriendo el peso de una referencia moribunda a una referencia activa.
El recuento de referencia ponderado fue ideado independientemente por Bevan [12] y Watson & Watson [13] en 1987.
En el recuento de referencias indirectas, es necesario realizar un seguimiento de la fuente de la referencia. Esto significa que se mantienen dos referencias al objeto: una directa que se utiliza para invocaciones y una indirecta que forma parte de un árbol de difusión, como en el algoritmo de Dijkstra-Scholten , que permite que un recolector de basura identifique objetos inactivos. Este enfoque evita que un objeto se descarte prematuramente.
Como algoritmo de recopilación, el recuento de referencias registra, para cada objeto, el número de referencias que otros objetos hacen a él. Si el recuento de referencias de un objeto llega a cero, el objeto se vuelve inaccesible y puede destruirse.
Cuando se destruye un objeto, también se reducen los recuentos de referencias de los objetos a los que hace referencia dicho objeto. Por este motivo, eliminar una única referencia puede provocar que se liberen muchos objetos. Una modificación habitual permite que el recuento de referencias sea incremental: en lugar de destruir un objeto en cuanto su recuento de referencias se vuelve cero, se lo añade a una lista de objetos sin referencias y, periódicamente (o según sea necesario), se destruyen uno o más elementos de esta lista.
Los recuentos de referencias simples requieren actualizaciones frecuentes. Siempre que se destruye o sobrescribe una referencia, el recuento de referencias del objeto al que hace referencia disminuye, y siempre que se crea o copia una, el recuento de referencias del objeto al que hace referencia aumenta.
El conteo de referencias también se utiliza en sistemas de archivos y sistemas distribuidos, donde la recolección de basura de seguimiento no incremental completa consume demasiado tiempo debido al tamaño del gráfico de objetos y la baja velocidad de acceso. [14]
El Modelo de objetos componentes (COM) de Microsoft y WinRT hacen un uso generalizado del recuento de referencias. De hecho, dos de los tres métodos que todos los objetos COM deben proporcionar (en la interfaz IUnknown ) incrementan o decrementan el recuento de referencias. Gran parte del shell de Windows y muchas aplicaciones de Windows (incluidos MS Internet Explorer , MS Office e innumerables productos de terceros) están basados en COM, lo que demuestra la viabilidad del recuento de referencias en sistemas a gran escala. [ cita requerida ]
Una de las principales motivaciones para el recuento de referencias en COM es permitir la interoperabilidad entre diferentes lenguajes de programación y sistemas de ejecución. Un cliente solo necesita saber cómo invocar métodos de objeto para administrar el ciclo de vida del objeto; por lo tanto, el cliente está completamente abstraído de cualquier asignador de memoria que utilice la implementación del objeto COM. Como ejemplo típico, un programa de Visual Basic que utiliza un objeto COM es independiente de si ese objeto fue asignado (y luego debe desasignarse) por un asignador de C++ u otro componente de Visual Basic.
C++ no realiza el recuento de referencias de forma predeterminada, cumpliendo con su filosofía de no agregar funcionalidad que pueda generar sobrecargas cuando el usuario no la haya solicitado explícitamente. Se puede acceder a los objetos que se comparten pero no se poseen a través de una referencia, un puntero sin formato o un iterador (una generalización conceptual de los punteros).
Sin embargo, por la misma razón, C++ proporciona formas nativas para que los usuarios opten por dicha funcionalidad: C++11 proporciona punteros inteligentes contados por referencia , a través de la std::shared_ptrclase, lo que permite la gestión automática de memoria compartida de objetos asignados dinámicamente. Los programadores pueden usar esto junto con punteros débiles (a través de std::weak_ptr) para romper dependencias cíclicas. Los objetos que se asignan dinámicamente pero no están destinados a ser compartidos pueden tener su vida útil administrada automáticamente utilizando un std::unique_ptr.
Además, la semántica de movimiento de C++11 reduce aún más el grado en el que es necesario modificar los recuentos de referencias al eliminar la copia profunda que normalmente se utiliza cuando una función devuelve un objeto, ya que permite una copia simple del puntero de dicho objeto.
Los frameworks Cocoa y Cocoa Touch de Apple (y frameworks relacionados, como Core Foundation ) usan conteo de referencias manual, de manera muy similar a COM . Tradicionalmente, esto se lograba cuando el programador enviaba manualmente retainmensajes releasea los objetos, pero el conteo automático de referencias , una característica del compilador de Clang que inserta automáticamente estos mensajes según sea necesario, se agregó en iOS 5 [15] y Mac OS X 10.7 . [16] Mac OS X 10.5 introdujo un recolector de basura de rastreo como una alternativa al conteo de referencias, pero quedó obsoleto en OS X 10.8 y se eliminó de la biblioteca de tiempo de ejecución Objective-C en macOS Sierra . [17] [18] iOS nunca ha admitido un recolector de basura de rastreo.
Delphi no es en su mayor parte un lenguaje de recolección de basura, en el sentido de que los tipos definidos por el usuario deben asignarse y desasignarse manualmente; sin embargo, sí proporciona recolección automática mediante el recuento de referencias para algunos tipos integrados, como cadenas, matrices dinámicas e interfaces, para facilitar su uso y simplificar la funcionalidad genérica de la base de datos. Depende del programador decidir si utilizar los tipos integrados; los programadores de Delphi tienen acceso completo a la gestión de memoria de bajo nivel como en C/C++. Por lo tanto, todo el costo potencial del recuento de referencias de Delphi se puede eludir fácilmente, si se desea.
Algunas de las razones por las que se puede haber preferido el recuento de referencias a otras formas de recolección de basura en Delphi incluyen:
El marco de programación orientada a objetos GObject implementa el conteo de referencias en sus tipos base, incluidas las referencias débiles . El incremento y decremento de referencias utiliza operaciones atómicas para la seguridad de subprocesos. Una cantidad significativa del trabajo de escritura de enlaces a GObject desde lenguajes de alto nivel consiste en adaptar el conteo de referencias de GObject para que funcione con el sistema de gestión de memoria propio del lenguaje.
El lenguaje de programación Vala utiliza el conteo de referencias de GObject como su sistema principal de recolección de basura, junto con el manejo de cadenas con gran cantidad de copias. [19]
Perl también utiliza el conteo de referencias, sin ningún manejo especial de referencias circulares, aunque (como en Cocoa y C++ arriba), Perl sí admite referencias débiles, lo que permite a los programadores evitar la creación de un ciclo.
PHP utiliza un mecanismo de conteo de referencias para la gestión de sus variables internas. [20] Desde PHP 5.3, implementa el algoritmo del artículo de Bacon mencionado anteriormente. PHP permite activar y desactivar la recopilación de ciclos con funciones de nivel de usuario. También permite forzar manualmente la ejecución del mecanismo de purga.
Python también utiliza el conteo de referencias y ofrece detección de ciclos (y puede recuperar ciclos de referencia). [21]
Al igual que otros lenguajes de bajo nivel, Rust no ofrece un recuento de referencias de forma predeterminada. En cambio, cualquier tipo construido se descartará cuando quede fuera del alcance. Cuando un programador necesita definir el alcance de un tipo construido, suele utilizar tiempos de vida.
Sin embargo, el lenguaje también ofrece varias alternativas a las formas complejas de gestión de memoria. La funcionalidad de conteo de referencias la proporcionan los tipos Rcy Arc, que son no atómicos y atómicos respectivamente.
Por ejemplo, el tipo Rc<T>proporciona propiedad compartida de un valor de tipo T, asignado en el montón para múltiples referencias a sus datos. [22]
utilizar std :: rc :: Rc ; estructura Cat { color : Cadena , } fn main () { let cat = Cat { color : "negro" .to_string () } ; let cat = Rc :: new ( cat ); } El uso de estas construcciones permite a los programadores evitar tiempos de vida por un pequeño costo de tiempo de ejecución. Ambos contadores de referencia llevan un registro de la cantidad de propietarios, ya que deben eliminarse cuando no quedan propietarios.
Una faceta notable de estos tipos está relacionada con su uso como referencia compartida. En Rust, las referencias compartidas no pueden mutar los datos que contienen, por lo que Rca menudo se incluyen con Cell, y Arccon Mutex, en contextos donde es necesaria la mutabilidad interna.
La mutabilidad interior UnsafeCelltambién tiene costos de rendimiento, por lo que, para obtener el máximo rendimiento, algunas aplicaciones pueden requerir complejidad adicional. [23]
Squirrel utiliza el conteo de referencias con detección de ciclos. Este pequeño lenguaje es relativamente desconocido fuera de la industria de los videojuegos; sin embargo, es un ejemplo concreto de cómo el conteo de referencias puede ser práctico y eficiente (especialmente en entornos de tiempo real). [ cita requerida ]
Swift utiliza el conteo de referencias para rastrear y administrar la memoria de las instancias de clase, y proporciona la weakpalabra clave para crear referencias débiles. Las instancias de tipos de valor no utilizan el conteo de referencias. [24]
Tcl 8 utiliza el conteo de referencias para la gestión de la memoria de los valores ( estructuras Tcl Obj ). Dado que los valores de Tcl son inmutables, es imposible formar ciclos de referencia y no se necesita ningún esquema de detección de ciclos. Las operaciones que reemplazarían un valor con una copia modificada generalmente se optimizan para modificar el original cuando su conteo de referencias indica que no se comparte. Las referencias se cuentan a nivel de estructura de datos, por lo que no surgen los problemas con actualizaciones muy frecuentes que se analizaron anteriormente.
Xojo también utiliza el conteo de referencias, sin ningún manejo especial de referencias circulares, aunque (como en Cocoa y C++ arriba), Xojo admite referencias débiles, lo que permite a los programadores evitar la creación de un ciclo.
Muchos sistemas de archivos mantienen recuentos de referencias a cualquier bloque o archivo en particular, por ejemplo, el recuento de enlaces de inodo en los sistemas de archivos de estilo Unix , que generalmente se conocen como enlaces duros . Cuando el recuento llega a cero, el archivo se puede desasignar de manera segura. Si bien aún se pueden realizar referencias desde directorios , algunos Unix solo permiten referencias desde procesos activos y puede haber archivos que existan fuera de la jerarquía del sistema de archivos.
{{cite conference}}: CS1 maint: multiple names: authors list (link){{cite journal}}: CS1 maint: multiple names: authors list (link)