Интернирование строк действительно полезно?

Question

Некоторое время назад я разговаривал о строках и различных языках, и возникла тема интернирование строк . Очевидно, Java и .NET Framework делают это автоматически со всеми строками, а также с несколькими языками сценариев. Теоретически, это экономит память, потому что вы не получаете несколько копий одной и той же строки, и это экономит время, потому что сравнения на равенство строк - это простое сравнение указателей, а не O (N), проходящий через каждый символ строки.

Но чем больше я об этом думаю, тем больше скептически отношусь к преимуществам концепции. Мне кажется, что преимущества в основном теоретические:

• Прежде всего, чтобы использовать автоматическое интернирование строк, все строки должны быть неизменяемыми, что делает многие задачи по обработке строк сложнее, чем они должны быть. (И да, я слышал все аргументы в пользу неизменности вообще. Это не главное.)
• Каждый раз, когда создается новая строка, она должна проверяться по таблице интернирования строк, что является по крайней мере операцией O (N). ( EDIT: Где N - размер строки, а не размер таблицы, поскольку это сбивает с толку людей.) Поэтому, если отношение сравнений равенства строк к созданию новой строки не слишком велико, маловероятно что сэкономленное чистое время является положительным значением.
• Если в таблице равенства строк используются сильные ссылки, строки никогда не будут собирать мусор, когда они больше не нужны, что приводит к потере памяти. С другой стороны, если таблица использует слабые ссылки, тогда классу строк необходим какой-то финализатор для удаления строки из таблицы, что замедляет процесс GC. (Это может быть довольно значительным, в зависимости от того, как реализована строковая внутренняя таблица. В худшем случае удаление элемента из хеш-таблицы может потребовать O (N) перестроения всей таблицы при определенных обстоятельствах.)

Это всего лишь результат того, что я подумал о деталях реализации. Я что-то пропустил? Обеспечивает ли интернирование строк какие-либо существенные преимущества в общем случае?

РЕДАКТИРОВАТЬ 2: Хорошо, очевидно, я действовал из ошибочной предпосылки. Человек, с которым я разговаривал, никогда не указывал, что интернирование строк было необязательным для вновь создаваемых строк, и на самом деле создавало сильное впечатление, что все наоборот. Спасибо Джону за разъяснение. Еще один принятый для него ответ.

Answer 1

