1

I have written a java program in which I am supposed to know that if the two nested for loops can finish their execution in 4 seconds or not If they finish their execution in 4 seconds then the program should continue else break the loop. I have three list A ,B and C and I am performing some operation and adding it to the list B. Even for the small inputs to the list A and C like 3, 6, 8, 4, My program throws run out of memory error

I am using one outer for loop for calculating time. If two for loops couldn't finish their execution in 4 seconds the loop should be terminate. I am using one count variable to keep track of the for loop execution even if for loop finished their execution before 4 seconds i am terminating the outer for loop.
Here is my code :

while(!(A.isEmpty())){
    ArrayList<Long> B = new ArrayList<>();
    for(long start = System.currentTimeMillis() ; start < System.currentTimeMillis() + 4 * 1000 ; ){
        for(long i : A){
            for(long j : C){
                if(i!=j){
                    B.add(Math.abs(i-j));
                }
            }
            count++;
            if(count==A.size());
                break;
        }
    }
}


What is wrong with this code ? How should I make it correct ?
Thank you.

Improve this question
5
  • 1
    It's an infinite loop, because you didn't write start++ or anything similar in your loop. Eventually you'll run out of memory I suppose. Commented Oct 16, 2016 at 19:28
  • Even if I increment start still not getting the output. I am confused that is it a best way to check that the nested for loop can finish their execution in 4 seconds or not ? Commented Oct 16, 2016 at 19:32
  • 1
    Your problem is that you are mixing up things. You want to A) compute something B) measure some time. As outlined in my answer, you should separate those two concerns! Commented Oct 16, 2016 at 19:33
  • The value of start will always be less than the value of the value returned by System.currentTimeMillis() in your outer for loop's test condition. This whole pattern looks horrible, but if you insist on using it then try creating an end time which is current time plus four seconds, and then change your for loop test condition to System.currentTimeMillis() < end. Commented Oct 16, 2016 at 19:54
  • If I understand this correctly, what you are trying to do is keep adding stuff to an ArrayList for 4 seconds, then stop? What is the point of this? And you can add a lot of elements in 4 seconds, of course you're going to run out of memory to store them unless you have lots of memory. Commented Oct 16, 2016 at 20:21

3 Answers 3

Reset to default
2

I think this design isn't really robust. Instead of calling the time function within that loop, I think you could be looking into using two threads here:

  1. Thread A kicks of thread B, and waits for n seconds
  2. Thread B does the computation
  3. When thread A wakes up, it simply checks if the computation is done

Alternatively, your main thread kicks of A and B; and A just comes back and tells you: time to check the results of B now.

And for your real problem; I guess one contributor is here:

B.add(Math.abs(i-j));

You see B (really bad name for a list of numbers btw!) taks Long objects. So that little call there creates at least one Long object per iteration. And you iterate over A and C. Without any sleeps or delays there. This means that your code is doing nothing else but iterating loops and creating new objects to fill that B list.

Now: how many loop iterations do you think you will see in 4 seconds? Enough to create millions and millions of objects?! And then: a dynamically growing list is nice, but you understand what it means when an ArrayList constantly goes over its capacity and needs to grow?! You understand that this means creation of new arrays, and copying around of all values?!

What I am saying is: look carefully how much work is really going on there; and how much (un)boxing of primitive/reference long/Long you got in your code.

One (maybe easy way) to test these ideas: change your code from using List of Longs into using fixed arrays with long values. That will have a nice side effect - it will force you think upfront about how many array slots you actually want to create. In your solution, you just keep looping and adding new objects (as said; leading to constant re-capacity increase operations for your B list).

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

Statement while(!(A.isEmpty())) will run an infinite loop causing B to be instantiated infinite times.

As a result causing OutOfMemoryError

Improve this answer

5 Comments

Assuming the gc is doing its job recreating a local variable within an infinite loop wouldnt create out of memory exception
@LucasKot-Zaniewski It all depends how much garbage is created per loop iteration. You see, if your CPU runs full speed through those loops, and each loop creates just one object that should be "garbaged" ... no GC in the world will be able to keep pace here. It takes time to do GC. And you dont have that time, when your code does nothing else but to create garbage!
...and gc doesn't run, or at least can't be depended on running, consistently or constantly like that.
Am currently running an infinite loop with just one ArrayList variable declared (adding 100 strings to it with each iteration) and referencing it later on to see how long it will take before the GC cant keep up...I suspect its going to be quite a long time but I will update with the result. Either way its not the issue OP was facing as you pointed out
Still running strong, even upped the ante to 100 mill strings, it appears from reading this ibm.com/developerworks/library/j-leaks that GC will prevent the program from having OOM in this scenario, so if you run the loop a million times between GC cycles then you create a million-1 ArrayList marked for garbage, why would this ratio change? Even if you had a super powered processor this would speed up the GC as well. The point being if you create super large objects in your loop then GC will take longer and longer BUT so will your loop.
-1

You Have an infinite loop, while(!(A.isEmpty)) will always be true because inside of your for loops you are never removing any elements from A. This will cause you to add an infinite amount of elements to B becuase of B.add(Math.abs(i-j));

Improve this answer

1 Comment

Although you are correct in saying this is an infinite loop (assuming single threaded program) this isnt causing the out of memory exception because B is redefined every time this outer loop runs so it wouldnt add infinite elements to B.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.