Recuento de referencias - Reference counting

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 , los recuentos de referencias pueden usarse para desasignar objetos que ya no son necesarios.

Ventajas y desventajas

La principal ventaja del recuento de referencias sobre el seguimiento de la recolección de basura es que los objetos se reclaman tan pronto como ya no se pueden hacer referencia a ellos, y de forma incremental, sin largas pausas para los ciclos de recolección y con una vida útil claramente definida de cada objeto. En aplicaciones o sistemas en tiempo real 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 la gestión de la memoria. También permite una gestión eficaz de los 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, 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.

Ejemplo de lista circular de una tesis de maestría de 1985. Los rectángulos denotan pares Lisp , con recuentos de referencia. Incluso si se elimina el puntero superior izquierdo entrante, todos los recuentos permanecen> 0.

El seguimiento de los ciclos de recolección de basura se activa con demasiada frecuencia si el conjunto de objetos activos ocupa la mayor parte de la memoria disponible; requiere espacio adicional para ser eficiente. El rendimiento del recuento de referencias no se deteriora a medida que disminuye la cantidad total de espacio libre.

Los recuentos de referencias también son información útil para utilizar 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 penalización de eficiencia debido a las copias frecuentes. Sin embargo, si el compilador (o el sistema en tiempo 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 cadena añadir declaración str ← str + "a"), puede reemplazar la operación con una mutación en el objeto original.

El recuento de referencias en forma ingenua tiene dos desventajas principales sobre la recolección de basura de rastreo, las cuales requieren mecanismos adicionales para mejorar:

Las frecuentes actualizaciones que implica son una fuente de ineficiencia. Si bien el seguimiento de los recolectores de basura puede afectar gravemente a la eficiencia a través del cambio de contexto y las fallas de la línea de caché, se recolectan con relativa poca frecuencia, mientras que el acceso a los objetos se realiza de forma continua. Además, lo que es menos importante, el recuento de referencias requiere que cada objeto gestionado por memoria reserve espacio para un recuento de referencias. Al rastrear recolectores de basura, esta información se almacena implícitamente en las referencias que hacen referencia a ese objeto, ahorrando espacio, aunque rastrear recolectores de basura, particularmente los incrementales, puede requerir espacio adicional para otros propósitos.
El algoritmo ingenuo descrito anteriormente no puede manejar ciclos de referencia ,un objeto que se refiere directa o indirectamente a sí mismo. Un mecanismo que se base exclusivamente en recuentos de referencias nunca considerará cadenas cíclicas de objetos para su eliminación, ya que se garantiza que su recuento de referencias no será cero (ver imagen). Existen métodos para abordar este problema, pero también pueden aumentar la sobrecarga y la complejidad del recuento de referencias; por otro lado, estos métodos solo deben aplicarse a los datos que pueden formar ciclos, a menudo un pequeño subconjunto de todos los datos. Uno de esos métodos es el uso dereferencias débiles, mientras que otro implica el uso de unalgoritmo debarrido de marcasque se llama con poca frecuencia para limpiar.

Además de estos, si la memoria se asigna a partir de una lista libre, el recuento de referencias adolece de mala localidad. 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) adolecen de un rendimiento de caché deficiente, ya que no implementan la copia de objetos.

Interpretación gráfica

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. Nosotros también tienen un vértice o vértices especiales que representan las variables locales y las referencias que tiene el sistema en tiempo de ejecución, y ningún borde va a estos nodos, aunque los bordes pueden ir de ellos a otros nodos.

En este contexto, el simple recuento de referencias de un objeto es el grado de su vértice. Eliminar un vértice es como recolectar un objeto. Solo se puede hacer cuando el vértice no tiene bordes 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, haciendo que sus objetos correspondientes también se recopilen si su in-degree también se convierte en 0 como resultado.

El componente conectado que contiene el vértice especial contiene los objetos que no se pueden recopilar, mientras que otros componentes conectados del gráfico solo contienen basura. Si se implementa un algoritmo de recolección de basura de 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 referencias (es decir, el número de bordes entrantes) cayera a cero.

Hacer frente a la ineficacia de las actualizaciones

