Showing posts with label String. Show all posts
Showing posts with label String. Show all posts

Wednesday, 29 June 2011

Beware of String functions - replaceAll and replace et. al

I was going through replaceAll function. I had following string:
String str = "com.vaani.src.dynamic.CompilationHelloWorld";

I had to replace all dot's with /.So I tried
str.replaceAll(".","/");

But what I was getting was,that my string converted to - //////////////////////////////////////////////////////////////////////////////////////

The reason is simple. It was using regex, so dot(.) means replace all with something, here /.
So I solved it using \\ before dot:
str.replaceAll("\\.","/");

Another solution is that because I am using character only, so why not use '' quotes rather than "", ie:
you can do following:
str.replaceAll('.','/');

We discussed something similar here as well.

Friday, 24 June 2011

String and memory leaks

Probably most of the Java users is aware that String object is more complex than just an array of char. To make the usage of strings in Java more robust additional measures were taken – for instance the String pool was created to save memory by reusing the same String objects instead of allocating new ones. Another optimization that I want to talk about today is adding the offset and count fields to the String object instances.
Why those fields were added? Their purpose is to help to reuse already allocated structures when using some of the string functionalities – like calculating substrings of a given string. The concept is that instead of creating an new char array for a substring we could just ‘reuse’ the old one. To be exact this is what String.substring() method does: instead of copying an char array for the returned object it creates a new String reusing char[] of the old one. Only the values of offset and count fields (which indicate the beginning and the length of a new string) are changed. See here first to see - how substring function works? Because the substring operation is quite often used this mechanism helps to save a lot of memory. It is important to add that this can work only because String objects are immutable. See the following snippet:

public static void sendEmail(String emailUrl) {
String email = emailUrl.substring(7); // 'mailto:' prefix has 7 letters
String userName = email.substring(0, email.indexOf("@"));
String domainName = email.substring(email.indexOf("@"));
}

public static void main(String[] args) {
sendEmail("mailto:user_name@domain_name.com");
}

Thanks to the way substring() is implemented when we extract the email, userName and domainName three new String objects are created, but the char array is not copied. All new string variables reuse the character array from emailUrl. Thanks to that reuse for really long urls we can save approximately 2/3 of memory we would use otherwise. Great, right?

Ok… now the dark side of that optimization! Check out this snippet:

public final static String START_TAG = "<title>";
public final static String END_TAG = "</title>";

public static String getPageTitle(String pageUrl) {
// retrieve the HTML with a helper function:
String htmlPage = getPageContent(pageUrl);

// parse the page content to get the title
int start = htmlPage.indexOf(START_TAG);
start = start + START_TAG.length();
int end = htmlPage.indexOf(END_TAG);
String title = htmlPage.substring(start, end);
return title;
}

In here we are extracting from the HTML page its title – can you see the problem with this code? Looks simple and correct, right?

Now, try to imagine that the htmlPage String is huge – more than 100.000 characters, but the title of this page has only 50 characters. Because of the optimization mentioned above the returned object will reuse the char array of the htmlPage instead of creating a new one… and this means that instead of returning a small string object you get back a huge String with 100.000 characters array!! If your code will invoke getPageTitle() method many times you may find out that you have stored only a thousand titles and already you are out of memory!! Scary, right?

Of course there is an easy solution for that – instead of returning the title in line 13, you can return new String(title). The String(String) constructor is always doing a subcopy of the underlying char array, so the created title will actually have only 50 characters. Now we are safe:)

So what is the lesson here? Always use new String(String)? No… In general the String optimizations are really helpful and it is worth to take advantage of them. You just have to be careful with what you are doing and be aware of what is going on ‘under the hood’ of your code. String class API is in some situations not intuitive, so beware!

Wednesday, 22 June 2011

Beware of String functions - they may use simple strings as regex

Some string function may look simple and perform task accordingly but surprise you sometimes. eg. consider the Split function:

