String.intern()
shipilev.net
shipilev.net
String a = "hello";
String b = "world";
assert a != b;
b = "hello";
assert a == b;
// OH NICE I'LL USE == FOR STRING COMPARISONS NOW
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.
I always assumed it came from internalize, or something like that.
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) 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.
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.
In CL, you don't really have a global "symbol table" or "atom table"; instead, interning is about the runtime lexical scopes under which code compilation happens, which consist of stacks of imported namespaces ("packages"), where each namespace exists as a mutable object holding identifier "slots".
(intern foo) is a mutation on the current namespace that creates a local variable "slot" for the identifier foo, shadowing any other foo that might have been in lexical scope from an import. That is, (intern foo) makes foo resolve internally to the current namespace.
(unintern foo) is the complementary mutation; it drops the foo identifier from the current namespace, allowing other symbols (slots in packages) that were previously shadowed by it to re-appear.
†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.
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
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.
How would you expect a programmer to ask "do these two pointers hold the same address?" .holdsSameAddressAs()?
I use .equals far more than ==.
Question: is Mary John?
You want the answer to be "yes" (Mary is John) since the is operator asks whether they hold addresses which have the same value.
But of course it's a broken terminology, because Mary and John are two different people, with their own physical locations etc. So you're overloading a word "is". I get that it works, but so does anything else you make programmers learn.
The same approach could work in imperative or OO languages. For immutable types == should be value equality, while mutable types are analogous to IORef or IOArray, so == should be reference equality. It comes down to observational equality, different instances of the number 2 shouldn't be distinguishable, but different mutable containers with the same contents should be distinguishable because you can make their contents different. I think observational equality is a good fit for pretty much all uses of equality in programming.
assertTrue(mary.getSign == john.getSign)
assertFalse(mary.getSign is john.getSign)
assertFalse(mary == john)
assertFalse(mary is john)this was the OP in this thread:
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.
However, that terminology is by no means universal. While, from what I can tell, "reference" as defined above is favoured in the Java and C# community, "pointer" is still used plenty. For example, the Java spec says "The reference values (often just references) are pointers to these objects"
All that being said, I do agree with what I think is the spirit of your comment, which is that when your language doesn't allow pointer manipulation it is less useful to ask whether two values point to/reference the same value.
In C++, yes, you do
(&a == &b)
(std::addressof(a) == std::addressof(b))
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.
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.
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.
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.
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;
}
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.
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.
If there are other core JVM developers that have similar blogs, I'd love to hear about them here.
The blog author is also one of JMH's authors.
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.
What native HashTable is used? Shouldn't the JVM be using an optimized one?
Edit: pardon the dupes, on unreliable mobile link :-(
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.
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...
How much of this also applies when using the standard Oracle JDK?
XInternAtom (XWindow function)
RegisterClass (Windows)
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.