Internamiento de cadenas - Enciclopedia

En la informática, la internación de cadenas es un método para almacenar solo una copia de cada valor de cadena distinto, que debe ser inmutable. La internación de cadenas hace que algunas tareas de procesamiento de cadenas sean más eficientes en tiempo o espacio, a cambio de que se requiera más tiempo cuando se crea o internan las cadenas. Los valores distintos se almacenan en una piscina de internación de cadenas.

La única copia de cada cadena se llama su internación y se busca típicamente mediante un método de la clase cadena, por ejemplo String.intern() en Java. Todas las cadenas constantes en tiempo de compilación en Java se internan automáticamente utilizando este método.

La internación de cadenas es compatible con algunos lenguajes de programación orientados a objetos modernos, incluyendo Java, Python, PHP (desde la versión 5.4), Lua y lenguajes .NET. Lisp, Scheme, Julia, Ruby y Smalltalk son entre los lenguajes con un tipo de símbolo que básicamente son cadenas internadas. La biblioteca del Standard ML de New Jersey contiene un tipo de átomo que hace lo mismo. Los selectores de Objective-C, que se utilizan principalmente como nombres de métodos, son cadenas internadas.

Las cadenas internadas también pueden ser otras instancias de objetos. Por ejemplo, en Java, cuando los valores primitivos se empacan en un objeto envoltorio, ciertos valores (cualquier booleano, cualquier byte, cualquier carácter de 0 a 127, y cualquier entero corto o entero entre -128 y 127) se internan, y cualquier dos conversiones de empacado de uno de estos valores garantizan que resulten en el mismo objeto.


Historia
Lisp introdujo la noción de cadenas internadas para sus símbolos. Históricamente, la estructura de datos utilizada como piscina de internación de cadenas se llamaba oblist (cuando se implementaba como una lista enlazada) o obarray (cuando se implementaba como un array).
Los dialectos modernos de Lisp típicamente distinguen símbolos de cadenas; la internación de una cadena dada devuelve un símbolo existente o crea uno nuevo, cuyo nombre es esa cadena. Los símbolos a menudo tienen propiedades adicionales que no tienen las cadenas, como el almacenamiento de valores asociados o el espacio de nombres. Esta distinción también es útil para evitar accidentalmente comparar una cadena internada con una no necesariamente internada, lo que podría llevar a fallos intermitentes dependiendo de los patrones de uso.


Motivación
La internación de cadenas acelera las comparaciones de cadenas, que a veces son un cuello de botella en aplicaciones (como los compiladores y los ejecutores de lenguajes de programación dinámicos) que dependen en gran medida de tablas de asociación con claves de cadena para buscar los atributos y métodos de un objeto. Sin internación, comparar dos cadenas distintas puede implicar examinar cada carácter de ambas. Esto es lento por varios motivos: inherentemente es O(n) en la longitud de las cadenas; típicamente requiere lecturas de varias regiones de memoria, lo que lleva tiempo; y las lecturas llenan la caché del procesador, lo que significa que hay menos caché disponible para otros fines. Con cadenas internadas, después de la operación de internación original, un simple test de identidad de objeto es suficiente; esto se implementsa típicamente como un test de igualdad de punteros, generalmente solo una instrucción de máquina con ninguna referencia a la memoria.

La internación de cadenas también reduce el uso de memoria si hay muchas instancias del mismo valor de cadena; por ejemplo, se lee de una red o desde el almacenamiento. Tales cadenas pueden incluir números mágicos o información de protocolo de red. Por ejemplo, los analizadores XML pueden internar nombres de etiquetas y atributos para ahorrar memoria. La transferencia de objetos a través de flujos de serialización de objetos Java RMI puede transferir cadenas internadas de manera más eficiente, ya que se utiliza el gestor de la cadena en lugar de objetos duplicados durante la serialización.


Problemas


= Multithreading =
Si las cadenas internadas no son inmutables, una fuente de inconvenientes es que la internación de cadenas puede ser problemática cuando se combina con el multithreading. En muchos sistemas, las cadenas internadas deben ser globales en todas las hilos dentro de un espacio de direcciones (o en cualquier contexto que pueda compartir punteros), por lo que la piscina de internación(es) es un recurso global que debe sincronizarse para el acceso concurrente seguro. Aunque esto solo afecta a la creación de cadenas (donde la piscina de internación debe verificarse y modificarse si es necesario), y el bloqueo de verificación doble puede usarse en plataformas donde esto es una optimización segura, la necesidad de exclusión mutua al modificar la piscina de internación puede ser costosa.
La contienda también puede reducirse dividiendo el espacio de cadenas en múltiples piscinas, que pueden sincronizarse independientemente una de otra.


= Recuperación de cadenas internadas no utilizadas =
Muchas implementaciones de cadenas internadas no intentan recuperar (manualmente o de otra manera) las cadenas que ya no se utilizan. Para aplicaciones donde el número de cadenas internadas es pequeño o fijo, o que son cortas, la pérdida de recursos del sistema puede ser tolerable. Pero para sistemas a largo plazo donde se crean grandes números de cadenas internadas en tiempo de ejecución, puede surgir la necesidad de recuperar cadenas no utilizadas. Esta tarea puede manejarla un recolector de basura, aunque para que funcione correctamente, deben almacenarse referencias débiles a cadenas internadas en la piscina de internación.


Ver también
Patrón de diseño Flyweight


Referencias


Enlaces externos
Clase Visual J# String
Clase String .NET
Biblioteca Guava Java - Interner - String.intern No-permgen y soporta otros tipos inmutables con implementaciones con referencias débiles y fuertes
Entendiendo el método intern() de Java para cadenas