Incrementar y disminuir los recuentos de referencias cada vez que se crea o destruye una referencia puede afectar significativamente el rendimiento. Las operaciones no solo llevan 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 actualizaciones de referencias con un conteo de referencias ingenuo.

Una técnica simple es que el compilador combine varias actualizaciones de referencia cercanas en una. 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 de recuento de referencias de Deutsch-Bobrow se basa en el hecho de que la mayoría de las actualizaciones de recuento de referencias son de hecho generadas por referencias almacenadas en variables locales. Ignora estas referencias, solo contando las referencias en estructuras de datos, pero antes de que se pueda eliminar un objeto con un recuento de referencia cero, el sistema debe verificar con un escaneo de la pila y registra que aún no existe ninguna otra referencia a él.

Otra técnica ideada por Henry Baker implica incrementos diferidos , 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, 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, lo que resultará en una liberación prematura.

Levanoni y Petrank obtuvieron una disminución drástica en los gastos generales de las actualizaciones de los mostradores . Introducen el método de fusión de actualizaciones que fusiona muchas de las actualizaciones de recuento de referencias redundantes. Considere un puntero que en un intervalo dado 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 típicamente ejecutar rc(O1)--, rc(O2)++, rc(O2)--, rc(O3)++, rc(O3)--, ..., rc(On)++. Pero la mayoría de estas actualizaciones son redundantes. Para que el recuento de referencia se evalúe correctamente al final del intervalo, es suficiente realizar rc(O1)--y rc(On)++. El resto de las actualizaciones son redundantes.

Levanoni y Petrank mostraron en 2001 cómo utilizar dicha actualización coalescente en un colector de recuento de referencias. Cuando se utiliza la combinación de actualizaciones con un tratamiento adecuado de los nuevos objetos, más del 99% de las actualizaciones de contador se eliminan para los puntos de referencia típicos de Java. Además, se elimina la necesidad de operaciones atómicas durante las actualizaciones de punteros en procesadores paralelos. Finalmente, presentaron un algoritmo mejorado que puede ejecutarse simultáneamente con aplicaciones multiproceso que emplean solo una sincronización fina.

El método de recuento de referencias ulteriores de Blackburn y McKinley en 2003 combina el recuento de referencias diferidas con un vivero de copias, observando que la mayoría de las mutaciones de puntero ocurren en objetos jóvenes. Este algoritmo logra un rendimiento comparable con los recopiladores de copias generacionales más rápidos con los tiempos de pausa limitados bajos del recuento de referencias.

Manejo de ciclos de referencia

Quizás la forma más obvia de manejar los ciclos de referencia es 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 juicioso de referencias "débiles" (no contadas) también puede ayudar a evitar retener ciclos; el marco de Cocoa , por ejemplo, recomienda utilizar referencias "sólidas" para las relaciones entre padres e hijos y referencias "débiles" para las relaciones entre padres e hijos.

Los sistemas también pueden diseñarse para tolerar o corregir los ciclos que crean de alguna manera. Los desarrolladores pueden diseñar código para "derribar" 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 lo derriba 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 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 de forma automática, sin requerir cambios en el diseño de la estructura de datos. Una solución simple 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 ordinario.

Bacon describe un algoritmo de recolección de ciclos para el conteo de referencias con 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 reduce a un valor distinto de cero. Todos los objetos en los que ocurre esto se colocan en una lista de raíces , y luego, periódicamente, el programa busca ciclos a través de los objetos accesibles desde las raíces. Sabe que ha encontrado un ciclo que se puede recopilar cuando disminuir todos los recuentos de referencias en un ciclo de referencias los reduce a cero. Una versión mejorada de este algoritmo de Paz et al. puede ejecutarse simultáneamente con otras operaciones y mejorar su eficiencia mediante el método de fusión de actualizaciones de Levanoni y Petrank.

Formas variantes

Aunque es posible aumentar los recuentos de referencias simples de diversas formas, a menudo se puede encontrar una mejor solución realizando el recuento de referencias de una manera fundamentalmente diferente. A continuación, describimos algunas de las variantes del recuento de referencias y sus ventajas e inconvenientes.

Recuento de referencias ponderadas

