▲ 145 points
back
63 comments
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
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.
'intern'ing in the Lisp world usually means to create a new object and put it under its name into some datastructure for later retrieval, unless the object already exists -> then the object is just retrieved.
The typical example is to intern a symbol into a symbol table (list, array, or in Common Lisp into a package). Here the symbol table is searched for a symbol with the required name. If it exists, the symbol will be returned. If it does not exist, the symbol will be created and registered in the symbol table.
But one might also use the word 'intern' for an operation to retrieve/put a user into a group, retrieve/put a resource into a pool, or similar operations.
The function INTERN dates back at least to Lisp 1.5 from 1962. See the Lisp 1.5 Programmer's Manual.
It's from Lisp, and where did Lisp take it from in the sixties, I don't know. But I'll bet that this particular Java method comes straight from Lisp, as there were some Lisp folks involved in making Java (in particular, Guy Steele worked on both Common Lisp ANSI standard and Java language specification).
> 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.
OED:
†1. intr. To enter or pass in; to be come incorporated or united with another being. Obs.
2. trans. To confine within the limits of a country, district, or place; to oblige to reside within prescribed limits without permission to leave them.
I believe the original term was for recent medical grads working at a hospital before they had their license. It was "okay" because they were internal, and supervised. Once they had the license, they could work unsupervised or externally.
> 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.
My first hearing of it was in conjunction with LISP macros, or more specifically creating hygenic LISP macros. I'm pretty sure it goes way back.
You can see an example of this here: http://stackoverflow.com/a/30016344
I think the problem is that == compares pointers, when it should've been sugar for .equals() instead.
it's tough. If a language has pointers, then you would expect == to compare whether the two sides have the same value (an address). I don't see a way around that.
How would you expect a programmer to ask "do these two pointers hold the same address?" .holdsSameAddressAs()?
D and Python use the "is" operator to compare reference identity. It is the lesser used operator and the more advanced concept, so using == for reference comparison is just a newbie trap, doubly so since you have to use == to compare equality for primitives.
> How would you expect a programmer to ask "do these two pointers hold the same address?"
In Java and C#, you rarely need to ask this question.
In fact, the .NET Framework overloads String, DateTime[0], etc so you can use == for almost all comparisons.
Except java doesn't have pointers, it has references. You can't do pointer arithmetic on references, nor can you take addresses and dereference.
I'd expect a programmer to ask: "is this object the same as this other object" and have the language support that by an operator like `is`. Instead of overloading `==` to mean value and reference equality depending on the context.
I ran into this once when I accidentally used == for a comparison to an empty string... and the condition went through part of the time because sometimes the empty string it was being compared through was also a constant....
new Java programmers, especially those coming from C# where == compares the strings.
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.
This is from Oracle JDK sources:
public boolean equals(Object anObject) {
if (this == anObject) {
return true;
}
...
hashCode is cached as well in field `hash` and lazily computed:
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
I hadn't spotted that in the hasCode() implementation. Thanks, that makes sense.
Regarding .equals(), indeed that shortcut exists but it didn't help my benchmark because it spent nearly all it's time comparing Strings which were not equal.
I switched the benchmark to compare all equal (interned) Strings and even then there .equals() is about half the speed of the reference equality check. I guess because of the method call overhead?
Yes I would have been sure that everything to do with Strings would have been optimized to the last cycle hence my surprise. I'm not sure about the state of Java intrinsics with the Oracle JDK but I would have thought that most of the String methods would be handled by intrinsics and be very heavily optimized.
Edit: correction - indeed microbenchmarking is tricky and I had a bug. If the (interned) Strings are equal then .equals() and reference comparison run at roughly the same speed.
I don't think that JVM will do magic and execute something different from actual sources, even for String. On the other hand, optimizing those bytecodes to compile to perfect machine code or playing with code to produce bytecode which will be correctly optimized by JIT is more reasonable approach, not only java.lang.String would benefit from those optimizations, but any other developer with similar code.
Method call overhead is real and calling equals method is slower compared to reference comparison, but eventually JIT might decide to inline this method call, so there'll be no overhead after that. Anyway it's unlikely, that those difference will be noticeable in real code, IMO.
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.
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.
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.
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.
I'd never seen the @Benchmark annotation before so I looked it up.
The blog author is also one of JMH's authors.
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.
Deserializing tons of records all having one of a few values for a particular field is an easy and probably fairly common use case.
Is "Anatomy Park" a Rick and Morty reference? http://rickandmorty.wikia.com/wiki/Anatomy_Park_(episode)
Please consider adding "JVM Anatomy Park" to the title.
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.
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).
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.
Some good content along the same vein with 16 years worth of articles: http://www.javaspecialists.eu/
"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?
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.
Yes, although Hashtable is legacy from JDK 1.0. New code should use HashMap or ConcurrentHashMap.
It's using a custom c++ hashtable:
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/s...
That is an implementation detail, there are many JVMs to choose from.
That is an implementation detail, there are many JVMs implementations to choose from.
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.
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.
> 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?
It would be interesting to know where it's used, was it used in the JDK for example?
Also see:
XInternAtom (XWindow function)
RegisterClass (Windows)
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.