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.
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
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.
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
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:
generatePermutations() method is triggered when a
Piece object is created. It calculates every permutation of the piece and caches all possible results of the
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:
Running the program once more
The source code of this updated version of our puzzle-solving program can be found in the
meteor.caching package. Running
shows us that we again improved the performance considerably. On our
test machine all solutions are found in 25 seconds. Caching resulted in
a six-fold speedup. If we use the
-verbose:gc switch, we also see that garbage collection is no longer an issue.
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.