2

My Java code contains a method (getPermutations) whose processing takes a huge amount of memory ( Complexity O(n!) ) and thus may throw an OutOfMemoryError. The important piece of code is this:

ArrayList<ArrayList<Station>> permutations = getPermutations(stations);

I do NOT want to increase the heap memory size on my particular machine, I can't change it on other ones either. What I am looking for is some sort of exception handling for this error (I am well aware that errors or throwables in general are not supposed to be caught).

So I want to react on an OutOfMemoryError with an adequate (graphical) message and prevent my tiny little program from crashing.

Is a SwingWorker the right way to go, how should it be used or are there better suiting alternatives?

Thanks in advance :-)

sleske
  • 81,358
  • 34
  • 189
  • 227
Laika
  • 21
  • 1
  • There is a related question which might be helpful: "Is it possible to catch out of memory exception in java?" http://stackoverflow.com/questions/1692230/is-it-possible-to-catch-out-of-memory-exception-in-java – sleske May 25 '11 at 09:18

6 Answers6

2

As you've noted, you're not supposed to include treatment of OutOfMemoryErrors in the program logic. The OutOfMemoryError is to be interpreted as "your program requires more memory than the JVM/OS has to offer you".

I suggest you consider returning an Iterator<ArrayList<Station>> instead and produce the permutations lazily, i.e., on demand. (As you probably know, the size of the returned collection is easily computed without knowing the actual content as well.)

Is a SwingWorker the right way to go?

Most likely no.

aioobe
  • 413,195
  • 112
  • 811
  • 826
  • Hi, the permutations are already computed on demand i.e. on button click in the graphical user interface. It my be the case that there's too much data, so the error is quite likely to occur – Laika May 24 '11 at 18:00
  • 1
    That's not what I meant. I mean you should compute *each* permutation as it is needed, for instance in the implementation of `Iterator.next()`. – aioobe May 24 '11 at 18:01
  • Thanks for your response. The considered method just determines all permutations recursively. Do you think of a class which implements Iterator or how should Iterator.next() be implemented? – Laika May 24 '11 at 18:24
  • Here's a suggestion: Rewrite the recursive method to use an explicit stack. Refactor the method so that it, instead of adding the permutation to the result, *returns* the permutation. Each time `next()` is called, the method picks up where it left off, iterates, and returns the next permutation. – aioobe May 24 '11 at 18:27
  • Do you furthermore consider a dedicated thread as a possibility to keep the event thread unaffected? That's how the SwingWorker came to my mind... – Laika May 24 '11 at 18:43
  • Depends on what you do each time the user performs an action. Does each action just process *one* permutation, then it doesn't seem necessary. – aioobe May 24 '11 at 18:56
  • No, all permutations have to be computed (that's why it's O(n!) ). So a the work should be done. But I have to care for the occurence of this error from the thread's processing.. – Laika May 24 '11 at 19:14
  • SwingWorkers are good if the actual process generates lots of GUI-feedback. Otherwise I'd suggest you use an ordinary thread. – aioobe May 24 '11 at 20:31
  • @Laika: even if all permutations are needed, they might not all be needed in memory **at the same time**. And if that's the case for you (it often is), then calculating the permutations on the fly can safe tons of memory. – Joachim Sauer May 31 '11 at 11:53
1

Catch OutOfMemoryError, although you would likely end up in a situation you cannot repair.

See this discussion: http://www.velocityreviews.com/forums/t149419-catch-outofmemory-exception.html for more information.

PS. Do you really want to get all the permutations in an array? Consider aioobe's answer, it is much better in terms of usability of your code.

Miki
  • 7,052
  • 2
  • 29
  • 39
1

If you are out of memory, you do not have enough heap space to draw windows and display messages. Therefore, catching it won't help you. As far as displaying a helpful message goes, I suggest you process the exit code of the process by using another process.

But why not avoid the out of memory error to begin with? Even small machines can produce permutations, you will just have to sacrifice runtime. How about saving intermediate results to a disk? If you are not delivering a library (which I assume is the case because you want to display error messages), why not change the internal model to be completely disk based?

Apoorv
  • 1,091
  • 6
  • 19
  • Agreed, I can't display windows when out of memory. Therefore I intended to run this exhaustive computation in a separate thread (that's why the SwingWorker came to my mind). If this thread crashes, my event thread should still be unaffected, right? – Laika May 24 '11 at 18:14
  • If that thread frees up enough memory then theoretically you can continue normal processing. I have seen similar things happen with other processes in the past but this is not guaranteed to happen. – Apoorv May 24 '11 at 18:44
1

Are you truly running out of memory? If you are processing the list iteratively and cleaning up after yourself, maybe. Perhaps however this is just a case of not allowing the GC to do the job that it should, java is not immune to memory leaks. Hanging references, Global / static variables etc can all cause objects to remain in scope when they should really be GC'd.

It may be useful to run a profiler (lots of them available for Eclipse) to see exactly what is taking up this extensive amount of memory.

Perhaps it would help to process in smaller batches? Having worked with financial data in the past I found it quite common to process millions of records at a time. Usually the best way to handle these situations is to break the processing into smaller, more manageable chunks.

Chris Kannon
  • 5,931
  • 4
  • 25
  • 35
0

You can just catch the OutOfMemoryError like any other exception, and report it however you'd like. SwingUtilities.invokeLater() would be a fine way to report the error in a dialog. It's not true that you'll have problems recovering -- coming back from an OutOfMemoryError is generally painless (if the surplus objects are now eligible to be collected, of course).

Ernest Friedman-Hill
  • 80,601
  • 10
  • 150
  • 186
  • "coming back from an OutOfMemoryError is generally painless " That seems doubtful; do you have any references for this claim? I would assume (like others here) that by the time you catch the OOME other things may have gone wrong already (e.g. other threads may have crashed as well). A program using Swing will have a GUI thread (the Event Dispatch Thread) running in parallel to the main thread; if that crashes first, you're out of luck. So if you can recover from OOME will probably depend on your program and environment. – sleske May 25 '11 at 09:15
0

I agree with the answers that suggest you grow your permutations in stages. Then, you can always recover when OutOfMemoryError is thrown:

boolean memoryFlag = false;  // flag is always available
try {
  Permutations bigVar = ... // some initial value
  while (/* condition */) {
    // Output your permutations so far discovered
    bigVar = ... // calculate the next extended set of permutations
  }
}
catch (OutOfMemoryError ex) {
  // bigVar is now out of scope, so is garbage
  System.gc();
  memoryFlag = true;
}
// program tests memoryFlag to report if out of memory occurred

Your user interface can continue to operate uninterrupted. This has worked for me before in single-threaded applications. With multiple threads, you run the risk of not being able to trap the error, since each Thread runs with its own handlers, and you might not have control over the scope of some Swing threads.

Tony Simons
  • 61
  • 1
  • 1