I recall seeing a couple of string-intensive programs that do a lot of string comparison but relatively few string manipulation, and that have used a separate table to map strings to identifiers for equality efficiency and memory use, e.g.:
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;
public Name(String str) { this.str = str; }
@Override public String toString() { return str; }
// equals() and hashCode() are not overridden!
}
I'm pretty sure one of those program was javac from OpenJDK, so not some toy application. Of course the actual class was more complex (and also I think it implemented CharSequence), but you get the idea; the entire program was littered with Name in any location you would expect String , and on the rare cases where string manipulation was needed, it converted to strings and then cached them again, conceptually like:
Name newName = Name.from(name.toString().substring(5));
I think I understand the point of this - especially when there are a lot of identical strings all around and a lot of comparisons - but couldn't the same be achieved by just using regular strings and intern ing them? The documentation for String.intern() explicitly says:
...
When the intern method is invoked, if the pool already contains a string equal to this String object as determined by the equals(Object) method, then the string from the pool is returned. Otherwise, this String object is added to the pool and a reference to this String object is returned.
It follows that for any two strings s and t, s.intern() == t.intern() is true if and only if s.equals(t) is true.
...
So, what are the advantages and disadvantages of manually managing a Name -like class vs using intern() ?
What I've thought about so far was:
- Manually managing the map means using regular heap,
intern()uses the permgen.
- When manually managing the map you enjoy type-checking that can verify something is a
Name, while an interned string and a non-interned string share the same type so it's possible to forget interning in some places.
- Relying on
intern()means reusing an existing, optimized, tried-and-tested mechanism without coding any extra classes.
- Manually managing the map results in a code more confusing to new users, and strign operations become more cumbersome.
... but I feel like I'm missing something else here.
Unfortunately, String.intern() can be slower than a simple synchronized HashMap. It doesn't need to be so slow, but as of today in Oracle's JDK, it is slow (probably due to JNI)
ReplyDeleteAnother thing to consider: you are writing a parser; you collected some chars in a char[], and you need to make a String out of them. Since the string is probably common and can be shared, we'd like to use a pool.
String.intern() uses such a pool; yet to look up, you'll need a String to begin with. So we need to new String(char[],offset,length) first.
We can avoid that overhead in a custom pool, where lookup can be done directly based on a char[],offset,length. For example, the pool is a trie. The string most likely is in the pool, so we'll get the String without any memory allocation.
If we don't want to write our own pool, but use the good old HashMap, we'll still need to create a key object that wraps char[],offset,length (something like CharSequence). This is still cheaper than a new String, since we don't copy chars.
I would always go with the Map because intern() has to do a (probably linear) search inside the internal String's pool of strings. If you do that quite often it is not as efficient as Map - Map is made for fast search.
ReplyDeletewhat are the advantages and disadvantages of manually managing a Name-like class vs using intern()
ReplyDeleteType checking is a major concern, but invariant preservation is also a significant concern.
Adding a simple check to the Name constructor
Name(String s) {
if (!isValidName(s)) { throw new IllegalArgumentException(s); }
...
}
can ensure* that there exist no Name instances corresponding to invalid names like "12#blue,," which means that methods that take Names as arguments and that consume Names returned by other methods don't need to worry about where invalid Names might creep in.
To generalize this argument, imagine your code is a castle with walls designed to protect it from invalid inputs. You want some inputs to get through so you install gates with guards that check inputs as they come through. The Name constructor is an example of a guard.
The difference between String and Name is that Strings can't be guarded against. Any piece of code, malicious or naive, inside or outside the perimeter, can create any string value. Buggy String manipulation code is analogous to a zombie outbreak inside the castle. The guards can't protect the invariants because the zombies don't need to get past them. The zombies just spread and corrupt data as they go.
That a value "is a" String satisfies fewer useful invariants than that a value "is a" Name.
See stringly typed for another way to look at the same topic.
* - usual caveat re deserializing of Serializable allowing bypass of constructor.
String.intern() in Java 5.0 & 6 uses the perm gen space which usually has a low maximum size. It can mean you run out of space even though there is plenty of free heap.
ReplyDeleteJava 7 uses its the regular heap to store intern()ed Strings.
String comparison it pretty fast and I don't imagine there is much advantage in cutting comparison times when you consider the overhead.
Another reason this might be done is if there are many duplicate strings. If there is enough duplication, this can save a lot of memory.
A simpler way to cache Strings is to use a LRU cache like 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) {
String s2 = STRING_CACHE.get(s);
if (!s.equals(s2))
STRING_CACHE.put(s,s2 = s);
return s2;
}
This ensure the cache of intern()ed Strings will be limited in number.
A faster but less effective way is to use a fixed array.
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;
}
The advantage of this approach is speed and that it can be safely used by multiple thread without locking. i.e. it doesn't matter if different threads have different view of STRING_CACHE.
So, what are the advantages and disadvantages of manually managing a
ReplyDeleteName-like class vs using intern()?
One advantage is:
It follows that for any two strings s and t, s.intern() == t.intern()
is true if and only if s.equals(t) is true.
In a program where many many small strings must be compared often, this may pay off.
Also, it saves space in the end. Consider a source program that uses names like AbstractSyntaxTreeNodeItemFactorySerializer quite often. With intern(), this string will be stored once and that is it. Everything else if just references to that, but the references you have anyway.