Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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 ?

share|improve this question
3  
What happens if you have generateString2(){ return "abc";} ? –  konijn Apr 14 at 13:17
    
return "abc" .. It will not create object every time.It would be faster than above cases. –  srikanth Apr 14 at 13:23
    
@srikanth why not run a small test? As this is java I wouldn't be so sure, that there is no new Object created. –  Vogel612 Apr 14 at 13:27
1  
I have solved a problem like this with JDOM. There are a number of inefficiencies in HashMap that make it less suitable for this sort of String Pooling. The code I linked uses an internal class ArrayCopy which is used instead of java.util.Arrays because the JDOM code needs to run on Java5 which does not have the copyOf methods in java.util.Arrays. –  rolfl Apr 14 at 15:28
3  
I don't think gc() is necessary there. –  Simon Kuang Apr 14 at 20:08

7 Answers 7

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);
}
share|improve this answer

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.

share|improve this answer
    
In both the cases the number of string objects getting Garbage collected are same. Ideally there should not be any difference ri8? Does increase in the size of heap effecting the performance of generateString() ? –  srikanth Apr 14 at 15:49
    
@srikanth: No, they're not the same. I've updated the answer a little bit. (I have to go offline now but I'll try to add a better explanation later.) –  palacsint Apr 14 at 16:14
    
@srikanth: Increasing the heap size would help. –  palacsint Apr 14 at 16:15
1  
+1 Nice catch, sir. When I was just glancing at this, I had a "wtf" moment myself. –  asteri Apr 14 at 16:27

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.

share|improve this answer
1  
To add on: String interning in Java 7 happens in heap, not PermGen anymore: bugs.java.com/bugdatabase/view_bug.do?bug_id=6962931 (I am also advocating testing this too within the context of the given question) –  h.j.k. Apr 15 at 4:04
    
Thanks for the reply. I have tested String.intern(). private static String generateString2() { return new String("abc").intern(); } . But this method taking more time than other two methods. Could you tell me the reason? p.s i'm running on windows using Java7 –  srikanth Apr 15 at 5:19
    
@srikanth I forgot to mention but tested that too in different environments and I'm getting inconsistent results... But I think the processing time of this is not really important. You are measuring the behavior of the garbage collector in a very limited context, and I don't think the results are relevant at all. –  janos Apr 15 at 5:29
    
how should i bench mark then? :) –  srikanth Apr 15 at 5:45
    
@srikanth I guess the only question that remains is whether to intern or not, as the first method would waste too much memory anyway. Is the time difference significant between your map solution and interning? If not then interning would be easier for you, as you don't have to implement the caching yourself. This may easily outweigh the drawback of minor timing differences. –  janos Apr 15 at 6:04

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).

share|improve this answer

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.

share|improve this answer
    
Good point +1 but note that there is no offset nor length in the String class any more. #2 here and stackoverflow.com/a/16123681/843804 –  palacsint Apr 14 at 19:36
1  
@palacsint Completed the Java7-and-earlier references to length/offset. –  rolfl Apr 14 at 19:51
    
Very good point @rolfl. :) –  srikanth Apr 15 at 5:43
    
Are you sure that new String(char[]) does not copy the array? –  Vojta Apr 15 at 20:19
    
@Vojta - For certain Java versions I am certain.... For recent Java7 and Java8, I will need to look. –  rolfl Apr 15 at 20:23

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.