Почему string.intern () такой медленный?

Question

Прежде чем кто-либо подвергнет сомнению факт использования string.intern(), позвольте мне сказать, что он мне нужен в моем конкретном приложении по соображениям памяти и производительности. ^[1]

Итак, до сих пор я использовал String.intern() и предполагал, что это самый эффективный способ сделать это. Однако я заметил, что с давних пор это является узким местом в программном обеспечении. ^[2]

Затем, совсем недавно, я попытался заменить String.intern() огромной картой, где я помещаю / получаю строки, чтобы каждый раз получать уникальный экземпляр. Я ожидал, что это будет медленнее ... но все было с точностью до наоборот! Это было невероятно быстро! Замена intern() путем нажатия / опроса карты (которая достигает того же результата) привела к ускорению более чем на один порядок.

Вопрос в том, почему intern() такой медленный?!? Почему бы тогда просто не создать резервную копию с помощью карты (или, собственно, просто настроенного набора), и это было бы невероятно быстрее? Я озадачен.

[1]: Для неубедительных: он обрабатывается на естественном языке и должен обрабатывать гигабайты текста, поэтому необходимо избегать много экземпляров одной и той же строки, чтобы избежать разрыва памяти и сравнения ссылочных строк, чтобы быть достаточно быстрым .

[2]: без него (нормальных строк) это невозможно, при этом этот конкретный шаг остается наиболее интенсивным для вычислений

EDIT:

Из-за удивительного интереса к этому посту, вот код для его проверки:

http://pastebin.com/4CD8ac69

И результаты интернирования чуть более 1 миллиона строк:

• HashMap: 4 секунды
• String.intern(): 54 секунды

Из-за того, что во избежание некоторого разогрева / кэширования ввода-вывода ОС и тому подобного, эксперимент был повторен путем инвертирования порядка обоих тестов:

• String.intern(): 69 секунд
• HashMap: 3 секунды

Как видите, разница очень заметна, более чем в десять раз. (Использование OpenJDK 1.6.0_22 64 бит ... но использование солнца привело к аналогичным результатам, я думаю)

Answer 1

В этой статье обсуждается реализация String.intern().В Java 6 и 7 реализация использовала хеш-таблицу фиксированного размера (1009), чтобы при увеличении числа записей производительность становилась O (n).Фиксированный размер можно изменить с помощью -XX:StringTableSize=N.По-видимому, в Java8 размер по умолчанию больше, но проблема остается.

Answer 2

Наиболее вероятная причина разницы в производительности: String.intern() - это собственный метод, а вызов нативного метода влечет за собой огромные накладные расходы.

Так почему же это нативный метод?Возможно, потому что он использует пул констант, который является низкоуровневой структурой VM.

Answer 3

@ Майкл Боргвардт сказал это в комментарии:

intern () не синхронизирован, по крайней мере, на уровне языка Java.

Я думаю, что вы имеете в видучто метод String.intern() не объявлен как synchronized в исходном коде класса String.И действительно, это верное утверждение.

Однако:

• Объявление intern() как synchronized блокирует только текущий экземпляр String, поскольку это экземплярметод, а не статический метод.Таким образом, они не могли реализовать синхронизацию пула строк таким способом.

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

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

Answer 4

Не могу сказать ни о каком большом опыте с этим, но о документах String:

"Когда вызывается метод intern, если пул уже содержит строку, равную этому String объекту, как определено методом {@link #equals (Object)}, тогда возвращается строка из пула. В противном случае, этот String объект добавляется в пул и возвращается ссылка на этот String объект. "

При работе с большим количеством объектов любое решение, включающее хеширование, превосходит решение, которое не делает. Я думаю, вы просто видите результат неправильного использования функции языка Java. Стажеры не могут выступать в качестве карты строк для вашего использования. Вы должны использовать карту для этого (или установить, в зависимости от обстоятельств). Таблица String предназначена для оптимизации на уровне языка, а не на уровне приложения.

Answer 5

Принятый ответ неверен. Строка. Замедление происходит из-за двух причин:
1. ограничение -XX: StringTableSize.
В java он использует внутреннюю хеш-таблицу для управления строковым кэшем, в java 6 значение StringTableSize по умолчанию равно 1009, что означает, что string.intern равен O (номер строкового объекта / 1009), когда создается все больше строковых объектов, становится медленнее.

\ openjdk7 \ точка доступа \ SRC \ доля \ ут \ файлов классов \ symbolTable.cpp

oop StringTable::intern(Handle string_or_null, jchar* name,  
                        int len, TRAPS) {  
  unsigned int hashValue = java_lang_String::hash_string(name, len);  
  int index = the_table()->hash_to_index(hashValue);  
  oop string = the_table()->lookup(index, name, len, hashValue);  
  // Found  
  if (string != NULL) return string;  
  // Otherwise, add to symbol to table  
  return the_table()->basic_add(index, string_or_null, name, len,  
                                hashValue, CHECK_NULL);  
}

2. В java 6 пул строкового кэша находится в области перми, а не в куче. Большую часть времени мы конфигурируем размер перми относительно небольшой.