Why is my java program becoming gradually slower?

Question

I recently built a Fibonacci generator that uses recursion and hashmaps to reduce complexity. I am using the System.nanoTime() to keep track of the time it takes for my program to print 10000 Fibonacci number. It started out good with less than a second but gradually became slower and now it takes more than 4 seconds. Can someone explain why this might be happening. The code is down here-

import java.util.*;
import java.math.*;

public class FibonacciGeneratorUnlimited {

    static int numFibCalls = 0;
    static HashMap<Integer, BigInteger> d = new HashMap<Integer, BigInteger>();
    static Scanner fibNumber = new Scanner(System.in);
    static BigInteger ans = new BigInteger("0");

    public static void main(String[] args){
        d.put(0 , new BigInteger("0")); 
        d.put(1 , new BigInteger("1"));

        System.out.print("Enter the term:\t");
        int n = fibNumber.nextInt();

        long startTime = System.nanoTime();

        for (int i = 0; i <= n; i++) {
            System.out.println(i + " : " + fib_efficient(i, d));
        }

        System.out.println((double)(System.nanoTime() - startTime) / 1000000000);
    }
    public static BigInteger fib_efficient(int n, HashMap<Integer, BigInteger> d) {
        numFibCalls += 1;
        if (d.containsKey(n)) {
            return (d.get(n));
        } else {
            ans = (fib_efficient(n-1, d).add(fib_efficient(n-2, d)));
            d.put(n, ans);
            return ans;
        }
    }
}

When you say that it started out fast but is now slower, what changed? Is this the code before or after the performance changed? — Daniel Pryden, Nov 08 '17 at 16:39
Or is that it takes more time to calculate *between* numbers? — Shirkam, Nov 08 '17 at 16:39
Maybe you should ask on [Codereview](https://codereview.stackexchange.com/) rather than here — Shirkam, Nov 08 '17 at 16:44
Just guessing, but maybe it's the map, which needs more time for the get-operation with the growing number of entries? — Jonas Heinisch, Nov 08 '17 at 16:44
Can you give us some examples of times versus numFibCalls? Is it taking longer with the same inputs? — Jamie, Nov 08 '17 at 16:52

Cpp plus 1 · Answer 1 · 2017-11-08T16:55:06.540

0

If you are restarting the program every time you make a new fibonacci sequence, then your program most likely isn't the problem. It might just be the your processor got hot after running the program a few times, or a background process in your computer suddenly started, causing your program to slow down.

edited Nov 08 '17 at 16:55

answered Nov 08 '17 at 16:41

Cpp plus 1

990
8
25

score 0 · Answer 2 · answered Nov 08 '17 at 17:03

More memory java -Xmx=... or less caching

public static BigInteger fib_efficient(int n, HashMap<Integer, BigInteger> d) {
    numFibCalls++;
    if ((n & 3) <= 1) { // Every second is cached.
        BigInteger cached = d.get(n);
        if (cached != null) {
            return cached;
        } else {
            BigInteger ans = fib_efficient(n-1, d).add(fib_efficient(n-2, d));
            d.put(n, ans);
            return ans;
        }
    } else {
        return fib_efficient(n-1, d).add(fib_efficient(n-2, d));
    }
}

Two subsequent numbers are cached out of four in order to stop the recursion on both branches for:

fib(n) = fib(n-1) + fib(n-2)

BigInteger isn't the nicest class where performance and memory is concerned.

Also, an ArrayList would use much less memory than a HashMap. An ArrayList would be suitable because all cached numbers are consecutive starting from 0. — DodgyCodeException, Nov 08 '17 at 17:09

score 0 · Answer 3 · answered Nov 08 '17 at 17:13

It started out good with less than a second but gradually became slower and now it takes more than 4 seconds.

What do you mean by this? Do you mean that you ran this exact same program with the same input and its run-time changed from < 1 second to > 4 seconds? If you have the same exact code running with the same exact inputs in a deterministic algorithm... then the differences are probably external to your code - maybe other processes are taking up more CPU on one run. Do you mean that you increased the inputs from some value X to 10,000 and now it takes > 4 seconds? Then that's just a matter of the algorithm taking longer with larger inputs, which is perfectly normal.

recursion and hashmaps to reduce complexity

That's not quite how complexity works. You have improved the best-case and the average-case, but you have done nothing to change the worst-case.

Now for some actual performance improvement advice

Stop printing out the results... that's eating up over 99% of your processing time. Seriously, though, switch out "System.out.println(i + " : " + fib_efficient(i, d))" with "fib_efficient(i,d)" and it'll execute over 100x faster. Concatenating strings and printing to console are very expensive processes.

Jorge Omar Medra · Answer 4 · 2017-11-09T06:18:38.933

It happens because the complexity for Fibonacci is Big-O(n^2). This means that, the larger the input the time increases exponentially, as you can see in the graph for Big-O(n^2) in this link. Check this answer to see a complete explanation about it´s complexity.

Now, the complexity of your algorithm increases because you are using a HashMap to search and insert elements each time that function is invoked. Consider remove this HashMap.

Why is my java program becoming gradually slower?

4 Answers4