3

So I'm working on parallelizing a genetic algorithm (coded in Java), and I've decided to use an Executor to manage the asynchronous execution of the fitness tests for the individuals in my population. I did this because it means I can create an executor with a fixed thread pool size and simply reuse those threads every generation as opposed to creating new threads every single generation.

Now, I have a set of tests I've been running to monitor the performance of my GA with growing population sizes, and I've run into a snag. Executing the following code:

        for(i=1;i<=11; i++){
            PopulationSize = 10*i;
            for(j=0;j<10;j++){

            startTime = System.nanoTime();

            P = new Population(PopulationSize, crossOverProbability, mutationProbability, conGens);         

            while(P.generation()<10){
                P.breedNewPop();    
            }

            endTime = System.nanoTime();
            time = (endTime - startTime) * Math.pow(10, -9);

            System.out.println("Done Trial " + i + ", Round " + j);
            }
        }

I get the following error : 

Exception in thread "main" java.lang.OutOfMemoryError: unable to create new native thread

The confusing thing to me is that this is happening at Trial 10, Round 4 - meaning it was able to run the first three rounds of Trial 10 without a problem. Since there should be no difference when running Round 4 (particularly, Round 4 doesn't call for any more threads than Rounds 1-3 of Trial 10), I wouldn't expect that it would have any issue. But it does.

The one theory I have right now is that Java is not doing proper garbage collection - what I mean is that it's, for some reason, not clearing out the old unused threads, and that's why it runs out of memory at such a peculiar moment. Thinking this was it, I tried both declaring and assigning P inside the loop, instead of just assigning it. That had no effect. I also tried adding P = null; System.gc(); at the end of the loop to try and force garbage collection before the new thread pool was made. Again, it made no difference.

Here are the relevant lines of code dealing with the executor:

In Population(): executor = Executors.newFixedThreadPool(popSize);

In Population.findFitness():

for(int i=0; i<individuals.length; i++){
        executor.execute(individuals[i]);
    }try {
        cdl.await();
    } catch (InterruptedException e) {
        System.out.println("Error: Thread interrupted.");
    }

(I'm using a CountDownLatch to wait for the execution of all threads to be completed - I already had it implemented from when I was parallelizing by putting each Individual's fitness tests into their own threads, instead of using a thread pool through the executor. The latch also seemed like it would fit better with my implementation of Individual than something like the invokeAll() method of an ExecutorService.)

The code for Individual.run():

public void run(){
    try{
        findFitness();
    }catch (Exception e){ 
        System.out.println("Error in Individual.run(): " + e.getMessage());
    }finally{
        stopLatch.countDown();
    }
}

At this point I'm at a loss as to what could be causing it. Does anyone have any ideas why this would be happening and how I could fix it?

P.S. I know I could try running the JVM with more memory, but that still doesn't explain the peculiar timing of the error. Considering that I'm programming this program on one machine and will eventually move it to another machine, I'd prefer to understand the reasons behind the error instead of fixing it in a relatively brute force manner.

UPDATE: Having gone through and run the trials again, this time watching the threads through JConsole, I can confirm that the executor is creating thread pools that are the right size just fine. However, the thread pools are NOT being destroyed - every Round of tests (ie. every time through the for loop that counts j), a new thread pool is produced but the old one remains. Why would this happen?

MattS
  • 717
  • 2
  • 7
  • 22
  • 3
    "The one theory I have right now is that Java is not doing proper garbage collection" - or more likely you have a bug in your code... – Mitch Wheat Jun 16 '12 at 06:27
  • 2
    Population size increases by 10 each iteration. How does memory usage depend on population size? If you're considering interactions between population members, this could lead to an exponential increase in memory requirements at each generation. You may just need more memory. Speaking of which, how much are you giving it? The default `-Xmx` is pretty small. – Jim Garrison Jun 16 '12 at 06:30
  • Take a look at this post: http://stackoverflow.com/q/10742634/1140748 maybe you have the same problem. – alain.janinm Jun 16 '12 at 08:32
  • @JimGarrison The executor is initialized with a fixed thread pool of max size equal to the population size - meaning there's at most one thread per individual. I understand that this is a lot, intentionally so - I'm trying to see what the limitations of the algorithm are. The strange thing is, as I said, there's no change in the thread pool size of Round 3 and Round 4 of Trial 10, so I really don't think that's what's causing the error - otherwise it should be coming up sooner, no? – MattS Jun 16 '12 at 09:43
  • It is strange that `ThreadPoolExecutor` (especially the `newCachedThreadPool()` variant, which allocates an unbounded maximum of threads when needed.) doesn't take care of this issue. Ideally the Executor would allow you to submit practically infinitely many `Runnables` for execution and allocate no more threads than supported by JVM, OS, etc. And `System` doesn't have a method `getRecommendedMaximumThreads()` either. – Kasper van den Berg Jun 16 '12 at 10:38
  • The code sample doesn't cover the part that involves threads. – Andreas Jun 16 '12 at 13:22
  • Can you post the code where that thread pool of yours is created? What Executor you create and how do you use it? – Nikem Jun 18 '12 at 07:41
  • Added the code for the executor initialization and passing methods to it. – MattS Jun 18 '12 at 17:10
  • Responding to your update, I'll point out the obvious. You're keeping references to your old thread pools. Null 'em out. – RalphChapin Jun 18 '12 at 17:47
  • @RalphChapin So as I said - the thread pool is part of the Population class. The population class gets overwritten every round. Not only that, but I also tried specifically setting P = null in an attempt to get the thread pool to clear, and it didn't work. – MattS Jun 18 '12 at 19:12
  • I just noticed there is a `shutdown()` method. You might want to try calling it explicitly. I was thinking you might be keeping a list _inside_ Population or other class, then I thought maybe the Executor was doing that. Then I thought what a pain it is to dig through Sun/Oracle's code (though that's a lot easier than digging through _Microsoft_'s code). Then I thought maybe there's a cleanup function. Check `shutdown`, then check your own code for hidden lists, then dig into Sun's code. (And maybe check for other _dispose/close_-type methods.) Good luck. – RalphChapin Jun 18 '12 at 19:44
  • shutdown() is for ExecutorServices, not Executors. I was hesitant to use an ExecutorService because it seemed like it'd take more work to implement, but I'm reconsidering that decision considering I've found nothing else to be able to clear the executor's thread pool. – MattS Jun 18 '12 at 20:34

2 Answers2

3

Running out of memory when creating threads with a fixed-sized thread pool sounds most peculiar. I suspect one of the following:

  • Your thread pool is actually not fixed sized; i.e. you got the pool creation parameters wrong.
  • Your code is creating threads somewhere else; e.g. by calling new Thread().start() explicitly. This might show up in the stacktrace.

The other possibility is that something external to the JVM is causing the JVM to be unable to allocate thread stacks. These aren't allocated in normal heap memory, so it won't be the -Xmx setting. It could be the default thread stack size setting, or it could be an external resource limit ... or a general resource starvation on your machine.

With this exception message:

Exception in thread "main" java.lang.OutOfMemoryError: 
     unable to create new native thread .

this is clearly not a normal "heap is too full" type of problem detected by the GC. The memory allocation that failed is a request for non-heap memory for a thread stack. Increasing the heap size is not going to help ... and it might even make things worse.

Forcing the GC to run won't help either. And it wouldn't help even in if the problem was triggered by allocation a heap object ... because the JVM will only throw a heap OOME after running the GC.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • 1
    +1 for *"Forcing the GC to run won't help either"*. I get the creeps whenever I see `System.gc()` in application code... – thkala Jun 16 '12 at 07:47
  • @thkala I completely understand, and I've never actually used it before. I just brought it out in this situation as a means of testing whether or not it was an issue with Java properly disposing of the old threads. – MattS Jun 16 '12 at 09:46
0

I'm going to make this an "answer" because there's getting to be a lot of comments.

I think what you want is ThreadPoolExecutor.

Actually, I think you might find it simpler just to go back to basics and launch a bunch of Thread instances and use the join method repeatedly to find out when they all finish. A proper thread pool will keep you from running 100's of threads at the same time on a 2-core machine, but I know from experience Java can keep 1000's of threads straight without need for a pool. (The way I code, most of the threads are waiting for locks and talking to each other, they're not all running flat out. But a lot of them are running flat out and they don't clog the CPU's.) At any rate, get all the threads going and then try some kind of pool.

Java provides all kinds of classes now to make multithreading easier and better, but it's not always real clear what they all actually do, particularly when you're trying to make a program work as opposed to writing a Master's thesis.

RalphChapin
  • 3,108
  • 16
  • 18
  • Calling a bunch of threads individually has the cost of creating and destroying those threads every generation though - the thread pool allows me to run my algorithm for, say, 500 generations while still just using the same threads over and over again, which will save quite a bit of time in the long run. But actually, I've switched over to an ExecutorService (from just a plain Executor), and it seems to be working fine now. I still have no idea why Java wasn't destroying the old threads, though. – MattS Jun 19 '12 at 01:44