OutOfMemoryError with DFS

Question

So I'm in full swing. When I first created my DFS algorithm, I used recursion. This resulted in a StackOverflow error. Well ... No, I'm just converting it to iteration. So I converted my code to iteration, and I used Stack to replicate method calls. However, now I get an OutOfMemoryError.

I just found out about my problem, there was a circular addiction. (Stupid me) Nevertheless, I am curious how someone else would approach this if there were no circular dependence. I should also mention that it was in Java.

My question pretty much is what to do when you know you don't have an infinite loop, but meet an OutOfMemoryError due to the stack from the DFS lookup.

Answer 1

A common cause of memory errors is that the program uses an algorithm that requires O (n) (or more) storage, and the best way is to find an algorithm or trick to use less memory, like O (1) or O (log n). The most common example is the processing of large files in blocks of constant size, that is, with O (1) memory, instead of first reading it into memory, namely O (n).

Another common cause of these errors is simple errors: accumulating garbage that you no longer need, or creating new objects when the algorithm requires reusing existing ones. Also in this case, a suitable solution detects an error and fixes it.

Only when you are sure that the algorithm is memory conservative, since you can intelligently do this and that there are no memory errors, does it make sense to play with JVM memory parameters ( -Xss to set the stack size, -Xms and -Xmx to set initial and maximum heap sizes).

Answer 2

Stop Overflow means exactly what it says, since you had a recursive algorithm, it means that your memory stack (for function calls) is full. take a look at the call stack document to understand how the stack pointers, frames, and reverse pointers work:

When you created the iterative algorithm, you ran out of memory because the variables you stored are not in the call stack, but are stored in the memory of the function itself (in the same stack stack).

Of course, technically, both errors mean that you have no memory, but each of them happened in a different way. One of them is endless recursive method calls, and the other is memory overflow.

EDIT As for your edited question, I don't think stackOverflow can happen without an infinite loop or recursion if you don't have enough memory on your system. Maybe add more RAM?

Answer 3

To a large extent, in all cases, if you hit the associated MEMORY with the exception of the first thing to do, it is long and hard to think about what you are doing (possibly using the memory profiler). There is a very good chance that you are holding onto data that you no longer need.

If you are sure that your program is behaving efficiently and your problems are simply related to the size and / or complexity of your data set, you can increase the stack or heap used by your application:

 -Xss64m 

Sets the stack size to 64 megabytes

 -Xmx1024m 

Sets the heap size to 1 gig.