В информатике интернирование строк — это метод хранения только одной копии каждого отдельного строкового значения, которое должно быть неизменяемым . [1] Интернирование строк делает некоторые задачи обработки строк более эффективными по времени или пространству за счет того, что требуется больше времени на создание или интернирование строки. Отдельные значения хранятся в пуле интернирования строк .
Единственная копия каждой строки называется ее интерн и обычно ищется методом класса строки, например String.intern() [2] в Java . Все константные строки времени компиляции в Java автоматически интернируются с использованием этого метода. [3]
Интернирование строк поддерживается некоторыми современными объектно-ориентированными языками программирования , включая Java, Python , PHP (начиная с версии 5.4), Lua [4]
и языки .NET . [5] Lisp , Scheme , Julia , Ruby и Smalltalk входят в число языков с типом символа , которые по сути являются интернированными строками. Библиотека Standard ML Нью-Джерси содержит atomтип, который делает то же самое. Селекторы Objective-C , которые в основном используются в качестве имен методов, являются интернированными строками.
Объекты, отличные от строк, могут быть интернированы. Например, в Java, когда примитивные значения упаковываются в объект -обертку , некоторые значения (любые boolean, любые byte, любые charот 0 до 127 и любые shortили intмежду −128 и 127) интернируются, и любые два преобразования упаковки одного из этих значений гарантированно приведут к одному и тому же объекту. [6]
Lisp ввел понятие интернированных строк для своих символов . Исторически структура данных, используемая в качестве пула интернированных строк, называлась oblist ( когда она была реализована как связанный список) или obarray (когда она была реализована как массив).
Современные диалекты Lisp обычно различают символы и строки; интернирование заданной строки возвращает существующий символ или создает новый, имя которого — эта строка. Символы часто имеют дополнительные свойства, которых нет у строк (например, хранение связанных значений или пространство имен): это различие также полезно для предотвращения случайного сравнения интернированной строки с необязательно интернированной строкой, что может привести к периодическим сбоям в зависимости от шаблонов использования.
Интернирование строк ускоряет сравнение строк, которое иногда является узким местом производительности в приложениях (таких как компиляторы и среды выполнения динамических языков программирования ), которые в значительной степени полагаются на ассоциативные массивы со строковыми ключами для поиска атрибутов и методов объекта. Без интернирования сравнение двух различных строк может включать проверку каждого символа обеих. [Примечание 1] Это медленно по нескольким причинам: это по своей сути O(n) по длине строк; обычно это требует чтения из нескольких областей памяти , что занимает время; и чтения заполняют кэш процессора, что означает, что остается меньше кэша, доступного для других нужд. С интернированными строками достаточно простой проверки идентичности объекта после исходной операции интернирования; это обычно реализуется как проверка равенства указателей, обычно просто одна машинная инструкция без какой-либо ссылки на память.
Интернирование строк также уменьшает использование памяти, если существует много экземпляров одного и того же строкового значения; например, оно считывается из сети или из хранилища . Такие строки могут включать магические числа или информацию о сетевом протоколе . Например, анализаторы XML могут интернировать имена тегов и атрибутов для экономии памяти. Сетевая передача объектов через потоки объектов сериализации Java RMI может передавать интернированные строки более эффективно, поскольку вместо дубликатов объектов при сериализации используется дескриптор объекта String. [7]
Если интернированные строки не являются неизменяемыми, одним из источников недостатков является то, что интернирование строк может быть проблематичным при смешивании с многопоточностью . Во многих системах интернирование строк должно быть глобальным для всех потоков в адресном пространстве (или для любых контекстов, которые могут совместно использовать указатели), таким образом, пул(ы) интернирования являются глобальными ресурсами, которые должны быть синхронизированы для безопасного параллельного доступа. Хотя это влияет только на создание строк (где пул интернирования должен быть проверен и изменен при необходимости), и на платформах, где это является безопасной оптимизацией, может использоваться блокировка с двойной проверкой , необходимость во взаимном исключении при изменении пула интернирования может быть дорогостоящей. [8]
Конкуренцию также можно уменьшить, разделив пространство строк на несколько пулов, которые можно синхронизировать независимо друг от друга.
Многие реализации интернированных строк не пытаются восстанавливать (вручную или иным образом) строки, которые больше не используются. Для приложений, где количество интернированных строк невелико или фиксировано, или которые недолговечны, потеря системных ресурсов может быть допустимой. Но для долго работающих систем, где во время выполнения создается большое количество строковых интернов, может возникнуть необходимость в восстановлении неиспользуемых интернов. Эту задачу может выполнить сборщик мусора , хотя для корректной работы слабые ссылки на строковые интерны должны храниться в пуле интернов.
String.intern()