10 ms·

String.intern()

145 points by dmit 9y ago

deleted 9y ago
[deleted]
TheGuyWhoCodes 9y ago
The code creates unique strings to "interns" which most likely isn't what would happen in a real world application (unless you know... code without thought), you'd inter strings with low variance usually. Not saying that it won't be slower but the memory usage might be lower.
- wtetzner 9y ago
  Yeah, blindly interning strings isn't a good idea, but it can be useful for certain use cases. For example, keys of maps where you know the keys won't vary much. It can reduce memory usage, and improve lookup performance (since doing a lookup requires a string comparison).
relics443 9y ago
"The performance is at the mercy of the native HashTable implementation, which may lag behind what is available in high-performance Java world, especially under concurrent access." What native HashTable is used? Shouldn't the JVM be using an optimized one?
- QuercusMax 9y ago
  I think by "native" they mean "implemented-in-c++-by-the-JVM", which potentially vary; not java.util.HashTable, which should be pretty standard across JVM implementations.
  - electrum 9y ago
    Yes, although Hashtable is legacy from JDK 1.0. New code should use HashMap or ConcurrentHashMap.
    - deleted 9y ago
      [deleted]
    - Tharkun 9y ago
      Please be careful with blanket statements like this. HashMap, Hashtable and ConcurrentHashMap behave differently in certain (subtle?) ways. ConcurrentHashMap doesn't like NULL but is thread-safe. Hashtable is synchronized, slow and thread-safe, but doesn't mind NULL. HashMap is not thread safe and doesn't mind NULL. Edit: pardon the dupes, on unreliable mobile link :-(
      - josefx 9y ago
        > Hashtable is synchronized, slow and thread-safe, but doesn't mind NULL. The issue with Hashtable or rather all legacy collection classes is that the API is rarely useful without additional synchronization. So you might as well use a HashMap wrapped by Collections.synchronizedMap or use a ConcurrentHashMap with a placeholder object instead of null.
- jakewins 9y ago
  It's using a custom c++ hashtable: https://github.com/JetBrains/jdk8u_hotspot/blob/master/src/share/vm/classfile/symbolTable.hpp#L255 https://github.com/JetBrains/jdk8u_hotspot/blob/master/src/s... Interestingly, the hash table implementation it's subclassing has changed from `HashTable` to `RehashableHashtable` between JDK7 and JDK8, so I guess there's at least been work to try and improve the performance there. The hashmap header is here, code lives in the matching cpp file in the same directory: https://github.com/JetBrains/jdk8u_hotspot/blob/master/src/share/vm/utilities/hashtable.hpp#L277 https://github.com/JetBrains/jdk8u_hotspot/blob/master/src/s...
  - pjmlp 9y ago
    That is an implementation detail, there are many JVMs to choose from.
    - jakewins 9y ago
      Absolutely - that's what the blog post is about, how OpenJDK's particular implementation behaves. When Aleksey is talking about the hashtables not being resizeable, he's talking about the project he works on, which is the code above.
      - pjmlp 9y ago
        I missed that.
- pjmlp 9y ago
  That is an implementation detail, there are many JVMs implementations to choose from.
gravypod 9y ago
This, and the few other articles up, are a great series. Having done Java development now for 30% of my life these are some amazing pointers. I'd love to buy a hard copy of these if they ever get up to a few dozen articles. Would be good to give to middle-experience devs (like myself) in the future.
- AKluge 9y ago
  Some good content along the same vein with 16 years worth of articles: http://www.javaspecialists.eu/ http://www.javaspecialists.eu/
