22 Dec 2014
I am working on improving my java experience. Running into the StringBuilder class, I wondered what the speedup would be. The example I decided to work with was a full binary tree, and making a text representation of it. A full binary tree grows exponentially depending on its size, so should be easy to generate long strings from this.
If we have a full binary tree of depth \(n\) we have a tree with \(2^n\) leaf nodes and \(2^n - 1\) internal nodes. The string representation I chose would therefore be of length \(3 (2^n - 1) + 2 \, 2^n\). I use the two implementations shown in FullBinTree 2 String.
A quick analysis shows that
toString1 has \(\sim 2^n\) new object
toString2 has one
StringBuilder that gets enlarged
\(\sim n\) times. Clearly both implementations have an exponential
component (since they need to visit all nodes of the tree), but if the object
creation is the main factor
toString2 should look linear in the area we can
Actual results are that the
StringBuilder version is about two times faster
than the version that using string concatenation with
+ (you can’t say the
version that doesn’t use
StringBuilder since if you look at the bytecode you
see the sequence of
+ is compiled into creating a
repeatedly adding to it).
I tried to use Coda Hale’s metrics library to extract more information, but this example seems too light to add additional measuring to it without influencing the results.