Caching Intermediate Results

The redesign of our puzzle-solving algorithm dramatically improved the execution speed of our program. For further optimizations, we'll have to look at technical performance techniques. An important issue to consider in Java programs is garbage collection. You can show the activity of the garbage collector during program execution by using the -verbose:gc command line switch.

java -verbose:gc meteor.algorithm.Solver

If we run our program with this switch, we see a lot of output from the garbage collector. Studying the source code tells us that the problem is the instantiation of a temporary ArrayList object in the placePiece() method of the Board class (see Listing 6). We use this ArrayList object to hold the board cells that a particular permutation of a piece would occupy. Instead of recalculating this list every time, it would be better to cache the results for later reference.

The findOccupiedBoardCells() method determines the cells of the puzzle board that would be occupied by a puzzle piece if a certain cell of that piece is placed on a certain board position. The results of the method are determined by three parameters: first we have the puzzle piece, or a permutation thereof; second we have the cell of the piece that we're using to manipulate the piece; and finally we have the cell of the board we'll put the piece on. To cache these results, we can associate a table with every possible piece permutation. This table holds the results of the findOccupiedBoardCells() method for that permutation using a specified piece cell index and board cell position. Listing 10 shows an updated version of the Piece class that maintains such a table:

public class Piece {
  private Piece[] permutations = new Piece[NUMBEROFPERMUTATIONS];
  private ArrayList[][] occupiedBoardCells =
    new ArrayList[Piece.NUMBEROFCELLS][Board.NUMBEROFCELLS];

  private void generatePermutations(Board board) {
    Piece prevPermutation=this;
    for (int i = 0; i < NUMBEROFPERMUTATIONS; i++) {
      // The original nextPermutation() has been renamed

      permutations[i]=
        ((Piece)prevPermutation.clone()).nextPermutation_orig();
      prevPermutation=permutations[i];
    }

    // Calculate occupied board cells for every permutation
    for (int i = 0; i < NUMBEROFPERMUTATIONS; i++) {
      permutations[i].generateOccupiedBoardCells(board);
    }
  }

  private void generateOccupiedBoardCells(Board board) {
    for (int i = 0; i < Piece.NUMBEROFCELLS; i++) {
      for (int j = 0; j < Board.NUMBEROFCELLS; j++) {
        occupiedBoardCells[i][j]=new ArrayList();
        resetProcessed(); // We're going to process the piece
        board.findOccupiedBoardCells(occupiedBoardCells[i][j],
                                     pieceCells[i],
                                     board.getBoardCell(j));
      }
    }
  }

  public Piece nextPermutation() {
    if (currentPermutation == NUMBEROFPERMUTATIONS)
      currentPermutation = 0;

    // The new implementation of nextPermutation() 
    // accesses the cache

    return permutations[currentPermutation++];
  }

  public ArrayList 
    getOccupiedBoardCells(int pieceCellIdx, int boardCellIdx) {
    // Access requested data in cache
    return occupiedBoardCells[pieceCellIdx][boardCellIdx];
  }
}

The generatePermutations() method is triggered when a Piece object is created. It calculates every permutation of the piece and caches all possible results of the findOccupiedBoardCells() method for those permutations. It is clear that we'll need access to the puzzle board if we want to calculate the occupied board cells. Also note that the permutations of a piece are clones of the original Piece object. Cloning a Piece involves a deep copy of all of its cells.

The only thing left to do is to access the cache from the placePiece() method of the Board class, which is shown in Listing 11:

public class Board {
  public boolean 
    placePiece(Piece piece, int pieceCellIdx, int boardCellIdx) {
    // Get all the boardCells that this piece would occupy
    ArrayList occupiedBoardCells =
      piece.getOccupiedBoardCells(pieceCellIdx, boardCellIdx);
    ...
  }
}

Running the program once more

The extra code we introduced to implement the cache obviously complicates the program. This is a typical downside of performance techniques that try to reduce computation time by storing intermediate results. However, in this case the performance gain seems to outweigh the added code complexity.