Terr_ 9y ago
Every time I see String.intern() my mind leaps to the problem of new Java programmers who are misled into this: String a = "hello"; String b = "world"; assert a != b; b = "hello"; assert a == b; // OH NICE I'LL USE == FOR STRING COMPARISONS NOW It works cause source-code literals are intern'ed down into identical objects by the compiler, but that's a special case that won't apply to strings created at runtime.
- userbinator 9y ago
  new Java programmers Or perhaps interns? ;-P In fact, I've wondered about the origins of the term "intern" since I first heard of it; the technique was already known to me and likely others as "tokenising" before that, however, since compilers would often have to compare identifiers and doing this to them made it much faster.
  - wtetzner 9y ago
    > In fact, I've wondered about the origins of the term "intern" since I first heard of it I always assumed it came from internalize, or something like that.
    - derefr 9y ago
      I was curious, but a good amount of Googling didn't turn up any etymology. I'll take a guess, though, that it's from Common Lisp, because CL's intern function (http://clhs.lisp.se/Body/f_intern.htm http://clhs.lisp.se/Body/f_intern.htm) is clearly part of a suite of names (intern, unintern, :internal, :external) where, in context, "intern" makes complete sense as the name for the function.
      - smarks 9y ago
        Usage of "intern" in this sense is much older than Common Lisp. The earliest reference I could find in a few minutes of searching is from 1974, from the MACLISP Reference Manual: http://www.softwarepreservation.org/projects/LISP/MIT/Moon-MACLISP_Reference_Manual-Apr_08_1974.pdf http://www.softwarepreservation.org/projects/LISP/MIT/Moon-M... See sections 6.3 and 6.4 and the glossary for definitions and uses of the word. Unfortunately they don't shed any light on where the term "intern" comes from. Typical usage is that a string is «"interned" or registered in an obarray» but it doesn't explain much more than that. Interning occurs most often at read time, when a string read from the input is turned into an atom, so I'd guess that "intern" is short for "internalize" or similar.
Robotbeat 9y ago
Is "Anatomy Park" a Rick and Morty reference? http://rickandmorty.wikia.com/wiki/Anatomy_Park_(episode) http://rickandmorty.wikia.com/wiki/Anatomy_Park_(episode)
filereaper 9y ago
Total aside from main topic, I love shipilev's posts. If there are other core JVM developers that have similar blogs, I'd love to hear about them here.
- deleted 9y ago
  [deleted]
deleted 9y ago
[deleted]
deepsun 9y ago
Have been doing Java for 14 years so far, never ever needed the .intern(). I can imagine it's use-case, but anyway does seem pretty rare case.
- 35bge57dtjku 9y ago
  Deserializing tons of records all having one of a few values for a particular field is an easy and probably fairly common use case.
kristianp 9y ago
It would be interesting to know where it's used, was it used in the JDK for example?
zaroth 9y ago
The instrumentation here is impressive. The amount of data inspection done with just a few simple commands is a bit overwhelming. Frankly, I rarely hope to find myself looking at this level of metrics. There's a lot down there I like to take for granted. But more likely I try to use methods like string.Intern() exactly never. Use code you know and understand. Frankly, use code you can trust. And wtf would trust a method string.Inter() to do... exactly, what? If you are writing a function to do something the name of the function must be the thing being done. What the heck is a 'static internalize'? The explicit HashMap was a few lines of code, and it's the most basic and obvious, and surprisingly performant approach. So definitely I agree you must use your own HashMap and not a static internalizer.
emmelaich 9y ago
I'd never seen the @Benchmark annotation before so I looked it up. The blog author is also one of JMH's authors. http://openjdk.java.net/projects/code-tools/jmh/ http://openjdk.java.net/projects/code-tools/jmh/
lorenzosnap 9y ago
We built an inmemory map and we were using String.intern for both keys and values. We could see that we were saving lots of memory but we had the problems described in the article. We then built our own 'String.intern' by using yet another static HashMap. It worked. It was the simplest alternative and it just did the job. Thanks alekskey for the nice article.
zde 9y ago
String.intern() would suck much less if strings had an "IS_INTERNED" flag which would prevent hashtable lookups for already interned strings. Really sad given the insane overhead Java strings have.
- leventov 9y ago
  No, it would suck more, because currently you have an option to avoid string.intern() altogether (and that is what you should do), and pay nothing for that in runtime. Another boolean flag may cost extra 4-8 bytes on the heap for each String object, whether you use String.intern() or not.
jwilk 9y ago
Please consider adding "JVM Anatomy Park" to the title.
derriz 9y ago
This is really an unscientific claim but I ran a hand crafted/hacked benchmark just to get a feeling for the numbers. For 5 to 35 character Strings, == is 20 to 40 times faster than String.equals(). Given that s1.equals(s2) if and only if s1.intern() == s2.intern() (assuming you haven't filled the string table), then this looks like an opportunity for a significant optimization. Before doing this, I had hoped that String.equals might check if both were "interned" and shortcut the character by character comparison if this was the case by just comparing references. But interpreting the results of my rough benchmark would suggest this isn't what is happening which would agree with the source provided for the String.equals method. Java String comparison is absolutely ubiquitous so I would have expected that an optimization like this might have been considered? Having said that, the supplied rt.jar source also suggests that the String.hashCode() computation isn't cached/memoized. This strikes me as odd given that Strings are immutatable and Strings are one of the most common key type for Maps.
- etatoby 9y ago
  You should compare the cost of one (or two) .intern() plus '==' against a single .equals() For example, if your code needs 10 .intern() and then performs 100 '==', that is possibly going to be faster than performing the equivalent 100 .equals() (or maybe not) But if you are comparing a single couple of strings, .equals() is always going to be faster. Not to mention that if you .intern() random strings, you risk running out of PermGen space. Even in the case of 100 comparisons among 10 strings, you may be better off using a custom HashMap. You can find all this information in the article.
  - derriz 9y ago
    I'm not suggesting that .equals() should be implemented by 2 inter() operations followed by a reference comparison. But that the implementation check whether the pair of Strings happened to be already .intern()ed, and then use the short circuit of a reference comparison. A programmer could then decide to intern _some_ non-constant Strings in their application if it made sense (i.e. they were frequently used in comparisons or as hash keys). And I don't think you can't run out of permgen as the String pool is a fixed size - unless I am misreading that section of the article. However now that I've thought about a bit more, I think the flaw in the idea is unrelated to your points but that currently it's not cheap to determine if a particular String is interned. The StringTable implementation would have to be changed otherwise it would require adding storage overhead to every String which would not be acceptable. This is also probably why .hashCode() doesn't memoize it's results.
khana 9y ago
intern() should be internal; not a publicly exposed 'dongle' switch. Never used it. Won't ever need it.
kazinator 9y ago
Also see: XInternAtom (XWindow function) RegisterClass (Windows)
pimlottc 9y ago
> in OpenJDK, String.intern() is native, and it actually calls into JVM, to intern the String in the native JVM String pool. How much of this also applies when using the standard Oracle JDK?

145 points by dmit 9y ago

deleted 9y ago

[deleted]

The code creates unique strings to "interns" which most likely isn't what would happen in a real world application (unless you know... code without thought), you'd inter strings with low variance usually. Not saying that it won't be slower but the memory usage might be lower.

wtetzner 9y ago
Yeah, blindly interning strings isn't a good idea, but it can be useful for certain use cases. For example, keys of maps where you know the keys won't vary much. It can reduce memory usage, and improve lookup performance (since doing a lookup requires a string comparison).

relics443 9y ago

"The performance is at the mercy of the native HashTable implementation, which may lag behind what is available in high-performance Java world, especially under concurrent access." What native HashTable is used? Shouldn't the JVM be using an optimized one?

QuercusMax 9y ago
I think by "native" they mean "implemented-in-c++-by-the-JVM", which potentially vary; not java.util.HashTable, which should be pretty standard across JVM implementations.
- electrum 9y ago
  Yes, although Hashtable is legacy from JDK 1.0. New code should use HashMap or ConcurrentHashMap.
  - deleted 9y ago
    [deleted]
  - Tharkun 9y ago
    Please be careful with blanket statements like this. HashMap, Hashtable and ConcurrentHashMap behave differently in certain (subtle?) ways. ConcurrentHashMap doesn't like NULL but is thread-safe. Hashtable is synchronized, slow and thread-safe, but doesn't mind NULL. HashMap is not thread safe and doesn't mind NULL. Edit: pardon the dupes, on unreliable mobile link :-(
    - josefx 9y ago
      > Hashtable is synchronized, slow and thread-safe, but doesn't mind NULL. The issue with Hashtable or rather all legacy collection classes is that the API is rarely useful without additional synchronization. So you might as well use a HashMap wrapped by Collections.synchronizedMap or use a ConcurrentHashMap with a placeholder object instead of null.
jakewins 9y ago
It's using a custom c++ hashtable: https://github.com/JetBrains/jdk8u_hotspot/blob/master/src/share/vm/classfile/symbolTable.hpp#L255 https://github.com/JetBrains/jdk8u_hotspot/blob/master/src/s... Interestingly, the hash table implementation it's subclassing has changed from `HashTable` to `RehashableHashtable` between JDK7 and JDK8, so I guess there's at least been work to try and improve the performance there. The hashmap header is here, code lives in the matching cpp file in the same directory: https://github.com/JetBrains/jdk8u_hotspot/blob/master/src/share/vm/utilities/hashtable.hpp#L277 https://github.com/JetBrains/jdk8u_hotspot/blob/master/src/s...
- pjmlp 9y ago
  That is an implementation detail, there are many JVMs to choose from.
  - jakewins 9y ago
    Absolutely - that's what the blog post is about, how OpenJDK's particular implementation behaves. When Aleksey is talking about the hashtables not being resizeable, he's talking about the project he works on, which is the code above.
    - pjmlp 9y ago
      I missed that.
pjmlp 9y ago
That is an implementation detail, there are many JVMs implementations to choose from.

gravypod 9y ago

This, and the few other articles up, are a great series. Having done Java development now for 30% of my life these are some amazing pointers. I'd love to buy a hard copy of these if they ever get up to a few dozen articles. Would be good to give to middle-experience devs (like myself) in the future.

AKluge 9y ago
Some good content along the same vein with 16 years worth of articles: http://www.javaspecialists.eu/ http://www.javaspecialists.eu/

Terr_ 9y ago

Every time I see String.intern() my mind leaps to the problem of new Java programmers who are misled into this: String a = "hello"; String b = "world"; assert a != b; b = "hello"; assert a == b; // OH NICE I'LL USE == FOR STRING COMPARISONS NOW It works cause source-code literals are intern'ed down into identical objects by the compiler, but that's a special case that won't apply to strings created at runtime.

userbinator 9y ago
new Java programmers Or perhaps interns? ;-P In fact, I've wondered about the origins of the term "intern" since I first heard of it; the technique was already known to me and likely others as "tokenising" before that, however, since compilers would often have to compare identifiers and doing this to them made it much faster.
- wtetzner 9y ago
  > In fact, I've wondered about the origins of the term "intern" since I first heard of it I always assumed it came from internalize, or something like that.
  - derefr 9y ago
    I was curious, but a good amount of Googling didn't turn up any etymology. I'll take a guess, though, that it's from Common Lisp, because CL's intern function (http://clhs.lisp.se/Body/f_intern.htm http://clhs.lisp.se/Body/f_intern.htm) is clearly part of a suite of names (intern, unintern, :internal, :external) where, in context, "intern" makes complete sense as the name for the function.
    - smarks 9y ago
      Usage of "intern" in this sense is much older than Common Lisp. The earliest reference I could find in a few minutes of searching is from 1974, from the MACLISP Reference Manual: http://www.softwarepreservation.org/projects/LISP/MIT/Moon-MACLISP_Reference_Manual-Apr_08_1974.pdf http://www.softwarepreservation.org/projects/LISP/MIT/Moon-M... See sections 6.3 and 6.4 and the glossary for definitions and uses of the word. Unfortunately they don't shed any light on where the term "intern" comes from. Typical usage is that a string is «"interned" or registered in an obarray» but it doesn't explain much more than that. Interning occurs most often at read time, when a string read from the input is turned into an atom, so I'd guess that "intern" is short for "internalize" or similar.

Robotbeat 9y ago

Is "Anatomy Park" a Rick and Morty reference? http://rickandmorty.wikia.com/wiki/Anatomy_Park_(episode) http://rickandmorty.wikia.com/wiki/Anatomy_Park_(episode)

filereaper 9y ago

Total aside from main topic, I love shipilev's posts. If there are other core JVM developers that have similar blogs, I'd love to hear about them here.

deleted 9y ago
[deleted]

deleted 9y ago

[deleted]

deepsun 9y ago

Have been doing Java for 14 years so far, never ever needed the .intern(). I can imagine it's use-case, but anyway does seem pretty rare case.

35bge57dtjku 9y ago
Deserializing tons of records all having one of a few values for a particular field is an easy and probably fairly common use case.

kristianp 9y ago

It would be interesting to know where it's used, was it used in the JDK for example?

zaroth 9y ago

The instrumentation here is impressive. The amount of data inspection done with just a few simple commands is a bit overwhelming. Frankly, I rarely hope to find myself looking at this level of metrics. There's a lot down there I like to take for granted. But more likely I try to use methods like string.Intern() exactly never. Use code you know and understand. Frankly, use code you can trust. And wtf would trust a method string.Inter() to do... exactly, what? If you are writing a function to do something the name of the function must be the thing being done. What the heck is a 'static internalize'? The explicit HashMap was a few lines of code, and it's the most basic and obvious, and surprisingly performant approach. So definitely I agree you must use your own HashMap and not a static internalizer.

emmelaich 9y ago

I'd never seen the @Benchmark annotation before so I looked it up. The blog author is also one of JMH's authors. http://openjdk.java.net/projects/code-tools/jmh/ http://openjdk.java.net/projects/code-tools/jmh/

lorenzosnap 9y ago

We built an inmemory map and we were using String.intern for both keys and values. We could see that we were saving lots of memory but we had the problems described in the article. We then built our own 'String.intern' by using yet another static HashMap. It worked. It was the simplest alternative and it just did the job. Thanks alekskey for the nice article.

zde 9y ago

String.intern() would suck much less if strings had an "IS_INTERNED" flag which would prevent hashtable lookups for already interned strings. Really sad given the insane overhead Java strings have.

leventov 9y ago
No, it would suck more, because currently you have an option to avoid string.intern() altogether (and that is what you should do), and pay nothing for that in runtime. Another boolean flag may cost extra 4-8 bytes on the heap for each String object, whether you use String.intern() or not.

jwilk 9y ago

Please consider adding "JVM Anatomy Park" to the title.

derriz 9y ago

This is really an unscientific claim but I ran a hand crafted/hacked benchmark just to get a feeling for the numbers. For 5 to 35 character Strings, == is 20 to 40 times faster than String.equals(). Given that s1.equals(s2) if and only if s1.intern() == s2.intern() (assuming you haven't filled the string table), then this looks like an opportunity for a significant optimization. Before doing this, I had hoped that String.equals might check if both were "interned" and shortcut the character by character comparison if this was the case by just comparing references. But interpreting the results of my rough benchmark would suggest this isn't what is happening which would agree with the source provided for the String.equals method. Java String comparison is absolutely ubiquitous so I would have expected that an optimization like this might have been considered? Having said that, the supplied rt.jar source also suggests that the String.hashCode() computation isn't cached/memoized. This strikes me as odd given that Strings are immutatable and Strings are one of the most common key type for Maps.

etatoby 9y ago
You should compare the cost of one (or two) .intern() plus '==' against a single .equals() For example, if your code needs 10 .intern() and then performs 100 '==', that is possibly going to be faster than performing the equivalent 100 .equals() (or maybe not) But if you are comparing a single couple of strings, .equals() is always going to be faster. Not to mention that if you .intern() random strings, you risk running out of PermGen space. Even in the case of 100 comparisons among 10 strings, you may be better off using a custom HashMap. You can find all this information in the article.
- derriz 9y ago
  I'm not suggesting that .equals() should be implemented by 2 inter() operations followed by a reference comparison. But that the implementation check whether the pair of Strings happened to be already .intern()ed, and then use the short circuit of a reference comparison. A programmer could then decide to intern _some_ non-constant Strings in their application if it made sense (i.e. they were frequently used in comparisons or as hash keys). And I don't think you can't run out of permgen as the String pool is a fixed size - unless I am misreading that section of the article. However now that I've thought about a bit more, I think the flaw in the idea is unrelated to your points but that currently it's not cheap to determine if a particular String is interned. The StringTable implementation would have to be changed otherwise it would require adding storage overhead to every String which would not be acceptable. This is also probably why .hashCode() doesn't memoize it's results.

khana 9y ago

intern() should be internal; not a publicly exposed 'dongle' switch. Never used it. Won't ever need it.

kazinator 9y ago

Also see: XInternAtom (XWindow function) RegisterClass (Windows)

pimlottc 9y ago

> in OpenJDK, String.intern() is native, and it actually calls into JVM, to intern the String in the native JVM String pool. How much of this also applies when using the standard Oracle JDK?