[FIXED] Why is declaring an array using so much CPU, and how can I optimize it?

Issue

I am writing a chess engine as a learning project. To decide what move to make, it needs to analyze all board states that can be reached by making 4 moves from the current board state. That means I have to analyze hundreds of thousands of boards.

The code is understandably slow, so I used the built in Netbeans profiler to see which function I should optimize. I was surprised to find that it was simply the creation of new arrays within copied Board objects that was using the most CPU.

Here is the function that it says is using the most CPU, specifically init1():

private void initializeFields(Color active) {
    init1();
    init2(active);
    init3();
    init4();
}

private void init1() {
    //this line appears to be using a ton of CPU
    pieces = new Piece[SQUARES_PER_SIDE][SQUARES_PER_SIDE];
}

private void init2(Color active) {
    activePlayer = active;
}

private void init3() {
    moveHistory = new LinkedList<>();
}

private void init4() {
    possibleMoves = null;
}

And here are the profiler results:

Obviously I understand that the vast amount of boards being created and looked at means that some small thing within the Board class is probably going to take the most CPU. However, I have 2 questions about this:

1. Why is declaration of an array taking the most CPU of anything withing Board?

I was expecting move calculation or analysis of the value of each board state to use more than simply creating arrays. Is it possible I am reading the results incorrectly?

2. How can I optimize my performance in this case?

I understand how to optimize algorithms, but I am not sure how to optimize an array declaration. I am also not sure what better data structure I can use to represent an 8x8 board than a 2 dimensional array.

Solution

1. Why is declaration of an array taking the most CPU of anything withing Board?

Because that is propbably almost all you do. Searching for free space in the heap is taking up more time than anything else.

2. How can I optimize my performance in this case?

Keep just one board and make each move, test it and undo the move for each step.

This is a bad approach if you ever want to parallelise but it is much quicker and more space-efficient. (good call @shmosel)

Answered By - OldCurmudgeon
Answer Checked By - Willingham (JavaFixing Volunteer)