В информатике интернирование строк - это метод хранения только одной копии каждого отдельного строкового значения, которое должно быть неизменным . [1] Интернирование строк делает некоторые задачи обработки строк более эффективными по времени или пространству за счет того, что для создания или интернирования строки требуется больше времени. Отдельные значения хранятся в внутреннем пуле строк .
Единственная копия каждой строки называется ее внутренней и обычно просматривается методом класса строки, например String.intern () [2] в Java . Все строки констант времени компиляции в Java автоматически интернируются с использованием этого метода. [3]
Интернирование строк поддерживается некоторыми современными объектно-ориентированными языками программирования , включая Java, Python , PHP (начиная с версии 5.4), Lua , [4] Ruby (с его символами), Julia и .NET . [5] Lisp , Scheme и Smalltalk относятся к языкам с символьным типом, которые в основном представляют собой интернированные строки. Библиотека Standard ML of New Jersey содержит атомный тип, который выполняет то же самое. Селекторы Objective-C , которые в основном используются как имена методов, представляют собой интернированные строки.
Могут быть интернированы объекты, отличные от строк. Например, в Java, когда примитивные значения в штучной упаковке в объект обертки , определенные значения (любой boolean
, любой byte
, любой char
от 0 до 127, и любой short
или int
от -128 до 127) интернированы, и любые два преобразования бокса одного из них значения гарантированно приведут к одному и тому же объекту. [6]
История
Lisp ввел понятие интернированных строк для своих символов . Исторически структура данных, используемая в качестве внутреннего пула строк, называлась облистом (когда он был реализован как связанный список) или obarray (когда он был реализован как массив).
Современные диалекты Лиспа обычно различают символы от строк; интернирование данной строки возвращает существующий символ или создает новый, имя которого совпадает с этой строкой. Символы часто имеют дополнительные свойства, которых нет у строк (например, хранение связанных значений или пространство имен): различие также полезно для предотвращения случайного сравнения интернированной строки с необязательно интернированной строкой, что может привести к периодическим сбоям в зависимости от шаблоны использования.
Мотивация
Интернирование строк ускоряет сравнение строк, что иногда является узким местом производительности в приложениях (например, компиляторах и средах выполнения динамических языков программирования ), которые в значительной степени полагаются на ассоциативные массивы со строковыми ключами для поиска атрибутов и методов объекта. Без интернирования сравнение двух разных строк может включать изучение каждого символа обеих. [Примечание 1] Это медленный процесс по нескольким причинам: по сути, длина строк составляет O (n) ; обычно требуется чтение из нескольких областей памяти , что требует времени; а операции чтения заполняют кеш процессора, а это означает, что для других нужд остается меньше кеша. С интернированными строками после исходной интернированной операции достаточно простого теста на идентичность объекта ; это обычно реализуется как проверка на равенство указателей, обычно это всего лишь одна машинная инструкция без обращения к памяти вообще.
Интернирование строк также снижает использование памяти, если имеется много экземпляров одного и того же строкового значения; например, он читается из сети или из хранилища . Такие строки могут включать в себя магические числа или информацию о сетевом протоколе . Например, синтаксические анализаторы XML могут вставлять имена тегов и атрибутов для экономии памяти. Сетевая передача объектов через потоки объектов сериализации Java RMI может передавать строки, которые интернированы более эффективно, поскольку дескриптор объекта String используется вместо повторяющихся объектов при сериализации. [7]
вопросы
Многопоточность
Одним из источников недостатков является то, что интернирование строк может быть проблематичным при смешивании с многопоточностью . Во многих системах требуется, чтобы стажеры по строкам были глобальными для всех потоков в адресном пространстве (или в любых контекстах, которые могут совместно использовать указатели), поэтому внутренний пул (ы) - это глобальные ресурсы, которые должны быть синхронизированы для безопасного одновременного доступа. Хотя это влияет только на создание строк (где внутренний пул должен быть проверен и при необходимости изменен), а блокировка с двойной проверкой может использоваться на платформах, где это безопасная оптимизация, необходимость во взаимном исключении при изменении внутреннего пула может быть дорогостоящим. . [8]
Конкуренцию можно также уменьшить, разделив пространство строк на несколько пулов, которые можно синхронизировать независимо друг от друга.
Восстановление неиспользованных интернированных строк
Многие реализации интернированных строк не пытаются вернуть (вручную или иным образом) строки, которые больше не используются. Для приложений, в которых количество интернированных строк невелико или фиксировано, или которые недолговечны, потеря системных ресурсов может быть допустимой. Но для систем с длительным сроком эксплуатации, в которых во время выполнения создается большое количество стажеров-строк, может возникнуть необходимость вернуть неиспользованных стажеров. Эта задача может быть обработана сборщиком мусора , хотя для правильной работы слабые ссылки на строковых стажеров должны храниться в внутреннем пуле.
Смотрите также
Заметки
- ^ Сравнение строк может быть остановлено при несовпадении первого символа. Для строгого равенства длины строк также можно сравнивать перед перемещением по строке: но определение длины строк с завершающим нулем требует обхода строки.
Рекомендации
- ^ "String.Intern Method (String)" . Сеть разработчиков Microsoft . Проверено 25 марта 2017 года .
- ^
String.intern()
- ^ «Глава 15. Выражения» . docs.oracle.com . Проверено 30 января 2019 .
- ^ "lua-users wiki: неизменяемые объекты" . lua-users.org . Проверено 30 января 2019 .
- ^ рпетруша. «Строковый класс (система)» . docs.microsoft.com . Проверено 30 января 2019 .
- ^ «Глава 5. Конверсии и акции» . docs.oracle.com . Проверено 30 января 2019 .
- ^ «Спецификация сериализации объектов Java: 1 - Архитектура системы» . docs.oracle.com . Проверено 30 января 2019 .
- ^ админ (3 сентября 2013). «String.intern в Java 6, 7 и 8 - многопоточный доступ» . java-performance.info . Проверено 30 января 2019 .
Внешние ссылки
- Visual J # String класс
- Класс .NET String
- Библиотека Java Guava - Interner - Non-permgen String.intern и поддерживает другие неизменяемые типы со слабыми и сильными ссылочными реализациями