En el recuento de referencias ponderadas, a cada referencia se le asigna un peso , y cada objeto rastrea no 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 gran peso, como 2 ¹⁶ . Siempre que se copia esta referencia, la mitad del peso va a la nueva referencia y la mitad del peso se queda con la referencia anterior. Dado que el peso total no cambia, no es necesario actualizar el recuento de referencia del objeto.

La destrucción de una referencia reduce el peso total por el peso de esa referencia. Cuando el peso total se vuelve cero, todas las referencias se han destruido. Si se intenta copiar una referencia con un peso de 1, la referencia tiene que "obtener más peso" agregando al 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 gran peso 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 el acceso al recuento de referencias del objeto es costoso, 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 simultaneidad 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 base de datos o distribuidas.

El problema principal con el conteo de referencias ponderadas simple es que la destrucción de una referencia aún requiere acceder al conteo 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 el peso de una referencia moribunda a una referencia activa.

El recuento de referencias ponderadas fue ideado de forma independiente por Bevan y Watson & Watson en 1987.

Recuento indirecto de referencias

En el recuento indirecto de referencias, es necesario realizar un seguimiento de la fuente de la referencia. Esto significa que se mantienen dos referencias al objeto: una directa que se usa para invocaciones; y una indirecta 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 se descarte prematuramente.

Ejemplos de uso

Recolección de basura

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 referencia de un objeto llega a cero, el objeto se ha vuelto inaccesible y puede ser destruido.

Cuando se destruye un objeto, los recuentos de referencias de los objetos a los que hace referencia ese objeto también disminuyen. Por este motivo, la eliminación de una única referencia puede dar lugar a la liberación de una gran cantidad de objetos. Una modificación común permite que el recuento de referencias sea incremental: en lugar de destruir un objeto tan pronto como su recuento de referencias se vuelve cero, se agrega a una lista de objetos sin referencia y periódicamente (o según sea necesario) uno o más elementos de esta lista son destruido.

Los recuentos de referencias simples requieren actualizaciones frecuentes. Siempre que una referencia se destruye o se sobrescribe, el recuento de referencias del objeto al que hace referencia se reduce, y siempre que se crea o se copia una, se incrementa el recuento de referencias del objeto al que hace referencia.

El recuento 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 velocidad de acceso lenta.

Modelo de objeto componente

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 deben proporcionar todos los objetos COM (en la interfaz IUnknown ) aumentan 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.

Una motivación principal para el recuento de referencias en COM es permitir la interoperabilidad entre diferentes lenguajes de programación y sistemas de tiempo de ejecución. Un cliente solo necesita saber cómo invocar métodos de objetos para administrar el ciclo de vida de los objetos; por lo tanto, el cliente se abstrae completamente de cualquier asignador de memoria que utilice la implementación del objeto COM. Como ejemplo típico, un programa de Visual Basic que usa 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 ++

C ++ no realiza el recuento de referencias de forma predeterminada, cumpliendo con su filosofía de no agregar funcionalidad que pueda incurrir en gastos generales donde el usuario no lo ha solicitado explícitamente. Se puede acceder a los objetos que se comparten pero que no son de propiedad a través de una referencia, un puntero sin formato o un iterador (una generalización conceptual de punteros).

