long loop counter appears to be very inefficient

Question

I just observed a weird performance issue in some Java toy example. Here is the complete program:

import java.util.Random;

public class Weird
{
    public static long fib(int n)
    {
        long a = 0;
        long b = 1;
        for (long i = 0; i < n; ++i)   // note: loop counter of type long
        {
            long c = a + b;
            a = b;
            b = c;
        }
        return a;
    }

    public static void main(String[] args)
    {
        System.out.print("Warming up the JIT... ");
        warmUpTheJIT();
        System.out.println("Starting measurement");

        long bogus = 0L;
        long before = System.nanoTime();
        for (int i = 0; i < 500_000_000; ++i)
        {
            bogus += fib(46);
        }
        long after = System.nanoTime();
        System.out.println(bogus);

        long duration = after - before;
        long ms = duration / 1_000_000;
        System.out.println(ms +" ms");
    }

    private static void warmUpTheJIT()
    {
        Random rand = new Random();
        long bogus = 0L;
        for (int i = 0; i < 1_000_000; ++i)
        {
            bogus += fib(rand.nextInt(47));
        }
        System.out.println(bogus);
    }
}

The code takes 21 seconds on my system (64 Bit Java 8 VM). However, if I change the loop counter from long to int, it only takes 27 MILLIseconds. That's about three orders of magnitude faster.

So... why does the type of a loop counter make such a huge difference?

Aren't we talking about the `for` loop in the `fib` function? That never sees a value larger than 47, which certainly fits in a `short`. Nevertheless, it would be poor code because the argument type is an `int` and *could* be bigger than a short. — nobody, May 12 '14 at 17:13
possible duplicate of [Why is long slower than int in x64 Java?](http://stackoverflow.com/questions/19844048/why-is-long-slower-than-int-in-x64-java) — devnull, May 12 '14 at 17:13
Also http://stackoverflow.com/questions/6903235/will-using-longs-instead-of-ints-benefit-in-64bit-java — devnull, May 12 '14 at 17:15
There is a number of optimisations which the JIT uses for `int` counters. Usually it doesn't make much difference, but they can make a big difference, is rare cases. — Peter Lawrey, May 12 '14 at 17:41

Peter Lawrey · Accepted Answer · 2014-05-12T17:58:54.440

This is how I might have written it

public class IntLoopMain {
    public static long fib(int n) {
        long a = 0;
        long b = 1;
        for (long i = 0; i < n; ++i) {  // note: loop counter of type long
            long c = a + b;
            a = b;
            b = c;
        }
        return a;
    }

    static volatile long total = 0;

    public static void main(String... args) {
        System.out.println("Warming up the JIT... ");

        long start = 0;
        for (int i = -100000; i < 200_000_000; ++i) {
            if (i == 0) {
                start = System.nanoTime();
                System.out.println("Starting measurement");
            }
            total += fib(46 + (i & 3));
        }
        long time = System.nanoTime() - start;
        if (total == 0)
            System.out.println(total);

        System.out.printf("Took %.3f secs%n", time / 1e9);
    }
}

with a long i loop

Took 8.166 secs

with an int i loop

Took 3.549 secs

if I take out the + (i & 3)

Took 7.296 secs <- long
Took 1.317 secs <- int

My point is that int loops are optimised more heavily (as they are more common)

Say I do some manual loop unrolling. AFAIK int loops do more unrolling.

public static long fib2(int n) {
    long a = 0;
    long b = 1;
    for (int i = 1; i < n; i+=2) {  // note: loop counter of type long
        long c = a + b;
        long d = b + c;
        a = c;
        b = d;
    }
    return (n & 1) == 0 ? a : b;
}

Using fib2(46)

Took 3.828 secs <- long
Took 1.321 secs <- int

Manual unrolling wouldn't help (unless the JIT doesn't unroll already)

long loop counter appears to be very inefficient

1 Answers1