En informática, la pasantía de cadenas es un método para almacenar solo una copia de cada valor de cadena distinto , que debe ser inmutable . [1] El internamiento de cadenas hace que algunas tareas de procesamiento de cadenas sean más eficientes en tiempo o espacio a costa de requerir más tiempo cuando se crea o se interna la cadena. Los distintos valores se almacenan en un grupo interno de cadenas .
La copia única de cada cadena se denomina interna y normalmente se busca mediante un método de la clase de cadena, por ejemplo String.intern () [2] en Java . Todas las cadenas de constantes en tiempo de compilación en Java se internan automáticamente utilizando este método. [3]
La internación de cadenas es compatible con algunos lenguajes de programación orientados a objetos modernos , incluidos Java, Python , PHP (desde 5.4), Lua , [4] Ruby (con sus símbolos), Julia y .NET . [5] Lisp , Scheme y Smalltalk se encuentran entre los lenguajes con un tipo de símbolo que son básicamente cadenas internas. La biblioteca del estándar ML de Nueva 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 internas.
Se pueden internar otros objetos que no sean cadenas. Por ejemplo, en Java, cuando los valores primitivos están encuadrados en un objeto contenedor , ciertos valores (cualquiera boolean
, cualquiera byte
, cualquiera char
de 0 a 127 y cualquiera short
o int
entre −128 y 127) se internan, y dos conversiones de boxeo cualesquiera de uno de estos los valores están garantizados para dar como resultado el mismo objeto. [6]
Historia
Lisp introdujo la noción de cadenas internas para sus símbolos . Históricamente, la estructura de datos utilizada como grupo interno de cadenas se llamaba oblist (cuando se implementó como una lista vinculada) u obarray (cuando se implementó como una matriz).
Los dialectos Lisp modernos típicamente distinguen los símbolos de las cadenas; internar 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 las cadenas no tienen (como el almacenamiento de valores asociados o el espacio de nombres): la distinción también es útil para evitar comparar accidentalmente una cadena interna con una cadena no necesariamente interna, lo que podría conducir a fallas intermitentes dependiendo de patrones de uso.
Motivación
La internación de cadenas acelera las comparaciones de cadenas, que a veces son un cuello de botella de rendimiento en aplicaciones (como compiladores y tiempos de ejecución de lenguajes de programación dinámicos ) que dependen en gran medida de matrices asociativas con claves de cadena para buscar los atributos y métodos de un objeto. Sin una pasantía, comparar dos cadenas distintas puede implicar examinar cada carácter de ambas. [Nota 1] Esto es lento por varias razones: es inherentemente O (n) en la longitud de las cadenas; normalmente requiere lecturas de varias regiones de la memoria , lo que lleva tiempo; y las lecturas llenan la memoria caché del procesador, lo que significa que hay menos memoria caché disponible para otras necesidades. Con cadenas internas, una simple prueba de identidad de objeto es suficiente después de la operación interna original; esto se implementa típicamente como una prueba de igualdad de puntero, normalmente una sola instrucción de máquina sin ninguna referencia de 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 desde una red o desde un almacenamiento . Tales cadenas pueden incluir números mágicos o información de protocolo de red . Por ejemplo, los analizadores XML pueden introducir nombres de etiquetas y atributos para ahorrar memoria. La transferencia de objetos en red a través de secuencias de objetos de serialización RMI de Java puede transferir cadenas que están internadas de manera más eficiente, ya que el identificador del objeto String se usa en lugar de objetos duplicados en la serialización. [7]
Asuntos
Subprocesos múltiples
Una fuente de inconvenientes es que la internación de cadenas puede ser problemática cuando se mezcla con subprocesos múltiples . En muchos sistemas, los pasantes de cadenas deben ser globales en todos los subprocesos dentro de un espacio de direcciones (o en cualquier contexto que pueda compartir punteros), por lo que los grupos de pasantes son recursos globales que deben sincronizarse para un acceso concurrente seguro. Si bien esto solo afecta la creación de cadenas (donde el grupo de internos debe ser verificado y modificado si es necesario), y el bloqueo con doble verificación se puede usar en plataformas donde esta es una optimización segura, la necesidad de exclusión mutua al modificar el grupo de internos puede ser costosa. . [8]
La contención también se puede reducir dividiendo el espacio de cadenas en varios grupos, que se pueden sincronizar de forma independiente entre sí.
Recuperación de cadenas internas no utilizadas
Muchas implementaciones de cadenas internas no intentan recuperar (manualmente o de otro modo) cadenas que ya no se utilizan. Para aplicaciones donde el número de cadenas internas es pequeño o fijo, o que son de corta duración, la pérdida de recursos del sistema puede ser tolerable. Pero para los sistemas de larga duración en los que se crea una gran cantidad de pasantes de cadena en tiempo de ejecución, puede surgir la necesidad de recuperar pasantes no utilizados. Esta tarea puede ser manejada por un recolector de basura , aunque para que esto funcione correctamente, las referencias débiles a los internos de cadenas deben almacenarse en el grupo de internos.
Ver también
Notas
- ^ La comparación de cadenas puede detenerse ante la primera discrepancia de caracteres. Para una igualdad estricta, las longitudes de las cadenas también se pueden comparar antes de atravesar la cadena: pero encontrar la longitud de las cadenas terminadas en nulo requiere atravesar la cadena.
Referencias
- ^ "Método String.Intern (String)" . Red de desarrolladores de Microsoft . Consultado el 25 de marzo de 2017 .
- ^
String.intern()
- ^ "Capítulo 15. Expresiones" . docs.oracle.com . Consultado el 30 de enero de 2019 .
- ^ "wiki lua-users: objetos inmutables" . lua-users.org . Consultado el 30 de enero de 2019 .
- ^ rpetrusha. "Clase de cadena (sistema)" . docs.microsoft.com . Consultado el 30 de enero de 2019 .
- ^ "Capítulo 5. Conversiones y promociones" . docs.oracle.com . Consultado el 30 de enero de 2019 .
- ^ "Especificación de serialización de objetos Java: 1 - Arquitectura del sistema" . docs.oracle.com . Consultado el 30 de enero de 2019 .
- ^ admin (3 de septiembre de 2013). "String.intern en Java 6, 7 y 8 - acceso multiproceso" . java-performance.info . Consultado el 30 de enero de 2019 .
enlaces externos
- Clase Visual J # String
- Clase de cadena .NET
- Biblioteca Java de Guava - Interner - Non-permgen String.intern y admite otros tipos inmutables con implementaciones de referencia débiles y fuertes