Sample Computer Science Lab Report


A sample report to illustrate this lab report format.

Performance comparison of String concatenation versus StringBuilder
John Dalbey
Partner:  Ian Anderson
November 6, 2012
CPE 103-00

Statement of Objective

In his book Effective Java, Joshua Bloch warns against using the String concatenation operator for repeated string concatentations.  For once-only use like
        System.out.println("Result:" + total + " years");
there's no problem.  But using a statement like this:
       result = result + "word";
in a loop will invoke a severe performance penalty. 

Bloch recommends using Java's StringBuilder class as a much faster alternative.
The purpose of this experiment is to see if String concatenation is really as bad as Bloch says it is, and if so, to determine if StringBuilder is really any better.

Theory

Bloch explains that since String is immutable, it can't simply append "word" to result, but that it has to make a copy of both operands then combine them and create a new string to hold the result.  The copy operation is very expensive; he asserts that it is a quadratic time operation.  So in theory we should expect to see the performance of StringBuilder is much faster than String.

Description of Experimental Setup

The experiments were performed on a desktop workstation with 3 GB RAM and a Dual Core Processor running at 2.6GHz.

Procedure

We wrote a small program that implements both techniques.  One method, concat(), uses a loop to repeat a String concatentation operation a given number of times.  A second method, concatFast() uses StringBuilder.  We wrote a main method that calls them inside a loop that provides an increasing limit for the number of concatentations, so several experimental trials can be run automatically.

The core of the concat() method builds a string using the concatenation operator "+=".  The concatFast() on the other hand, uses StringBuilder's append() method. We chose an arbitrary length of 80 characters for the string to be appended.


String Concatenation vs. StringBuilder 
for (int i=0; i < numItems; i++)
{
 result += sentence; 
}
  
for (int i=0; i < numItems; i++)
{
    builder.append(sentence);
}

The complete program code is provided in the appendix.

Data

We ran the program three times and averaged the observed times. The following table summarizes the running times for increasing number of items.

Average run times in seconds.
Number of
Items
 String
Concatenation		 StringBuilder
1000 0.352 0.001
2000 1.441 0.004
3000 3.473 0.003
4000 6.449 0.004
5000 10.163 0.006
6000 14.672 0.007
7000 20.125 0.007
8000 26.366 0.008
9000 33.538 0.013
10000 41.602 0.012
11000 51.463 0.014
12000 61.983 0.013
13000 70.170 0.015
14000 81.600 0.016
15000 93.925 0.018


Analysis of Data

To visualize the data, we created this chart of runtimes:
Graph

Discussion of Results

The results we obtained confirm Bloch's prediction.  The graph definitely shows that the String concatenation run times are quadratic.   There is a clear exponential rate of increase in run time as the number of concatenations gets larger.   The difference when compared with StringBuilder is quite dramatic.

Conclusions

Due to the immutable nature of Java's String class, our experiment indicates that one should use caution when using the concatenation operator.  It can produce surprisingly long runtimes in seemingly benign usage.  Bloch recommends the StringBuilder class as the preferred alternative for doing any string manipulation operations, and our study supports his advice.

Appendices

Here is the complete source code for our program.
/**
 * Experiment with string concatentation versus StringBuilder
 * Reference: Bloch, Effective Java, Item 51 (pg 227).
 * @author J. Dalbey
 * @version 11/6/12
 */
public class StringTiming
{
    static String sentence = "0123456789012345678901234"
    + "0123456789012345678901234"
    + "0123456789012345678901234"
    + "0123456789012345678901234";

    // String concatenation
    public static String concat(int numItems)
    {
        String result="";
        for (int i=0; i < numItems; i++)
        {
            result += sentence;
        }
        return result;
    }

    // StringBuilder append()
    public static String concatFast(int numItems)
    {
        StringBuilder builder = new StringBuilder();
        for (int i=0; i < numItems; i++)
        {
            builder.append(sentence);
        }
        return builder.toString();
    }
   
    public static void main(String[] args)
    {
        // Run several experimental trials
        for (int numItems = 1000; numItems<=15000; numItems += 1000)
        {
            System.out.println("Number of Items: " + numItems);
            long starttime = System.currentTimeMillis();
            concat(numItems);
            long endtime = System.currentTimeMillis();
            System.out.println("  concat() elapsed time (secs): " + (endtime - starttime)/1000.0);
   
            starttime = System.currentTimeMillis();
            concatFast(numItems);
            endtime = System.currentTimeMillis();
            System.out.println("  concatFast() elapsed time (secs): " + (endtime - starttime)/1000.0);
        }
    } 
}

Here is the raw program output for the three trials:
Trial #1
Number of Items: 1000
  concat() elapsed time (secs): 0.285
  concatFast() elapsed time (secs): 0.0020
Number of Items: 2000
  concat() elapsed time (secs): 1.378
  concatFast() elapsed time (secs): 0.0080
Number of Items: 3000
  concat() elapsed time (secs): 3.406
  concatFast() elapsed time (secs): 0.0030
Number of Items: 4000
  concat() elapsed time (secs): 6.301
  concatFast() elapsed time (secs): 0.0040