Нет, Java и .NET не делают это "автоматически со всеми строками".Они (ну, Java и C #) делают это с константами строковыми выражениями, выраженными в байт-коде / IL, и по запросу через String.intern и String.Intern(.NET) методы.Точная ситуация в .NET интересна, но в основном компилятор C # гарантирует, что каждая ссылка на одинаковую строковую константу в сборке в конечном итоге ссылается на один и тот же строковый объект.Это может быть эффективно сделано во время инициализации типа и может сэкономить кучу памяти.

Это не происходит каждый раз, когда создается новая строка.

(Что касается неизменности строк, я, например, чрезвычайно рад, что строки неизменяемы. Я не хочу снимать копию каждый раз, когда получаю параметр и т. Д., Большое спасибо.Мы не видели, что это усложняет задачи обработки строк, либо ...)

И, как отмечали другие, поиск строки в хеш-таблице обычно не является операцией O (n), если только вы неневероятно неудачно с хеш-коллизиями ...

Лично я не использую интернирование строк в коде пользовательской земли;если мне нужен какой-то кеш строк, я создам HashSet<string> или что-то подобное.Это может быть полезно в различных ситуациях, когда вы ожидаете встретить одни и те же строки несколько раз (например, имена элементов XML), но с простой коллекцией вы не загрязняете системный кэш.

Answer 2

Прежде всего, чтобы использовать автоматическую интернирование строк, все строки должны быть неизменяемый, что делает многие задачи обработки строк сложнее, чем они должны быть. (И да, я слышал все аргументы за неизменность в целом. Дело не в этом.)

Это правда, и строка неизменна в Java. Я не уверен, что это плохо. Не вдаваясь в неизменность и изменяемость, мне нравится думать, что это отличный дизайн из-за кеширования и гораздо большей простоты, к которой я не буду подходить.

Каждый раз, когда создается новая строка, она должна быть проверена на соответствие таблица интернирования строк, которая является как минимум операцией O (N). Так что если отношение сравнения равенства строк к созданию новой строки довольно высока, маловероятно, что сэкономленное время является положительным значение.

Не совсем O (n). Вы можете создавать хеш-карты и / или другие структуры данных, которые приведут это к почти постоянному поиску.

Если в таблице равенства строк используются сильные ссылки, строки будут никогда не собирать мусор, когда он больше не нужен, таким образом тратить память. С другой стороны, если таблица использует слабые ссылки, тогда строковому классу требуется какой-то финализатор для удаления строка из таблицы, тем самым замедляя процесс GC. (Которая могла бы быть довольно значительным, в зависимости от того, как таблица строк интерна реализованы. В худшем случае удаление элемента из хеш-таблицы может требует O (N) перестроить всю таблицу под определенным обстоятельства.)

Вы правы в этом, и я бы с вами согласился. Кроме того, я чувствую, что обработка GC и незначительна. Преимущества в долгосрочной перспективе гораздо полезнее, чем сборщик мусора, выполняющий дополнительную проверку. Я не уверен, что вы имеете в виду O (n) для удаления из хеш-таблицы. Большинство операций с хеш-таблицами: O (1)

Итак, в целом, я думаю, что вы предполагаете, что большинство операций являются линейными. Но поиск строк ближе к постоянному времени. Таким образом, этот подход будет иметь незначительную потерю производительности, но огромный выигрыш в памяти. Что, я бы сказал, того стоит.

Вот хорошая цитата о том, что на самом деле происходит и как это экономит память.

Для экономии памяти (и ускорения тестирования на равенство) Java поддерживает «Интернирование» струн. Когда метод intern () вызывается на String, поиск выполняется на таблице интернированных строк. Если Строковый объект с тем же содержимым уже находится в таблице, ссылка на строку в таблице возвращается. В противном случае Строка добавляется в таблицу и возвращается ссылка на нее.

Answer 3

a.equals (b) очень быстр для случайных строк. Это медленно только для строк, которые длинные и одинаковые (или почти одинаковые)

Random rand = new Random(1);
String[] list = new String[2000];
for(int i=0;i<list.length;i++)
    list[i] = "1234567"+Long.toString(rand.nextInt(36*37), 36); // semi random
int count = 0;
long start = System.nanoTime();
for(int i=0;i<list.length;i++)
    for(int j=0;j<list.length;j++)
        if (list[i].equals(list[j]))
            count++;
long time = System.nanoTime() - start;
System.out.printf("The average time for equals() was %,d ns.%n", time/list.length/list.length);

на ноутбуке с частотой 2,3 ГГц

The average time for equals() was 19 ns.

Если вы интернировали () первое значение и вам нужно интернировать () одно значение для сравнения

       if (list[i] == list[j].intern())

печать

The average time for equals() was 258 ns.

Это распространенный случай, поскольку у вас часто есть одно значение, которое, как вы знаете, является интернированным, а второе - входным, а не интернированным.

если вы используете только строки International и == it и не учитываете стоимость, выведите

The average time for equals() was 4 ns.

Что во много раз быстрее, если вы проводите миллионы сравнений. Однако для небольшого числа сравнений вы экономите 8 нс, но это может стоить на 250 нс больше.

Может быть проще избежать intern () и использовать equals ().

Answer 4

Вот документация Python , взятая из него:

sys.intern(string)

Введите строку в таблицу «внутренних» строк и верните внутреннюю строку- которая является самой строкой или копией.Внутренние строки полезны для получения небольшой производительности при поиске в словаре - если ключи в словаре интернированы, а ключ поиска интернирован, сравнение ключей (после хэширования) может быть выполнено сравнением указателя вместо сравнения строк.Обычно имена, используемые в программах Python, автоматически интернируются, а словари, используемые для хранения атрибутов модуля, класса или экземпляра, имеют интернированные ключи.

Строковые строки не являются бессмертными;вы должны хранить ссылку на возвращаемое значение intern (), чтобы получить от него выгоду.

Answer 5

Интернирование строк полезно, когда вам нужно несколько раз сравнить строки (1) из конечного набора (2).

Тогда издержки интернирования строки перевешиваются благодаря возможности делать быстрый == вместо equals().

Иногда это может быть быстрее, чем при использовании HashMap, который использует вызовы hashCode() и equals().

Answer 6

Обеспечивает ли интернирование строк какие-либо существенные преимущества в общем случае?

Да.Это огромная.Попробуйте это в Java.

Напишите простые тесты, которые сравнивают тысячи полуслучайных строк на равенство с интернированием и без него.

a.equals( b )  is slow

a == b is fast.

Answer 7

Все перечисленные вами пункты действительны в определенной степени.Но есть и важные контраргументы.

1. Неизменность очень важна, особенно если вы используете хеш-карты, и они часто используются.
2. Операции компоновки строки очень медленныев любом случае, потому что вам нужно постоянно перераспределять массив, содержащий символы.
3. С другой стороны, subString() операции выполняются очень быстро.
4. Строковое равенство действительно часто используется, и вы 'не теряй ничего там.Причина в том, что строки не интернируются автоматически.На самом деле в Java, если ссылки различаются, equals() возвращается к символьному сравнению.
5. Очевидно, что использование сильных ссылок для таблицы интернов не является хорошей идеей.Вы должны жить с накладными расходами GC.
6. Обработка строк Java была разработана с целью экономии пространства, особенно для константных строк и операций с подстрокой.

В целом я бы сказал,в большинстве случаев того стоит и хорошо вписывается в концепцию кучи, управляемой виртуальной машиной.Я мог бы представить некоторые особые сценарии, где это может быть настоящей болью.