Why is iteration through List<String> slower than split string and iterate over StringBuilder?

Question

I was wondering why a List<String> for each loop is slower than a split for each on a StringBuilder

This is my code:

package nl.testing.startingpoint;

import java.text.DecimalFormat;
import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String args[]) {
        NumberFormat formatter = new DecimalFormat("#0.00000");

        List<String> a = new ArrayList<String>();
        StringBuffer b = new StringBuffer();        

        for (int i = 0;i <= 10000; i++)
        {
            a.add("String:" + i);
            b.append("String:" + i + " ");
        }

        long startTime = System.currentTimeMillis();
        for (String aInA : a) 
        {
            System.out.println(aInA);
        }
        long endTime   = System.currentTimeMillis();

        long startTimeB = System.currentTimeMillis();
        for (String part : b.toString().split(" ")) {

            System.out.println(part);
        }
        long endTimeB   = System.currentTimeMillis();

        System.out.println("Execution time from StringBuilder is " + formatter.format((endTimeB - startTimeB) / 1000d) + " seconds");
        System.out.println("Execution time List is " + formatter.format((endTime - startTime) / 1000d) + " seconds");

    }
}

The result is:

• Execution time from StringBuilder is 0,03300 seconds
• Execution time List is 0,06000 seconds

I would expect the StringBuilder to be slower because of the b.toString().split(" ")).

Can anyone explain this to me?

Answer 1

(This is a completely revised answer. See ¹ for why. With thanks to Buhb for making me take a second look! Note that he/she has also posted an answer.)

---

Beware your results, micro-benchmarks in Java are very tricky and your benchmarking code is doing I/O, amongst other things; see this question and its answers for more: How do I write a correct micro-benchmark in Java?

And indeed, as far as I can tell, your results were misleading you (and me, initially). Although an enhanced for loop on a String array is much faster than it is on an ArrayList<String> (more on that below), the .toString().split(" ") overhead would appear to still dominate and make that version slower than the ArrayList version. Markedly slower.

Let's determine which is faster using a throughly-designed and tested tool for microbenchmarking: JMH.

I'm using Linux, so here's how I set it up (the $ is just to indicate a command prompt; what you type is after that):

1. First, I installed Maven since I don't normally have it installed:

$ sudo apt-get install maven

2. Then I used Maven to create a sample benchmark project:

$ mvn archetype:generate \
          -DinteractiveMode=false \
          -DarchetypeGroupId=org.openjdk.jmh \
          -DarchetypeArtifactId=jmh-java-benchmark-archetype \
          -DgroupId=org.sample \
          -DartifactId=test \
          -Dversion=1.0

That creates the benchmark project in a test subdirectory, so:

$ cd test

3. In the resulting project, I deleted the default src/main/java/org/sample/MyBenchmark.java and created three files in that folder for benchmarking:

Common.java: Really boring:

package org.sample;

public class Common {
    public static final int LENGTH = 10001;
}

Originally I expected to need more there...

TestList.java:

package org.sample;

import java.util.List;
import java.util.ArrayList;
import java.text.NumberFormat;
import java.text.DecimalFormat;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Scope;

public class TestList {

    // This state class lets us set up our list once and reuse it for tests in this test thread
    @State(Scope.Thread)
    public static class TestState {
        public final List<String> list;

        public TestState() {
            // Your code for creating the list
            NumberFormat formatter = new DecimalFormat("#0.00000");
            List<String> a = new ArrayList<String>();
            for (int i = 0; i < Common.LENGTH; ++i)
            {
                a.add("String:" + i);
            }
            this.list = a;
        }
    }

    // This is the test method JHM will run for us
    @Benchmark
    public void test(TestState state) {
        // Grab the list
        final List<String> strings = state.list;

        // Loop through it -- note that I'm doing work within the loop, but not I/O since
        // we don't want to measure I/O, we want to measure loop performance
        int l = 0;
        for (String s : strings) {
            l += s == null ? 0 : 1;
        }

        // I always do things like this to ensure that the test is doing what I expected
        // it to do, and so that I actually use the result of the work from the loop
        if (l != Common.LENGTH) {
            throw new RuntimeException("Test error");
        }
    }
}

TestStringSplit.java:

package org.sample;

import java.text.NumberFormat;
import java.text.DecimalFormat;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Scope;

@State(Scope.Thread)
public class TestStringSplit {

    // This state class lets us set up our list once and reuse it for tests in this test thread
    @State(Scope.Thread)
    public static class TestState {
        public final StringBuffer sb;

        public TestState() {
            NumberFormat formatter = new DecimalFormat("#0.00000");

            StringBuffer b = new StringBuffer();        

            for (int i = 0; i < Common.LENGTH; ++i)
            {
                b.append("String:" + i + " ");
            }

            this.sb = b;
        }
    }

