java.lang.String is one of the mostly used classes in Java. Interestingly, it is important to know some of its implementation details in order to avoid memory leaks.
Consider the following seemingly innocent piece of code:
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class StrangeStringThing {
private static Random rnd = new Random();
private static final int MEGA = 1024*1024;
private static String createRandomStr(int length){
StringBuilder sb = new StringBuilder(length);
for(int i=0;i<length;i++)
sb.append((char)('a'+rnd.nextInt('z'-'a'+1)));
return sb.toString();
}
public static void main(String[] args){
List<String> substrings = new ArrayList<String>();
for(int i=0;i<100;i++){
String randomStr = createRandomStr(MEGA);
String subStr = randomStr.substring(1000,1004);
substrings.add(subStr);
}
}
}
This code generates a very long random string, and then keeps only a 5 chars long substring of it. This process is repeated 100 times. We expect to end this program with 100 strings of length 5.
Surprisingly, if we try to run this code with the heap size limited to 100MB (-Xmx100m), we get an OutOfMemoryError. How did that happen? all temporary large strings should have been cleared by the garbage collection, so there should be a really small memory footprint. Furthermore, the documentation of java.lang.String does not indicate any misuse of the API.
How are Java Strings stored?
The Java language specification defines precisely the API of class String, its Unicode details, its immutability, and the way String literals should be handled. Naturally, it does not define how Strings should be represented internally, and what are the required time/space complexities of the different operations on them. These aren’t functional requirements. As a consequence, different JVM providers have the freedom to choose their preferred design for class String. Sun’s implementation (and also IBM’s) represent a string with a combination of 3 data members:
- value – A reference to a char array
- offset – A start index, inside the array
- count – The actual length of the string.
When allocating a new string, the char array contains exactly the string content. Offset is set to 0, and count is set to the char array length. Then, when calling the method substring(..) upon it, the new string being returned contains a reference to the same char array, but its offset and count members are modified, reflecting the requested subsequence of chars. The sharing of the same char array by multiple String instances is possible, since strings are immutable. There are two benefits of this implementation approach in comparison to a substring implementation based on copying:
1) Memory usage is usually reduced, specially in cases where many substrings of the same string are taken, or if the substrings are long
2) substring(..) runs in constant time, instead of linear time
Obviously there is a tradeoff here – if the string utilization pattern is not as described in (1), we may suffer from excessive memory consumption. The code above demonstrates this edge case: we take very small substrings of very large strings, where the latter are temporary. The temporary strings (referenced by randomStr) ARE collected by the garbage collector during the loop. However, their internal char arrays can not be collected, since they are being shared with the sub-strings. Therefore, the very long char arrays are kept unintentionally in memory, and that constitutes a memory leak.
The solution is simple – forcing the substrings to be copied into a new compact char array. This is done by replacing line 22 above with:
String subStr = new String(randomStr.substring(1000,1004));
It looks like the API designers were aware of the the possibility of substring being implemented as described, so they added a copy constructor specifically for avoiding the memory leak. Note that otherwise this constructor is useless, because we are dealing with an immutable class.
Is this a Java bug?
There is currently an open bug report in Sun’s bug database regarding this issue. It doesn’t look like it will be fixed soon, because doing so may introduce performance regression in many existing programs. Besides, there is a very simple workaround (described above), what makes the priority of this bug relatively low.
Summary
Java developers should be aware of the prevalent String.substring(..) implementation, and its memory leak potential risk. Whenever we know that the original string we take the substring from has a shorter life span than the substring itself, we should consider using the copy constructor to avoid sharing of the underlying char array.
The Java Explorer 