String.intern () против ручного преобразования строки в идентификатор?

Question

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

public class Name {
    public static Map<String, Name> names = new SomeMap<String, Name>();
    public static Name from(String s) {
        Name n = names.get(s);
        if (n == null) {
            n = new Name(s);
            names.put(s, n);
        }
        return n;
    }
    private final String str;
    private Name(String str) { this.str = str; }
    @Override public String toString() { return str; }
    // equals() and hashCode() are not overridden!
}

Я почти уверен, что одной из этих программ была javac из OpenJDK, так что это не какое-то игрушечное приложение. Конечно, реальный класс был более сложным (и я думаю, что он реализовал CharSequence), но вы поняли - вся программа была засорена Name в любом месте, где вы ожидаете String, и в редких случаях, когда строка была необходима манипуляция, она преобразовывалась в строки и затем снова кэшировала их, концептуально:

Name newName = Name.from(name.toString().substring(5));

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

...
При вызове метода intern, если пул уже содержит строку, равную этому объекту String, как определено методом equals (Object), возвращается строка из пула. В противном случае этот объект String добавляется в пул и возвращается ссылка на этот объект String.

Отсюда следует, что для любых двух строк s и t s.intern () == t.intern () имеет значение true, если и только если s.equals (t) имеет значение true.
...

Итак, Каковы преимущества и недостатки ручного управления Name -подобным классом по сравнению с использованием intern()?

То, о чем я до сих пор думал, было:

• Управление картой вручную означает использование обычной кучи, intern() использует permgen.
• При ручном управлении картой вы наслаждаетесь проверкой типов, которая может что-то проверить, является Name, в то время как интернированная строка и не интернированная строка имеют одинаковый тип, так что в некоторых местах можно забыть интернирование.
• Использование intern() означает повторное использование существующего, оптимизированного, проверенного и проверенного механизма без кодирования каких-либо дополнительных классов.
• Ручное управление картой приводит к тому, что код становится более запутанным для новых пользователей, а сложные операции становятся более громоздкими.

... но я чувствую, что мне здесь чего-то не хватает.

Answer 1

К сожалению, String.intern() может быть медленнее, чем простой синхронизированный HashMap. Он не должен быть таким медленным, но на сегодняшний день в Oracle JDK он медленный (вероятно, из-за JNI)

Еще одна вещь для рассмотрения: вы пишете парсер; вы собрали несколько символов в char[], и вам нужно сделать из них строку. Поскольку строка, вероятно, является общей и может использоваться совместно, мы хотели бы использовать пул.

String.intern() использует такой пул; но чтобы посмотреть вверх, вам понадобится строка для начала. Итак, нам нужно new String(char[],offset,length) сначала.

Мы можем избежать этих издержек в пользовательском пуле, где поиск может быть выполнен непосредственно на основе char[],offset,length. Например, пул является trie . Скорее всего, строка находится в пуле, поэтому мы получим строку без выделения памяти.

Если мы не хотим писать свой собственный пул, а используем старый добрый HashMap, нам все равно нужно создать ключевой объект, который обернет char[],offset,length (что-то вроде CharSequence). Это все еще дешевле, чем новая строка, так как мы не копируем символы.

Answer 2

String.intern () в Java 5.0 и 6 использует пространство perm gen, которое обычно имеет небольшой максимальный размер. Это может означать, что вам не хватает места, даже если есть много свободной кучи.

Java 7 использует свою обычную кучу для хранения строк intern () ed.

Сравнение строк это довольно быстро, и я не думаю, что есть много преимуществ в сокращении времени сравнения, если учесть накладные расходы.

Другая причина, по которой это может быть сделано, - это если много повторяющихся строк. Если дублирования достаточно, это может сэкономить много памяти.

Более простой способ кэширования строк - использовать кэш LRU, такой как LinkedHashMap

private static final int MAX_SIZE = 10000;
private static final Map<String, String> STRING_CACHE = new LinkedHashMap<String, String>(MAX_SIZE*10/7, 0.70f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > 10000;
    }
};

public static String intern(String s) {
    // s2 is a String equals to s, or null if its not there.
    String s2 = STRING_CACHE.get(s);
    if (s2 == null) {
        // put the string in the map if its not there already.
        s2 = s;
        STRING_CACHE.put(s2,s2);
    }
    return s2;
}

Вот пример того, как это работает.

