Why does caching of string objects perform faster?

Question

I'm trying to implement String-Pool. I'm maintaining a HashMap<String,String> to store the keys.

public class TestStringCaching {
    static Map < String, String > cache = new HashMap < String, String > ();
    public static void main(String[] args) {
        int iter = 8000000;
        String[] temp = new String[iter];
        long st1 = System.currentTimeMillis();
        for (int i = 0; i < iter; i++) {
            temp[i] = generateString();
        }
        System.out.println(System.currentTimeMillis() - st1);
        st1 = System.currentTimeMillis();
        for (int i = 0; i < iter; i++) {
            temp[i] = generateString1();
        }
        System.out.println(System.currentTimeMillis() - st1);
        System.gc();
    }

    private static String generateString() {
        return new String("abc");
    }

    private static String generateString1() {
        String str = new String("abc");
        if (cache.containsKey(str))
            return cache.get(str);
        else {
            cache.put(str, str);
            return cache.get(str);
        }

    }

}

In both of the cases getString() and getString1() same number of string objects are created. But fetching from the map/cache is blistering fast compared to normal creation of String.

Why is that happening ?

Answer 1

Why skimp on braces? Putting braces around the if-block in generateString() costs you almost nothing — not even an extra line of code. Make it a habit to always include explicit braces so that you never write a disaster like this. (Don't think that it can't happen to you! Accidents often have more than one contributing factor — so don't be a contributing factor.)

private static String generateString1() {
    String str = new String("abc");
    if (cache.containsKey(str))
        return cache.get(str);
    else {
        cache.put(str, str);
        return cache.get(str);
    }
}

That could be better expressed as:

private static String generateString1() {
    String str = new String("abc");
    if (!cache.containsKey(str)) {
        cache.put(str, str);
    }
    return cache.get(str);
}

If you really don't like braces, putting the action on the same line as the if could also be acceptable:

private static String generateString1() {
    String str = new String("abc");
    if (!cache.containsKey(str)) cache.put(str, str);
    return cache.get(str);
}

Answer 2

generateString

• It creates 8000000 String instances on the heap and stores their references in the array.
• Every array slot refers to a different String instance.
• It uses more memory and GC might use a lot of CPU time.

generateString1

• It uses only one String instance and every index of the array points to this same instance (this is the instance which is created first).
• Although generateString1 creates a new String instance (String str = new String("abc");) on every call they could be collected by the garbage collector right at the end of the method, so it uses less memory.

On the first iteration this code path runs:

String str = new String("abc"); // str#1 instance
cache.containsKey(str); // return false
// else branch:
cache.put(str, str);
return cache.get(str);

On the subsequent calls this code path runs:

String str = new String("abc"); // str#x instances
cache.containsKey(str) // returns true
return cache.get(str);

On the subsequent calls the method creates the str String (str#x instance) and uses it for only cache lookup. It retrieves the cached str#1 instance from the map and returns that. The created str#x instance is available for garbage collection at the end of the method.

JVM might be smart

Note that the temp variable is not used at all, so a smart JVM/hotspot could eliminate it completely (since it's dead code) and you might get invalid benchmark results. Benchmarking is not an easy task. To prevent this I'd change

System.out.println(System.currentTimeMillis() - st1);

to

System.out.println(System.currentTimeMillis() - st1);
System.out.println(Arrays.hashCode(temp));

So the JVM can't get rid of the code, it has to use it for showing the result. You might find this answer also useful: Sum the difference of two arrays

Comparing memory consumption

You can compare memory consumption by printing the following:

System.out.println("mem: " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()));

Running only generateString uses 224 MByte memory. Running only generateString1 uses 32 MByte memory. (To get proper results here you need the printing of Arrays.hashCode(temp) in the code!)

If you change

private static String generateString() {
    return new String("abc");
}

to

private static String generateString() {
    return new String("abc").intern();
}

(as it was suggested by janos) it will also use around 32 MByte memory.

Answer 3

I tried this on 2 different computers and I'm getting inconsistent results. Sometimes the first method is faster, sometimes the other. It also depends on the number of iterations, with a pretty wild spread. I think the outcome depends on:

• the JVM implementation and version, especially the default garbage collector settings and behavior
• the currently active garbage collector settings

The most important point is not so much the processing time, but the implications in terms of memory use: the first method will store N instances of String on the heap while the other will store only 1. The difference in processing time is more of an otherwise meaningless trivia.

---

While on the subject of caching Strings, I think it's worth mentioning about the technique of String interning. For example if your application loads 100k records from a database and you use rs.getString("city") for each record when in fact there are only 10 distinct city names, then you could be wasting a lot of memory. In such situation, storing the results of rs.getString("city").intern() could reduce memory usage dramatically, at the expense of using more PermGen space instead of the heap.

As @h-j-k added in comments:

To add on: String interning in Java 7 happens in heap, not PermGen anymore: http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6962931 (I am also advocating testing this too within the context of the given question)

Considering the memory usage, I think it's safe to say that in your real-world application you should go either with your own Map cache or interning. As you posted in a comment, here's an excellent post comparing the performance of these two options. However, keep in mind that the result of such benchmark will always depend on your JVM implementation and its tuning options. Managing your own cache could be tedious sometimes in a realistic situation. If the speed of this is of real concern in your application, you might want to repeat the benchmark in the application itself, rather than just in an isolated experiment.

Answer 4

The part of this exercise that concerns me most, and has not been addressed, is that you are not creating 8,000,000 full string instances. You are creating 8,000,000 light-weight wrappers to a single 3-char array.

Consider the chain of events when you create a new String("abc") instance:

1. The Java compiler identifies the String constant "abc".
2. It allocates space in perm-gen for it (or somewhere on the heap in Java8).
3. The constant consists of a 3-char array char[] chars = {'a', 'b', 'c'} and a String instance consisting of a pointer to the array (and in some Java7 versions and earlier, an offset (0) and a length (3)).
4. When the code is run, the new String("abc") is run, and it creates a new String instance, but not a new char[] array. The char-array is a constant, immutable value, so there is no reason to change it.
5. the new String points to the exact same char-array as the String constant (and, in some Java7 versions and earlier, it has the offset and length of 0 and 3).

The bottom line is that you are not creating 8,000,000 Strings, you are creating 8,000,000 half-strings, and reusing one char[] array 8,000,000 times.

Answer 5

If code creates a string, quickly finds out that an identical string exists somewhere (e.g. in a HashMap), and replaces the reference to the new string with a reference to the cached one, then the garbage collector can immediately discard the new string without having to spend any time copying it out of the "Eden" heap. This is a useful optimization when it can be done cheaply.

The reason such caching is not normally done as a matter of course is that having a string in the cache will only be helpful when more strings with identical content are going to be created and checked against the cache, and it may be decidedly counterproductive if there are strings in the cache whose content doesn't match those of any strings that will be generated in future. If String were a native type which was treated specially by the virtual machine and garbage collector, it could include logic to cache the backing store in cases where it was useful, without storing unbounded amounts of useless data. While native support wouldn't be strictly necessary for such a feature, the overhead required to implement it without native support would in most cases be greater than the performance benefits it would offer (native GC/JVM support would both reduce the cost in those cases where no benefit was achieved, and improve the benefits in those cases where it was).

Answer 6

My guess is that the reason is very likely to be a garbage collection.

Very possible explanation:

As it was said in the first case you have a big array eating up a lot of space and if the GC gets run during that time it will first do a minor collection. In minor collection there is a copy GC used that is the worse the more objects survive. In your case "all" of your objects survive = slow minor collection. Then you have to get it into Old generation. Then as you add more and more string that are to survive you have to again run minor collection (all of them survive = slow) and so on. In the other case your hash map is small and will get soon to old generation that will unlikely to be collected again. All the new Strings will die right away because you use the hashed ones and the more objects are garbage the quicker the minor collection is.

You can verify it by running JVM with -verbose:gc -XX:+PrintGCTimeStamps -XX:+PrintGCDetails and it tells you how many times and how long each garbage collection took. I am pretty sure this can give you the sum of times very close to the difference you are observing. If not, I would be curious for you to share your results.

Answer 7

Another aspect to consider is cache locality as the pool grows. The cost of allocating a small temporary string may be far less than an L1/L2 cache miss. You could randomly generate strings such that the pool will grow to thousands of unique values to see if it has any effect on the benchmark.