title: Why filtering an unsorted list is faster than filtering a sorted list
body: <p>I've been playing with Java 8 <code>Streams - API</code> and I decided to microbenchmark <code>stream()</code> and <code>parallelStream()</code> streams. As expected the <code>parallelStream()</code> was as twice as fast, but something else popped up - If I sort the data before passing them to the <code>filter</code> it takes 5-8 times more time to <code>filter-&gt;map-&gt;collect</code> the result, than passing an unsorted list.</p>
  
  <h2>Unsorted</h2>
  
  <pre><code>(Stream) Elapsed time [ns] : 53733996 (53 ms)
  (ParallelStream) Elapsed time [ns] : 25901907 (25 ms)
  </code></pre>
  
  <h2>Sorted</h2>
  
  <pre><code>(Stream) Elapsed time [ns] : 336976149 (336 ms)
  (ParallelStream) Elapsed time [ns] : 204781387 (204 ms)
  </code></pre>
  
  <h2>Here is the code</h2>
  
  <pre><code>package com.github.svetlinzarev.playground.javalang.lambda;
  
  import static java.lang.Long.valueOf;
  
  import java.util.ArrayList;
  import java.util.List;
  import java.util.Random;
  import java.util.stream.Collectors;
  
  import com.github.svetlinzarev.playground.util.time.Stopwatch;
  
  public class MyFirstLambda {
      private static final int ELEMENTS = 1024 * 1024 * 16;
  
      private static List&lt;Integer&gt; getRandom(int nElements) {
          final Random random = new Random();
          final List&lt;Integer&gt; data = new ArrayList&lt;Integer&gt;(nElements);
          for (int i = 0; i &lt; MyFirstLambda.ELEMENTS; i++) {
              data.add(random.nextInt(MyFirstLambda.ELEMENTS));
          }
          return data;
      }
  
      private static void benchStream(List&lt;Integer&gt; data) {
          final Stopwatch stopwatch = new Stopwatch();
          final List&lt;Long&gt; smallLongs = data.stream()
                  .filter(i -&gt; i.intValue() &lt; 16)
                  .map(Long::valueOf)
                  .collect(Collectors.toList());
          stopwatch.log("Stream");
          System.out.println(smallLongs);
      }
  
      private static void benchParallelStream(List&lt;Integer&gt; data) {
          final Stopwatch stopwatch = new Stopwatch();
          final List&lt;Long&gt; smallLongs = data.parallelStream()
                  .filter(i -&gt; i.intValue() &lt; 16)
                  .map(Long::valueOf)
                  .collect(Collectors.toList());
          stopwatch.log("ParallelStream");
          System.out.println(smallLongs);
      }
  
      public static void main(String[] args) {
          final List&lt;Integer&gt; data = MyFirstLambda.getRandom(MyFirstLambda.ELEMENTS);
          // Collections.sort(data, (first, second) -&gt; first.compareTo(second)); //&lt;- Sort the data
  
          MyFirstLambda.benchStream(data);
          MyFirstLambda.benchParallelStream(data);
  
          MyFirstLambda.benchStream(data);
          MyFirstLambda.benchParallelStream(data);
  
          MyFirstLambda.benchStream(data);
          MyFirstLambda.benchParallelStream(data);
  
          MyFirstLambda.benchStream(data);
          MyFirstLambda.benchParallelStream(data);
  
          MyFirstLambda.benchStream(data);
          MyFirstLambda.benchParallelStream(data);
      }
  }
  </code></pre>
  
  <h2>Update</h2>
  
  <p>Here is a better benchmark code</p>
  
  <pre><code>package com.github.svetlinzarev.playground.javalang.lambda;
  
  import static java.lang.Long.valueOf;
  
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.List;
  import java.util.Random;
  import java.util.stream.Collectors;
  
  import com.github.svetlinzarev.playground.util.time.Stopwatch;
  
  public class MyFirstLambda {
      private static final int ELEMENTS = 1024 * 1024 * 10;
      private static final int SMALLER_THAN = 16;
      private static final int WARM_UP_ITERRATIONS = 1000;
  
      private static List&lt;Integer&gt; getRandom(int nElements) {
          final Random random = new Random();
          final List&lt;Integer&gt; data = new ArrayList&lt;Integer&gt;(nElements);
          for (int i = 0; i &lt; MyFirstLambda.ELEMENTS; i++) {
              data.add(random.nextInt(MyFirstLambda.ELEMENTS));
          }
          return data;
      }
  
      private static List&lt;Long&gt; filterStream(List&lt;Integer&gt; data) {
          final List&lt;Long&gt; smallLongs = data.stream()
                  .filter(i -&gt; i.intValue() &lt; MyFirstLambda.SMALLER_THAN)
                  .map(Long::valueOf)
                  .collect(Collectors.toList());
          return smallLongs;
      }
  
      private static List&lt;Long&gt; filterParallelStream(List&lt;Integer&gt; data) {
          final List&lt;Long&gt; smallLongs = data.parallelStream()
                  .filter(i -&gt; i.intValue() &lt; MyFirstLambda.SMALLER_THAN)
                  .map(Long::valueOf)
                  .collect(Collectors.toList());
          return smallLongs;
      }
  
      private static long filterAndCount(List&lt;Integer&gt; data) {
          return data.stream()
                  .filter(i -&gt; i.intValue() &lt; MyFirstLambda.SMALLER_THAN)
                  .count();
      }
  
      private static long filterAndCountinParallel(List&lt;Integer&gt; data) {
          return data.parallelStream()
                  .filter(i -&gt; i.intValue() &lt; MyFirstLambda.SMALLER_THAN)
                  .count();
      }
  
      private static void warmUp(List&lt;Integer&gt; data) {
          for (int i = 0; i &lt; MyFirstLambda.WARM_UP_ITERRATIONS; i++) {
              MyFirstLambda.filterStream(data);
              MyFirstLambda.filterParallelStream(data);
              MyFirstLambda.filterAndCount(data);
              MyFirstLambda.filterAndCountinParallel(data);
          }
      }
  
      private static void benchmark(List&lt;Integer&gt; data, String message) throws InterruptedException {
          System.gc();
          Thread.sleep(1000); // Give it enough time to complete the GC cycle
  
          final Stopwatch stopwatch = new Stopwatch();
          MyFirstLambda.filterStream(data);
          stopwatch.log("Stream: " + message);
  
          System.gc();
          Thread.sleep(1000); // Give it enough time to complete the GC cycle
  
          stopwatch.reset();
          MyFirstLambda.filterParallelStream(data);
          stopwatch.log("ParallelStream: " + message);
  
          System.gc();
          Thread.sleep(1000); // Give it enough time to complete the GC cycle
  
          stopwatch.reset();
          MyFirstLambda.filterAndCount(data);
          stopwatch.log("Count: " + message);
  
          System.gc();
          Thread.sleep(1000); // Give it enough time to complete the GC cycle
  
          stopwatch.reset();
          MyFirstLambda.filterAndCount(data);
          stopwatch.log("Count in parallel: " + message);
      }
  
      public static void main(String[] args) throws InterruptedException {
          final List&lt;Integer&gt; data = MyFirstLambda.getRandom(MyFirstLambda.ELEMENTS);
  
          MyFirstLambda.warmUp(data);
          MyFirstLambda.benchmark(data, "UNSORTED");
  
          Collections.sort(data, (first, second) -&gt; first.compareTo(second));
          MyFirstLambda.benchmark(data, "SORTED");
  
          Collections.sort(data, (first, second) -&gt; second.compareTo(first));
          MyFirstLambda.benchmark(data, "IN REVERSE ORDER");
  
      }
  }
  </code></pre>
  
  <p>And again the results are similar:</p>
  
  <pre><code>   16:09:20.470 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Stream: UNSORTED) Elapsed time [ns] : 66812263 (66 ms)
  16:09:22.149 [main] INFO  c.g.s.playground.util.time.Stopwatch - (ParallelStream: UNSORTED) Elapsed time [ns] : 39580682 (39 ms)
  16:09:23.875 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Count: UNSORTED) Elapsed time [ns] : 97852866 (97 ms)
  16:09:25.537 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Count in parallel: UNSORTED) Elapsed time [ns] : 94884189 (94 ms)
  16:09:35.608 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Stream: SORTED) Elapsed time [ns] : 361717676 (361 ms)
  16:09:38.439 [main] INFO  c.g.s.playground.util.time.Stopwatch - (ParallelStream: SORTED) Elapsed time [ns] : 150115808 (150 ms)
  16:09:41.308 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Count: SORTED) Elapsed time [ns] : 338335743 (338 ms)
  16:09:44.209 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Count in parallel: SORTED) Elapsed time [ns] : 370968432 (370 ms)
  16:09:50.693 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Stream: IN REVERSE ORDER) Elapsed time [ns] : 352036140 (352 ms)
  16:09:53.323 [main] INFO  c.g.s.playground.util.time.Stopwatch - (ParallelStream: IN REVERSE ORDER) Elapsed time [ns] : 151044664 (151 ms)
  16:09:56.159 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Count: IN REVERSE ORDER) Elapsed time [ns] : 359281197 (359 ms)
  16:09:58.991 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Count in parallel: IN REVERSE ORDER) Elapsed time [ns] : 353177542 (353 ms)
  </code></pre>
  
  <p>So, my question is why filtering an unsorted list is faster than filtering a sorted list ?</p>