Java 8 - Does external iteration perform better than internal iteration?

Question

So, I read a book for Java 8 when I saw that they are doing a comparison between external and internal iteration and thinking about comparing these two characteristics.

I have a method that simply sums a sequence of integers to n.

Iterative:

private static long iterativeSum(long n) {

    long startTime = System.nanoTime();
    long sum = 0;

    for(long i=1; i<=n; i++) {
        sum+=i;
    }


    long endTime = System.nanoTime();
    System.out.println("Iterative Sum Duration: " + (endTime-startTime)/1000000);

    return sum;
}

Sequential - using internal iteration

private static long sequentialSum(long n) {

    long startTime = System.nanoTime();

    //long sum = LongStream.rangeClosed(1L, n)
    long sum = Stream.iterate(1L, i -> i+1)
            .limit(n)
            .reduce(0L, (i,j) -> i+j);

    long endTime = System.nanoTime();
    System.out.println("Sequential Sum Duration: " + (endTime-startTime)/1000000);

    return sum;
}

I tried to benchmark them, it turned out that the one that uses external iteration works much better than with internal iteration.

Here is my driver code:

public static void main(String[] args) {

    long n = 100000000L;

    for(int i=0;i<10000;i++){
    iterativeSum(n);
    sequentialSum(n);
    }
    iterativeSum(n);
    sequentialSum(n);
}

The run time for Iteravtive was always <50 ms, while the run time for sequential was always> 250 ms.

I cannot understand why the internal iteration does not perform the external iteration here?

Answer 1

, , : Stream API , . JMH:

@Warmup(iterations = 5, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 10, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Fork(3)
@State(Scope.Benchmark)
public class IterativeSum {
    @Param({ "100", "10000", "1000000" })
    private int n;

    public static long iterativeSum(long n) {
        long sum = 0;

        for(long i=1; i<=n; i++) {
            sum+=i;
        }
        return sum;
    }

    @Benchmark
    public long is() {
        return iterativeSum(n);
    }
}

: . :

Benchmark             (n)  Mode  Cnt     Score     Error  Units
IterativeSum.is       100  avgt   30     0.074 ±   0.001  us/op
IterativeSum.is     10000  avgt   30     6.361 ±   0.009  us/op
IterativeSum.is   1000000  avgt   30   688.527 ±   0.910  us/op

Stream API:

public static long sequentialSumBoxed(long n) {
    return Stream.iterate(1L, i -> i+1).limit(n)
                 .reduce(0L, (i,j) -> i+j);
}

@Benchmark
public long ssb() {
    return sequentialSumBoxed(n);
}

:

Benchmark             (n)  Mode  Cnt     Score     Error  Units
IterativeSum.ssb      100  avgt   30     1.253 ±   0.084  us/op
IterativeSum.ssb    10000  avgt   30   134.959 ±   0.421  us/op
IterativeSum.ssb  1000000  avgt   30  9119.422 ±  22.817  us/op

: 13-21x . , . :

public static long sequentialSum(long n) {
    return LongStream.iterate(1L, i -> i+1).limit(n)
                     .reduce(0L, (i,j) -> i+j);
}

@Benchmark
public long ss() {
    return sequentialSum(n);
}

:

Benchmark             (n)  Mode  Cnt     Score     Error  Units
IterativeSum.ss       100  avgt   30     0.661 ±   0.001  us/op
IterativeSum.ss     10000  avgt   30    67.498 ±   5.732  us/op
IterativeSum.ss   1000000  avgt   30  1982.687 ±  38.501  us/op

, 2.8-10x . :

public static long rangeSum(long n) {
    return LongStream.rangeClosed(1, n).sum();
}

@Benchmark
public long rs() {
    return rangeSum(n);
}

:

Benchmark             (n)  Mode  Cnt     Score     Error  Units
IterativeSum.rs       100  avgt   30     0.316 ±   0.001  us/op
IterativeSum.rs     10000  avgt   30    28.646 ±   0.065  us/op
IterativeSum.rs   1000000  avgt   30  2158.962 ± 514.780  us/op

3,1-4,5 . , Stream API , MaxInlineLevel JVM, . , -XX:MaxInlineLevel=20, :

Benchmark             (n)  Mode  Cnt     Score     Error  Units
IterativeSum.rs       100  avgt   30     0.111 ±   0.001  us/op
IterativeSum.rs     10000  avgt   30     9.552 ±   0.017  us/op
IterativeSum.rs   1000000  avgt   30   729.935 ±  31.915  us/op

: 1,05-1,5 .

, , JIT-, Stream API . ( n*(n+1)/2 ??). API Stream MaxInlineLevel.