public class LineParser {
private final String[] values;

public LineParser(String line, String separator) {
values = line.split(separator);
}

public String getValue(int index) {
return values[index];
}
}

It’s a simple class that encapsulates parsing a text line and stores the result. Let's see.
public static void main(String[] args) {
LineParser parser1 = new LineParser("A,B,C", ",");
System.out.println("parser1:" + parser1.getValue(1));

LineParser parser2 = new LineParser("A B C", " ");
System.out.println("parser2:" + parser2.getValue(1));

LineParser parser3 = new LineParser("A|B|C", "|");
System.out.println("parser3:" + parser3.getValue(1));

LineParser parser4 = new LineParser("A\\B\\C", "\\");
System.out.println("parser4:" + parser4.getValue(1));
}

Output
For the first and second parser there is no surprise: the second value is ‘B’ and that’s exactly what gets printed. The third one instead of a second value prints ‘A’ – the first one… If that’s not strange enough the last parser throws an exception! That’s really unexpected!!

So where’s the catch? What’s wrong? Some of you already knew it, some probably start to suspect it… It’s all because of String.split() method – instead of taking a separator String as a parameter (which I tried to silently imply in the code) it takes a regular expression. Because of that two last parsers failed – both pipe and backslash signs have special meaning in Java regexps!
Mystery solved, so problem is gone… is it really? Of course you might be tempted just to fix the snippet above by writing the regexps correctly – this would be fine for this code. Now go home and check your code: do you use user-provided values in String.split()? What about String.replaceAll()? If you do you might be in real trouble… The real lesson is that some of the String methods take as a parameter plain Strings (eg: String.regionMatches()) while other expect a String with a regular expression (eg: String.matches()). Beware and double check!


Checking whether string is parseable to integer or double

This seems basic, right? In most cases it is, but as almost everything in Java this problem has its subtle pitfalls and problems. It is mainly because Java does not provide a simple utility method that can answer this question. Today I wanted to share with you several ways of solving this problem and describe their good and bad sides.

Why should you care?

Checking for that in many cases is unnecessary. If the format of data is defined and its contract states that the string is an integer you can just parse it and deal with unlikely exception that an error occurs. The problem is when there is no such a contract and you have to decide based on whether the string is an integer what actions to perform next. In that case plain try-catch check may be too expensive for you:

public boolean isInteger(String string) {
try {
Integer.valueOf(string);
return true;
} catch (NumberFormatException e) {
return false;
}
}

This method’s execution cost is high because of two factors: one is that to determine if string is an integer we have to do the whole parsing and throw away the result. Second is that we use exception throwing (which is expensive) to direct the program flow. The good thing about this code is its simplicity – you can at a glance say the method is correct.

Let’s use RegExp!

Much faster is to create a regular expression and use it to check whether string contains an integer or double. The good thing about this approach is that the regexp can be precompiled and used several times after:

private static Pattern doublePattern = Pattern.compile("-?\\d+(\\.\\d*)?");

public boolean isDouble(String string) {
return doublePattern.matcher(string).matches();
}

Unfortunately this method has important flaws: the pattern above will work for the most basic string representation of Double, but what about more advanced like “1.23E-12″. Even if you improve this pattern (belive me, its difficult) there are still some checks that it will not be able to perform, for instance checking if the integer is above Integer.MAX_INT.


What about Scanner?

There is a way of combining the two approaches shown above together: first check with regexp if string is possibly be an integer and if it seems to be one, try to perform the actual parsing. If the regexp is ‘good enough’ the number of false positives resulting in NumberFormatException will be acceptable. The good news is this approach is already implemented by a Scanner class. See the following example:

public static void main(String[] args) {
Scanner scanner = new Scanner("Test string: 12.3 dog 12345 cat 1.2E-3");

while (scanner.hasNext()) {
if (scanner.hasNextDouble()) {
Double doubleValue = scanner.nextDouble();
} else {
String stringValue = scanner.next();
}
}
}