Sin embargo, del mismo modo, C ++ proporciona formas nativas para que los usuarios opten por dicha funcionalidad: C ++ 11 proporciona punteros inteligentes contados de 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 (via 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 usando un std::unique_ptr.

Además, la semántica de movimiento de C ++ 11 reduce aún más el grado en que los recuentos de referencias deben modificarse al eliminar la copia profunda que se usa normalmente cuando una función devuelve un objeto, ya que permite una copia simple del puntero de dicho objeto.

Cacao (Objective-C)

Los marcos Cocoa y Cocoa Touch de Apple (y los marcos relacionados, como Core Foundation ) utilizan el recuento de referencias manual, al igual que COM . Tradicionalmente esto se logró mediante el programador de enviar manualmente retainy releasemensajes a los objetos, pero la cuenta automática de referencia , un Clang se añadió característica compilador que inserta automáticamente estos mensajes, según sea necesario, en iOS 5 y Mac OS X 10.7 . Mac OS X 10.5 introdujo un recolector de basura de seguimiento como una alternativa al recuento de referencias, pero quedó obsoleto en OS X 10.8 y se eliminó de la biblioteca de tiempo de ejecución de Objective-C en macOS Sierra . iOS nunca ha admitido un recolector de basura de rastreo.

Delphi

La mayoría de las veces, 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 una 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 de la base de datos genérica. 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 puede, si se desea, eludir fácilmente.

Algunas de las razones por las que el conteo de referencias puede haberse preferido a otras formas de recolección de basura en Delphi incluyen:

Los beneficios generales del recuento de referencias, como la recopilación rápida.
Los ciclos no pueden ocurrir o no ocurren en la práctica porque ninguno de los tipos integrados recolectados de basura es recursivo. (usando interfaces uno podría crear tal escenario, pero ese no es un uso común)
La sobrecarga en el tamaño del código requerida para el recuento de referencias es muy pequeña (en x86 nativo, generalmente una sola instrucción LOCK INC, LOCK DEC o LOCK XADD, que garantiza la atomicidad en cualquier entorno), y no se necesita un hilo de control separado para la recopilación como lo haría ser necesario para un recolector de basura de rastreo.
Muchas instancias del tipo de recolección de basura más comúnmente utilizado, la cadena, tienen una vida útil corta, ya que normalmente son valores intermedios en la manipulación de cadenas. Una gran cantidad de uso de cadenas locales podría optimizarse, pero el compilador actualmente no lo hace.
El recuento de referencias de una cadena se comprueba antes de mutar una cadena. Esto permite que las cadenas de recuento de referencia 1 se muten directamente mientras que las cadenas de recuento de referencia más altas se copian antes de la mutación. Esto permite preservar el comportamiento general de las cadenas pascal de estilo antiguo y, al mismo tiempo, eliminar el costo de copiar la cadena en cada asignación.
Debido a que la recolección de basura solo se realiza en tipos integrados, el recuento de referencias se puede integrar de manera eficiente en las rutinas de la biblioteca utilizadas para manipular cada tipo de datos, manteniendo baja la sobrecarga necesaria para actualizar los recuentos de referencias. Además, gran parte de la biblioteca en tiempo de ejecución está en ensamblador optimizado a mano.
El tipo de cadena se puede convertir en un puntero a char, y las operaciones de alto rendimiento se pueden realizar de esa manera. Esto es importante ya que tanto Delphi como FPC implementan su RTL en Pascal. Varios otros tipos automatizados tienen tales opciones de fundición.

GObject

El marco de programación orientado a objetos de GObject implementa el recuento 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 los subprocesos. Una parte importante del trabajo de escribir enlaces a GObject desde lenguajes de alto nivel radica en adaptar el recuento de referencias de GObject para que funcione con el sistema de gestión de memoria del propio lenguaje.

El lenguaje de programación Vala utiliza el recuento de referencias de GObject como su sistema principal de recolección de basura, junto con el manejo de cadenas con muchas copias.

Perl

Perl también usa el conteo 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

PHP utiliza un mecanismo de recuento de referencias para su gestión de variables internas. Desde PHP 5.3, implementa el algoritmo del artículo mencionado anteriormente de Bacon. 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.

Pitón

Python también utiliza el recuento de referencias y también ofrece detección de ciclos (y puede recuperarlos).

Oxido

Rust usa vidas útiles declaradas en el código para liberar memoria. El óxido tiene una estructura Rcy Arc.

El tipo Rc<T>proporciona propiedad compartida de un valor de tipo T, asignado en el montón.

use std::rc::Rc;

struct Cat {
    color: String,
}

fn main() {
    let cat = Cat { color: "black".to_string() };
    let cat = Rc::new(cat);
}

Ardilla

La ardilla utiliza el recuento de referencia 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 conteo de referencias puede ser práctico y eficiente (especialmente en entornos en tiempo real).

Tcl

Tcl 8 utiliza el recuento de referencias para la gestión de la memoria de valores ( estructuras Tcl Obj ). Dado que los valores de Tcl son inmutables, los ciclos de referencia son imposibles de formar 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 discutidos anteriormente.

Xojo

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.

Sistemas de archivos

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 forma segura. Si bien aún se pueden hacer referencias desde directorios , algunos Unix solo permiten referencias de procesos en vivo, y puede haber archivos que existan fuera de la jerarquía del sistema de archivos.

Languages

In other projects