Optimizing method of input stream to read faster / Improving concatenation speed

Question

Currently I am reading a 100,0000+/- line input (example: http://pastebin.com/zhuHLcvA) which ends with a single ";".

Using this code it takes over 20 seconds to read on my pc (which is far too long):

public static String readFromStandardIO() {

    String returnValue = "";

    try {
        BufferedReader reader = new BufferedReader(new InputStreamReader(
                System.in));
        String userInput;
        // System.out.println("Enter polynomials:\n");
        while (true) {
            userInput = reader.readLine();
            // System.out.println(userInput);
            returnValue = returnValue.concat(userInput);
            if (userInput.equals(";")) {
                break;
            }
        }

    } catch (Exception e) {

    }

    return returnValue;

}

Using a timing method I get odd results:

long start = System.nanoTime();
pol = readFromStandardIO();
long elaspedTime = System.nanoTime() - start;
System.out.println("reading stream took: " + elaspedTime);      

and it ouputs:

reading stream took: 1914854722

It seems that the line concatenation is slowing everything down:

returnValue = returnValue.concat(userInput)

Without it everything is instantaneous.

How do I go about improving the speed of concatenation?

Answer 1

public static String readFromStandardIO() {
   StringBuilder returnValue = new StringBuilder(9999999);
   try {
       BufferedReader reader = new BufferedReader(System.in);
       String userInput;
       while ((userInput = reader.readLine()) != null) {
          returnValue.append(userInput);
       }
       reader.close();
   } catch (Exception e) {

   }
   return returnValue.toString();
}

or this one is much faster (if your jdk supports *.nio):

public static String readFromStandardNIO() {
    java.nio.ByteBuffer buffer = java.nio.ByteBuffer.allocate(20480000);
    try {
        ReadableByteChannel channel = Channels.newChannel(System.in);
        channel.read(buffer);
        channel.close();
    } catch (Exception e) {

    }
    return new String(buffer.array());
}

Answer 2

String concatenation does not come for free: the problem is memory allocation.

Every time you lengthen a string, the string buffer needs to be enlarged, meaning 1) dynamic allocation of a new memory zone and 2) moving the entire string.

Assume you grow the string in chunks of 100 characters, and perform this 1000 times. You will invoke the allocator 100 times, and move 100 + 200 + 300 + ... 100,000 characters, i.e. 50,050,000 instead of 100,000 !

More generally, getting a string in N reads implies that every character is moved about N/2 times instead of... 1.

The cure is to preallocate a buffer that is large enough and perform the concatenation "by hand".