Number of Items: 5000
  concat() elapsed time (secs): 10.038
  concatFast() elapsed time (secs): 0.0060
Number of Items: 6000
  concat() elapsed time (secs): 14.557
  concatFast() elapsed time (secs): 0.0060
Number of Items: 7000
  concat() elapsed time (secs): 19.91
  concatFast() elapsed time (secs): 0.0070
Number of Items: 8000
  concat() elapsed time (secs): 26.088
  concatFast() elapsed time (secs): 0.0070
Number of Items: 9000
  concat() elapsed time (secs): 33.099
  concatFast() elapsed time (secs): 0.012
Number of Items: 10000
  concat() elapsed time (secs): 40.913
  concatFast() elapsed time (secs): 0.012
Number of Items: 11000
  concat() elapsed time (secs): 49.612
  concatFast() elapsed time (secs): 0.014
Number of Items: 12000
  concat() elapsed time (secs): 59.07
  concatFast() elapsed time (secs): 0.013
Number of Items: 13000
  concat() elapsed time (secs): 69.38
  concatFast() elapsed time (secs): 0.014
Number of Items: 14000
  concat() elapsed time (secs): 80.6
  concatFast() elapsed time (secs): 0.014
Number of Items: 15000
  concat() elapsed time (secs): 94.295
  concatFast() elapsed time (secs): 0.014

Trial #2
Number of Items: 1000
  concat() elapsed time (secs): 0.429
  concatFast() elapsed time (secs): 0.0020
Number of Items: 2000
  concat() elapsed time (secs): 1.548
  concatFast() elapsed time (secs): 0.0020
Number of Items: 3000
  concat() elapsed time (secs): 3.496
  concatFast() elapsed time (secs): 0.0030
Number of Items: 4000
  concat() elapsed time (secs): 6.504
  concatFast() elapsed time (secs): 0.0030
Number of Items: 5000
  concat() elapsed time (secs): 10.24
  concatFast() elapsed time (secs): 0.0080
Number of Items: 6000
  concat() elapsed time (secs): 14.745
  concatFast() elapsed time (secs): 0.0080
Number of Items: 7000
  concat() elapsed time (secs): 20.264
  concatFast() elapsed time (secs): 0.0070
Number of Items: 8000
  concat() elapsed time (secs): 26.487
  concatFast() elapsed time (secs): 0.0080
Number of Items: 9000
  concat() elapsed time (secs): 33.603
  concatFast() elapsed time (secs): 0.014
Number of Items: 10000
  concat() elapsed time (secs): 41.547
  concatFast() elapsed time (secs): 0.012
Number of Items: 11000
  concat() elapsed time (secs): 53.547
  concatFast() elapsed time (secs): 0.012
Number of Items: 12000
  concat() elapsed time (secs): 66.752
  concatFast() elapsed time (secs): 0.013
Number of Items: 13000
  concat() elapsed time (secs): 70.83
  concatFast() elapsed time (secs): 0.017
Number of Items: 14000
  concat() elapsed time (secs): 81.976
  concatFast() elapsed time (secs): 0.018
Number of Items: 15000
  concat() elapsed time (secs): 93.952
  concatFast() elapsed time (secs): 0.022

Trial #3
Number of Items: 1000
  concat() elapsed time (secs): 0.341
  concatFast() elapsed time (secs): 0.0
Number of Items: 2000
  concat() elapsed time (secs): 1.397
  concatFast() elapsed time (secs): 0.0020
Number of Items: 3000
  concat() elapsed time (secs): 3.517
  concatFast() elapsed time (secs): 0.0030
Number of Items: 4000
  concat() elapsed time (secs): 6.541
  concatFast() elapsed time (secs): 0.0040
Number of Items: 5000
  concat() elapsed time (secs): 10.211
  concatFast() elapsed time (secs): 0.0050
Number of Items: 6000
  concat() elapsed time (secs): 14.714
  concatFast() elapsed time (secs): 0.0070
Number of Items: 7000
  concat() elapsed time (secs): 20.2
  concatFast() elapsed time (secs): 0.0080
Number of Items: 8000
  concat() elapsed time (secs): 26.524
  concatFast() elapsed time (secs): 0.0080
Number of Items: 9000
  concat() elapsed time (secs): 33.911
  concatFast() elapsed time (secs): 0.014
Number of Items: 10000
  concat() elapsed time (secs): 42.346
  concatFast() elapsed time (secs): 0.012
Number of Items: 11000
  concat() elapsed time (secs): 51.229
  concatFast() elapsed time (secs): 0.016
Number of Items: 12000
  concat() elapsed time (secs): 60.127
  concatFast() elapsed time (secs): 0.013
Number of Items: 13000
  concat() elapsed time (secs): 70.3
  concatFast() elapsed time (secs): 0.013
Number of Items: 14000
  concat() elapsed time (secs): 82.225
  concatFast() elapsed time (secs): 0.017
Number of Items: 15000
  concat() elapsed time (secs): 93.527
  concatFast() elapsed time (secs): 0.018


Last modified on 11/06/2012 12:06:56