    // This is the test method JHM will run for us
    @Benchmark
    public void test(TestState state) {
        // Grab the StringBuffer, convert to string, split it into an array
        final String[] strings = state.sb.toString().split(" ");

        // Loop through it -- note that I'm doing work within the loop, but not I/O since
        // we don't want to measure I/O, we want to measure loop performance
        int l = 0;
        for (String s : strings) {
            l += s == null ? 0 : 1;
        }

        // I always do things like this to ensure that the test is doing what I expected
        // it to do, and so that I actually use the result of the work from the loop
        if (l != Common.LENGTH) {
            throw new RuntimeException("Test error");
        }
    }
}

4. Now we have our tests, we build the project:

$ mvn clean install

5. And we're ready to test! Close any programs you don't need running, then fire off this command. This takes a while, and you want to leave your machine alone during the process. Go grab a cup o'Java.

$ java -jar target/benchmarks.jar -f 4 -wi 10 -i 10

(Note: The -f 4 means "only do four forks, not ten"; -wi 10 means "only do 10 warmup-iterations, not 20;" and -i 10 means "only do 10 test iterations, not 20". If you want to be really rigorous, leave them off and go to lunch rather than just taking a coffee break.)

Here's the result I get with JDK 1.8.0_74 on my 64-bit Intel machine:

Benchmark              Mode  Cnt      Score      Error  Units
TestList.test         thrpt   40  65641.040 ± 3811.665  ops/s
TestStringSplit.test  thrpt   40   4909.565 ±   33.822  ops/s

The loop-through-list version did more than 65k operations/second compared to fewer than 5000 ops/sec for the split-and-loop-through-array version.

So your initial expectation that the List version would be faster because of the cost of doing the .toString().split(" ") was correct. Doing that and looping the result is markedly slower than using the List.

---

About the enhanced for on String[] vs. List<String>: It is markedly faster to loop through String[] than through List<String>, so that .toString().split(" ") must have cost us a lot. To test just the looping portion, I used JMH with the TestList class earlier, and this TestArray class:

package org.sample;

import java.util.List;
import java.util.ArrayList;
import java.text.NumberFormat;
import java.text.DecimalFormat;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Scope;

public class TestArray {

    // This state class lets us set up our list once and reuse it for tests in this test thread
    @State(Scope.Thread)
    public static class TestState {
        public final String[] array;

        public TestState() {
            // Create an array with strings like the ones in the list
            NumberFormat formatter = new DecimalFormat("#0.00000");
            String[] a = new String[Common.LENGTH];
            for (int i = 0; i < Common.LENGTH; ++i)
            {
                a[i] = "String:" + i;
            }
            this.array = a;
        }
    }

    // This is the test method JHM will run for us
    @Benchmark
    public void test(TestState state) {
        // Grab the list
        final String[] strings = state.array;

        // Loop through it -- note that I'm doing work within the loop, but not I/O since
        // we don't want to measure I/O, we want to measure loop performance
        int l = 0;
        for (String s : strings) {
            l += s == null ? 0 : 1;
        }

        // I always do things like this to ensure that the test is doing what I expected
        // it to do, and so that I actually use the result of the work from the loop
        if (l != Common.LENGTH) {
            throw new RuntimeException("Test error");
        }
    }
}

I ran it just like the test earlier (four forks, 10 warmups and 10 iterations); here are the results:

Benchmark        Mode  Cnt       Score      Error  Units
TestArray.test  thrpt   40  568328.087 ±  580.946  ops/s
TestList.test   thrpt   40   62069.305 ± 3793.680  ops/s

Nearly an order of magnitude more operations/second to loop through the array than the list.

That doesn't surprise me, since the enhanced for loop can work directly on the array, but has to use an Iterator returned by the List in the List case and make method calls to it: Two calls per loop (Iterator#hasNext and Iterator#next) for 10,001 loops = 20,002 calls. Method calls are cheap, but they're not free, and even if the JIT inlines them, the code of those calls still has to run. ArrayList's ListIterator has to do some work before it can return the next array entry, whereas when the enhanced for loop knows it's dealing with an array, it can work directly on it.

The test classes above have testing cruft in them, but to see why the array version is faster, let's look at this simpler program:

import java.util.List;
import java.util.ArrayList;

public class Example {
    public static final void main(String[] args) throws Exception {
        String[] array = new String[10];
        List<String> list = new ArrayList<String>(array.length);
        for (int n = 0; n < array.length; ++n) {
            array[n] = "foo" + System.currentTimeMillis();
            list.add(array[n]);
        }

        useArray(array);
        useList(list);

        System.out.println("Done");
    }

    public static void useArray(String[] array) {
        System.out.println("Using array:");
        for (String s : array) {
            System.out.println(s);
        }
    }

    public static void useList(List<String> list) {
        System.out.println("Using list:");
        for (String s : list) {
            System.out.println(s);
        }
    }
}

Using javap -c Example after compiling it, we can look at the bytecode of the two useXYZ functions; I've boldfaced the loop portions of each and set them off slightly from the rest of each function:

