En informática , el recuento de referencias es una técnica de programación para almacenar el número de referencias , punteros o identificadores de un recurso, como un objeto, un bloque de memoria, espacio en disco y otros.
En los algoritmos de recolección de basura , se pueden usar recuentos de referencias para desasignar objetos que ya no son necesarios.
La principal ventaja del recuento de referencias sobre la recolección de basura de rastreo es que los objetos se recuperan tan pronto como ya no se puede hacer referencia a ellos, y de forma incremental, sin largas pausas en los ciclos de recolección y con una vida útil de cada objeto claramente definida. En aplicaciones en tiempo real o sistemas con memoria limitada, esto es importante para mantener la capacidad de respuesta. El recuento de referencias también se encuentra entre las formas más sencillas de implementar de gestión de memoria. También permite una gestión eficaz de recursos que no son memoria, como objetos del sistema operativo, que a menudo son mucho más escasos que la memoria (los sistemas de seguimiento de recolección de basura utilizan finalizadores para esto, [ cita necesaria ] pero la recuperación retrasada puede causar problemas). Los recuentos de referencia ponderados son una buena solución para la recolección de basura en un sistema distribuido.
Los ciclos de recolección de basura de seguimiento se activan con demasiada frecuencia si el conjunto de objetos activos llena la mayor parte de la memoria disponible; [ cita necesaria ] requiere espacio adicional para ser eficiente. [ cita necesaria ] El rendimiento del recuento 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 de tiempo de ejecución. Por ejemplo, los sistemas que dependen en gran medida de objetos inmutables , como muchos lenguajes de programación funcionales, pueden sufrir una pérdida de eficiencia debido a las copias frecuentes. [ cita necesaria ] Sin embargo, si el compilador (o sistema de ejecución ) sabe que un objeto en particular tiene solo una referencia (como la mayoría lo hace en muchos sistemas), y que la referencia se pierde al mismo tiempo que se crea un nuevo objeto similar ( como en la instrucción de agregar cadena str ← str + "a"), puede reemplazar la operación con una mutación en el objeto original.
El recuento de referencias en forma ingenua tiene tres desventajas principales sobre la recolección de basura de rastreo, las cuales requieren mecanismos adicionales para mejorar:
Además de esto, si la memoria se asigna desde una lista libre, el recuento de referencias adolece de una localidad deficiente. El recuento de referencias por sí solo no puede mover objetos para mejorar el rendimiento de la caché, por lo que los recolectores de alto rendimiento también implementan un recolector de basura de seguimiento. 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 trata de 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 una arista de un objeto A a un objeto B si A tiene una referencia a B. También tienen un vértice o vértices especiales que representan las variables locales y las referencias mantenidas por el sistema de ejecución, y ninguna arista va nunca a estos nodos, aunque las aristas 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. Sólo se puede hacer cuando el vértice no tiene aristas entrantes, por lo que no afecta el grado exterior de ningún otro vértice, pero puede afectar el grado interior de otros vértices, haciendo que sus objetos correspondientes también se recopilen si sus como resultado, in-grade también se convierte en 0.
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 recopilado tan pronto como su recuento de referencia (es decir, el número de flancos entrantes) cayó a cero.
Incrementar y disminuir el recuento de referencias cada vez que se crea o destruye una referencia puede impedir significativamente el rendimiento. Las operaciones no solo toman tiempo, sino que dañan el rendimiento de la 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 conteo de referencias ingenuo.
Una técnica sencilla consiste en que el compilador combine varias actualizaciones de referencias cercanas en una sola. Esto es especialmente eficaz para referencias que se crean y 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 del recuento de referencias se generan a partir de 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 cero, el sistema debe verificar con un escaneo de la pila y los registros que todavía no existe ninguna otra referencia.
Otra técnica ideada por Henry Baker implica incrementos diferidos , [4] en los 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, no es necesario actualizar el contador. Esto elimina una gran cantidad de actualizaciones asociadas con referencias de corta duración (como el ejemplo anterior de conteo 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 caiga a cero, para evitar una liberación prematura.
Levanoni y Petrank obtuvieron una reducción espectacular de los gastos generales de actualización de los contadores . [5] [6] Introducen el método de fusión de actualizaciones que fusiona muchas de las actualizaciones redundantes del recuento de referencias. Considere un puntero que en un intervalo determinado de 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 evaluar correctamente el recuento de referencia al final del intervalo basta con realizar rc(O1)--y rc(On)++. El resto de actualizaciones son redundantes.
Levanoni y Petrank mostraron en 2001 cómo utilizar dicha actualización fusionada en un recopilador de recuento de referencias. Cuando se utiliza la combinación de actualizaciones con un tratamiento adecuado de nuevos objetos, más del 99% de las actualizaciones del contador se eliminan para los puntos de referencia típicos de Java.
Curiosamente, la fusión de actualizaciones también elimina la necesidad de emplear operaciones atómicas durante las actualizaciones del puntero en una configuración concurrente, lo que resuelve problemas de recuento de referencias en una configuración concurrente. Por lo tanto, la fusión de actualizaciones resuelve el tercer problema del recuento ingenuo de referencias (es decir, una sobrecarga costosa en un entorno concurrente). Levanoni y Petrank presentaron un algoritmo mejorado que puede ejecutarse simultáneamente con aplicaciones multiproceso empleando sólo una sincronización fina. [7]
El método de conteo de referencias ulterior de Blackburn y McKinley en 2003 [8] combina el conteo de referencias diferido con un vivero de copias, observando que la mayoría de las mutaciones de punteros ocurren en objetos jóvenes. Este algoritmo logra un rendimiento comparable al de los recolectores de copias generacionales más rápidos con tiempos de pausa de conteo de referencias limitados bajos.
Quizás la forma más obvia de manejar los ciclos de referencia sea diseñar el sistema para evitar crearlos. Un sistema puede prohibir explícitamente los ciclos de referencia; Los sistemas de archivos con enlaces físicos suelen hacer esto. El uso sensato de referencias "débiles" (no contadas) también puede ayudar a evitar ciclos de retención; El marco Cocoa , por ejemplo, recomienda utilizar referencias "fuertes" para las relaciones entre padres e hijos y referencias "débiles" para las relaciones entre hijos y padres. [9]
Los sistemas también pueden diseñarse para tolerar o corregir de alguna manera los ciclos que crean. Los desarrolladores pueden diseñar código para "derribar" explícitamente las referencias en una estructura de datos cuando ya no sean necesarias, aunque esto tiene el costo de exigirles que realicen un seguimiento manual de la vida útil de esa estructura de datos. Esta técnica se puede automatizar creando un objeto "propietario" que derribe cuando se destruya; 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 pueden incluso ignorarse en sistemas con vidas cortas y una pequeña cantidad de basura cíclica, particularmente cuando el sistema se desarrolló utilizando una metodología para evitar estructuras de datos cíclicas siempre que sea posible, generalmente a expensas de la eficiencia.
Los informáticos también han descubierto formas de detectar y recopilar ciclos de referencia automáticamente, sin requerir cambios en el diseño de la estructura de datos. Una solución sencilla es utilizar periódicamente un recolector de basura de seguimiento 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 recopilación cíclica para el recuento de referencias con similitudes con el seguimiento de recopiladores, incluidos los mismos límites de tiempo teóricos. Se basa en la observación de que un ciclo sólo puede aislarse cuando un recuento de referencia se reduce 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 en los objetos accesibles desde las raíces. Sabe que ha encontrado un ciclo que se puede recopilar cuando al disminuir todos los recuentos de referencias en un ciclo de referencias, todos se reducen a cero. [10] Una versión mejorada de este algoritmo realizada por Paz et al. [11] puede ejecutarse simultáneamente con otras operaciones y mejorar su eficiencia mediante el uso del método de actualización coalescente de Levanoni y Petrank. [5] [6]
Aunque es posible aumentar los recuentos de referencia simples de diversas formas, 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 rastrea el número de referencias que se refieren a él, sino el peso total de las referencias que se refieren a él. 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 del peso permanece en la referencia anterior. Dado que el peso total no cambia, no es necesario actualizar el recuento de referencia del objeto.
Destruir una referencia disminuye el peso total en el peso de esa referencia. Cuando el peso total llega a cero, todas las referencias han sido destruidas. Si se intenta copiar una referencia con un peso de 1, la referencia tiene que "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 necesitar acceder a un recuento de referencias cuando se copia una referencia es particularmente útil cuando es costoso acceder al recuento de referencias del objeto, por ejemplo porque está en otro proceso, en el disco o incluso a través de 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 ponderadas es más útil en aplicaciones paralelas, multiproceso, de bases de datos o distribuidas.
El principal problema con el recuento de referencias ponderadas simple es que destruir una referencia aún requiere acceder al recuento de referencias, y si se destruyen muchas referencias, esto puede causar los mismos cuellos de botella que buscamos evitar. Algunas adaptaciones del recuento de referencias ponderadas buscan evitar esto transfiriendo peso de una referencia moribunda a una referencia activa.
El recuento de referencias ponderadas fue ideado de forma independiente 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 las invocaciones; y uno indirecto que forma parte de un árbol de difusión, como en el algoritmo de Dijkstra-Scholten , que permite a un recolector de basura identificar objetos muertos. Este enfoque evita que un objeto sea descartado prematuramente.
Como algoritmo de recopilación, el recuento de referencias rastrea, para cada objeto, un recuento del número de referencias que tienen otros objetos. Si el recuento de referencias de un objeto llega a cero, el objeto se vuelve inaccesible y puede destruirse.
Cuando se destruye un objeto, todos los objetos a los que hace referencia ese objeto también reducen su recuento de referencias. Debido a esto, eliminar una única referencia puede generar la liberación de una gran cantidad de objetos. Una modificación común permite que el recuento de referencias se haga incremental: en lugar de destruir un objeto tan pronto como su recuento de referencias llega a cero, se agrega a una lista de objetos sin referencia y periódicamente (o según sea necesario) se agregan uno o más elementos de esta lista. destruido.
Los recuentos de referencias simples requieren actualizaciones frecuentes. Cada vez que se destruye o sobrescribe una referencia, el recuento de referencias del objeto al que hace referencia disminuye, y cada vez que se crea o copia una, el recuento de referencias del objeto al que hace referencia se incrementa.
El recuento de referencias también se utiliza en sistemas de archivos y sistemas distribuidos, donde la recolección completa de basura de rastreo no incremental requiere demasiado tiempo debido al tamaño del gráfico de objetos y la lenta 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 disminuyen 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) se basan en COM, lo que demuestra la viabilidad del recuento de referencias en sistemas a gran escala. [ cita necesaria ]
Una motivación principal para el recuento de referencias en COM es permitir la interoperabilidad entre diferentes lenguajes de programación y sistemas de ejecución. Un cliente sólo necesita saber cómo invocar métodos de objetos para gestionar el ciclo de vida de los objetos; 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 ser desasignado) por un asignador de C++ u otro componente de Visual Basic.
C++ no realiza recuento de referencias de forma predeterminada, cumpliendo con su filosofía de no agregar funcionalidades que puedan generar gastos generales cuando el usuario no lo haya solicitado explícitamente. Se puede acceder a los objetos que se comparten pero que no son de propiedad mediante una referencia, un puntero sin formato o un iterador (una generalización conceptual de punteros).
Sin embargo, de la misma manera, 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 administració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 que no están destinados a ser compartidos pueden tener su vida útil administrada automáticamente mediante un archivo std::unique_ptr.
Además, la semántica de movimiento de C++ 11 reduce aún más la medida en que es necesario modificar los recuentos de referencias al eliminar la copia profunda que normalmente se usa cuando una función devuelve un objeto, ya que permite una copia simple del puntero de dicho objeto.
Los marcos Cocoa y Cocoa Touch de Apple (y marcos relacionados, como Core Foundation ) utilizan el recuento de referencias manual, muy parecido a COM . Tradicionalmente, esto se lograba mediante el envío manual retainde releasemensajes por parte del programador a los objetos, pero en iOS 5 [15] y Mac OS X 10.7 se agregó el Recuento automático de referencias , una función del compilador Clang que inserta automáticamente estos mensajes según sea necesario . [16] Mac OS X 10.5 introdujo un recolector de basura de seguimiento como alternativa al recuento 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.
En su mayoría, Delphi no es un lenguaje de recolección de basura, en el sentido de que los tipos definidos por el usuario aún deben asignarse y desasignarse manualmente; sin embargo, proporciona recopilación automática mediante 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, si se desea, todos los costes potenciales del recuento de referencias de Delphi pueden evitarse fácilmente.
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 orientado a objetos GObject implementa el conteo de referencias en sus tipos base, incluidas las referencias débiles . El incremento y decremento de referencia utiliza operaciones atómicas para la seguridad de los subprocesos. Una cantidad significativa del trabajo al escribir enlaces a GObject desde lenguajes de alto nivel radica en adaptar el recuento de referencias de GObject para que funcione con el propio sistema de gestión de memoria del lenguaje.
El lenguaje de programación Vala utiliza el recuento de referencias de GObject como su principal sistema de recolección de basura, junto con el manejo de cadenas con muchas copias. [19]
Perl también usa recuento de referencias, sin ningún manejo especial de referencias circulares, aunque (como en Cocoa y C++ arriba), Perl 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 su gestión de variables internas. [20] Desde PHP 5.3, implementa el algoritmo del artículo de Bacon mencionado anteriormente. PHP le permite activar y desactivar la colección de ciclos con funciones a nivel de usuario. También le permite forzar manualmente la ejecución del mecanismo de purga.
Python también utiliza el recuento de referencias y también ofrece detección de ciclos (y puede recuperar ciclos de referencia). [21]
Rust utiliza vidas declaradas en el código para liberar memoria. Rust tiene una estructura Rcy Arc, que son atómicas y no atómicas respectivamente.
El tipo Rc<T>proporciona propiedad compartida de un valor de tipo Tasignado en el montón. [22]
utilizar std :: rc :: Rc ; estructura Gato { color : Cadena , } fn main () { let cat = Cat { color : "negro" . Encadenar () }; let gato = Rc :: nuevo ( gato ); } Squirrel utiliza el recuento de referencias con detección de ciclos. Este diminuto lenguaje es relativamente desconocido fuera de la industria de los videojuegos; sin embargo, es un ejemplo concreto de cómo el recuento de referencias puede ser práctico y eficiente (especialmente en entornos de tiempo real). [ cita necesaria ]
Swift utiliza el recuento de referencias para rastrear y administrar la memoria en todo el idioma y proporciona la weakpalabra clave para crear referencias débiles. [23]
Tcl 8 utiliza el recuento de referencias para la gestión de memoria de 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 recuento 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 comentados anteriormente.
Xojo también usa 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 físicos . Cuando el recuento llega a cero, el archivo se puede desasignar de forma segura. Si bien aún se pueden hacer 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)