CODEWITHSUNDEEP
javaarraysmemory-managementstack-overflow
Boye Borg
Boye Borg

Reputation: 13

StackOverflowError in Java while working with arrays and recursion

The lifeCycle-method in my MatrixCreatureContainer-class throws a stack overflow error after about 3-4k iterations. Why is that? I assume it has something to do with memory allocation, but I cannot figure out how to solve it. I tried reading about the java garbage collector, but nothing I did seemed to help. 

public class MatrixCreatureContainer {

    private final static int NUMBER_OF_CREATURES = 20;
    private static Random rand;

    public static void main(String[] args){

        rand = new Random();
        List<MatrixCreature> population = new ArrayList<MatrixCreature>();

        for(int i = 0; i < NUMBER_OF_CREATURES ; i++){
            population.add(new MatrixCreature());
        }

        Collections.sort(population);

        lifeCycle(population,0, 4000);
    }

    private static void lifeCycle(List<MatrixCreature> population, int generation, int iterations){

        if (generation == iterations) return;

        List<MatrixCreature> newPopulation = new ArrayList<MatrixCreature>();

        while(population.size() != 0){
            MatrixCreature mother = population.remove(rand.nextInt(population.size()));
            MatrixCreature father = population.remove(rand.nextInt(population.size()));
            newPopulation.add(new MatrixCreature(mother,father));
            newPopulation.add(new MatrixCreature(mother,father));
            newPopulation.add(new MatrixCreature(mother,father));
        }

        Collections.sort(newPopulation);

        newPopulation = newPopulation.subList(0,NUMBER_OF_CREATURES);

        lifeCycle(newPopulation,generation + 1, iterations);

    }

}

The MatrixCreature-class basically only holds an integer array (int[]) of 20 integers. The constructor takes in two other matrixCreatures, and combines the arrays of two the matrixCreatures given, with a small chance of mutation. Each matrixCreature gets a score (where 0 is the best) of how close the sum of the numbers in the array is to 55. It's that score the population of each generation in the MatrixCreatureContainer is sorted by, such that the 20 "best" of each generation survives.
I can post the code to the MatrixCreature-class if it's relevant.

Thanks in advance :)

-Boye

Upvotes: 1

Views: 175

Answers (3)

Jon Skeet
Jon Skeet

Reputation: 1503449

With this call:

lifeCycle(population,0, 4000);

you're basically asking for a stack with 4000 frames (at least - see later). That isn't totally beyond reason, but in fact there's no reason to make this recursive at all. You can easily just change the method to be iterative - and even remove the generation parameter:

private static void lifeCycle(List<MatrixCreature> population, int iterations) {
    for (int generation = 0; generation < iterations; generation++) {
        // Body of previous method here
    }
}

Additionally, you keep creating views using newPopulation = newPopulation.subList(...). You probably don't want to do that - it means that every operation will need to go through a huge number of stack frames, as each call to a view will delegate to its underlying list... and if that's another view, it needs to keep going, etc. Icky. If those view calls actually require a couple of stack frames per "layer" you could easily end up with a stack of around 12K calls in your original code...

I would suggest creating a copy of the relevant portion of the list on each iteration instead - and then returning the final list.

Upvotes: 1

Erwin Bolwidt
Erwin Bolwidt

Reputation: 31299

Java does not support tail-recursion optimization, so your last line in the lifeCycle method creates a new stack frame for every iteration.

With your memory size, and the number of local variables, you have determined that you can have about 4000 stack frames. Solution: rewrite your method using a for-loop. It's a small change, you don't really need recursion for your method.

Upvotes: 0

Dawnkeeper
Dawnkeeper

Reputation: 2873

Each lifecycle starts with its own population and creates a new one for the next generation (with always 3 creatures inside; is this intended ?)

So after 4000 iterations you have those 4000 population lists hanging around as they never went out of scope.

Upvotes: 0

Related Questions