String Concatenation In Java

While working on my project the issue of efficiency while concatenating strings came up. In Java manipulation of Strings is usually done via two classes, the String class & the StringBuilder class. The String class is more popular among developers, since it provides enough functionality to cover most people’s needs and the resulting syntax is intuitive. The StringBuilder class is seldom used compared to the String class because it doesn’t add anything extra that the regular String class already doesn’t cover and it’s syntax is somewhat burdensome. The only time it’s really ever used is when concatenation is being done and efficiency is a critical factor. Why can’t the String class be used exclusively when concatenating strings? Well, it is usually not recommended primarily because Strings in Java are immutable, and concatenation requires the creation of a new String object. This is a relatively inexpensive action and when done infrequently results in minimal overhead. However, when concatenation is done a lot, like in a loop for instance, then it becomes phenomenally expensive and unnecessary.

According to the Java documentation, the StringBuilder class is used to represent a mutable sequence of characters. Concatenation of StringBuilders occurs in place thereby resulting in a significant increase in efficiency and greater time savings. The only area in which the StringBuilder class loses out to its competition is syntax and aesthetics. Use of the StringBuilder class potentially inhibits readability, as the syntax for its use requires the calling of methods (i.e. instead of concatenating strings a & b like this: a + b, it's like this: a.append(b)).

For the longest time I’d been under the impression that it didn’t matter whether or not you used the StringBuilder class because the compiler would transmute the code to the more efficient alternative anyways (smart compiler is smart). This assumption was merely an assumption and had no basis in anything whatsoever. So to settle the issue once and for all I decided to test everything empirically:

This was the code I used:

//String Builder
long x = 0, y = 0;
x = System.nanoTime();
StringBuilder s = new StringBuilder();
for (int i = 0; i < 10000; i++) {
s.append(“x”);
}
y = System.nanoTime();

//String
long x = 0, y = 0;
x = System.nanoTime();
String s = “”;
for (int i = 0; i < 10000; i++) {
s += “x”;
}
y = System.nanoTime();

After running the above code, I got the following times:
StringBuilder: avg time 0.01s.
String: avg time 0.20 seconds.
Evidently, the StringBuilder class is much more efficient (more than ten times so). So while Donald Knuth’s classic aphorism:

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

… should be adhered to at all times, it is probably best to consider using the StringBuilder class exclusively when concatenating strings of any sort. For some more insight into how the compiler deals with strings in different contexts peruse this excellent Stack Overflow thread (http://stackoverflow.com/questions/1532461/stringbuilder-vs-string-concatenation-in-tostring-in-java):

Lift Off!

GSoC has been under-way for about two weeks now. Since we’re still in the early stages, my time has mostly been taken up by doing community-bonding activities (i.e. getting to know all the people in the team, reading the user guide and looking at the documentation). In addition to doing a lot of reading I’ve also been researching various profiling tools. In all the Java projects I’ve worked on, I’ve never had to do any sort of profiling, so this is something I’m very keen on mastering. As of right now, I haven’t really looked at any of them thoroughly. The only one I’ve kind of skimmed over is VisualVM. Initially, I found VisualVM to be very finnicky and baroque. When I did profiling in Python I remember there was a way in which you could assess the particular time cost of individual method calls. This is something that I’ve been unable to do in VisualVM for whatever reason. I’m planning on finding this out ASAP, and as soon as I accumulate enough knowledge on profiling as a whole I am going to dedicate an entire entry to the topic.

Obviously, once a significant amount of work has been done on the math package, assessing the time cost of individual method calls will be imperative. However, checking for improvements in this fashion is perhaps not the best strategy to use. By this I mean that it might or might not be a fruitful strategy depending on what we’re trying to achieve. Working on the basis of method calls might not be the best way to go about doing things because it might lead to a loss in perspective and cause us to lose sight of the bigger picture. In some cases a holistic approach might be better. So, with that in mind, let’s just backtrack. What is it, we are trying to achieve? What’s the end goal of this project? The end goal of the project is to create a new package structure and a new way of handling formulas in JSBML such that: (a) It’s much more straightforward (i.e. instead of one ASTNode class being used to represent different types of nodes, different classes will be used). (b) Evaluation of mathematical formulas is more efficient. Since most JSBML users are unaware of the library’s internal implementation, the efficiency aspect (b) is perhaps more important to them. For people who have never looked at the code, the straightforwardness of formula handling is not a concern of theirs. It’s only when formula handling manifests in something tangible (i.e. a slowing down of SBML file processing), that they actually start to care about what it is that’s going on ‘underneath the hood’.

Right now there are two JSBML-dependent tools that make heavy use of abstract syntax trees for which an improvement in efficiency will prove beneficial. The first one is the Systems Biology Simulation Core Library, which works with quantitative biological models encoded in SBML and the second one is SBMLToLatex an application that converts SBML files to a human readable LaTeX format. Since the performance of both of these tools, is somewhat dependent on how efficiently JSBML can handle formulas this means they could both potentially serve as benchmarking tools. Setting a baseline performance for both (with the current implementation of JSBML) and referring back to this would be a great way to track progress. For SCL this would require us to simulate all of the models contained in the SBML Test Suite and to keep a detailed record of the time spent for each simulation. Similarly, the performance of SBML2LaTeX could be easily tracked by forcing it to convert a large and complex SBML file to LaTeX. It should be noted that SCL, as it is right now, doesn’t directly use the ASTNode data structures in JSBML and because of this it can’t really be used to track improvements in performance (at least not in the way that I’ve suggested). However, after talking to my mentors it seems like there’s a way in which it could be forced to use JSBML directly. If this is possible, then I think using JSBML with SCL would be a great way to start off the project.

Another thing to keep in mind, is that once the math package has been implemented, the library’s functionality will have to be the same as it was before. There’s a fairly large number of applications that depend on JSBML and require it’s API to remain consistent. The best way to ensure that the library’s behaviour remains the same from version to version is to of course use unit tests. Only one class (ASTNode) is used to represent all the different kinds of nodes in abstract syntax trees, so the unit tests have been designed in such a way as to check that the class is accomplishing this task faultlessly. Even though a new math package is being added to the library, it will not be accessed directly by users. The ASTNode class will end up wrapping around it (this is keeping in line with the whole, let’s keep it the same mantra). So essentially this means, that even though JSBML’s internal structure will have undergone considerable change, the interface between the user and the library will remain the same, and all the unit tests will pass. The unit test shown below will perhaps illustrate what I’m trying to convey:

ASTNode realNode = new ASTNode(3.14);
assertTrue(realNode.isReal());

Right now this test, works because, when you create a new ASTNode and provide a double as the only parameter, a special constructor is called, which calls a very specific function that sets the value of the ASTNode to 3.14 and sets the type of the ASTNode to REAL. Once the math package is complete, this unit test will pass as well and from the point of view of the user, the ASTNode will be the same ASTNode, but it’s internal structure will be completely different. For the newly implemented ASTNode, providing a double as the only parameter will result in the ASTNode calling another class (let’s call this class ASTRealNode), creating an object out of it, and pointing to it in some fashion. In this case, to verify that the ASTNode is in fact an ASTRealNode, all one would have to do is to check that the class name of the object is ASTRealNode. Again from the perspective of the user using the newer version of ASTNode nothing of consequence will have occurred. However, in reality, quite a number of changes will have been made that render the evaluation of mathematical formulas (which are stored in the form of abstract syntax trees), much more efficient.

The first of any modifications done to ASTNode will involve, the interfacing of the class with the two classes ASTCiNumberNode & ASTUnaryFunctionNode in the math package. As an example, the relationship between ASTNode & ASTCiNumberNode looks something like this:

Implementing the two classes, making the proper edits to ASTNode and verifying everything by running the unit tests should serve as a good first step. Right now, both classes are sitting in their proper location in the math package but no changes to ASTNode have been made. As soon as this is done, and everything is confirmed to be working correctly, more will be mentioned on this.