public static void main(String... args) {
    String lo = "lo";
    for (int i = 0; i < 10; i++) {
        String a = "hel" + lo + " " + (i & 1);
        String b = intern(a);
        System.out.println("String \"" + a + "\" has an id of "
                + Integer.toHexString(System.identityHashCode(a))
                + " after interning is has an id of "
                + Integer.toHexString(System.identityHashCode(b))
        );
    }
    System.out.println("The cache contains "+STRING_CACHE);
}

печать

String "hello 0" has an id of 237360be after interning is has an id of 237360be
String "hello 1" has an id of 5736ab79 after interning is has an id of 5736ab79
String "hello 0" has an id of 38b72ce1 after interning is has an id of 237360be
String "hello 1" has an id of 64a06824 after interning is has an id of 5736ab79
String "hello 0" has an id of 115d533d after interning is has an id of 237360be
String "hello 1" has an id of 603d2b3 after interning is has an id of 5736ab79
String "hello 0" has an id of 64fde8da after interning is has an id of 237360be
String "hello 1" has an id of 59c27402 after interning is has an id of 5736ab79
String "hello 0" has an id of 6d4e5d57 after interning is has an id of 237360be
String "hello 1" has an id of 2a36bb87 after interning is has an id of 5736ab79
The cache contains {hello 0=hello 0, hello 1=hello 1}

Это обеспечит ограничение числа кэшей intern () ed Strings.

Более быстрый, но менее эффективный способ - использовать фиксированный массив.

private static final int MAX_SIZE = 10191;
private static final String[] STRING_CACHE = new String[MAX_SIZE];

public static String intern(String s) {
    int hash = (s.hashCode() & 0x7FFFFFFF) % MAX_SIZE;
    String s2 = STRING_CACHE[hash];
    if (!s.equals(s2))
        STRING_CACHE[hash] = s2 = s;
    return s2;
}

Тест выше работает так же, за исключением того, что вам нужно

System.out.println("The cache contains "+ new HashSet<String>(Arrays.asList(STRING_CACHE)));

для распечатки содержимого, которое показывает следующее, включите в null пустые записи.

The cache contains [null, hello 1, hello 0]

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

Answer 3

Я бы всегда использовал Map, потому что intern() имеет для выполнения (возможно, линейного) поиска внутри пула строк String.Если вы делаете это довольно часто, это не так эффективно, как Карта - Карта создана для быстрого поиска.

Answer 4

Каковы преимущества и недостатки ручного управления именованным классом по сравнению с использованием intern ()

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

Добавление простой проверки к конструктору Name

Name(String s) {
  if (!isValidName(s)) { throw new IllegalArgumentException(s); }
  ...
}

может обеспечить * отсутствие Name экземпляров, соответствующих недопустимым именам, таким как "12#blue,,"это означает, что методам, которые принимают Name s в качестве аргументов и которые используют Name s, возвращенные другими методами, не нужно беспокоиться о том, где могут появиться недействительные Name s.

Чтобы обобщить этот аргументПредставьте, что ваш код - это замок со стенами, предназначенными для защиты от недопустимых входов.Вы хотите, чтобы некоторые входные данные проходили, поэтому вы устанавливаете ворота с охранниками, которые проверяют входные данные по мере их поступления.Конструктор Name является примером охранника.

Разница между String и Name заключается в том, что String s нельзя защитить.Любой фрагмент кода, злонамеренный или наивный, внутри или за пределами периметра, может создать любое строковое значение.Багги String код манипуляции аналогичен вспышке зомби внутри замка.Охранники не могут защитить инвариантов, потому что зомби не нужно проходить мимо них.Зомби просто распространяют и портят данные по ходу их работы.

То, что значение "is" String удовлетворяет меньшему количеству полезных инвариантов, чем значение "is" Name.

См. строчно набрал для другого взгляда на ту же тему.

* - обычная повторная десериализация предостережения Serializable, позволяющая обходить конструктор.

Answer 5

Итак, каковы преимущества и недостатки ручного управления именованным классом по сравнению с использованием intern ()?

Одно из преимуществ:

Отсюда следует, что для любых двух строк s и t s.intern () == t.intern () имеет значение true, если и только если s.equals (t) имеет значение true.

В программетам, где нужно сравнивать множество маленьких строк, это может окупиться.Кроме того, это экономит место в конце.Рассмотрим исходную программу, которая довольно часто использует такие имена, как AbstractSyntaxTreeNodeItemFactorySerializer.С intern () эта строка будет сохранена один раз и все.Все остальное, если только ссылки на это, но ссылки у вас все равно есть.