Строковое интернирование
В информатике интернирование строк — это метод хранения только одной копии каждого отдельного строкового значения, которая должна быть неизменяемой . [1] Интернирование строк делает некоторые задачи обработки строк более эффективными по времени или пространству за счет увеличения времени при создании или интернировании строки. Различные значения хранятся во внутреннем пуле строк .
Единственная копия каждой строки называется ее интерном и обычно ищется методом класса строки, например String.intern(). [2] на Яве . Все строки констант времени компиляции в 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]
История
[ редактировать ]Лисп ввел понятие интернированных строк для своих символов . Исторически структура данных, используемая в качестве внутреннего пула строк, называлась oblist ( когда она была реализована как связанный список) или 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: Неизменяемые объекты» . lua-users.org . Проверено 30 января 2019 г.
- ^ рпетруша. «Строковый класс (система)» . docs.microsoft.com . Проверено 30 января 2019 г.
- ^ «Глава 5. Конверсии и продвижение» . docs.oracle.com . Проверено 30 января 2019 г.
- ^ «Спецификация сериализации объектов Java: 1 — Архитектура системы» . docs.oracle.com . Проверено 30 января 2019 г.
- ^ «String.intern в Java 6, 7 и 8 — многопоточный доступ» . java- Performance.info . 3 сентября 2013 года . Проверено 30 января 2019 г.