useArray:

  public static void useArray(java.lang.String[]);
    Code:
       0: getstatic     #15                 // Field java/lang/System.out:Ljava/io/PrintStream;
       3: ldc           #18                 // String Using array:
       5: invokevirtual #17                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
       8: aload_0
       9: astore_1
      10: aload_1
      11: arraylength
      12: istore_2
      13: iconst_0
      14: istore_3

      15: iload_3
      16: iload_2
      17: if_icmpge     39
      20: aload_1
      21: iload_3
      22: aaload
      23: astore        4
      25: getstatic     #15                 // Field java/lang/System.out:Ljava/io/PrintStream;
      28: aload         4
      30: invokevirtual #17                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
      33: iinc          3, 1
      36: goto          15

      39: return

useList:

  public static void useList(java.util.List);
    Code:
       0: getstatic     #15                 // Field java/lang/System.out:Ljava/io/PrintStream;
       3: ldc           #19                 // String Using list:
       5: invokevirtual #17                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
       8: aload_0
       9: invokeinterface #20,  1           // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
      14: astore_1

      15: aload_1
      16: invokeinterface #21,  1           // InterfaceMethod java/util/Iterator.hasNext:()Z
      21: ifeq          44
      24: aload_1
      25: invokeinterface #22,  1           // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
      30: checkcast     #2                  // class java/lang/String
      33: astore_2
      34: getstatic     #15                 // Field java/lang/System.out:Ljava/io/PrintStream;
      37: aload_2
      38: invokevirtual #17                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
      41: goto          15

      44: return

So we can see useArray operating directly on the array, and we can see useList's two calls to Iterator methods.

Of course, most of the time it doesn't matter. Don't bother worrying about these things until and unless you have identified the code you're optimizing to be a bottleneck.

---

¹ This answer has been thoroughly revised from its original version, because I assumed in the original version that the assertion that the split-then-loop-array version being faster was true. I completely failed to check that assertion, and just jumped into the analysis of how the enhanced for loop is faster on arrays than lists. My bad. Many thanks again to Buhb for making me take a closer look.

Answer 2

Benchmarking java is hard, because of all kinds of optimizations and JIT compilations.

I'm sorry to say you can draw no conclusions from your test. The least you must do is to create two different programs, one for each scenario, and run them separately. I extended on your piece of code, and wrote this:

NumberFormat formatter = new DecimalFormat("#0.00000");

List<String> a = new ArrayList<String>();
StringBuffer b = new StringBuffer();

for (int i = 0;i <= 10000; i++)
{
    a.add("String:" + i);
    b.append("String:" + i + " ");
}

long startTime = System.currentTimeMillis();
for (String aInA : a)
{
    System.out.println(aInA);
}
long endTime   = System.currentTimeMillis();

long startTimeB = System.currentTimeMillis();
for (String part : b.toString().split(" ")) {

    System.out.println(part);
}
long endTimeB   = System.currentTimeMillis();

long startTimeC = System.currentTimeMillis();
for (String aInA : a)
{
    System.out.println(aInA);
}
long endTimeC   = System.currentTimeMillis();

System.out.println("Execution time List is " + formatter.format((endTime - startTime) / 1000d) + " seconds");
System.out.println("Execution time from StringBuilder is " + formatter.format((endTimeB - startTimeB) / 1000d) + " seconds");
System.out.println("Execution time List second time is " + formatter.format((endTimeC - startTimeC) / 1000d) + " seconds");

It gave me the following result:

Execution time List is 0.04300 seconds
Execution time from StringBuilder is 0.03200 seconds
Execution time List second time is 0.01900 seconds

Also, if I remove the System.out.println statements in the loop, and instead just append the strings to a StringBuilder, I get execution times in the milliseconds, instead of tens of milliseconds, which tells me that the splitting vs list looping cant be responsible for one method taking twice the time of the other.

In general, IO is comparatively slow, so your code spends most of its time executing println-statements.

Edit: Ok, so I've done my homework now. Got inspired by the link supplied by @StephenC and created a benchmark using JMH. The methods being benchmarked follows:

public void loop() {
            for (String part : b.toString().split(" ")) {
                bh.consume(part);
            }
        }



    public void loop() {
        for (String aInA : a)
        {
            bh.consume(aInA);
        }

And the result:

Benchmark                          Mode  Cnt    Score   Error  Units
BenchmarkLoop.listLoopBenchmark    avgt  200   55,992 ± 0,436  us/op
BenchmarkLoop.stringLoopBenchmark  avgt  200  290,515 ± 0,975  us/op

So to me, it looks like the list version is quicker, which is consistent with your initial intuition.

Answer 3

In case of split you are operating on an array directly, so it is quite fast. ArrayList uses array inside, but adds some code around it so it has to be slower than iterating over a pure array.

But saying that I woulnd't use such microbenchmark at all - after JIT has run the results might be different.

And more importantly, do what is more readable, worry about performance when you have issues with it, not before - cleaner code is better in the beginning.