Igoranze Igoranze - 5 months ago 12
Java Question

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

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

(This is a completely revised answer. See 1 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.


1 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.