In essence Scanner breaks down the given string into tokens around whitespace and allows you to iterate trough them. It gives you useful access methods like ‘hasNextDouble()’ to check whether the next token is a Double or not and allows you to get it in a parsed version as a Double with ‘nextDouble()’ method.

Internals of Scanner show that it in fact combines both the regexp and exception catching methods, which makes it quite efficient. The downside is that the Scanner object itself is heavy and prepared to parsing larger text strings, so it may be ineffective if you need to use it on a simple strings like “123″.

Wait! It does not work for me!!

It is possible that you start using one of the methods above on a real life data and at some point things stop making sense… Why? Because we forgot about something important: the numbers are locale-sensitive and its string representation depends from country to country. For instance ten thousand in US is 10,000, in Poland 10 000 and in Italy 10.000. See that none of the methods above could successfully parse neither Polish or Italian numbers! What can you do in those cases? You have to use for parsing a NumberFormat class with specified locale:

private static NumberFormat italianDouble =
NumberFormat.getNumberInstance(Locale.ITALIAN);

public boolean isItalianDouble(String string) {
return (italianDouble.parse(string) != null);
}

Now you can finally see that 10,000 is a valid integer. Unfortunately with NumberFormat you get another set of problems – it is too liberal in parsing numbers! The method above will return true for 10,000 and false for both abc and x1, but it will return true also for 10abc as it looks only for a suffix in the string, not a total match.

Conclusion

As you can see none of the solutions shown above is perfect – each of the method aboves has its flaws and advantages. Because of that the choice which one is the best for you strongly depends on the context of your program. The important factors are: how often do you need to do a check like that, what is the false result ratio, whether you parse long human readable text or just few given values and whether you care about locale specific issues. It is also possible that in your code you’ll need a combination of them or to add some specific tweaks to one of them.

String utility : unquoting the string

This is another simple Java string utility method, which can be used to unquote a string value. This method takes care of single and double quotes both along with handling the null string. It returns the string as it is when the string is not quoted.

public static String unquote(String s) {
if (s != null && ((s.startsWith("\"") && s.endsWith("\""))
|| (s.startsWith("'") && s.endsWith("'")))) {

s = s.substring(1, s.length() - 1);
}
return s;
}

Somethings to remember about saving memory with the String.intern method

Imagine that you have a flat file in csv format. And it has a 100 million rows from which you are about to read data to store and process in your app.
The data is in the format (orderId, storeIdentifier, amountDue).
What optimization can you do here?
Note that the storeIdentifier is going to be repeated a lot. Every time you read a record and split it into a string and possibly store it into an in-memory data structure, you will be creating a new String object. So 100 million String objects will be created for the storeIdentifier. But you know that there are only (say) 100 stores in all! So there is a massive amount of wasted memory.
What you can do here is – Right after you have read the storeIdentifier string, do this -
storeIdentifier = storeIdentifier.intern();
That would put the store identifier into the String pool and keep the number of String instances with the same data minimal by returning the String from the pool once it has been put into it by the first invocation for the string.
Points to Note
  1. Use intern() only if you really need to use it. And only if you know the extra instances are going to be a problem. And only if you really understand how it works.
  2. Older JVMs had a problem collecting interned strings. Newer JVMs handle this fine. Don’t worry about leaks due to a growing pool. If other references are gone, interned strings will be collected by the GC.
  3. Interned strings go into the PermGen Space area of memory in some JVMs. This is not part of the normal heap. If you send too many strings here, an OutOfMemoryError will hit you even though your heap may have several GB available.
  4. Interned strings can be compared with == rather than .equals(). This is a bit faster. But it is rarely worth the brittle code.
  5. Calling String.intern() can be a performance hit. It takes CPU cycles to maintain the pool and do the comparisons. Are you sure you are saving enough memory to make it worth the CPU? Measure. Don’t guess.
  6. Use String.intern() only if the set of possible Strings that will be interned has a bound tight enough such that the set of different strings is much smaller than the total number of strings that will be read.